Page 53 - Fister jr., Iztok, Andrej Brodnik, Matjaž Krnc and Iztok Fister (eds.). StuCoSReC. Proceedings of the 2019 6th Student Computer Science Research Conference. Koper: University of Primorska Press, 2019
P. 53
ving multi-depot vehicle routing problem
with particle swarm optimization
Matic Pintarič Sašo Karakatič
University of Maribor, Faculty University of Maribor, Faculty
of Electrical Engineering and of Electrical Engineering and
Computer Science Computer Science
Koroška cesta 46 Koroška cesta 46
Maribor, Slovenia Maribor, Slovenia
matic.pintaric@student.um.si saso.karakatic@um.si
ABSTRACT Yao et al. [18] proposed custom particle swarm optimization
algorithm for carton heterogeneous vehicle routing problem.
Multi-depot vehicle routing problem (MDVRP) is an optimization Kumar et al. [19] proposed a PSO for vehicle routing problem
problem with practical real-world applications in the commercial with time window constraint. More recently, Norouzi et al. [20]
transportation sector. It deals with the optimization of the time extended VRP with time window problem with additional fuel
and cost of the transportation of goods from and to customers consumption constraint and solved the problem also with PSO.
from numerous predefined serving depots. The multi-depot variant All these approaches treat routing problem as a discreet problem.
adds constraints of multiple serving depots and variable customer As we used optimization framework, which only works with
serving capacity and is a NP hard problem. In this paper, we continuous optimization problem, the approaches from the
present an application of Particle Swarm Optimization (PSO) for referenced papers could not be used and a transformation was
continuous optimization to MDVRP, where nature-inspired necessary.
optimization framework NiaPy is used. As MDVRP is a discreet
optimization problem, but NiaPy is suited to work only with The remaining of the paper is structured as follows. Second
continuous optimization problems, a transformation with the section presents and formulates MDVRP and PSO. Next section
repairing mechanism must be used. Our proposed approach is presents our proposed approach and its implementation with
presented in detail and is tested on several standard MDVRP NiaPy framework. Fourth section presents the results of the
benchmark sets to provide a sufficient evidence of usability of the experiment of the proposed approach on the standard benchmark
approach. sets. Last section discusses the results of the experiments and
finishes with the concluding remarks.
Keywords
2. SOLVING MDVRP
Multi-depot Vehicle Routing Problem, Continuous optimization,
Particle Swarm Optimization Logistic companies and other carriers, tasked with transporting or
picking up shipments, face with route optimization on a daily
1. INTRODUCTION level. The well-optimized route, taken by their fleets of vehicles,
means saving fuel and thus reducing overall daily cost. From this
Optimization is a daily problem we face with in an increasing we can see that similar scenarios are present in in everyday life
number of different logistics services, such as for example mail and present a problem worth solving well.
delivery, passenger transportation and other transportation of
goods [1], [2], [4]. Because solving such problems is - due to The described problem is called VRP and was first addressed by
restrictions on the route often quite difficult, we mostly rely on George Dantzig and John Ramser in 1959, as a solution to
computer intelligence. By this we mean different algorithms that optimize fuel delivery. It is a NP hard combinatorial optimization
have some heuristics rules, which result in good solutions. They problem, generalized from travelling salesman problem, so there
are classified as metaheuristic algorithms and often also referred is no polynomial time solution known to it [1], [3]. The result of
to as nature-inspired or evolutionary algorithms (EA) [6], [9]. the problem is the optimal set of routes for multiple vehicles,
transporting goods to or from customers, subject to restrictions
In order to execute the experiment of a comparison between along the routes. We also need to keep in mind that only one
different EA, we firstly developed a system that allows vehicle can visit specific customer at a time [1], [7].
application of any EA to the vehicle routing problem (VRP). Then
we tackled the VRP using five different evolutionary algorithms, Over time, different classifications of the problem have formed
which are genetic algorithm (GA), evolution strategy (ES), due to differences in constraints. The most common versions of
differential evolution (DE), particle swarm optimization (PSO) the problem are VRP with capacity constraints (CVRP), multi-
and harmony search (HS). Considering the obtained results, we depot VRP (MDVRP) and VRP with time windows constraints
decided to pay more attention to the PSO algorithm. (VRPTW). In addition, just about every problem classification
also has a certain distance limit of the individual vehicle [1], [4].
PSO is a popular algorithm for solving many complex
optimization problems, including routing problems. In 2008 We focused on solving MDVRP classification of the problem,
Mohemmed et al. [16] used PSO for simple routing problem with which is also less frequently referred to as multi-depot capacitated
custom priority-based encoding and heuristic operator to prevent vehicle routing problem (MDCVRP) [4]. The version of the
loops in the path construction. Next in 2009, Ai and problem, in addition to multiple customers, consists of multiple
Kachitvichyanukul [17] presented PSO with multiple social depots and thus more predefined vehicles - each vehicle can carry
structures to solve VRP with simultaneous pickup and delivery.
StuCoSReC Proceedings of the 2019 6th Student Computer Science Research Conference DOI: https://doi.org/10.26493/978-961-7055-82-5.53-56 53
Koper, Slovenia, 10 October
with particle swarm optimization
Matic Pintarič Sašo Karakatič
University of Maribor, Faculty University of Maribor, Faculty
of Electrical Engineering and of Electrical Engineering and
Computer Science Computer Science
Koroška cesta 46 Koroška cesta 46
Maribor, Slovenia Maribor, Slovenia
matic.pintaric@student.um.si saso.karakatic@um.si
ABSTRACT Yao et al. [18] proposed custom particle swarm optimization
algorithm for carton heterogeneous vehicle routing problem.
Multi-depot vehicle routing problem (MDVRP) is an optimization Kumar et al. [19] proposed a PSO for vehicle routing problem
problem with practical real-world applications in the commercial with time window constraint. More recently, Norouzi et al. [20]
transportation sector. It deals with the optimization of the time extended VRP with time window problem with additional fuel
and cost of the transportation of goods from and to customers consumption constraint and solved the problem also with PSO.
from numerous predefined serving depots. The multi-depot variant All these approaches treat routing problem as a discreet problem.
adds constraints of multiple serving depots and variable customer As we used optimization framework, which only works with
serving capacity and is a NP hard problem. In this paper, we continuous optimization problem, the approaches from the
present an application of Particle Swarm Optimization (PSO) for referenced papers could not be used and a transformation was
continuous optimization to MDVRP, where nature-inspired necessary.
optimization framework NiaPy is used. As MDVRP is a discreet
optimization problem, but NiaPy is suited to work only with The remaining of the paper is structured as follows. Second
continuous optimization problems, a transformation with the section presents and formulates MDVRP and PSO. Next section
repairing mechanism must be used. Our proposed approach is presents our proposed approach and its implementation with
presented in detail and is tested on several standard MDVRP NiaPy framework. Fourth section presents the results of the
benchmark sets to provide a sufficient evidence of usability of the experiment of the proposed approach on the standard benchmark
approach. sets. Last section discusses the results of the experiments and
finishes with the concluding remarks.
Keywords
2. SOLVING MDVRP
Multi-depot Vehicle Routing Problem, Continuous optimization,
Particle Swarm Optimization Logistic companies and other carriers, tasked with transporting or
picking up shipments, face with route optimization on a daily
1. INTRODUCTION level. The well-optimized route, taken by their fleets of vehicles,
means saving fuel and thus reducing overall daily cost. From this
Optimization is a daily problem we face with in an increasing we can see that similar scenarios are present in in everyday life
number of different logistics services, such as for example mail and present a problem worth solving well.
delivery, passenger transportation and other transportation of
goods [1], [2], [4]. Because solving such problems is - due to The described problem is called VRP and was first addressed by
restrictions on the route often quite difficult, we mostly rely on George Dantzig and John Ramser in 1959, as a solution to
computer intelligence. By this we mean different algorithms that optimize fuel delivery. It is a NP hard combinatorial optimization
have some heuristics rules, which result in good solutions. They problem, generalized from travelling salesman problem, so there
are classified as metaheuristic algorithms and often also referred is no polynomial time solution known to it [1], [3]. The result of
to as nature-inspired or evolutionary algorithms (EA) [6], [9]. the problem is the optimal set of routes for multiple vehicles,
transporting goods to or from customers, subject to restrictions
In order to execute the experiment of a comparison between along the routes. We also need to keep in mind that only one
different EA, we firstly developed a system that allows vehicle can visit specific customer at a time [1], [7].
application of any EA to the vehicle routing problem (VRP). Then
we tackled the VRP using five different evolutionary algorithms, Over time, different classifications of the problem have formed
which are genetic algorithm (GA), evolution strategy (ES), due to differences in constraints. The most common versions of
differential evolution (DE), particle swarm optimization (PSO) the problem are VRP with capacity constraints (CVRP), multi-
and harmony search (HS). Considering the obtained results, we depot VRP (MDVRP) and VRP with time windows constraints
decided to pay more attention to the PSO algorithm. (VRPTW). In addition, just about every problem classification
also has a certain distance limit of the individual vehicle [1], [4].
PSO is a popular algorithm for solving many complex
optimization problems, including routing problems. In 2008 We focused on solving MDVRP classification of the problem,
Mohemmed et al. [16] used PSO for simple routing problem with which is also less frequently referred to as multi-depot capacitated
custom priority-based encoding and heuristic operator to prevent vehicle routing problem (MDCVRP) [4]. The version of the
loops in the path construction. Next in 2009, Ai and problem, in addition to multiple customers, consists of multiple
Kachitvichyanukul [17] presented PSO with multiple social depots and thus more predefined vehicles - each vehicle can carry
structures to solve VRP with simultaneous pickup and delivery.
StuCoSReC Proceedings of the 2019 6th Student Computer Science Research Conference DOI: https://doi.org/10.26493/978-961-7055-82-5.53-56 53
Koper, Slovenia, 10 October
