2
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ hint: look at constraint (4) in the .ipynb, and try to write an equivalent equation for time. $\endgroup$ – Kuifje Nov 13 '20 at 9:20
6
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ you are now 4000! $\endgroup$ – BCLC Nov 14 '20 at 17:02
  • $\begingroup$ I think I got it thanks but just to clarify shouldn't be $t_j=\max\{a_i,t_i\}+\Delta_{ij} + s_i$ instead of $t_j=\max\{a_i,t_i+\Delta_{ij} + s_i\}$ . Where $s_i$ is the service time at node $i$. $\endgroup$ – AGH Nov 15 '20 at 18:59
  • $\begingroup$ $t_j = \max\{a_i,t_i + \Delta_{ij} +s_i\}$ looks good to me. You have to consider two cases : a) service time + travel time is smaller than $a_i$, in this case you wait, and $t_j = a_i$ or b) is larger and in this case $t_j = t_i +$ service time +travel time $\endgroup$ – Kuifje Nov 15 '20 at 19:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.