BookmarkSubscribeRSS Feed
🔒 This topic is solved and locked. Need further help from the community? Please sign in and ask a new question.
DanHouston
Obsidian | Level 7

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
RobPratt
SAS Super FREQ

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:

sascommunities021721.png

Is it OK to use fewer than 50 vehicles?  The solver allows you to specify lower and upper bounds for that, and I used the upper bound only.

View solution in original post

6 REPLIES 6
RobPratt
SAS Super FREQ

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:

SAS Help Center: VRP Statement

SAS Help Center: vrp Action

DanHouston
Obsidian | Level 7
Want a bigger dataset to try out?

Probably going to take us a bit to upgrade.
RobPratt
SAS Super FREQ

Yes, please.

DanHouston
Obsidian | Level 7

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.

RobPratt
SAS Super FREQ

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:

sascommunities021721.png

Is it OK to use fewer than 50 vehicles?  The solver allows you to specify lower and upper bounds for that, and I used the upper bound only.

DanHouston
Obsidian | Level 7

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.

sas-innovate-2024.png

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.

 

Register now!

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.

Discussion stats
  • 6 replies
  • 1168 views
  • 3 likes
  • 2 in conversation