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