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 '20 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$ – dimboukosis Jan 28 '20 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 '20 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$ – dimboukosis Feb 6 '20 at 12:50

Your Answer

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

Browse other questions tagged or ask your own question.