Waste collection distribution for easier routing

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.