Waste collection distribution for easier routing

No Thumbnail Available
Journal Title
Journal ISSN
Volume Title
Perustieteiden korkeakoulu | Master's thesis
Ask about the availability of the thesis by sending email to the Aalto University Learning Centre oppimiskeskus@aalto.fi
Date
2016-06-13
Department
Major/Subject
Ohjelmistotekniikka
Mcode
T3001
Degree programme
Tietotekniikan koulutusohjelma
Language
en
Pages
59
Series
Abstract
Vehicle routing is a difficult and important problem in waste management. Creating routes with optimal drive-times for a fleet of vehicles is an NP-hard problem even in the simplest cases, and the real-world use-cases can include many kinds of additional constraints and objectives. This thesis proposes a method for transforming a periodic delivery vehicle routing problem into a set of simpler problems that do not include the periodicity constraint. The method is based on a clustering algorithm, which attempts to divide the collection points into clusters so that the collection weights and drive-times are distributed evenly among the clusters, while trying to keep them spatially non- overlapping and compact. Tabu search metaheuristic is used to prevent the search from getting stuck in a local optimum. The clusterer is used to divide the points into groups representing weekdays, and then those groups are further divided into groups for different weeks and days depending on their collection intervals. The test results indicate that the method can be used to create high quality routing solutions. While the result requires some manual fixes before creating the actual routes, the final routes compared favourably with the comparison data.

Autojen reititys on vaikea ja tärkeä ongelma jätehuollossa. Ajoajaltaan optimaalisten reittien luonti on helpoimmassakin tapauksessa NP-vaikea ongelma, mutta todellisissa käyttötapauksissa siihen liittyy usein vielä muitakin lisärajoituksia ja -tavoitteita. Tämän diplomityön tavoitteena oli kehittää menetelmä, joka muuntaa jaksollisen reititysongelman (periodic delivery vehicle routing problem) joukoksi muita, yksinkertaisempia ongelmia, jotka eivät sisällä jaksollisuutta. Menetelmä perustuu klusterointialgoritmiin, joka jakaa keräyspisteet ryhmiksi siten, että ajoaika ja kerättävä paino jakautuvat klustereille tasaisesti, mutta kuitenkin siten, että joukot ovat tiiviitä ja maantieteellisesti erossa toisistaan. Haun juuttuminen paikalliseen optimiin estetään käyttämällä tabuhaku-metaheuristiikkaa. Keräyspisteet klusteroidaan viikonpäiviä vastaaviksi ryhmiksi, jotka klusteroidaan edelleen vastaamaan eri viikoilla ja päivillä kerättäviä pisteitä perustuen pisteiden tyhjennysväleihin. Testitulokset osoittavat, että menetelmää voidaan käyttää korkealaatuisten reititysratkaisujen tuottamiseksi. Vaikka menetelmän tuottama tulos vaatiikin hieman käsin tehtäviä korjauksia ennen varsinaisten reittien luontia, lopulliset reitit olivat laadukkaita vertailureitteihin verrattuna.
Description
Supervisor
Soisalon-Soininen, Eljas
Thesis advisor
Wirpi, Olli
Keywords
vehicle routing problem, clustering, metaheuristics, waste collection
Other note
Citation