Routing snow shovels and gritters in Eindhoven

Routing snow shovels and gritters in Eindhoven

Given a simple graph with a length or cost function on the edges, the Chinese Postman problem asks for a minum cost set of edges that should be doubled to obtain a Eulerian multigraph. The set of edges that is doubled corresponds to a set of streets of minimum total length that a postman should traverse twice if he needs to traverse all the streets in a certain town or quarter (where the graph corresponds to the town's street plan). If the given graph is Eulerian, there is no need to double any edges, and any Eulerian tour of the graph is an optimum route for the postman. In a practical application (think not only of delivering mail, but also of routing snow shovels or garbage trucks), the graph is not likely to be Eulerian, and the challenge is to compute an optimal route for the postman (shovel, garbage truck) by different methods. For directed and undirected graphs, the Chinese Postman problem is well-solved.

wikipedia on the Chinese postman, or Route inspection problem

However, in practical applications, the graph is usually mixed: some edges are directed (one-way streets), and others are not. Moreover, in practical applications there is not just one vehicle that should be routed to cover all the streets at least once, but a fleet of vehicles is available that should together cover all streets. Finally, in practical applications, many more conditions may apply. For gritters, one important condition is that the gritter should go straight on every crossing that it has not traversed before.

Goals of this bachelor final project:

*Collect data relevant for routing snow shovels and/or gritters in the Eindhoven area. That is, construct at least one practical instance for a variant of the Chinese postman problem, that involves a fleet of several vehicles, and that takes the most important additional conditions on the routing into account.

* Study literature on algorithms for the Chinese Postman problem in mixed graphs, and solution methods for possible variants (involving multiple vehicles) relevant for the Eindhoven application. Distinguish variants that can be solved in polynomial time, and variants that are NP-complete.

* Construct mathematical (programming) models for the practical instance(s), and solve them using suitable software.

* Report back to the Eindhoven municipality on possible consequences for routing snow shovels and/or gritters in Eindhoven.