Knowledge base: Warsaw University of Technology

Settings and your account

Back

Zastosowanie populacyjnych metaheurystyk uwzgledniajacych rozkład danych problemu do rozwiazywania problemu dynamicznej marszrutyzacji

Michał Okulewicz

Abstract

This thesis presents the possibility of using continuous metaheuristic algorithms for solving Dynamic Vehicle Routing Problem (DVRP). DVRP belongs to a group of transportation problems, which most famous representative is a Traveling Salesman Problem (TSP). The goal of the DVRP is to find an assignment of requests to vehicles, and a route for each of the vehicles, which minimize the total route length. Dynamic nature of the DVRP comes from the fact that some of the requests become known only during the optimization process. DVRP differs from the Stochastic Vehicle Routing Problem (SVRP), in which the approximate location and volume of the requests are known. Literature methods to solving DVRP process it as a sequence of dependent static Vehicle Routing Problem (VRP) instances. Although, continuous problem encoding has been utilized for the VRP, no such approach has been proposed for the DVRP. This thesis introduces such an algorithm, denoted ContDVRP, which by utilizing a continuous search space allows for a direct application of population based metaheuristics, like Particle Swarm Optimization (PSO) or Differential Evolution (DE). The initial encoding has been introduced independently from research on the VRP, while the final version integrates the author’s approach with the methods of Ai and Kachitvichyanukul. Effectiveness of the algorithm is tested on a set of 21 benchmark instances, converted from a static VRP instances by Kilby et al. and Montemanni et al. ContDVRP has obtained the largest number of significantly better average results than other algorithms presented in the literature. Best average result is achieved on two types of experiments: the one using a limit of fitness function evaluations, and the one using time limit to stop the optimization process. Besides experimental proof of abilities of continuous DVRP encoding its properties are thoroughly analyzed. The thesis presents ContDVRP as both the example of a dynamic optimization algorithm and a method of solving vehicle routing problems. Thesis experimentally proves that the choice of the encoding is a more crucial factor than the choice of the optimization algorithm in terms of achieving a certain solution quality on a given instance. This thesis extends knowledge about the features on the continuous encodings and their computation time to quality ratio. Additionally: (1) it introduces solving capacitated clustering problem as an alternative method to greedy construction of initial candidate solutions, (2) points out the most important optimization techniques in terms of results quality, (3) extends experimental knowledge on impact of parallel processing on computation time and quality of the achieved results. Final chapters of this thesis are dedicated to the analysis of the DVRP dynamics and its features which allowed for a success of the approach of solving DVRP as a sequence of static instances (without explicit accounting for the growth of the problem during the process). The thesis states, and experimentally proves, that it is possible to improve the quality of solution by estimating the expected sum of requests’ volume. The optimization process accounting for the expected growth of the number of requests shows a greater stability of the candidate solutions’ sequences. That stability has been measured by the number of requests reassignments and changes in the number of needed vehicles.
Record ID
WUT0182120d51af41b2bb7e45cb47ac9558
Diploma type
Doctor of Philosophy
Author
Title in Polish
Zastosowanie populacyjnych metaheurystyk uwzgledniajacych rozkład danych problemu do rozwiazywania problemu dynamicznej marszrutyzacji
Language
(pl) Polish
Certifying Unit
Faculty of Mathematics and Information Science (FMIS)
Discipline
information science / (technology domain) / (technological sciences)
Status
Finished
Title date
23-02-2017
Supervisor
External reviewers
Krzysztof Krawiec Krzysztof Krawiec,, Author's external affiliation: Politechnika Poznańska
Leszek Rutkowski Leszek Rutkowski,, Author's external affiliation: Politechnika Częstochowska
Honored
yes
Pages
142
Keywords in English
xxx
Abstract in English
This thesis presents the possibility of using continuous metaheuristic algorithms for solving Dynamic Vehicle Routing Problem (DVRP). DVRP belongs to a group of transportation problems, which most famous representative is a Traveling Salesman Problem (TSP). The goal of the DVRP is to find an assignment of requests to vehicles, and a route for each of the vehicles, which minimize the total route length. Dynamic nature of the DVRP comes from the fact that some of the requests become known only during the optimization process. DVRP differs from the Stochastic Vehicle Routing Problem (SVRP), in which the approximate location and volume of the requests are known. Literature methods to solving DVRP process it as a sequence of dependent static Vehicle Routing Problem (VRP) instances. Although, continuous problem encoding has been utilized for the VRP, no such approach has been proposed for the DVRP. This thesis introduces such an algorithm, denoted ContDVRP, which by utilizing a continuous search space allows for a direct application of population based metaheuristics, like Particle Swarm Optimization (PSO) or Differential Evolution (DE). The initial encoding has been introduced independently from research on the VRP, while the final version integrates the author’s approach with the methods of Ai and Kachitvichyanukul. Effectiveness of the algorithm is tested on a set of 21 benchmark instances, converted from a static VRP instances by Kilby et al. and Montemanni et al. ContDVRP has obtained the largest number of significantly better average results than other algorithms presented in the literature. Best average result is achieved on two types of experiments: the one using a limit of fitness function evaluations, and the one using time limit to stop the optimization process. Besides experimental proof of abilities of continuous DVRP encoding its properties are thoroughly analyzed. The thesis presents ContDVRP as both the example of a dynamic optimization algorithm and a method of solving vehicle routing problems. Thesis experimentally proves that the choice of the encoding is a more crucial factor than the choice of the optimization algorithm in terms of achieving a certain solution quality on a given instance. This thesis extends knowledge about the features on the continuous encodings and their computation time to quality ratio. Additionally: (1) it introduces solving capacitated clustering problem as an alternative method to greedy construction of initial candidate solutions, (2) points out the most important optimization techniques in terms of results quality, (3) extends experimental knowledge on impact of parallel processing on computation time and quality of the achieved results. Final chapters of this thesis are dedicated to the analysis of the DVRP dynamics and its features which allowed for a success of the approach of solving DVRP as a sequence of static instances (without explicit accounting for the growth of the problem during the process). The thesis states, and experimentally proves, that it is possible to improve the quality of solution by estimating the expected sum of requests’ volume. The optimization process accounting for the expected growth of the number of requests shows a greater stability of the candidate solutions’ sequences. That stability has been measured by the number of requests reassignments and changes in the number of needed vehicles.
Thesis file
  • File: 1
    Okulewicz.pdf
Request a WCAG compliant version

Uniform Resource Identifier
https://repo.pw.edu.pl/info/phd/WUT0182120d51af41b2bb7e45cb47ac9558/
URN
urn:pw-repo:WUT0182120d51af41b2bb7e45cb47ac9558

Confirmation
Are you sure?
Report incorrect data on this page
clipboard