Turn on suggestions

Auto-suggest helps you quickly narrow down your search results by suggesting possible matches as you type.

Showing results for

Options

- RSS Feed
- Mark Topic as New
- Mark Topic as Read
- Float this Topic for Current User
- Bookmark
- Subscribe
- Mute
- Printer Friendly Page

🔒 This topic is **solved** and **locked**.
Need further help from the community? Please
sign in and ask a **new** question.

- Mark as New
- Bookmark
- Subscribe
- Mute
- RSS Feed
- Permalink
- Report Inappropriate Content

Posted 02-17-2021 12:32 PM
(1161 views)

I have an optimization model that assigns facilities to a distribution center and now I want to begin routing vehicles to serve those assigned facilities. I've worked through the vehicle routing problem, and even adapted it to work with my data. The problem I am having is it seems to work fine for less than 50 nodes and 10 trucks. I need to do something more like 300 nodes and up to 100 trucks.

The code I have right now is:

proc cas; loadactionset "optimization"; source pgm; /* Read in DDU Data */ set <str> NODES; num ddu_longitude {NODES}; num ddu_latitude {NODES}; num demand {NODES}; read data RDC1_NODES into NODES=[name] ddu_latitude ddu_longitude demand; num num_vehicles = &num_vehicles; num capacity = &capacity; set ARCS={i in NODES, j in NODES: i ne j}; set VEHICLES = 1..&num_vehicles; str depot= 'DDU649'; /* The cost is the geodist between each node */ num cost {<i,j> in ARCS} init geodist(ddu_latitude[i],ddu_longitude[i],ddu_latitude[j],ddu_longitude[j],'M'); var Flow {ARCS,VEHICLES} >= 0 <= capacity; var UseNode {NODES,VEHICLES} binary; var useArc {ARCS, VEHICLES} binary; /* each non-depot node must be serviced by at least one vehicle */ con Assignment {i in NODES diff {depot}}: sum {k in VEHICLES} UseNode[i, k] >=1; /* each vehicle must start at the depot node */ for{k in VEHICLES} fix UseNode[depot, k]=1; /* some vehicle k traverses an arc that leaves node i if and only if UseNode[i,k] = 1 */ con LeaveNode {i in NODES, k in VEHICLES}: sum {<(i), j> in ARCS} UseArc[i, j, k]=UseNode[i, k]; /* some vehicle k traverses an arc that enters node i if and only if UseNode[i,k] = 1 */ con EnterNode {i in NODES, k in VEHICLES}: sum {<j, (i)> in ARCS} UseArc[j, i, k]=UseNode[i, k]; /* the amount of demand supplied by vehicle k to node i must equal demand if UseNode[i,k] = 1; otherwise, it must equal 0 */ con FlowBalance {i in NODES diff {depot}, k in VEHICLES}: sum {<j, (i)> in ARCS} Flow[j, i, k] - sum {<(i), j> in ARCS} Flow[i, j, k]=demand[i] * UseNode[i, k]; /* if UseArc[i,j,k] = 1, then the flow on arc (i,j) must be at most capacity if UseArc[i,j,k] = 0, then no flow is allowed on arc (i,j) */ con VehicleCapacity {<i, j> in ARCS, k in VEHICLES}: Flow[i, j, k] <=Flow[i, j, k].ub * UseArc[i, j, k]; /* decomp by vehicle */ for {i in NODES, k in VEHICLES} do; LeaveNode[i, k].block=k; EnterNode[i, k].block=k; end; for {i in NODES diff {depot}, k in VEHICLES} FlowBalance[i, k].block=k; for {<i, j> in ARCS, k in VEHICLES} VehicleCapacity[i, j, k].block=k; /* minimize the total distance traversed */ min TotalCost = sum {<i,j> in ARCS, k in VEHICLES} cost[i,j] * UseArc[i,j,k]; save mps rdc_tsp; endsource; optimization.runOptmodel/code=pgm; run; quit; proc optmilp data=mycas.rdc_tsp primalout=mycas.rdc_tsp_sol dualout=mycas.rdc_tsp_dual maxtime=3600 ; decomp logfreq=1; run;

Any ideas would be greatly appreciated.

1 ACCEPTED SOLUTION

Accepted Solutions

- Mark as New
- Bookmark
- Subscribe
- Mute
- RSS Feed
- Permalink
- Report Inappropriate Content

Thank you for sending the larger data with 618 nodes and 50 vehicles. The VRP solver quickly (in 12 seconds) found a solution that uses 38 vehicles and has objective value 7984.2935718:

NOTE: The number of nodes in the input graph is 618. NOTE: The number of links in the input graph is 190653. NOTE: The network solver is called. NOTE: Processing the vehicle routing problem using 1 threads across 1 machines. NOTE: The initial VRP heuristics found a solution with cost 7984.2935718 using 11.93 (cpu: 11.50) seconds.

The solver then spent a long time trying to prove optimality. In computational experiments with smaller instances, the heuristic solutions are usually within 1% of optimal. Here is the resulting plot:

6 REPLIES 6

- Mark as New
- Bookmark
- Subscribe
- Mute
- RSS Feed
- Permalink
- Report Inappropriate Content

I can now share the news I hinted at yesterday. As of today's release (2020.1.3), the network solver in OPTMODEL has a VRP option that invokes a specialized algorithm to solve the vehicle routing problem:

SAS Help Center: SOLVE WITH NETWORK Statement

The same example with 22 nodes now solves in less than one second:

SAS Help Center: Vehicle Routing Problem (CVRPLIB)

The same VRP algorithm is available in PROC OPTNETWORK and the optNetwork action set as of the 2020.1.1 release:

- Mark as New
- Bookmark
- Subscribe
- Mute
- RSS Feed
- Permalink
- Report Inappropriate Content

Want a bigger dataset to try out?

Probably going to take us a bit to upgrade.

Probably going to take us a bit to upgrade.

- Mark as New
- Bookmark
- Subscribe
- Mute
- RSS Feed
- Permalink
- Report Inappropriate Content

Yes, please.

- Mark as New
- Bookmark
- Subscribe
- Mute
- RSS Feed
- Permalink
- Report Inappropriate Content

Attached is a ZIP file with a CSV and the CODE I am currently running (does not finish, just sits and spins).

RDC1 is the depot and DDU* are the locations to deliver to.

- Mark as New
- Bookmark
- Subscribe
- Mute
- RSS Feed
- Permalink
- Report Inappropriate Content

Thank you for sending the larger data with 618 nodes and 50 vehicles. The VRP solver quickly (in 12 seconds) found a solution that uses 38 vehicles and has objective value 7984.2935718:

NOTE: The number of nodes in the input graph is 618. NOTE: The number of links in the input graph is 190653. NOTE: The network solver is called. NOTE: Processing the vehicle routing problem using 1 threads across 1 machines. NOTE: The initial VRP heuristics found a solution with cost 7984.2935718 using 11.93 (cpu: 11.50) seconds.

The solver then spent a long time trying to prove optimality. In computational experiments with smaller instances, the heuristic solutions are usually within 1% of optimal. Here is the resulting plot:

- Mark as New
- Bookmark
- Subscribe
- Mute
- RSS Feed
- Permalink
- Report Inappropriate Content

WOW!

In this case using less is fine, in the actual case as I continue to build out there will be some time constraints and that may actually drive truck count upwards.

Thanks so much for testing it.....now to figure out the upgrade path to get to this enhancement.

**Don't miss out on SAS Innovate - Register now for the FREE Livestream!**

Can't make it to Vegas? No problem! Watch our general sessions LIVE or on-demand starting April 17th. Hear from SAS execs, best-selling author Adam Grant, Hot Ones host Sean Evans, top tech journalist Kara Swisher, AI expert Cassie Kozyrkov, and the mind-blowing dance crew iLuminate! Plus, get access to over 20 breakout sessions.

Multiple Linear Regression in SAS

Learn how to run multiple linear regression models with and without interactions, presented by SAS user Alex Chaplin.

Find more tutorials on the SAS Users YouTube channel.