4

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}\}$.

SecretAgentMan
  • 1,895
  • 2
  • 13
  • 39
BobHU
  • 165
  • 3
  • 2
    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. – Sune Apr 25 '22 at 17:19
  • 1
    Could you please tell us the paper you are referring to? – PeterD Apr 25 '22 at 19:17
  • @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? – PeterD Apr 25 '22 at 19:43
  • 1
    Related, with the exact same notation: https://or.stackexchange.com/questions/7643/vrptw-is-there-a-way-to-prevent-waiting-at-a-node-before-starting-service – RobPratt Apr 25 '22 at 19:58

2 Answers2

2

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.

prubin
  • 39,078
  • 3
  • 37
  • 104
  • 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. – PeterD Apr 25 '22 at 19:10
  • @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. – prubin Apr 25 '22 at 20:06
  • 1
    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. – PeterD Apr 25 '22 at 20:26
  • @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]$. – BobHU Apr 26 '22 at 04:07
  • @PeterD If it doesn't ensure the tightness, the problem is as follows. Say I have a node $i$ with time window $[3, 6]$, and the vehicle arrives $i$ at $t=4$ (exact time), then $w_i$ could be any value in $[4,6]$. For simplicity, we set all service time to be 0 here. Let's say $w_i=5$ here, then if it travels to next node $j$ takes $t_{ij}=2$, it would arrive $j$ at $t=6$, but for $w_j$, the value is $w_i+t_{ij}=5+2=7$, then say the time window for $j$ is $[4,6]$, then according to $w_j \le b_j$, this route violates the constraint. However, it actually arrives at t=6, which satisfies $[4,6]$. – BobHU Apr 26 '22 at 04:21
  • 1
    @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). – prubin Apr 26 '22 at 16:23
2

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.

Sune
  • 6,457
  • 2
  • 17
  • 31
  • 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. – BobHU Apr 26 '22 at 08:41
  • 1
    @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. – Sune Apr 26 '22 at 09:04
  • 1
    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. – BobHU Apr 26 '22 at 09:22