topic Re: Scaling up Vehicle Routing Problem in Mathematical Optimization, Discrete-Event Simulation, and OR

Scaling up Vehicle Routing Problem

DanHouston — Wed, 17 Feb 2021 17:32:55 GMT

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.

Re: Scaling up Vehicle Routing Problem

RobPratt — Wed, 17 Feb 2021 18:19:19 GMT

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

Re: Scaling up Vehicle Routing Problem

DanHouston — Wed, 17 Feb 2021 20:07:34 GMT

Want a bigger dataset to try out?

Probably going to take us a bit to upgrade.

Re: Scaling up Vehicle Routing Problem

RobPratt — Wed, 17 Feb 2021 20:48:25 GMT

Yes, please.

Re: Scaling up Vehicle Routing Problem

DanHouston — Thu, 18 Feb 2021 00:45:59 GMT

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.

Re: Scaling up Vehicle Routing Problem

RobPratt — Thu, 18 Feb 2021 22:44:38 GMT

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:

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.

Re: Scaling up Vehicle Routing Problem

DanHouston — Fri, 19 Feb 2021 02:31:31 GMT

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.