topic Re: Road network optimization problem in Mathematical Optimization, Discrete-Event Simulation, and OR

Road network optimization problem

Ceciestunnomtemporaire — Tue, 08 Dec 2015 18:25:38 GMT

Greetings,

I would like to write an algorithm that would minimize the distance to travel a series of roads. In input, I have the longitude and latitude of the beginning and the end of each road. This problem looks like the Traveling Salesman Problem (https://en.wikipedia.org/wiki/Travelling_salesman_problem) or the Route inspection Problem (https://en.wikipedia.org/wiki/Route_inspection_problem).

However, I have to pass through each one of these roads and backtracking is inevitable (there are some dead-ends). I found the optnet procedure on SAS help, but I cannot resolve my problem, because the TSP hypothesis is to pass once per point and only undirected graphs are accepted.

I tried to use the beginning of each roads as points, but it is not working as intended. I would appreciate any help.

Thanks,

Marc-Antoine

Re: Road network optimization problem

RobPratt — Wed, 09 Dec 2015 15:00:32 GMT

Can you please share your data and code, or at least some sample data?

By the way, although your problem is not TSP, note that the TSP algorithm supports directed graphs in SAS/OR 14.1:

http://support.sas.com/documentation/cdl/en/ornoaug/68159/HTML/default/viewer.htm#ornoaug_whatsnew_sect005.htm

Re: Road network optimization problem

Ceciestunnomtemporaire — Wed, 09 Dec 2015 15:24:23 GMT

My data looks like this:

data have;
input road_id $ length longitude_begin latitude_begin longitude_end latitude_end class $15.;
cards ;
H1 5000 -70.1 45.2 -70.3 45.1 Highway
H2 5200 -70.3 45.1 -70.5 45.3 Highway
H3 4200 -70.5 45.3 -70.6 45.7 Highway
R1 1200 -71.4 45.0 -71.3 45.1 Contiguous
R2 1000 -71.3 45.1 -71.2 45.1 Contiguous
;
run;

Of course there are way more than that (average of 2000 roads ID per group). In this example, the roads H1, H2 and H3 are connected and can be used in 1 direction only. The roads R1 and R2 and connected and can be used in both directions.

Thanks for your time !

Re: Road network optimization problem

RobPratt — Wed, 09 Dec 2015 19:35:57 GMT

As described in Application 19.14 of Network Flows (Ahuja, Magnanti, Orlin), the directed version of the problem can be formulated as a minimum-cost network flow problem with 0 supply at each node and a lower bound of 1 unit of flow on each arc. You can use either PROC OPTNET...

http://support.sas.com/documentation/cdl/en/ornoaug/68159/HTML/default/viewer.htm#ornoaug_optnet_details23.htm

...or the network solver in PROC OPTMODEL:

http://support.sas.com/documentation/cdl/en/ormpug/68156/HTML/default/viewer.htm#ormpug_networksolver_details19.htm

Re: Road network optimization problem

Ceciestunnomtemporaire — Thu, 10 Dec 2015 13:11:41 GMT

I don't understand exactly how the problem is working. If the supply is at 0, does it mean there is no limit ? I am trying to write a simple example, but it does not compute...

Howerer, I thought of something else. I used the "Shortpath" statement in the Optnet procedure. It is giving me the shortest path between every pair of points I have in my data. I then use the number of nodes between each Source/sink as the weight for the TSP problem based on those paths. It's like creating fictive edges so that I can use each nodes more than once.

Right now, I am using SAS 9.3, so I cannot use the directed version of the problem, but the results are great. It covers a great part of the network. We might switch to 9.4 soon and I think that I would be able to solve the majority of my problem with this version.

Thanks !

Re: Road network optimization problem

RobPratt — Thu, 10 Dec 2015 16:30:18 GMT

Supply of 0 at a node just forces inflow to be equal to outflow at that node. There is no upper bound for the flow on each arc, but the minimization objective will drive it to be as small possible, according to the arc costs. If you post your simple example, I'll take a look. One thing you might have missed is that the two-way arcs should be replaced with two one-way arcs in the input data.

The undirected version of the problem is addressed in Application 19.15 of Network Flows. The solution approach does compute all-pairs shortest paths as the first step (as you mentioned), and this is also available in PROC OPTNET or PROC OPTMODEL. Note here that the shortest paths are with respect to the sum of arc distances, not the number of arcs. But the second step is a weighted matching problem on a complete graph consisting of the odd-degree nodes, where the new cost of edge (i,j) is the shortest path distance between i and j in the original graph. You can solve this problem by using the MILP solver in PROC OPTMODEL. There is a binary decision variable for each edge, and if the solver returns a value of 1 for edge (i,j), it means that all the arcs in the shortest path between i and j in the original network should be added. In fact, you can call the network solver and then the MILP solver in the same PROC OPTMODEL session.

Re: Road network optimization problem

Ceciestunnomtemporaire — Fri, 18 Dec 2015 19:38:15 GMT

Thanks, this is helping me a lot. Is is working for a great number of my groups.

Just to know, is there a way to know why is the problem infeasible ? I am dividing my groups by connected components, but the ones with greater number of nodes are not running and the problem is said infeasible, and I do not find why.

The first thing I could think is my network need more links between the set of nodes, but I already added "fake links" to each pair of nodes. If I could find a way to find the nodes I need to remove or the links I need to add to be able to have a feasible problem, that would be interesting.

Re: Road network optimization problem

RobPratt — Fri, 18 Dec 2015 21:41:29 GMT

For network problems, adding dummy nodes and arcs with high cost is the usual approach to diagnose infeasibility, as you have described. But since you are having trouble with that approach, you might consider using the IIS detection feature that diagnoses infeasibility for linear programming problems:

http://support.sas.com/documentation/cdl/en/ormpug/68156/HTML/default/viewer.htm#ormpug_lpsolver_details15.htm

This method requires an explicit LP formulation, and you can use the code in the following example, which solves a generic minimum-cost network flow problem:

http://support.sas.com/documentation/cdl/en/ormpug/68156/HTML/default/viewer.htm#ormpug_lpsolver_examples05.htm

You should replace the SOLVE statement with:

solve with LP / iis=on;

expand / iis;

Re: Road network optimization problem

Ceciestunnomtemporaire — Fri, 19 Feb 2016 19:02:32 GMT

Thanks for the tips, it helped me a lot.

However, for some groups, I am having an error and I can't find and solution on google. The error is:

ERROR: objValue:12356273 objValueLB:12356273

I think it may be an error of memory (the value is ~~the the~~ not the same every time). I tried some options, but the problem is still happening. Do you have an idea of where it might come from?

Thanks !

Re: Road network optimization problem

RobPratt — Fri, 19 Feb 2016 19:27:29 GMT

Can you please attach data and code for one of the groups that yields this error?

Re: Road network optimization problem

Ceciestunnomtemporaire — Fri, 19 Feb 2016 20:06:22 GMT

The example is joined (names have been changed) and the code I'm using is:

	proc optnet 
		graph_direction=directed

	   /*loglevel   = none*/
	   data_links = optimize;
/*	   out_nodes  = not_test_out2;*/
	   tsp out = Test_out2 cutstrategy=2 emphasis=1 HEURISTICS=3 CONFLICTSEARCH=2;
	run;

I've tried with and without the TSP options, but it's not different.

Re: Road network optimization problem

RobPratt — Sat, 20 Feb 2016 17:17:49 GMT

I am able to replicate this behavior, and it turns out to be a known issue in the TSP solver when the objective value is large. It will be fixed in the next release, but as a workaround you can scale the input weights by dividing by 1000. Doing so averted the issue for me.

Re: Road network optimization problem

Ceciestunnomtemporaire — Mon, 22 Feb 2016 16:34:28 GMT

Yes, it worked for me too and for my other groups I had problems.

Thank you for your time, it is really appreciated!