Cable routing as VRP problem and avoidance of crossings

[Christos Galinos]

Hi everyone,

I am building a model similar to VRP with the intention to minimize the route of a cable that connects wind turbines (WTs) with each other (one or more strings). These strings then terminate to a common point which is the sub-station location.

I used the provided example and build a model where the shortest route can be found. I then added capacity constraints to limit the maximum number of WTs (nodes) that are connected to a string (i.e. route of one vehicle)

Now I want to avoid cable crossings (overlaps), in other words as a VRP problem to avoid crossings of routes. I have a difficulty to set these constraints as part of the problem. Do you have any suggestions on how to tackle this?

I am thinking that every time a node-node connection/route is made then somehow to calculate on the fly and penalize remaing nodes/routes that are going to cross the already established route. But I have a difficulty to put this as a piece of code. What do you think about this approach, any thoughts?

Thank you in advance for any feedback,
Christos

[christoph...@gmail.com]

Just curious about your problem: It seems that a "Y" configuration with two lines going into a wind turbine and one coming out towards the station shouldn't be possible, is this correct?

[Priidik Vilumaa]

Hi, 

aren't such problems typically formulated and solved by minimum spanning trees? I don't see why you would want to have a full circuit like a VRP tour.

Best,

Priidik

[Christos Galinos]

Hi Priidik,

Thanks for your feedback. Essentially you can formulate the cable routing problem to be an equivalent VRP problem.

1) Depending on the 'electrical' requirements you can have a 'full circuit' (i.e. closed loop) requirement for back up purposes in case of a failure of an individual WT.
2) On the other hand as you mentioned you can opt for 'open loops' (i.e. the last WT's cable will not terminated anywhere further). This can be easily formulated in a VRP approach by setting in the distance matrix the depot ('substation') column to zeros. (i.e. every distance from a WT back to substation to zero).

Then the question remains, in such a case how to avoid route crossings (cable overlaps)

[Laurent Perron]

The routing library has no notion of crossing.

The only approach I would use would be CP-SAT with a planar graph when crossing would be natural.

You can also try to generate paths, and pre-compute incompatibilities when 2 paths cross.

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00

--
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.
To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/dbe25aac-10d4-437a-851f-0a0c9ec5cb91n%40googlegroups.com.

[Christos Galinos]

Hi,

"Y" configuration  (i.e. branches) is another solution that is also used in some cases but usually it's not the prefered one. See attached sketch with the 3 different approaches.

Best regards,
Christos

On Friday, March 1, 2024 at 12:18:06 PM UTC+2 christoph...@gmail.com wrote:

[A S]

Hi Priidik, 

Let's assume you want to solve this simple example 

• You want to connect each pair of similar colors with a separate wire 
• The every two adjacent cells can be connected to each other (horizontally, vertically or diagonally) 
• A wire is not allowed to cross any other wire  
• The wire is not allowed to pass the white cells 

If we use CP-SAT model and addCircuit the we can solve it 

 

The solution will be 

To obtain the optimal solution the blue and orange wire will cross each other. 

To avoid it, as Laurent suggested you can add a list of banned crossing 

you should find a list of banned paths 

(1,16,wire1) + (15,2,wire2) <= 1 

This will avoid crossing 

The solution will be 

The code is available here on Github 

https://github.com/OptimizationExpert/Pyomo/blob/main/VRP_Circuit_CP_Wiring_nocross.ipynb 

Alireza Soroudi

--

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.

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/bd62baef-b86c-4572-9ca3-a5203da2863fn%40googlegroups.com.

[Laurent Perron]

Wow

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/CAM3LguK3dsAx_m%3DVMuwVvSidH8roRW31rvZzWqvjg_w3pUsyFQ%40mail.gmail.com.

[Christos Galinos]

@Laurent  Perron, thank you for your feedback.

@Alireza thanks a lot for your feedback and your practical example with the code. That's indeed what I am looking for to tackle the optimum cable route and avoid crossings problem.
I would like to make the inputs more general and allow the solver to find the optimum routes that connect more than 2 points. i.e. to define the maximum number of cars (cables) and their capacity (e.g. connect up to 3 locations/WTs per cable) and then also more general the dropping locations (WTs). So no need to specify which WTs are connected together. Just let the solver to find the optimum connections.

I am trying to modify your code gradually and:

1)  Define a common starting point of all routes/cables, say location 22, where the location of depot is (i.e. substation)
 2) Specify all the WT-locations in one variable e.g. the ones you define in your example 72, 139, 89, 152, 46, 96. These doesn't matter how are going to be connected as soon as they respect the constraints. 

When I try this:
st_fn = {0:(22,139) ,1:(22,152) , 2:(22,96)} # start/end connection points, where all the 3 routes have a common starting point-(depot/substation), I got no solution ("INFEASIBLE"). Do you have any suggestions on modifications of your code?

Thank you in advance,
Christos