How does the VRPTW model ensure the arrival time at next station tightened?

Question

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

Answer 1

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.

Answer 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.