CACIC 2023 - Universidad Nacional de Luján - ISBN 978-987-9285-51-0
Abstract. In this article, we present a search technique based on metaheuristics for approximately solving the vehicle routing problem with time windows (VRPTW). The Problem Aware Local Search (PALS) is the metaheuristic selected, which proves to be a powerful technique for solving the DNA Fragment Assembly Problem. PALS performs a trajectory in the search space by improving a single solution using a specific move operator. A detailed description of the algorithmic design points and the operators for the VRPTW are carried out. Furthermore, preliminary results are shown and analyzed.
Keywords: Vehicle Routing Problem with Time Windows, Optimization, Problem Aware Local Search (PALS)
1 Introduction
Vehicle Routing Problems (VRP) [1] have been a
subject of active research in the optimization community for the last 60 years.
Since then, many changes in the initial problem formulation have been made. In
this sense, a well-known variant of the VRP incorporates Time Windows (VRPTW),
which is present in many real-world scenarios, such as in distribution
operations, where the time window of the delivery is a crucial parameter of the
problem. The VRPTW consists in delivering goods to a set of customers with known
demands through minimumcost vehicle routes, beginning and finishing at the
depot. Each customer is to be serviced once by only one vehicle. In addition,
each vehicle has a limited capacity, and each customer has an associated time
window. This last restriction indicates that each customer provides a time
frame within which a particular service or task must be completed (for example,
loading or unloading a vehicle). A vehicle may arrive early, but it must wait
until the start of service time.
Regarding the practical relevance of VRP and
its NP-hardness [1], solving this problem and its variants are of great
interest for both the research community and logistics and transportation
companies. Therefore, heuristic algorithms have been proposed, mainly divided
into construction and local search heuristics [2,3]. In contrast to heuristics,
metaheuristics intend to escape from local optimum, as they explore a more
significant subset of the solution space [4,5,6]. In particular, in this work,
a trajectory-based metaheuristic known as Problem Aware Local Search (PALS) [7]
is used to solve the VRPTW. PALS performs a trajectory in the search space by
improving a single-solution using a specific local search. The PALS main
strength is to estimate variations on the fitness values, without having to
calculate the complete fitness function for each point in the neighborhood.
Therefore, a very inexpensive and systematic explorative search over the whole
neighborhood is efficiently carried out in each iteration. Then only the
candidate neighbors are stored, exploiting the promising search areas. After
this, PALS selects one of the candidates and this is applied to the solution.
This process continues until no more candidate neighbors are generated.
PALS was
designed for solving the DNA Fragment Assembly Problem. In [8], the authors
extended its application to other NP-hard optimization problems. The good
results found in [8] motivated the adaptation of PALS to the VRPTW problem. The
work’s contribution is centered around the adaptation of PALS to the features
exhibited for the VRPTW, as a permutation-based combinatorial optimization
problem. Consequently, the solution representation, the move operator, the
criteria to select a move, and more details are described in following
sections. Finally, a discussion of the research state is carried out.
2 Problem Formulation
The time dependent vehicle routing
problem with hard time windows studied in this research can be described as
follows [5]. Let a set of identical vehicles denoted by K and by a direct network G(N,A), where N is the set of nodes and A =
(i,j) : i ̸= j,i,j ∈ N is the set of arcs. Node 0 represents
the central depot, while N∗ =
{N/0} denotes the customers. Every
arc (i,j), which is a path from node i to node j, is characterized by the distance dij. The value tij
stands for the travel time from node i to node j and has the
same value with dij, as
the assumption that each distance unit corresponds to one specific time unit is
made. Each customer i is represented
by the demand qi, the
service time needed si and
the time window (ei,li),
where ei is the opening
time and li the closing
time. Customers must be served by exactly one vehicle that may arrive any time
within the time window. The arrival time is given by ti. Additionally, if the vehicle arrives before the
beginning of the time window (ei),
it must wait for wki time,
until service is possible, while no vehicle may arrive after the end of the
time interval (li).
The VRPTW
goal is to service all customers, minimizing the number of vehicles and the
total time or traveled distance while simultaneously ensuring that all the
constraints are satisfied. The mathematical model of the VRPTW, presented in
equations 1 to 9, uses 
as
decision variable that is equal to 1 if vehicle k drives from node i to
node j, and 0 otherwise.
3 PALS to solve VRPTW
The pseudo-code of PALS to solve VRPTW is shown
in Algorithm 1. A random initial permutation, s, is created in order to represent a solution. In each iteration,
the current permutation is the base to generate systematically all possible
movements by applying the move operator. For each movement, PALS computes ∆f as the difference between
the partial fitness evaluations, which are calculated before and after the move
operator application by means of the CalculateDelta
function. The set L is formed by the movements with ∆f ≤ 0 (called candidate
movements). The best candidate is selected from L and is applied to the current solution, starting the cycle again
until no possible changes. Furthermore, the PALS design points that are
specific aspects of the problem requiere to be adapted to the VRPTW problem,
such as solution representation, move operators, fitness function, and CalculateDelta function. We also redefine two algorithmic
design points as seeding strategy and criterion to select a movement from L.
Representation. The solution representation must be suitable
and relevant to the tackled optimization problem. We apply one widely used in
the literature that consists of a list of routes, where each one is a
permutation of integers that indicates a sequence of customers represented by a
unique integer ID. Conse-
Algorithm 1 PALS
to solve VRPTW
initialize s; {generate the initial solution}
repeat
L = ∅; for i = 0 to N do
for j = 0 to N do
∆f =
CalculateDelta(s,i,j); if ∆f
≤ 0 then
L = L∪ <i,j,∆f>;
{Add candidate movements to L} end if
end for
end for
if L <> ∅ then
<i,j,∆f> =
Extract(L); {Select a movement from
L}
ApplyMovement(s,i,j); {Modify the solution} end if
until no changes return s;
quently, a VRPTW solution encoded by a list of
permutations must satisfy the following conditions to be legal: all customers
must be present in the list, and no duplicate customers are allowed (Eqs. 4 to
7).
Move Operator. The move operator is an adaptation
of the Interchange operator for this solution representation, where the client i assigned to route k can interchange its visit turn with a client j belonging to the same route or another one.
Fitness function. Our definition takes into account
the second VRPTW objective function (Eq. 2) and customer time windows, (ei,li), applying
an adaptive penalization [9] wherever the vehicle arrives after the closing
time and repairing the solution when the maximum vehicle capacity (
) is exceeded.
CalculateDelta
function. This
function is directly related to the move operator and the fitness function. As
a result, we define CalculateDelta function by applying partially the
fitness function only on the modified routes.
Seeding Strategies. We propose an heuristic seeding strategy that
considers the
and the whole demand (Pi∈N
qi) to determine the minimum number of vehicles
(or routes), attending the first VRPTW objective and calculated as the Eq.10
presents. After that, the customers are randomly selected and inserted in a
route, which is chosen in uniform way.
Criteria to select movements from L. Our PALS version applies uniformly the original criterion that extracts the best candidate movement or the criterion that chooses a candidate in a random way [8]. In this way, we avoid the search stagnating in local optima.
4 Discussion
In this research phase, we conduct tests on the proposed PALS using a
benchmark widely used in the literature, as Solomon’s instances [3]. Fig. 1
shows the PALS behavior considering the variations of the fitness and objective
functions during the search. As both functions exhibit different value ranges,
we plot their evolution on the x-axis but with distinct scales on the left and
right y-axes; therefore, the fitness values are shown on the left, while the
objective ones are displayed on the right. In this sense, we observe a
significant reduction in fitness function for small, middle, and large
instances (with 25, 50, and 100 customers, respectively), but a much smaller
decrease in the objective function. Our future research step is to improve this
algorithm to find the optimal solutions and avoid search stagnation.
References
1. J. K. Lenstra and A. H. G. R. Kan, “Complexity of vehicle routing and scheduling problems,” Networks, vol. 11, pp. 221–227, 1981.
2. O. Br¨aysy and M. Gendreau, “Vehicle routing problem with time windows, part i: Route construction and local search algorithms,” Transportation Science, vol. 39, no. 1, pp. 104–118, 2005.
3.
M. M.
Solomon, “Algorithms for the vehicle routing and scheduling problems with time
window constraints,” Operations Research,
vol. 35, no. 2, pp. 254–265, 1987.
4.
T.-C.
Chiang and W.-H. Hsu, “A knowledge-based evolutionary algorithm for the
multiobjective vehicle routing problem with time windows,” Computers Operations Research, vol. 45, pp. 25–37, 2014.
5.
G. D.
Konstantakopoulos, S. P. Gayialis, E. P. Kechagias, G. A. Papadopoulos, and I.
P. Tatsiopoulos, “A multiobjective large neighborhood search metaheuristic for
the vehicle routing problem with time windows,” Algorithms, vol. 13, no. 10, 2020.
6. A. Dixit, A. Mishra, and A. Shukla, “Vehicle routing
problem with time windows using meta-heuristic algorithms: A survey,” in Harmony Search and Nature Inspired
Optimization Algorithms, N. Yadav, A. Yadav, J. C. Bansal, K. Deep, and J.
H. Kim, Eds. Singapore: Springer Singapore, 2019, pp. 539–546.
7. E. Alba and G. Luque, “A new local search algorithm
for the DNA fragment assembly problem,” in Evolutionary
Computation in Combinatorial Optimization, EvoCOP’07, ser. Lecture
Notes in Computer Science, vol. 4446. Valencia: Springer, 2007, pp. 1–12.
8.
G. F.
Minetti, G. Luque, and E. Alba, “The problem aware local search algorithm: an
efficient technique for permutation-based problems,” Soft computing, pp. 1–14, 2017.
9.
M.
Gendreau, A. Hertz, and G. Laporte, “A tabu search heuristic for the vehicle
routing problem,” Mgmt Sci, vol. 40,
pp. 1276–1290, 10 1994.