How would you mathematically formulate this as an optimization problem?

Say you had a set of cities, and it takes a certain amount of time to travel between one city $i$ and another $j$, call this $c_{ij}$. To get from city A to city B as fast as possible would simply be a Shortest Path problem.

Now assume you had $N$ cars that want to travel from city A to city B. They all leave A at different times. Then assuming that our set of $c_{ij}$ stays constant, they should all take the same path.

But in reality, say there are certain edges that only a single car can traverse at once. While that car is traversing it, others need to form a queue. Pretend this is a toll booth for example. Not just that, but the traversal time differs from car to car.

I'm imaging this to be the equivalent of $c_{ij}$ varying over time due to traffic, but I don't think that's quite valid, because once a car begins "traversing" (i.e. enters the queue, or is getting processed by the toll booth) it's $c_{ij}$ stays the same as when it entered.

My goal is to mathematically formulate this as an optimiztion problem, with the decision variables being the routes (per car) that minimize mean travel time from A to B (or the sum of travel times for $N$ cars).

So to recap:

• $N$ cars leave city A at different times, heading for city B.
• Some edges can only be traversed by one car at a time, so queues can form.
• These traversal times can vary from car to car. (If this makes it too complicated, then scratch that and assume all cars are the same).
• With full knowledge of what times cars leave A, there is a set of routes that each car can take to minimize "traffic", and that is equivalent to minimizing mean travel time, or the sum of all travel times, for a fixed $N$.

I'm at quite a loss to formulate this, since the routing decision depends on all the other routing decisions (or at least past ones). Is there a class of similar problems? How would you formulate this? Or am I going about it the wrong way?

1 Answer

I believe it can be formulated as a mixed integer linear program, albeit a somewhat cumbersome one. The model I have in mind draws in part of routing problems (using a binary variable for each combination of vehicle and arc to handle the routing) and in part from machine scheduling (using continuous variables to represent the time a vehicle enters and exits an arc, if it in fact uses the arc -- similar to start/end time variables for jobs on machines, to avoid having them overlap on the machine).

The model I doodled has quite a few binary variables (and quite a few continuous variables, but they're relatively cheap) and (gulp) quite a few "big M" constraints (which are conceptually valid but can create performance issues).