VRPTW implementation

Question

Does anybody have an example of the vehicle routing problem with time windows (VRPTW), implemented on Python with CPLEX library, AMPL, or MiniZinc? So far I've looked into https://github.com/industrial-ucn/jupyter-examples/blob/master/optimization/cvrp-cplex.ipynb which I found really helpful for the VRP problem, but I'm looking for VRPTW implementation. I haven't found any example for MiniZinc yet. So if anybody has one at hand so I could try to understand.

Answer 1

Before implementing anything, you need to understand the equations. A good approach is to think in terms of resources. When handling capacity constraints, you are dealing with a load resource which is limited to the vehicle's capacity. When dealing with constraints linked to time, you need an extra resource for this. Each of these resources can be delt with in a similar fashion. In essence, you use equations that keep track of how these resources are incremented when using an arc.

You need to write an equivalent equation as the one which keeps track of the total load : $$ x_{ij} = 1 \quad\Rightarrow \quad u_j =u_i +q_j \quad \forall (i,j)\in A $$ This means that if you use arc $(i,j)$, then the total load that has been delivered up to node $j$, $u_j$, is the total load up to node $i$, $u_i$, plus the amount that is delivered at node $j$, $q_j$.

So if $t_i$ is a variable that denotes the time at which you reach node $i$, and if $\Delta_{ij}$ denotes the time it takes to go from $i$ to $j$, you can write the following equation: $$ x_{ij} = 1 \quad \Rightarrow \quad t_j = t_i + \Delta_{ij} \quad \forall (i,j)\in A $$ Once you have this, writing the time window constraint should be straightforward.

Note however that this formulation assumes that the lower bounds on the time windows $[a_i,b_i]$ are hard. Typically, this is not the case, as waiting is usually allowed upon arrival. In this case, the above constraint has to be tweaked as follows:

$$ x_{ij} = 1 \quad \Rightarrow \quad t_j = \max\{a_j,t_i + \Delta_{ij}\} \quad \forall (i,j)\in A $$

Also, there may be a service time at each node. If you understand the above equations, you should be able to take this service time into account.