Car Selection

Direct download AIMMS Project: Car Selection

Story

This example matches people to cars. Not every person can be matched to every car, for a variety of reasons:

  1. The car owner may impose limits on the drivers allowed.

  2. The drivers may not be willing to drive every car.

A matching needs to be found, such that as many as possible people can be driving at the same time.

Mathematical program

This model is an example of a matching problem, matching people to cars. The mathematical formulation is as follows:

Car assignment problem

Sets and indices:

\(C\), \(c \in C\)

Cars

\(P\), \(p \in P\)

Persons

Parameters:

\(A_{c,p} \in \{0..1\}\)

a 1 permits

Variables:

\(X_{c,p}|A_{c,p} \in \{0..1\}\)

1 iff chosen

Constraints:

\(\forall c: \sum_p X_{c,p} \leq 1\)

At most one person per car

\(\forall p: \sum_c X_{c,p} \leq 1\)

At most one car per person

Maximize:

\(\sum_{c,p} X_{c,p}\)

The number of matches

Remarks:

  1. The \(A_{c,p}\) is the set of arcs, according to which assignment is permitted.

  2. The \(X_{c,p}\) are the variables. The notation \(X_{c,p}|A_{c,p}\) limits the variables to only those arcs that are permitted.

  3. This constraint ensures that a car is not driven by more than one person.

  4. This constraint ensures that a person does not drive more than one car.

  5. The objective is to make as many combinations of (person, car) as possible.

See also:

User Interface

In this AIMMS project the use of pictures as nodes in a network is illustrated. These pictures are stored inside the project as so-called project user files. Project user files can only be reached in developer mode, through the menu bar command: Tools > Project User Files.

The results are illustrated in a network object, with pictures of the cars as nodes.

The number of cars and the number of participants can be changed by the user, where the possible combinations are generated randomly. New possible combinations will be determined when the number of participants or cars is changed, or by pushing the “generate possible pairs” button.

Keywords: Project User Files, Mixed Integer Programming model, MIP, Matching Problem, Network object, Nodes and arcs, Bitmap