Route optimization using arc routing for household waste collection

No Thumbnail Available
Journal Title
Journal ISSN
Volume Title
Insinööritieteiden korkeakoulu | Master's thesis
Ask about the availability of the thesis by sending email to the Aalto University Learning Centre oppimiskeskus@aalto.fi
Date
2015-12-14
Department
Major/Subject
Geoinformation Technology
Mcode
IA3002
Degree programme
Master’s Programme in Geoinformatics
Language
en
Pages
39+5
Series
Abstract
Arc routing is concerned with the traversal of edges of a graph network. This thesis discusses the directed Chinese postman problem (DCPP), a type of arc routing problem on a directed graph. The Chinese postman problem is concerned with a mailman that starts at the post office, traverses every street in his territory at least once and then returns to the post office. The objective being, while delivering mails, to walk as little as possible. Incidentally, the Chinese postman problem is the ‘edge’ equivalent of the traveling salesman problem. Unlike the traveling salesman problem however, the chinese postman problem on undirected graphs has polynomial running time algorithm; which makes it an appealing choice for some application domains. In some ways, the DCPP relates to the problem of household waste collection due to the fact that, waste bins are located along street edges and a collection truck essentially needs to traverse streets to get to the bins. A pseudopolynomial algorithm and its implementation is presented for demonstrating the solution to the DCPP.
Description
Supervisor
Virrantaus, Kirsi
Thesis advisor
Nikander, Jussi
Serkkola, Ari
Keywords
routing in household waste collection, Chinese postman problem, arc routing, garbage collection
Other note
Citation