I have made some progress on my previous question (Is there a known MILP to schedule routes after routes are made).
I have derived the sets of the problem, which are:
1) Itineraries of vehicle: $i \in I$
2) Customer $j$ in itinerary $i$: $c_{ij} \in C$

With the following Parameters.
1) Start of $j$-th time window of itinerary $i$: $tws_{ij}$
2) End of $j$-th time window of itinerary $i$: $twe_{ij}$
3) Duration of travel from customer $j$ to customer $k$ of itinerary $i$: $d_{ijk}$
4) Processing Time of customer $j$ of itinerary $i$: $P_{ij}$
5) Waiting time: $wt$

With decision variables:
1) $c_{ij}$: Start of service at customer $j$ of itinerary $i$

The certain constraints up to now are:
\begin{align}c_{ij} + P_{ij} + d_{ij(j+1)} - c_{i(j+1)} &\leqslant 0, &&\forall i\in I,j\in C\\c_{ij} + wt &\geqslant tws_{ij} , &&\forall i\in I,j\in C\\c_{ij} &\leqslant twe_{ij}, &&\forall i\in I,j\in C\end{align}

These three sets of constraints ensure the time windows violations for each itinerary, and the ban of overlapping customers within an itinerary. My question is the following. How can I ensure the ban of overlapping for each itinerary with the other?

Thank you very much!

  • $\begingroup$ Your notation is a bit unclear. Since $C$ has no subscripts, I assume it is the set of all customers. Having constraints involving $c_{ij}$ for all $i\in I, j\in C$ would then imply that customer 2 ($j=2$) belongs to every itinerary (and, from the other constraints, would seem to imply that customer 2 is the second customer in every itinerary). $\endgroup$
    – prubin
    Jan 27, 2020 at 20:54
  • $\begingroup$ Hello prubin, thank you for you comment. Each Itinerary contains a number of customers. Hence each itinerary has to have a notation for its customers. For example $c_{12}$ is the second customer of the first itinerary and $c_{22}$ is the second customer of the second itinerary. You were correct. Customer 2 should not imply that is the second customer in every itinerary. $\endgroup$ Jan 28, 2020 at 7:34
  • $\begingroup$ I gather you have a single vehicle. Is the assumption that the vehicle will complete each itinerary before moving on to the next itinerary? If so, does each itinerary return the vehicle to "base"? If not, you have to account for travel time from the end of one itinerary to the beginning of the next. $\endgroup$
    – prubin
    Jan 29, 2020 at 19:26
  • $\begingroup$ That is correct. The vehicle returns to a base. Hence I need to take into account the time back to the base and the time from the base to the next customer. $\endgroup$ Feb 6, 2020 at 12:50


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.