Route optimization using arc routing for household waste collection

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.