Arc Routing Problem (e.g. Chinese Postman)

[Jochen]

Hi,

Is it possible to use ortools for Arc Routing Problems, such as the Chinese Postman Problem? I.e. I want to visit a set of lines rather than points. Unfortunately, I couldn't find any examples (and I'm using Python, so I'm even more restricted)

If it was possible to make the algorithm visit points multiple times, the TSP problem could probably be modified, but I think that's not the case.

Thanks!

[Vincent Furnon]

If you consider the line graph of your original graph (https://en.wikipedia.org/wiki/Line_graph), solving the node routing problem on it is equivalent to solving the arc routing one on the original graph, and you can use OR Tools' routing library for that.

Note that there are many arc routing problem types for which a polynomial algorithm exists, so using the routing library for these cases won't be as efficient.

Vincent

--
You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Jana Koehler]

Hi Vincent,

I have a more specific question.  The CPP is NP-hard on mixed graphs with directed and undirected egdes, otherwise polynomial-time algorithms exist. The line graph you mention only seems to support undirected graphs and seems to reduce the CPP to the TSP problem. I was looking at the examples for TSP in the OR-Tools Routing library. All graphs seem to be undirected.

many thanks in advance for clarification

cheers

Jana

[blind.line]

I did something similar a while back with street sweeping. I converted the street map into its dual, so that each edge in the street map became a point to visit. I used PostGIS to do the graph conversion work as I recall. Then I used ORTools to build the per-vehicle street sweeping plans so that all streets are swept with a minimum total distance travelled. 

I have a link on my website: https://activimetrics.com/presentations/2020/pgconf/streetsweep/

James

On Aug 9, 2023, at 01:28, Jana Koehler <jana...@gmail.com> wrote:

Hi Vincent,

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/895bd084-3a3d-4e4d-afd8-d3943d799526n%40googlegroups.com.

[ramdhan wibawa]

Hi,

would you mind sharing the code? I have similar problem but I am stuck on how to convert graph into desired matrix for or tools.

thank you

[blind.line]

I think I just used the built in tools in PostGIS or pgrouting, plus some sql. Off topic for this list, plus not that hard. 

James

On Aug 19, 2023, at 06:08, ramdhan wibawa <ramdhana...@gmail.com> wrote:

Hi,

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/ad3ca514-510b-4755-8b49-ef9d92a4bb58n%40googlegroups.com.