My seminary paper deals with renewing tourist paths over a certain area. The workers doing the renewing must obviously go through all the paths at least once, but they are limited by a certain distance per day (e.g. 10 km). Where they begin or end is not relevant, they can use the car to get to the start just as well.
I have a table of paths, specified by starting location, end location and the length. What model should I use to get the optimal solution, where the number of "mandays" is minimized, while all paths get renewed.
I tried Chinesse Postman, but it returns one big cycle, which is not exactly what I want.
Example:
Imagine a graph with 4 nodes A-D, with following paths: A-B 10, A-B 10, A-C 10, B-D 10, C-D 10, C-D 10. Yes, there are two paths between nodes A-B and C-D. The optimal solution is to renew each edge in one day, resulting in 6 days. But the Chinese problem returns a path of 70, because it must go through one of the edges twice (the graph has no Euler cycle - kind of like the seven bridges of Königsberg). So the solution would span 7 days, renewing one path twice.
