Optimizing Vehicles

[Santha]

Hi

Request your support here. I am trying to base this link to do my model. I do not have Viya 4.0. What i want to achieve is slightly different. i have a bunch of nodes, one of them being a depot. I know which NodeID it is. I am trying to optimize routes for each vehicle. I have unlimited supply of vehicles. 

My objective function is optimize total distance travelled as is the case in the link above.

My constraints are:
(a) The total demand on a given vehicle cannot exceed 3,400 at any point of time in its journey.
(b) All vehicles should come back to depot.
(c) The total distance travelled by a vehicle cannot exceed 3,000 miles.

(d) No stop constraints. I set an arbitary 400 here.

Here is my attempt. I am getting infeasibility. I know something is not right in the way I have set up the constraints.

/*Variables*/
%let capacity = 3400;
%let num_vehicles=40;
%let dist=3000;
%let max_stops=400;
proc optmodel;
   set NODES;
   str ModelNode {NODES};
   num ModelLat {NODES};
   num ModelLong {NODES};
   num Volume {NODES};
   num capacity = &capacity;
   num num_vehicles = &num_vehicles;
   read data CASUSER.vrpdata into NODES =[NodeID] ModelNode ModelLat ModelLong Volume ;
   set ARCS = {i in NODES, j in NODES: i ne j};
   set VEHICLES = 1..num_vehicles;

num depot = 99999;
	
   /* define the arc dist as the rounded Euclidean distance */
   num dist {<i,j> in ARCS} = (if j ne depot then GEODIST(ModelLAt[i],ModelLong[i],ModelLat[j],ModelLong[j],'M') else 0);   
/* if j=depot, this means that we want to treat the last leg to depot as 0 so that the truck goes to depot as home base free */

    /* Creating an Sparse Matrix to remove any unwanted arcs*/
	set LOGICAL_ARCS = {<i,j> in ARCS: dist[i,j] <= &dist};
	/*print {<i,j> in LOGICAL_ARCS} dist; */

   /* Flow[k] is the amount of demand carried by vehicle k */
   var Flow {VEHICLES} >= 0 <= capacity;
   
/* UseNode[i,k] = 1, if and only if node i is serviced by vehicle k */
   var UseNode {NODES, VEHICLES} binary;
   /* UseArc[i,j,k] = 1, if and only if arc (i,j) is traversed by vehicle k */
   var UseArc {LOGICAL_ARCS, VEHICLES} binary;

  
   /*-----------------------OBJECTIVE FUNCTION-------------------------------*/
   /* minimize the total distance traversed */
   min TotalCost = sum {<i,j> in LOGICAL_ARCS, k in VEHICLES} dist[i,j] * UseArc[i,j,k];

  /*----------------------------CONSTRAINTS-------------------------------------*/
  /* each non-depot node must be serviced by at least one vehicle */
           /*ASSIGNMENT CONSTRAINT*/ 
   con Assignment {i in NODES diff {depot}}:
      sum {k in VEHICLES} UseNode[i,k] >= 1;


/*   for{k in VEHICLES} fix UseNode[depot,k] = 1; */
   con VisitDepot {i in NODES diff {depot}, k in VEHICLES}:
      UseNode[i,k] <= UseNode[depot,k]
   suffixes=(block=k);
/* if a vehicle visits a particular node, then it has to exit via the depot */

/*DISTANCE CONSTRAINT*/
	CON Distance {k in VEHICLES}: 
 sum {<i,j> in LOGICAL_ARCS} dist[i,j] * UseArc[i,j,k] <= &dist;

     	  /*STOPS CONSTRAINT*/
	CON Stops {k in VEHICLES}: 
    sum {i in NODES diff {depot}} UseNode[i,k] <= &max_stops; 

/*   some vehicle k traverses an arc that leaves node i if and only if UseNode[i,k] = 1 */
/* 			LEAVE NODE CONSTRAINT */
   con LeaveNode {i in NODES, k in VEHICLES}:
      sum {<(i),j> in LOGICAL_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 */
/* 			ENTER NODE CONSTRAINT   */
   con EnterNode {i in NODES, k in VEHICLES}:
      sum {<j,(i)> in LOGICAL_ARCS} UseArc[j,i,k] = UseNode[i,k];

  /* the amount of Volume supplied by vehicle k to node i must equal Volume if UseNode[i,k] = 1; otherwise, it must equal 0 */
			/*FLOW BALANCE CONSTRAINT*/ 
   con FlowBalance {k in VEHICLES}: 
       sum {i in NODES diff {depot}} Flow[k] 
       =  sum {i in NODES diff {depot}} Volume[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) */
			
/*VEHICLE CAPACITY CONSTRAINT*/ 
   con VehicleCapacity {k in VEHICLES}:
      sum {<i,j> in LOGICAL_ARCS } Flow[k] <= sum {<i,j> in LOGICAL_ARCS} Flow[k].ub * UseArc[i,j,k];

 /* decomp by vehicle *//*DECOMPOSITION*/
   for {i in NODES, k in VEHICLES} do;
      LeaveNode[i,k].block = k;
      EnterNode[i,k].block = k;
   end;
   for {k in VEHICLES} Distance[k].block = k;
   for {k in VEHICLES} Stops[k].block = k;
   for {i in NODES diff {depot}, k in VEHICLES} FlowBalance[k].block = k;
   for {k in VEHICLES} VehicleCapacity[k].block = k;


  /* solve using decomp (aggregate formulation) */
   solve with MILP / decomp varsel=ryanfoster presolver=basic relobjgap=0.01;
   /* OUTPUT */
   /* create solution data set */
 create data solution_data (where=(x1<>x2 and y1<>y2)) from [i j k]=
      {<i,j> in LOGICAL_ARCS, k in VEHICLES: UseArc[i,j,k].sol > 0.5}
      StartNode=ModelNode[i] StartCity=ModelNode[i] x1=ModelLat[i] y1=ModelLong[i] 
      EndNode=ModelNode[j] EndCity=ModelNode[j] x2=ModelLat[j] y2=ModelLong[j]
	  flow=Flow[i,j,k] dist=dist[i,j] 
      function='line' drawspace='datavalue';
quit;


proc sgplot data=solution_data noautolegend;
   scatter x=x1 y=y1 / datalabel=i;
   vector x=x2 y=y2 / xorigin=x1 yorigin=y1 group=k noarrowheads;
   xaxis display=none;
   yaxis display=none;
run;

[Santha]

When I increase my capacity to 34000 it does solve. I do not know yet if it is correct though. 

[RobPratt]

Please provide the input data.

[Santha]

Here is the data attached.

Thank you. 

[RobPratt]

Your problem is similar to the doc example, and you have correctly added the Distance and Stops constraints (SAS Viya 4 users can alternatively call a specialized solver for the vehicle routing problem with time windows).  But for correctness, you should also keep the Flow[i,j,k] variable and FlowBalance and VehicleCapacity constraints as they are in the doc example (but with ARCS replaced with LOGICAL_ARCS and demand[i] replaced with Volume[i]):

   var Flow {LOGICAL_ARCS, VEHICLES} >= 0 <= capacity;

   con FlowBalance {i in NODES diff {depot}, k in VEHICLES}:
       sum {<j,(i)> in LOGICAL_ARCS} Flow[j,i,k] - sum {<(i),j> in LOGICAL_ARCS} Flow[i,j,k]
       = Volume[i] * UseNode[i,k];

   con VehicleCapacity {<i,j> in LOGICAL_ARCS, k in VEHICLES}:
      Flow[i,j,k] <= Flow[i,j,k].ub * UseArc[i,j,k];

With these changes, even the LP relaxation of the problem is infeasible, and you can diagnose the infeasibility by using the IIS= option as follows:

   solve relaxint / iis=1;
   expand / iis;

On my machine, several variables and constraints that involve node 2140 appear in the resulting IIS.  Investigation of the input data reveals that nodes 2140, 340, 114, 925, and 2526 all have Volume > 3400 and so cannot be served by a vehicle with capacity = 3400.  If you either remove these nodes or increase the capacity to the largest Volume (4759.34806), the problem becomes infeasible.

Note also these log messages:

WARNING: Duplicate key <99999> was read at observation 32.
WARNING: Duplicate key <99999> was read at observation 33.
WARNING: Duplicate key <99999> was read at observation 34.
WARNING: Duplicate key <99999> was read at observation 35.
WARNING: Duplicate key <99999> was read at observation 36.
WARNING: Duplicate key <99999> was read at observation 37.
WARNING: Duplicate key <99999> was read at observation 38.
WARNING: Duplicate key <99999> was read at observation 39.
WARNING: Duplicate key <99999> was read at observation 40.
WARNING: Duplicate key <99999> was read at observation 41.
WARNING: Duplicate key <99999> was read at observation 42.

The reason for the warnings is that the NodeID column is used as the key in the READ DATA statement, but you have several observations with NodeID = 99999.

[Santha]

Rob - Thanks a lot for you support as always. Based on your suggestion, I have removed duplicates in my code. In addition to that, I have increased my vehicle capacity to 5000. That was fine and model solved just fine. I have three supporting questions.  Please find attached an excel file that has SASInput, SASOutput ,k=7Illustration and DesiredOutput of output. 

(a) For all vehicles except (k=8 and k=9), the model seems to be fine. I understand exactly how the model behaves and I have illustrated in the PPT as well. However, is it possible to get it in reverse, like a mirror image of it, as shown in "Desired output" tab in excel. I have illustrated this for k=7th vehicle.

(b) For k=8 and k=9 specifically though, there is something that I do not get. Example, k=8th vehicle, it goes from NodeID=99999 to 689 and 689 to 924 and then instead of 924, the model says it goes from 926 to 99999. Same pattern for k=9th vehicle. Am i missing something here? You can see these in red cells in "SAS Output" tab.  Does it mean, the model does not enforce that all vehicles has to end in Depot, even with our distance constraints and objective function?

(c) Ideally what I want to achieve is this: In the business context, these nodes are vendor locations who has some stuff to be sent. The vehicle picks up that vendor's load and the vehicle finally ends up in the Depot.  But about their starting point, it can start in a depot or at any other vendor point also but the ending point always has to be the depot.  Can you guide on how to tweak/set the model and the output for this?

[RobPratt · Accepted solution]

Regarding vehicles k=8 and k=9, the behavior you described is a result of the WHERE= clause in the CREATE DATA statement:

 create data solution_data (where=(x1<>x2 and y1<>y2)) from [i j k]=

Some of your nodes (like 924, 925, and 926) have identical coordinates, and the WHERE= clause omits any arcs between such pairs of co-located nodes.  Just remove the WHERE= clause, and you will see the expected arcs in the resulting output data set.

For the other question about decrementing flow instead of incrementing it, please start a new post.