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.