4
$\begingroup$

In VRPTW problem, given

  • $[a_i, b_i]$: the time window for node $i$
  • $x_{ijk}$: a binary variable that represents that the vehicle $k$ travels from node $i$ to $j$ (yes 1 otherwise 0)
  • $s_i$: the service time at node $i$
  • $t_{ij}$: the traveling time from node $i$ to $j$

I see paper and books widely formulate the constraints related to time as follows:

\begin{align} &w_{ik} + s_{i} + t_{ij} - w_{jk} \leq (1 - x_{ijk})M_{ij} \tag{1} \\ &w_{ik} \geq a_{i} \tag{2} \\ &w_{ik} \leq b_{i} \tag{3} \end{align}

Here $w_{ik}$ was mentioned as the arrival time of vehicle $k$ to node $i$, (1) is actually the linearized version of

\begin{align} x_{ijk}(w_{ik} + s_{i} + t_{ij} - w_{jk})\le0 \tag{4} \end{align}

and (2) and (3) are the time window constraints.

If $x_{ijk}=1$, we expect the representation of arrival time to $j$ to be (the time of arrival at $i$) + (the service time at $i$) + (time cost to travel from $i$ to $j$)

However, under the circumstance where $x_{ijk}=1$, then $1-x_{ijk}=0$, we get $w_{ik} + s_i + t_{ij} - w_{jk} \le 0$, i.e., $w_{jk} \ge w_{ik} + s_i + t_{ij} $.

This could be interpreted as: the arrival time at $j$ is greater and equal to the expected time

Then I am confused that how can we prevent the case where $w_{jk}$ is larger than what we expected?

Of course, there is also a possibility that the expected time is below the lower bound of time window $a_i$, the vehicle is assumed to be waiting to $a_i$, and this is ensured by (2). However, still, the $\ge$ in (2) leaves the possibility for it to be larger than $a_i$.

I used to see that in some literature, the objective contains minimization of the sum of such variables so that the case can be prevented. However, here the objective is only minimizing the travel cost $\sum_{i,j,k}c_{ij} \cdot x_{i,j,k}$.

Based on the result from CPLEX, I see the values of $w_{jk}$ indeed tightened to $\max\{a_j, w_{ik} + s_i + t_{ij}\}$.

$\endgroup$
4
  • 2
    $\begingroup$ You can interpret the $w_{ik} $ as the time at which *service* starts at node $i$ by vehicle $k$ (if $x_{ijk} =1$). That is, $w_{ik} $ is not the time of arrival, but the time of service start. $\endgroup$
    – Sune
    Apr 25, 2022 at 17:19
  • 1
    $\begingroup$ Could you please tell us the paper you are referring to? $\endgroup$
    – PeterD
    Apr 25, 2022 at 19:17
  • $\begingroup$ @BobHU This means that multiple optimal solutions could exist and which solution you get is dependent on the solver. What CPLEX results are you referring to? $\endgroup$
    – PeterD
    Apr 25, 2022 at 19:43
  • 1
    $\begingroup$ Related, with the exact same notation: or.stackexchange.com/questions/7643/… $\endgroup$
    – RobPratt
    Apr 25, 2022 at 19:58

2 Answers 2

2
$\begingroup$

I think the confusion may stem from the fact that you minimize the cost of being on the road. Hence, you do not really minimize the time used on the routes. One simple way to move the focus more to the time dimension is to change your objective function to $\min \sum_{i\in N}\sum_{k\in K}w_{ik}$, where $N$ is the set of customers and $K$ is the set of vehicles. This way you push back the start of service as much as possible.

Another approach (that I would not advice) is to also require the reverse inequality: $x_{ijk}=1\Rightarrow w_{ik}+s_i+t_{ij} \geq w_{jk}$. This way you will have that $x_{ijk}=1\Rightarrow w_{ik}+s_i+t_{ij} = w_{jk}$. You can do this in a similar fashion as you have modelled the other time-accumulating inequalities.

The problem, however, is that if you require that service must start when you arrive at a customer, you may create some very strange routes where longer detours are taken in order to hit the time windows.

$\endgroup$
3
  • $\begingroup$ Actually, I understand that if arriving at a station before the start time of the time window $a_i$, the vehicle has to wait until $a_i$, therefore $\ge$ is used instead of $=$ to cater for this situation. What confuses me is that under the situation where the vehicle actually arrives after $a_i$, it indeed should start the service immediately. However, $\ge$ still leaves the possibility of some slack time here. Meanwhile, as you mentioned, the objective does not consider time-related costs, making me confused on what exactly should we interpret $w_{jk}$ here. $\endgroup$
    – BobHU
    Apr 26, 2022 at 8:41
  • 1
    $\begingroup$ @BobHU I could be the devil's advocate here and ask "why should the vehicles start service immediately if it arrives after $a_i$?". You have not added any logic to the problem that enforces this requirement. I gennerally think of the route VRPTW as follows: the $x_{ijk}$ variables are the important ones, as they tell the dispatcher which routes to use. The $w_{ik}$-variables on the other hand, are just there to ensure that the routes are indeed feasible. The driver will, en route, make the decisions about when exactly service starts at each customer. $\endgroup$
    – Sune
    Apr 26, 2022 at 9:04
  • 1
    $\begingroup$ OK, now I understand your explanation. Here the constraints only ensure service time no earlier than $\max${arriving time, lower bound of time window}, not necessarily the arriving time. Solutions under such a model are definitely feasible. $\endgroup$
    – BobHU
    Apr 26, 2022 at 9:22
2
$\begingroup$

There may be some slack in the system. Suppose that there is one vehicle, and the optimal solution has the vehicle go from node 1 to node 2. Assuming everything moves as early as possible, the vehicle completes the service at node 1 at time 10. Travel time to node 2 is 3, but the window at node 2 does not open until time 20. So there is 7 time units of "slack". You can think of the "arrival time" $w_{2,1}$ as the time the vehicle "enters the premises" or "officially arrives" at node 2. According to the constraint $w_{i,k}\ge a_i$, $w_{2,1}$ cannot be less than 20. So either the vehicle dawdles in the vicinity of node 1 before heading to node 2, or it dawdles in the vicinity of node 2 before officially arriving, or it takes the scenic route (travel time greater than $t_{1,2} = 3$), or some combination of those.

$\endgroup$
6
  • $\begingroup$ Good comment, but I think the question was not about understanding the TW constraints themselves, but rather about the tightness of $w_{ik}$, given the objective function that minimizes solely travel time. $\endgroup$
    – PeterD
    Apr 25, 2022 at 19:10
  • $\begingroup$ @PeterD True, but the question mentions $w_{jk}$ being "larger than what we expected", and the "what we expected" part I'm pretty sure is predicated on not considering slack in the schedule. $\endgroup$
    – prubin
    Apr 25, 2022 at 20:06
  • 1
    $\begingroup$ I understood the question in the following way: Example: Lets say we have only one customer with a large time window $[a_i, b_i]$ and we want to minimize the total travel time. The decision variable $w_i$ could now take many values, while all decisions are optimal. What ensures the that $w_i=a_i$, i.e. "what we expected"? If this is what the question is about, then the answer would be that the model he presented does not ensure the tightness. But lets agree that the question is somewhat vague. $\endgroup$
    – PeterD
    Apr 25, 2022 at 20:26
  • $\begingroup$ @PeterD Sorry for being vague in the description. Actually, the expected time here I assume is the maximum value between $w_i + s_i + t_{ij}$ and $a_i$, which means if the vehicle arrives earlier than $a_i$, it waits until $a_i$. Otherwise, the value $w_j$ should be exactly $w_i + s_i + t_{ij}$. However, in the equation expression, the relationship is $\ge$, which leaves the possibility of $w_j$ to be any value in $[w_i + s_i + t_{ij}, b_i]$. $\endgroup$
    – BobHU
    Apr 26, 2022 at 4:07
  • 1
    $\begingroup$ @BobHU In your example, the solver will choose $w_i=4$ and $w_j=6$ to satisfy the constraints if the route in question is desirable (optimal or at least better than the current incumbent solution). There is no danger that the "wiggle room" in choosing $w_i$ will result in an infeasible route (or a desirable feasible route being mistakenly judged infeasible). $\endgroup$
    – prubin
    Apr 26, 2022 at 16:23

Your Answer

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

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