4
$\begingroup$

Hi I am trying to solve a vehicle routing problem using Tabu search, I have successfully completed implementation of constraints for CVRP by giving penalties to objective function , how do I implement time window as a constraint?

$\endgroup$
  • 1
    $\begingroup$ You can define a penalty for each node and activate it when the time window is violated. $\endgroup$ – Kuifje Sep 11 at 21:23
2
$\begingroup$

Vehicle Routing Problem with Time Window constraints Let imagine a logistics network consisting of a warehouse and numerous retailers. All stocks enter into the logistics network through the depot and from this one the goods are distributed to the retails via a fleet of vehicles. Each retailer (customer) specifies to the load to be delivered. In addition, if retailer specifies a period of time (time window) in which the delivery should occur then the model is called Vehicle Routing Problem with Time Window constraints(VRPTW). The objective is to find a set of routes which minimizes the total length of the routes or the number of used vehicles without violating the vehicle capacity and time window constraints. Let the index set of the $n$ retailers be denoted $N=1,2, \cdots, n$.

Let the load which has to be delivered be $w_i$.

Let the earliest starting time for the service of unload be $r_i$. The value of $r_i$ can be thought as a release time of the i-th job in machine scheduling environment so that it designates the time job (retailer) is available for processing.

Let the duration of unloading activity be $d_i$ that is the time required to complete the service. The value of $d_i$ can be thought as the processing time of the i-th job in the machine scheduling environment

Let the latest termination time for the service be $l_i$ that is the time the service can end. The value of $l_i$ can be thought as the due date for the i-th job.

For the depot (the depot is located at the origin, $i=0$ ) and for each retailer there is a time window

$ [r_i, l_i]$

during which it must be served where $i=0,1, 2, \cdots, n$. The service start time at each node must be $\geq r_i$ and the arrival time at each node must be $\leq l_i$. If a vehicle arrives at time $<r_i$ then the vehicle must wait before starting to serve the retailer.

$r_i < l_i - d_i $

or $r_i = l_i - d_i $ if there is not a slack between release time and due date.

Note that $r_i, l_i, d_i$ are parameters and are known without uncertainty.

TW Constraint

Let $x_{i,k,m}$ be a Boolean variable: $x_{i,k,m} = 1$ if m-th vehicle travels from i-th node to k-th node, zero otherwise. For simplicity, we will suppose m=1. Let $t_k$ be a continuous decision variable representing the arrival time at node $k$ that is instant the service can start. We assign a travel time $t_{ij}$ to every edge i-j. The time window constraint can be formulated as:

$t_i \geq r_i$ and $t_i \leq l_i$ for all $i=1,2, \cdots, n$.

Let assume the travel times $t_{ij}$ satisfy the triangle inequality, i.e.

$ t_{ik} + t_{kj} \geq t_{ij} $ for all $i=1,2, \cdots, n$.

The generic temporal constraints can be formulated as

$\left\{ \begin{array}{l} t_j \geq t_i + (r_j – l_i + d_i + t_{ij} ) \cdot x_{i,j} – M \cdot (l_i – r_j) \cdot (1- x_{i,j}) \\ t_i \geq r_i \\ t_i \leq l_i \\ t_i , t_j \ge 0 \end{array} \right. $

| improve this answer | |
$\endgroup$
  • $\begingroup$ I have solved the problem by considering traveling time instead of distance, and checked( total time travelled + unloading time < latest delivery time) $\endgroup$ – sudarsan vs Sep 24 at 4:46

Your Answer

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

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