Route optimization using arc routing for household waste collection

No Thumbnail Available

URL

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