# Vehical routing problem with time windows

**URL:** https://discourse.julialang.org/t/vehical-routing-problem-with-time-windows/123550
**Category:** Optimization (Mathematical)
**Tags:** question
**Created:** [December 6, 2024, 8:32pm UTC](https://discourse.julialang.org/t/vehical-routing-problem-with-time-windows/123550 "2024-12-06T20:32:08Z")
**Posts on this page:** 2
**Page:** 1

<div class="post-metadata">

### Author: ![aditya\_lokesh](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/aditya_lokesh/32/213701_2.png) [@aditya\_lokesh](https://discourse.julialang.org/u/aditya_lokesh)
#### Post date: [December 6, 2024, 8:32pm UTC](https://discourse.julialang.org/t/vehical-routing-problem-with-time-windows/123550/1 "2024-12-06T20:32:09Z")

</div>

The VRPTW is defined by a fleet of vehicles, V, a set of customers,  
C, and a directed graph Q, Typically the fleet is considered to be homo-  
geneous, that is, all vehicles are identical. The graph consists of |C| + 2  
vertices, where the customers are denoted 1,2,… ,n and the depot is  
represented by the vertices 0 (“the starting depot”) and n + 1 (“the re-  
turning depot”). The set of all vertices, that is, 0 , 1 , . . . , n-(-1 is denoted  
J\f. The set of arcs, v4, represents direct connections between the depot  
and the customers and among the customers. There are no arcs ending  
at vertex 0 or originating from vertex n + 1. With each arc (i,i), where  
i ^ j^ we associate a cost Cij and a time tij^ which may include service  
time at customer i.  
Each vehicle has a capacity q and each customer i a demand di. Each  
customer i has a time window [ai^hi] and a vehicle must arrive at the  
customer before hi. If it arrives before the time window opens, it has to  
wait until ai to service the customer. The time windows for both depots  
are assumed to be identical to [ao,&o] which represents the scheduling  
horizon. The vehicles may not leave the depot before ao and must return  
at the latest at time 6n+i-  
It is assumed that g, a^, 6^, d^, QJ are non-negative integers and tij  
are positive integers. Note that this assumption is necessary to develop  
an algorithm for the shortest path with resource constraints used in the  
column generation approach presented later. Furthermore it is assumed  
that the triangle inequality is satisfled for both cij and tij.  
The model contains two sets of decision variables x and s. For each  
arc (i, j ) , where i 7^ j , i / n + 1, j ^ 0, and each vehicle k we define  
Xij]^ as  
{ 1, if vehicle k drives directly from vertex i to vertex j ,  
0, otherwise.  
The decision variable Sik is defined for each vertex i and each vehi-  
cle k and denotes the time vehicle k starts to service customer i. In  
case vehicle k does not service customer i, sik has no meaning and con-  
sequently it’s value is considered irrelevant. We assume ao = 0 and  
therefore 5o/c = 0, for all k.  
The goal is to design a set of routes that minimizes total cost, such  
that  
• each customer is serviced exactly once,  
• every route originates at vertex 0 and ends at vertex n + 1, and  
70 COL UMN GENERA TION  
• the time windows of the customers and capacity constraints of the  
vehicles are observed.  
This informal VRPTW description can be stated mathematically as a  
multicommodity network flow problem with time windows and capacity  
constraints:  
m i n ^ ^ ^ CijXijk s.t, (3.1)  
I ] I ] ^ Ü ^ = 1 ViGC, (3.2)  
keVjeM  
^ di Y^ Xijk \<q /k eV, (3.3)  
ieC jeAf  
J2xojk = l VfcGV, (3.4)  
jeJ\f  
Y^ Xihk - Yl ^^^J^ = ^ “iheC.WkeV, (3.5)  
leAf jeAf  
Y,Xi,n+i.k = l VfceV, (3.6)  
ieM”  
Xijk{sik + Uj - Sjk) \< 0 Vi, j G Af, Vfc G V, (3.7)  
ai \< Sik \<bi Vi G AT, Vfc G V, (3.8)  
Xijk € {0,1} Vi, j G AT, Vfc G V. (3.9)  
The objective function (3.1) minimizes the total travel cost. The con-  
straints (3.2) ensure that each customer is visited exactly once, and (3.3)  
state that a vehicle can only be loaded up to it’s capacity. Next, equa-  
tions (3.4), (3.5) and (3.6) indicate that each vehicle must leave the  
depot 0; after a vehicle arrives at a customer it has to leave for another  
destination; and finally, all vehicles must arrive at the depot n + 1. The  
inequalities (3.7) establish the relationship between the vehicle depar-  
ture time from a customer and its immediate successor. Finally con-  
straints (3.8) affirm that the time windows are observed, and (3.9) are  
the integrality constraints. Note that an unused vehicle is modeled by  
driving the “empty” route (0,n + 1).  
The model can also incorporate a constraint giving an upper bound  
on the number of vehicles, as is the case in Desrosiers, Dumas, Solomon  
and Soumis (1995):  
^J2’^^Jk\<\V\ VfcGV, VjGAA (3.10)  
keVjeAf  
3 VRPTW 71  
Note also that the nonhnear restrictions (3.7) can be hnearized as:  
Sik + tij - Mij{l - Xijk) \< Sjk Vi, j G A/", Vfc G V. (3.11)  
The large constants Mij can be decreased to max{6i+t^j —a^}, (z, j) G A,  
For each vehicle, the service start variables impose a unique route  
direction thereby eliminating any subtours. Hence, the classical VRP  
subtour elimination constraints become redundant. Finally, the objec-  
tive function (3.1) has been universally used when solving the VRPTW  
to optimality. In the research on heuristics it has been common to min-  
imize the number of vehicles which may lead to additional travel cost.  
The VRPTW is a generalization of both the traveling salesman prob-  
lem (TSP) and the VRP. When the time constraints (3.7) and (3.8))  
are not binding the problem relaxes to a VRP. This can be modeled by  
setting a^ = 0 and 6^ = M, where M is a large scalar, for all customers  
i. If only one vehicle is available the problem becomes a TSP. If sev-  
eral vehicles are available and the cost structure is: CQJ — 1^ j E C and  
Cij = 0, otherwise, we obtain the bin-packing problem. Since trips be-  
tween customers are “free”, the order in which these are visited becomes  
unimportant and the objective turns to “squeezing” as much demand as  
possible into as few vehicles (bins) as possible. In case the capacity con-  
straints (3.2) are not binding the problem becomes a m-TSPTW, or, if  
only one vehicle is available, a TSPTW

The full problem is mentioned here  
`http://alvarestech.com/temp/vrptw/Vehicle%20Routing%20Problem%20with%20Time%20Windows.pdf`

Struggling to develop a model for column generation for and having issues related to model definition itself unable to figure out the model.  
Can someone please provide a model for the above problem

---

<div class="post-metadata">

### Author: ![gdalle](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gdalle/32/27854_2.png) [@gdalle](https://discourse.julialang.org/u/gdalle)
#### Post date: [December 6, 2024, 9:20pm UTC](https://discourse.julialang.org/t/vehical-routing-problem-with-time-windows/123550/2 "2024-12-06T21:20:12Z")

</div>

This looks like a homework problem. If you have a **specific** question, feel free to ask it, but the people here will not write your whole model for you.