A cyclic exchange neighborhood search algorithm and transformations for the Generalized Vehicle Routing Problem

 |  Login

Show simple item record

dc.contributor Aalto-yliopisto fi
dc.contributor Aalto University en
dc.contributor.advisor Bartolini, Enrico
dc.contributor.author Mattila, Markus
dc.date.accessioned 2018-06-01T11:34:04Z
dc.date.available 2018-06-01T11:34:04Z
dc.date.issued 2018-05-08
dc.identifier.uri https://aaltodoc.aalto.fi/handle/123456789/31543
dc.description.abstract Vehicle routing problems have numerous applications in fields such as transportation, supply logistics and network design. The optimal design of these routes fall in the category of NP-hard optimization problems, meaning that the computational complexity increases extremely fast with increasing problem size. The Generalized Vehicle Routing Problem (GVRP) is a general problem type that includes a broad variety of other problems as special cases. The main special feature of the GVRP is that the customers are grouped in clusters. For each cluster, only one customer is visited. In this thesis, we implement a heuristic algorithm to solve GVRP instances in reasonable time. Especially, we include a cyclic exchange method that considers a very large search neighborhood. In addition, we study the related Capacitated m-Ring-Star Problem (CmRSP). We present the Distance-Constrained Capacitated m-Ring-Star Problem (DCmRSP) and show that it contains the Multivehicle Covering Tour Problem (MCTP) as a special case. We show that DCmRSP instances can be transformed to (distance-constrained) GVRP with minor adaptations and solved with the same heuristic algorithm. Our algorithm is able to find best known solutions to all GVRP test instances; for two of them, our method shows strict improvement. The transformed CmRSP and MCTP instances are solved successfully by the same algorithm with adequate performance. en
dc.description.abstract Ajoneuvoreititysongelmilla on lukuisia sovelluksia muun muassa logistiikan ja verkostosuunnittelun aloilla. Tällaisten reittien optimaalinen ratkaiseminen kuuluu NP-vaikeiden optimointiongelmien kategoriaan, eli ratkaisuun vaadittava laskentateho kasvaa erittäin nopeasti ongelman koon suhteen. Yleistetty ajoneuvoreititysongelma (Generalized Vehicle Routing Problem, GVRP) on ongelmatyyppi, joka kattaa joukon muita reititysongelmia erikoistapauksina. GVRP:n selkein erityispiirre on asiakkaiden jako ryppäisiin: kussakin ryppäässä on käytävä tasan yhden asiakkaan luona. Tässä diplomityössä esitellään ja toteutetaan heuristinen algoritmi, joka etsii kohtalaisessa ajassa ratkaisuja GVRP-ongelmiin. Menetelmä sisältää kiertovaihtoalgoritmin, joka kykenee etsimään ratkaisuja hyvin laajasta ympäristöstä. Tutkimuksen kohteena on lisäksi m-rengastähtiongelma (Capacitated m-Ring-Star Problem, CmRSP). Esittelemme ongelman etäisyysrajoitetun version (DCmRSP), ja näytämme, että kyseiseen ongelmaan sisältyy usean ajoneuvon peittävän reitin ongelma (Multivehicle Covering Tour Problem). Näytämme, että DCmRSP-ongelman pystyy pienin muutoksin muuntamaan GVRP-ongelmaksi ja ratkaisemaan samalla heuristisella algoritmilla. Algoritmi löytää parhaat tunnetut ratkaisut kaikkiin GVRP-testitehtäviin. Kahdessa tapauksessa ratkaisu on parempi aiemmin löydettyihin nähden. Algoritmi kykenee ratkaisemaan muunnetut CmRSP- ja MCTP-testitehtävät kohtalaisella ratkaisulaadulla. fi
dc.format.extent 66
dc.format.mimetype application/pdf en
dc.language.iso en en
dc.title A cyclic exchange neighborhood search algorithm and transformations for the Generalized Vehicle Routing Problem en
dc.title Kiertovaihtoalgoritmi ja muunnoksia yleistetylle ajoneuvoreititysongelmalle fi
dc.type G2 Pro gradu, diplomityö fi
dc.contributor.school Perustieteiden korkeakoulu fi
dc.subject.keyword combinatorial optimization en
dc.subject.keyword vehicle routing en
dc.subject.keyword heuristic algorithm en
dc.subject.keyword cyclic exchange en
dc.identifier.urn URN:NBN:fi:aalto-201806012970
dc.programme.major Systems and Operations Research fi
dc.programme.mcode SCI3055 fi
dc.type.ontasot Master's thesis en
dc.type.ontasot Diplomityö fi
dc.contributor.supervisor Ehtamo, Harri
dc.programme Master’s Programme in Mathematics and Operations Research fi
local.aalto.electroniconly yes
local.aalto.openaccess yes


Files in this item

This item appears in the following Collection(s)

Show simple item record

Search archive


Advanced Search

article-iconSubmit a publication

Browse

My Account