Algorithms 15 00412 v2
Algorithms 15 00412 v2
Algorithms 15 00412 v2
Article
Branch and Price Algorithm for Multi-Trip Vehicle Routing
with a Variable Number of Wagons and Time Windows
Leila Karimi *,† and Chowdhury Nawrin Ferdous †
Department of Mathematics and Computer Science, University of Lethbridge, Lethbridge, AB T1K 3M4, Canada
* Correspondence: l.karimi@uleth.ca
† These authors contributed equally to this work.
Abstract: Motivated by the transportation needs of modern-day retailers, we consider a variant of the
vehicle routing problem with time windows in which each truck has a variable capacity. In our model,
each vehicle can bring one or more wagons. The clients are visited within specified time windows,
and the vehicles can also make multiple trips. We give a mathematical programming formulation for
the problem, and a branch and price algorithm is developed to solve the model. In each iteration
of branch and price, column generation is used. Different subproblems are created based on the
different capacities to find the best column. We use CPLEX to solve the problem computationally and
extend Solomon’s instances to evaluate our approach. To our knowledge, ours is the first such study
in this field.
Keywords: vehicle routing problem; multi-trip; time windows; column generation; branchand price
1. Introduction
Citation: Karimi, L.; Nawrin Ferdous,
C. Branch and Price Algorithm for
The Vehicle Routing Problem (VRP) initially emerged when Dantzig and Ramser
Multi-Trip Vehicle Routing with a
formulated and resolved the problem of supplying fuel to service stations around the end
Variable Number of Wagons and of the fifties of the last century [1].
Time Windows. Algorithms 2022, 15, The VRP definition states that n customers with discrete quantities of goods must
412. https://doi.org/10.3390/ be served by m vehicles initially located at a depot. A VRP is to determine the optimal
a15110412 routes taken by a group of vehicles while serving a group of users. The objective is to
minimize the overall transportation cost. The solution to the classical VRP problem is a set
Academic Editor: Roberto
of routes visiting all the customers exactly once that all begin and end in the depot. The
Montemanni
transportation cost is improved by reducing the total traveled distance [2].
Received: 24 August 2022 The Multi-Trip Vehicle Routing Problem with Time Windows (MTVRPTW) is a type
Accepted: 1 November 2022 of the classical Vehicle Routing Problem with Time Windows (VRPTW) with more than
Published: 4 November 2022 one trip for a vehicle during a workday. A trip is a timed route when more than one route
Publisher’s Note: MDPI stays neutral
can be allocated to a vehicle. The multi-trip feature is needed when the vehicle fleet size
with regard to jurisdictional claims in is limited. In this case, a benefit is a reduced number of drivers and vehicles. Besides, in
published maps and institutional affil- practice, industries cannot provide an unlimited number of vehicles to serve all customers,
iations. and they tend to prefer a limited number of vehicles to do more than one trip. Despite its
apparent practical relevance, this variant of the classical VRP has not been the subject of a
large number of studies. Refs. [3–5] are a few papers worked on Multi trip vehicle routing
problem (MTVRP).
Copyright: © 2022 by the authors. Multi-trip vehicle routing problem with a variable number of wagons and time win-
Licensee MDPI, Basel, Switzerland. dows defines a variant of the classical vehicle problem in which the capacity of vehicles
This article is an open access article can be determined given the total demand of the route when a vehicle is prepared to leave
distributed under the terms and the depot. In this situation, one, two, or three wagons can be attached to make a vehicle
conditions of the Creative Commons
ready to service the customers. The number of wagons and vehicles is limited, and the
Attribution (CC BY) license (https://
vehicle configuration will stay the same during all vehicle trips. This new methodology is
creativecommons.org/licenses/by/
suitable to decrease time and cost by reducing the number of vehicles, drivers, and fuel
4.0/).
consumption, which is specifically more critical in distributing goods over large distances
like two different cities or from large cities to rural areas.
The main contribution of this work is to introduce a mathematical model for Multi-trip
Vehicle Routing Problem with a Variable number of Wagons and Time Windows (MTVRP-
VW-TW). We develop a Branch and Price method to find an optimal solution. Column
generation is used for each iteration of the branch and pricing. Various subproblems
are formed to choose the appropriate column based on the various capacities. We used
modified Solomon’s instances [6] to test the algorithm. It is the first time the model has
been presented and solved with exact methods.
The rest of the paper is organized as follows. We review the relevant research in
Section 2. We give the definition and mathematical model for MTVRP-VW-TW in Section 3.
Column generation for MTVRP-VW-TW is presented in Section 4. MTVRP-VW-TW is
solved using the branch and price algorithm in Section 5. The detailed experimental study
is discussed in Section 6. Section 7 concludes this paper with a discussion of the limitations
of this work and possible future extensions.
2. Literature Review
Multi-trip vehicle routing problem (MTVRP) is an essential type of vehicle routing
problem in the real world that is studied less than other versions of vehicle routing problem,
specifically, for exact methods. Ref. [7] is a survey that categorizes and examines urban
logistic flows. As a result, it outlines the three main scientific issues that must be resolved:
time dependency, the arrangement of the distribution on multiple levels and trips, and
dynamic information. Fleischmann [8] proposed a modification of the savings heuristic
and used a Bin Packing Problem heuristic to assign the routes to vehicles with multiple uses.
Taillard, Laporte, and Gendreau [9] presented a tabu search algorithm with three phases to
solve the problem. Brando and Mercer [10] proposed another tabu search algorithm with
a variable neighborhood to find a solution with the least cost. The algorithm is a three-phase
algorithm that creates an initial solution by a heuristic and then uses tabu search (reinsertion
and exchange of customers) to improve the solution and restore feasibility. Brandão and
Mercer [11] also presented a more complex problem when mixed fleets and maximum
overtime constraints are allowed. Salhi [12] proposed the many-to-many location-routing
problem. Campbell and Savelsbergh [13] described insertion heuristics that can be used
effectively when time windows constraints are added to the problem.
Petch and Salhi [5] developed a multi-phase constructive heuristic for the MTVRP,
which in phase one generates a VRP solution using a savings approach, and phase 3 gener-
ates a VRP solution by route population approach. Phase 2 is a VRPM construction and
improvement stage in which an MTVRP solution is constructed using bin-packing with
the minimization of overtime as the objective. Salhi and Petch [14] improved their previous
method to a hybrid Genetic Algorithm with the same objective. Olivera and Viera [15] pre-
sented an adaptive memory approach to minimize total routing cost. Cattaruzza et al. [16]
used a hybrid genetic algorithm with a new local search operator that is a combination of
standard VRP moves and swaps between trips to minimize total traveling time. Wassan
et al. [17] proposed a two-level variable Neighborhood Search to generate an MT-VRPB
initial solution to minimize the total cost. Tirkolaee et al. [18] formulated a new model for
a robust multi-trip vehicle routing problem with intermediate depots and time windows
to address the uncertain nature of the demand. Anggodo et al. [19] presented a genetic
algorithm for multi-trip vehicle routing problems with time windows. More heuristic
approaches are in [20–23], in which a hybrid genetic algorithm, a simulated annealing, a
hybrid particle swarm optimization algorithm, and a hybrid genetic algorithm are used
respectively. A new impact integer programming formulation for the multi-trip vehicle
routing problem with time windows is developed in [24].
A limited number of papers on the exact methods for MTVRP exist. Desrosiers and
Solomon [25] were the first to use column generation in a Dantzig-Wolfe decomposition
framework. Halse [26] implemented Lagrangean decomposition. After that, Kohl and
Algorithms 2022, 15, 412 3 of 19
Madsen [27] extended Lagrangean relaxation. These approaches were further developed
using Dantzig-Wolfe decomposition, including cutting planes or parallel platforms in Kohl,
Desrosiers, Madsen, Solomon, and Soumis [28]; Larsen [29]; Cook and Rich [30]. A hybrid
algorithm, a combination of Lagrangean relaxation and Dantzig-Wolfe decomposition, was
presented by Kallehauge [31]. Chabrier, Danna and Le Pape [32]; Feillet, Dejax, Gendreau
and Gueguen [33]; Rousseau, Gendreau and Pesant [34]; Larsen [29]; Chabrier [35]; Irnich
and Villeneuve [36]; Danna and Le Pape (2005) [37] presented algorithms based on the
subproblem methods. Hernandez et al. [3], and Nabila Azi et al. [38] suggested the branch
and price algorithm with two phases. In the first phase, all paths are generated. In the
second phase, the problem is solved by column generation. Macedo et al. [39] proposed
an approach using a pseudo-polynomial model. Munari and Morabito [40] presented
a branch-price-cut for a multi-trip vehicle routing problem; Faiz et al. [41] has two inte-
ger programs for the open vehicle routing problem and uses column generation to solve
them; Azi et al. [4] gave column generation embedded in branch and price algorithm to
solve multi-trip vehicle routing problem with time windows using dynamic program-
ming to generate all non-dominated paths by label correcting algorithm which are used
in the subproblem; Seixas and Mendes [42] presented a branch and price algorithm to
solve the multi-trip vehicle routing problem with time windows and driver work hours.
Bettinelli et al. [43] used a branch-and-cut-and-price algorithm to solve the multi-trip sepa-
rate pickup and delivery problem with time windows. A branch-cut-and-price algorithm is
developed in [44] for the single and multi-trip two-echelon vehicle routing problem with
time windows. A new variant of the multi-trip vehicle routing problem for the case of
being in a queue while the unloading capacity is full is presented in [45] which is solved
using a branch-and-price-and-cut algorithm.
We are unaware of any work on exact methods for the multi-trip vehicle routing
problem with time windows and the flexibility of having different wagons attached to
service customers, as in this paper. In contrast to the previous works like [3,4,38] which
give branch and price algorithms for MTVRP, we formulate a new variant of MTVRP in
which the capacity can be different. This requires a modification of the branch and price
algorithms. We have a different master problem compared to the previous work. There are
three sub-problems with three different objective functions, and each subproblem is solved
by constructing a new route graph based on the capacity of the vehicle in which we look
for all the non-dominated tours.
At every point on the route, the time windows and capacity constraints are satisfied. The
workday of each vehicle is a sequence of routes where each route starts and ends at the
depot and we call it a tour. Multiple routes can be performed by a vehicle during one day,
and these routes are collectively called a tour. These routes are denoted by the set R and
the maximum number of routes in any tour (for any vehicle) is fixed in our model.
Each vehicle can be configured to use one, two, or three wagons giving it different
capacities. The configuration of each vehicle must stay the same on all trips. Next, we define
some of the mathematical model’s decision variables. The decision variable sir k denotes
the time that the vehicle k starts to service customer i in route r. If the vehicle k does not
service customer i in route r, sir k has no meaning; consequently, its value is considered
k
irrelevant. Variable xijr is one if vehicle k drives directly from customer i to customer j and
zero otherwise in route r. Variable zkn is used to determine how many wagons vehicle k
needs, where n is in {1, 2, 3}. If z32 = 1, vehicle 3 has 2 wagons. Therefore, z31 and z33 must
be 0, which means vehicle 3 does not have 1 or 3 wagons. Moreover, finally, qk is the kth
vehicle’s capacity, depending on the number of wagons attached.
k 1 if vehicle k drives directly from vertex i to vertex j on route r
xijr =
0 otherwise
1 if the m wagons are attached for vehicle k
zkm =
0 otherwise
We assume a0 = 0 and therefore s0rk = 0, for all k and r. The goal is to design a set of
min ∑ ∑ ∑ ∑ dijr
k k
xijr (1)
k ∈V r ∈ R i ∈ N j ∈ N
s.t.
∑ ∑ ∑ xijr
k
=1 ∀i ∈ C (2)
k ∈V r ∈ R j ∈ N
∑ di ( ∑ xijr
k
) ≤ qk ∀k ∈ V, ∀r ∈ R (3)
i ∈C j∈ N
3
qk = ∑ mqzkm ∀k ∈ V (4)
m =1
3
∑ ∑ mzkm ≤ |W | (5)
m =1 k ∈V
Algorithms 2022, 15, 412 5 of 19
3
∑ zkm = 1 ∀k ∈ V (6)
m =1
∑ k
x0jr =1 ∀k ∈ V, ∀r ∈ R (7)
j∈ N \{0}
∑ xihr
k
− ∑ xhjr
k
=0 ∀h ∈ C, ∀k ∈ V, ∀r ∈ R (8)
i∈ N j∈ N
∑ k
xi,n +1,r = 1 ∀k ∈ V, ∀r ∈ R (9)
i ∈ N \{n+1}
k k
sir + si + tij − M(1 − xijr ) ≤ skjr ∀i ∈ N \ {n + 1}, ∀ j ∈ N \ {0}, ∀k ∈ V, ∀r ∈ R (10)
ai ∑ k
xijr ≤ k
sir ≤ bi ∑ k
xijr ∀i ∈ C, ∀k ∈ V, ∀r ∈ R (11)
j∈ N −{0} j∈ N −{0}
k
s0r ≥ skn+1,r−1 ∀r ∈ R, ∀k ∈ V (12)
k
xijr ∈ {0, 1} ∀i, j ∈ N, ∀k ∈ V, ∀r ∈ R (13)
zkm ∈ {0, 1} ∀k ∈ V, m ∈ {1, 2, 3} (14)
k
sir ≥0 ∀i ∈ C, ∀k ∈ V, ∀r ∈ R (15)
k
q ≥0 ∀k ∈ V (16)
The objective function (1) minimizes the total distances of tours. The constraints (2)
ensure that each customer is visited exactly once. Equations (3) and (4) state that the total
demand on a route can not exceed the capacity of each vehicle depending on the number of
wagons attached. The constraint in (5) shows the number of wagons in total. Constraints (6)
ensure that a vehicle is assigned only one configuration. Equations (7)–(9) indicate that
each vehicle must leave the depot 0; flow conservation constraints; finally, all vehicles
must return to the depot n + 1. The inequalities (10) establish the relationship between the
vehicle departure time from a customer and its immediate successor. Constraints (11) assert
that the time windows are observed. Constraints (12) ensure a proper trip sequencing for
the workday of a vehicle that the starting time of the next trip of the vehicle must be after
the finishing time of its previous trip. Equations (13) and (14) are integer variables.
min ∑ dw yw (18)
w∈Ω
s.t.
∑ aiw yw ≥ 1 ∀i ∈ C (19)
w∈Ω
∑ y w ≤ |V | (20)
w∈Ω
∑ n w y w ≤ |W | (21)
w∈Ω
yw ∈ {0, 1} ∀w ∈ Ω (22)
The objective function (18) is to minimize the total distances of all tours. Con-
straints (19) ensure that each customer is visited at least once. The constraint (20) states
that the number of all tours must be less than the number of vehicles. Constraint (21) states
that the number of wagons used in all the vehicles must be less than the total number
of wagons.
The solution is a subset of Ω. As the number of columns is exponential in the number
of customers, we solve the restricted master problem (RMP) with a limited number of
columns for the initial solution. The columns are progressively added into RMP. The
LP-relaxation of RMP (RLMP) is solved with an LP solver to obtain the dual variables
associated with the optimal solution of the RLMP. These dual values are sent to the
subproblem to determine new tours with a negatively reduced cost, and these new tours
are added to the master problem. The process will continue until there are no more tours
with a negatively reduced cost. This guarantees an optimal solution to the RLMP.
t̄inr +1 ← binr +1
Finally, we will have t̄ri0 which is the latest departure of the route r and again in
a similar way we obtain the latest arrival time of the route as well as the latest feasible
schedules (t̄ri ) at each customer using a forward sweep, so each t̄ri can be calculated as:
j j
Case 1: there is no waiting time (vehicle doesn’t arrive before time windows) in the
latest feasible time of customers, then we can shift the latest times by the minimum of (t̄ri )
j
and ai j , so we can calculate it for each route as:
By deducting these units from the latest departure and arrival times, the earliest
departure and arrival can be obtained. So, we have:
t0r = t̄0r − δr
and,
trn+1 = t̄rn+1 − δr
Having all the latest departure and arrival times as well as the earliest departure
and arrival times, it is possible to write the time windows for all routes as: [t0r , t̄0r ] and
[trn+1 , t̄rn+1 ].
Case 2: If there are some waiting times in the latest feasible time for customers. Then,
we can not leave the depot earlier, when the latest arrival times are before the time windows.
So, the earliest departure and arrival times will be the same as the latest departure and
arrival times respectively.
t0r = t̄0r
and,
trn+1 = t̄rn+1
In case 2, the time windows for departure and arrival will be a single point. So, the
0 0
route r 0 can be served after route r if trn+1 + δr ≤ t̄0r .
Given all this information, now to create the route graph, we must note that there
must not be any common customer between routes r and r 0 and the latest arrival time of
the route r must be less than the latest departure time of the next route r 0 . If both conditions
are met, then there is an edge from r to r 0 .
∑ X0r = 1 (25)
r∈ AT
∑ Xr,n+1 = 1 (26)
r∈ AT
Tr + (t̄rn+1 − t̄0r ) − M(1 − Xrs ) ≤ Ts ∀(r, s) ∈ A T (27)
t0r ≤ Tr ≤ t̄0r ∀r ∈ V T
(28)
T
Xrs ∈ {0, 1} ∀(r, s) ∈ A (29)
Tr ≥ 0 ∀(r, s) ∈ A T (30)
The objective function (23) is to reduce the cost of the tour. Constraint (24) indicates
that the vehicle must leave a route and go to the next one. Constraints (25) and (26) ensure
that the tour starts and ends at the depot. The inequalities (27) establish the relationship
between the vehicle departure time from a route and its immediate successor. Constraints
(28) assert that the time windows of routes are observed.
The following flowchart shows the process of generating all non-dominated tours for
the sub-problem with one wagon in Figure 1. The same procedure is used for two other
sub-problems.
Input Graph
Generate All
Non-dominated
paths (Section 4.3)
Generate Route
Graph (Section 4.4)
Algorithm 1 Cont.
Initialization {Generate all non-dominated tours}
HkT ← {(0, ..., 0)}
for all Rk ∈ V T − { p} do
FT kh ← ∅
end for
ET = { p}
while E T ! = ∅ do
Choose Rk ∈ E T
for all Rh ∈ SuccT ( Rk ) do
FT kh ← ∅
for all LkT ∈ HkT do
if Rkh = 0 then
FT kh ← FT kh ∪ ExtendT ( LkT , Rh )
end if
end for
HhT ← DominatedT ( FT kh ∪ HhT )
if HhT has changed then
ET ← ET ∪ { Rh }
end if
end for
E T ← E T − { Rk }
end while
All non-dominated tours will be generated using the extend and dominate function in
the label-correcting algorithm. There are three subproblems based on the various capacity.
All tours will be generated for these three subproblems. First, we will see if there is a new
tour with a negative reduced cost in the subproblem with one wagon. If so, the column will
be added to the master problem. If not, the second subproblem will be checked. Suppose a
new tour with a negative reduced cost is added to the master problem. If not, we will check
the third subproblem, which uses three wagons. We solve the subproblems until all tours
with the negative reduced cost are found and added to the master problem. The following
flowchart shows the procedure of the algorithm in Figure 2.
Algorithms 2022, 15, 412 13 of 19
Master Problem
(Section 4.1)
No
No
No
Yes
Solution Integral Done
No
Branch and
price (Section 5)
to branching [4]. The minimum capacity for all vehicles that service a single customer is
one wagon.
Search Strategy: The branch and price tree is explored using a depth-first search.
Lower and Upper Bound: The solution to RLMP at the root node gives a lower bound
for the problem. We solve the master problem using CPLEX. The integer solution of the
master problem given by the CPLEX 12.8 is used as the upper bound.
Branching Strategy: Two branching strategies are used. We branch on the number of
vehicles and the arcs.
Branching on the Number of Vehicles: We sum the value of variables of the optimal
0
solution of RLMP, so k = ∑w∈Ω0 yw , where Ω ⊆ Ω. If k is fractional, two branches are
created. For each branch, one additional constraint is added to the master problem. These
two constraints are:
∑ yw ≤ bk c
0
w∈Ω
and
∑ 0 y w ≥ b k + 1c.
w∈Ω
The dual variable value corresponding to the new constraint is added to the subprob-
lem, and the column generation is done again for this new child node.
Branching on Arcs: The branch on an arc happens when the flow on an arc (i, j) is
fractional. We calculate the flow on any arc that is in some column. The sum of the yw ,
0
w ∈ Ω on the columns that include an arc (i, j), will give the flow on the arc. The arc with
fractional value is taken. So, these branches will be:
• Left branch: xij = 1, which means the customer j must be visited right after customer
i in all tours of RLMP and the route graph. To enforce it, all columns in the RLMP
and the route graph that contains arc (i, k) with k 6= j and (k, j) with k 6= i must be
deleted. Also, if xi = ∑w∈Ω0 aiw yw , then the decision variables for vertices i and j are
set to one in RLMP, xi = 1 and x j = 1.
• Right branch: xij = 0, which means the customer j must not follow the customer i
immediately. So all tours must be removed, including the arc (i, j) in RLMP and the
route graph.
modified the number of vehicles and capacity in type C1, R1 to 25 vehicles, and the capacity
of 200 changed to 15 vehicles, 30 wagons, 3 routes and a capacity of 150 for each wagon.
For type C2, 25 vehicles and a capacity of 700 are changed to 15 vehicles, 30 wagons, 3
routes, and a capacity of 500 for each wagon. For type R2 with a capacity of 1000 changed
to 15 vehicles, 30 wagons, 3 routes, and a capacity of 700 for each wagon. Tables 1–3 show
the results.
Table 1. 25 Customers.
Table 2. 50 Customers.
Table 3. 10 Customers.
All the instances have a large integrality gap and it takes a lot of time to solve the
mathematical model.
Experimental Results
The results of the branch and price algorithm are presented next. The program
was implemented in the optimization programming language OPL, using ILOG CPLEX.
Algorithms 2022, 15, 412 16 of 19
CEDAR, the Compute Canada cluster, was used for experimentation, with a limit of 4 h on
each solve and a maximum memory requirement of 40GB. Our algorithm was able to find
optimal solutions for R1, R2, RC1, and RC2.
The results are in Table 4 where the column named Instances is the type of the instance.
The gap is between the LP-relaxation value at the root and the optimal integer value in %.
CPU time is calculated as differences between the time recorded at the root and the end of
the algorithm in seconds. Obj is the total distance. Iter is the number of iterations used to
solve RLMP by CPLEX. Cols is the number of columns generated during the branch and
price algorithm. Node is the number of nodes explored in the search tree. The route is the
max number of routes used in all tours. Tour is the number of tours used to visit customers.
CPU Time
Instance Gap Obj Iter Cols Node Route Tour
(s)
RC102 994.364 869.56 563.562 20 17 3 2 2
RC103 994.364 899.163 563.562 20 17 3 2 2
RC105 994.548 398.842 545.237 18 17 1 2 2
RC106 993.178 111.626 682.168 13 12 1 2 3
RC107 994.189 202.428 581.069 11 10 1 2 2
RC108 994.121 670.193 587.86 17 14 3 2 2
RC202 992.434 470.885 756.612 5 4 1 1 2
RC203 992.434 470.885 756.612 5 4 1 1 2
RC204 993.722 872.675 627.785 3 2 1 1 2
RC206 794.258 139.613 724.979 8 7 1 2 1
RC207 991.067 446.75 893.255 15 14 1 2 1
RC208 797.627 800.939 388.128 3 2 1 1 1
R102 993.936 102.048 606.438 7 6 1 2 2
R103 993.936 106 606.438 7 6 1 2 2
R108 993.326 1287.93 667.381 16 13 3 2 2
R110 994.023 171.832 597.728 10 9 1 2 2
R111 993.629 2010.17 637.106 14 12 3 2 2
R202 991.33 455.858 867.046 5 4 1 2 1
R203 991.33 458.102 867.046 5 4 1 2 1
R204 993.722 881.522 627.785 3 2 1 1 2
R205 992.355 102.946 764.518 3 2 1 2 1
R206 993.992 581.478 600.814 3 2 1 1 2
R207 993.992 593.218 600.814 3 2 1 1 2
R208 993.993 612.737 600.683 3 2 1 1 2
R209 992.61 345.444 739.023 8 7 1 1 2
R210 993.672 1068.08 632.814 3 2 1 1 2
R211 996.263 443.173 373.736 2 1 1 1 1
6.3. Analysis
The mathematical model was tested, and it can take hours, or days to give solutions
with gaps of around 60%, this is why we need to use a method like a branch and a price,
which is an exact method to have the optimal solution of the problem.
The mathematical model is a new one in that the mathematical test confirms the
validation of the model and the branch and price test shows solving the model optimally.
The branch and price algorithm solves the model for the small instances, but it gives the
optimal solution for these instances that the model can not provide.
During experimentation, we notice that the algorithm explores more nodes if a similar
capacity (one wagon) is used for all tours. Giving the algorithm the option to check more
tours with two wagons and three before starting a new branch makes it faster and explores
a smaller number of nodes. The number of added columns before starting a new branch
increases when different capacities are used. Varying capacity can significantly affect the
number of explored nodes. The upper bound that the CPLEX provides us is a good upper
Algorithms 2022, 15, 412 17 of 19
bound close to the optimal solution and it helps to explore fewer nodes and have a solution
faster.
The algorithm solves type 2 instances where the time windows are more expansive on
the horizon. It is faster and uses fewer iterations. For type C instances, branch and price
could not find a solution to the time cut-off limit. All the instances listed in Table 4 were
solved optimally within four hours.
We need to solve two resource constraints, the shortest path problem to determine
a column with a negative reduced cost, and we need also to construct a route graph. The
shortest path problem is solved using dynamic programming whose run time depends on
the number of non-dominated paths which can be exponential. For large instances, this
type of program run out of memory to store all the non-dominated paths. That is why we
cannot solve large instances using column generation, as a part of future work we will look
at other methods for solving the resource constraint shortest path problem.
Abbreviations
The following abbreviations are used in this manuscript:
References
1. Dantzig, G.B.; Ramser, J.H. The Truck Dispatching Problem. Manag. Sci. 1959, 6, 80–91. [CrossRef]
2. Caric, T.; Gold, H. Vehicle Routing Problem; InTech: London, UK, 2008.
3. Hernandez, F.; Feillet, D.; Giroudeau, R.; Naud, O. An exact method to solve the multitrip vehicle routing problem with time
windows and limited duration. TRISTAN 2010, 7, 366–369.
4. Azi, N.; Gendreau, M.; Potvin, J.Y. An exact algorithm for a vehicle routing problem with time windows and multiple use of
vehicles. Eur. J. Oper. Res. 2010, 202, 756–763. [CrossRef]
5. Petch, R.J.; Salhi, S. A multi-phase constructive heuristic for the vehicle routing problem with multiple trips. Discret. Appl. Math.
2003, 133, 69–92. [CrossRef]
6. Solomon, M.M. Algorithms for the vehicle routing and scheduling problems with time window constraints. Oper. Res. 1987,
35, 254–265. [CrossRef]
7. Cattaruzza, D.; Absi, N.; Feillet, D.; González-Feliu, J. Vehicle routing problems for city logistics. EURO J. Transp. Logist. 2017,
6, 51–79. [CrossRef]
8. Fleischmann, B. The Vehicle Routing Problem with Multiple Use of Vehicles. Ph.D. Thesis, Fachbereich Wirtschaftswissenschaften,
Universität Hamburg, Hamburg, Germany, 1990.
9. Taillard, É.D.; Laporte, G.; Gendreau, M. Vehicle routeing with multiple use of vehicles. J. Oper. Res. Soc. 1996, 47, 1065–1070.
[CrossRef]
10. Brandao, J.; Mercer, A. A tabu search algorithm for the multi-trip vehicle routing and scheduling problem. Eur. J. Oper. Res. 1997,
100, 180–191. [CrossRef]
11. Brandão, J.C.S.; Mercer, A. The multi-trip vehicle routing problem. J. Oper. Res. Soc. 1998, 49, 799–805. [CrossRef]
12. Nagy, G.; Salhi, S. The many-to-many location-routing problem. Top 1998, 6, 261–275. [CrossRef]
13. Campbell, A.M.; Savelsbergh, M. Efficient insertion heuristics for vehicle routing and scheduling problems. Transp. Sci. 2004,
38, 369–378. [CrossRef]
14. Salhi, S.; Petch, R. A GA based heuristic for the vehicle routing problem with multiple trips. J. Math. Model. Algorithms 2007,
6, 591–613. [CrossRef]
15. Olivera, A.; Viera, O. Adaptive memory programming for the vehicle routing problem with multiple trips. Comput. Oper. Res.
2007, 34, 28–47. [CrossRef]
16. Cattaruzza, D.; Absi, N.; Feillet, D.; Vigo, D. An iterated local search for the multi-commodity multi-trip vehicle routing problem
with time windows. Comput. Oper. Res. 2014, 51, 257–267. [CrossRef]
17. Wassan, N.; Wassan, N.; Nagy, G.; Salhi, S. The multiple trip vehicle routing problem with backhauls: Formulation and a two-level
variable neighbourhood search. Comput. Oper. Res. 2017, 78, 454–467. [CrossRef]
18. Tirkolaee, E.B.; Goli, A.; Bakhsi, M.; Mahdavi, I. A robust multi-trip vehicle routing problem of perishable products with
intermediate depots and time windows. Numer. Algebr. Control Optim. 2017, 7, 417–433. [CrossRef]
19. Anggodo, Y.; Ariyani, A.; Ardi, M.; Mahmudy, W. Optimization of multi-trip vehicle routing problem with time windows using
genetic algorithm. J. Environ. Eng. Sustain. Technol. 2017, 3, 92–97.
20. Tirkolaee, E.B.; Hosseinabadi, A.A.R.; Soltani, M.; Sangaiah, A.K.; Wang, J. A hybrid genetic algorithm for multi-trip green
capacitated arc routing problem in the scope of urban services. Sustainability 2018, 10, 1366. [CrossRef]
21. Babaee Tirkolaee, E.; Abbasian, P.; Soltani, M.; Ghaffarian, S.A. Developing an applied algorithm for multi-trip vehicle routing
problem with time windows in urban waste collection: A case study. Waste Manag. Res. 2019, 37, 4–13. [CrossRef]
22. Chen, D.; Pan, S.; Chen, Q.; Liu, J. Vehicle routing problem of contactless joint distribution service during COVID-19 pandemic.
Transp. Res. Interdiscip. Perspect. 2020, 8, 100233. [CrossRef]
23. Zhen, L.; Ma, C.; Wang, K.; Xiao, L.; Zhang, W. Multi-depot multi-trip vehicle routing problem with time windows and release
dates. Transp. Res. Part E Logist. Transp. Rev. 2020, 135, 101866. [CrossRef]
24. Neira, D.A.; Aguayo, M.M.; De la Fuente, R.; Klapp, M.A. New compact integer programming formulations for the multi-trip
vehicle routing problem with time windows. Comput. Ind. Eng. 2020, 144, 106399. [CrossRef]
25. Desrochers, M.; Desrosiers, J.; Solomon, M. A new optimization algorithm for the vehicle routing problem with time windows.
Oper. Res. 1992, 40, 342–354. [CrossRef]
Algorithms 2022, 15, 412 19 of 19
26. Halse, K. Modeling and Solving Complex Vehicle Routing Problems. Ph.D. Thesis, Technical University of Denmark, Kongens
Lyngby, Denmark, 1992.
27. Kohl, N.; Madsen, O.B.G. An optimization algorithm for the vehicle routing problem with time windows based on Lagrangian
relaxation. Oper. Res. 1997, 45, 395–406. [CrossRef]
28. Kohl, N.; Desrosiers, J.; Madsen, O.B.; Solomon, M.M.; Soumis, F. 2-path cuts for the vehicle routing problem with time windows.
Transp. Sci. 1999, 33, 101–116. [CrossRef]
29. Larsen, J. Parallelization of the Vehicle Routing Problem with Time Windows; Citeseer: Lyngby, Denmark, 1999.
30. Cook, W.; Rich, J.L. A Parallel Cutting-Plane Algorithm for the Vehicle Routing Problem with Time Windows; Technical Report; Rice
University: Houston, TX, USA, 1999.
31. Kallehauge, B.; Larsen, J.; Madsen, O.B. Lagrangean Duality and Non-Differentiable Optimization Applied on Routing with Time
Windows-Experimental Results; Relatório interno IMM-REP-2000-8; Department of Mathematical Modeling, Technical University
of Denmark: Lyngby, Denmark, 2000.
32. Chabrier, A.; Danna, E.; Le Pape, C. Coopération entre génération de colonnes avec tournées sans cycle et recherche locale
appliquée au routage de véhicules. In Proceedings of the Journées Nationales sur la Résolution Pratique de Problèmes NP-
Complets, Nice, France, 27–29 May 2002; pp. 83–97.
33. Feillet, D.; Dejax, P.; Gendreau, M.; Gueguen, C. An exact algorithm for the elementary shortest path problem with resource
constraints: Application to some vehicle routing problems. Netw. Int. J. 2004, 44, 216–229. [CrossRef]
34. Rousseau, L.M.; Gendreau, M.; Pesant, G.; Focacci, F. Solving VRPTWs with constraint programming based column generation.
Ann. Oper. Res. 2004, 130, 199–216. [CrossRef]
35. Chabrier, A. Vehicle routing problem with elementary shortest path based column generation. Comput. Oper. Res. 2006,
33, 2972–2990. [CrossRef]
36. Irnich, S.; Villeneuve, D. The shortest path problem with k-cycle elimination (k > 3): Improving a branch and price algorithm for
the VRPTW. INFORMS J. Comput. 2003, 10, 1–15.
37. Danna, E.; Le Pape, C. Accelerating branch-and-price with local search: A case study on the vehicle routing problem with time
windows. In Column Generation; Desaulniers, G., Desrosiers, J., Solomon, M.M., Eds.; Kluwer Academic Publishers: Amsterdam,
The Netherlands, 2005; Charpter 3.
38. Azi, N.; Gendreau, M.; Potvin, J.Y. An exact algorithm for a single-vehicle routing problem with time windows and multiple
routes. Eur. J. Oper. Res. 2007, 178, 755–766. [CrossRef]
39. Macedo, R.; Alves, C.; de Carvalho, J.V.; Clautiaux, F.; Hanafi, S. Solving the vehicle routing problem with time windows and
multiple routes exactly using a pseudo-polynomial model. Eur. J. Oper. Res. 2011, 214, 536–545. [CrossRef]
40. Munari, P.; Morabito, R. A branch-price-and-cut algorithm for the vehicle routing problem with time windows and multiple
deliverymen. Top 2018, 26, 437–464. [CrossRef]
41. Faiz, T.I.; Vogiatzis, C.; Noor-E-Alam, M. A column generation algorithm for vehicle scheduling and routing problems. Comput.
Ind. Eng. 2019, 130, 222–236. [CrossRef]
42. Seixas, M.P.; Mendes, A.B. A branch-and-price approach for a multi-trip vehicle routing problem with time windows and driver
work hours. In Proceedings of the Congreso Latino-Iberoamericano de Investigación Operativa. Simpósio Brasileiro de Pesquisa
Operacional, Rio de Janeiro, Brazil, 24–28 September 2012; pp. 3469–3480.
43. Bettinelli, A.; Cacchiani, V.; Crainic, T.G.; Vigo, D. A branch-and-cut-and-price algorithm for the multi-trip separate pickup and
delivery problem with time windows at customers and facilities. Eur. J. Oper. Res. 2019, 279, 824–839. [CrossRef]
44. Marques, G.; Sadykov, R.; Dupas, R.; Deschamps, J.C. A branch-cut-and-price approach for the single-trip and multi-trip
two-echelon vehicle routing problem with time windows. Transp. Sci. 2022 . [CrossRef]
45. Huang, N.; Li, J.; Zhu, W.; Qin, H. The multi-trip vehicle routing problem with time windows and unloading queue at depot.
Transp. Res. Part E Logist. Transp. Rev. 2021, 152, 102370. [CrossRef]
46. Solomon’s Benchmark Instances. Available online: https://www.sintef.no/projectweb/top/vrptw/100-customers/ (accessed on
20 August 2022).