# What model should I use?

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.

-
This question does not appear to be on topic for this site. I have asked the math moderators whether they would be interested. In the meantime, please edit your text to make it clear what your question is! – whuber Nov 21 '12 at 22:55
This might be a Computer Science question, but it looks like it's missing a first paragraph to explain what you're trying to achieve: you jumped directly into your failed solution, and I don't understand what you were trying to solve. – Gilles Nov 21 '12 at 22:59
I suspect there are more constraints than you have specified here, because there appears to be nothing in the current statement of the problem that would prohibit the answer from being the ceiling of the total path length divided by $10$: that's how many man-days it would take to renew that much path at the rate of $10$ km per day. Providing a small concrete example of the problem along with its desired solution might clarify what you're looking for. – whuber Nov 23 '12 at 15:54
@whuber I added an example. – Vera Jindrova Nov 26 '12 at 21:07