Comparison of solution methods for the dynamic pickup and delivery problem with time windows
Loading...
URL
Journal Title
Journal ISSN
Volume Title
Perustieteiden korkeakoulu |
Master's thesis
Unless otherwise stated, all rights belong to the author. You may download, display and print this publication for Your own personal use. Commercial use is prohibited.
Authors
Date
2021-12-14
Department
Major/Subject
Systeemitiede ja operaatiotutkimus
Mcode
SCI3055
Degree programme
Master’s Programme in Mathematics and Operations Research
Language
en
Pages
51 + 7
Series
Abstract
The Vehicle Routing Problem (VRP) is classical problem of combinatorial optimization, in which a fleet of vehicles and a set of locations are given, and the problem is to route the vehicles to visit the locations at minimum cost. Its dynamic counterpart (DVRP) and its variants have received an amount of research during the past decades, owing to the advancement of information and communication technologies which have aided the process of vehicle routing. In a dynamic VRP, the information related to solving the problem is revealed over time, in contrast to the static VRP, where all information needed to solve the problem fully is known beforehand. In this work a variant of the DVRP called the Dynamic Pickup and Delivery Problem with Time Windows (DPDPTW) is studied, and in particular, how different solution methods perform in solving instances of it. These methods consist of five different metaheuristics and four different first solution strategies. Metaheuristics are the most used solution methods in the literature of VRPs, and they can be described as high-level strategies that guide lower level heuristics to obtain better solutions. First solution strategies are simple methods which provide feasible initial solutions to the VRPs for the metaheuristics to start their search from. The main results obtained were that the metaheuristic Guided Local Search (GLS) outperforms other methods in most scenarios, and that the choice of first solution strategy has a large impact on the final solution quality but depends on the problem parameters. Path Most Constrained Arc (PMCA) is the most reliable first solution strategy out of the ones compared. While the applicability of the results is somewhat limited, they are generally supported by the literature and are useful within their context.Ajoneuvon reititysongelma (Vehicle Routing Problem, VRP) on klassinen kombinatorisen optimoinnin ongelma, jossa joukko ajoneuvoja ja joukko sijainteja on annettu, ja ajoneuvoille tulee määrittää reitit siten että jokaisessa pisteessä käydään vain kerran ja että reittien kokonaiskustannukset minimoidaan. Vastaavaa dynaamista ongelmaa (DVRP) on tutkittu kasvavissa määrin viime vuosikymmenten aikana muun muassa kehittyvän teknologian ansiosta. Dynaamisessa ongelmassa ratkaisemiseen liittyvää informaatiota saadaan ajan myötä, toisin kuin staattisessa ongelmassa, jossa kaikki informaatio on saatavilla etukäteen. Tässä työssä tutkitaan dynaamista lähettiongelmaa aikaikkunoilla, joka on eräs ajoreititysongelman variantti. Erityisesti tavoitteena on selvittää miten eri ratkaisumenetelmät — jotka koostuvat viidestä metaheuristiikasta ja neljästä konstruktiivisesta heuristiikasta — sopivat ongelman ratkaisemiseen. Metaheuristiikat ovat yleisin ratkaisumenetelmätyyppi ajoreititysongelmissa, ja niitä voidaan luonnehtia korkean tason strategioiksi, jotka ohjaavat matalamman tason heuristiikoita saavuttaakseen paremman laatuisia ratkaisuja. Konstruktiiviset heuristiikat ovat yksinkertaisia menetelmiä, jotka etsivät käypiä lähtöratkaisuja metaheuristiikoille. Keskeisimmät johtopäätökset ovat, että metaheuristiikka Guided Local Search (GLS) suoriutuu muita paremmin useimmissa olosuhteissa, ja että konstruktiivisen heuristiikan valinta vaikuttaa vahvasti lopullisen ratkaisun laatuun. Path Most Constrained Arc (PMCA) on valituista konstruktiivisista heuristiikoista luotettavin. Olosuhteet, joissa näitä tuloksia voi sellaisenaan soveltaa, ovat jokseenkin rajoittuneet, mutta näissä olosuhteissa ne ovat hyödyllisiä.Description
Supervisor
Punkka, AnttiThesis advisor
Lampinen, HeliKeywords
ajoreititysongelma, metaheuristiikka, konstruktiivinen heuristiikka, simulaatio