# 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 if and only if 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.