Optimizing vehicles to depot

[Santha]

Hi Rob

Starting a new topic for the last question to close this discussion. This is based off this thread. What I want to do is increment as opposed to decrement. I have enclosed an excel file that the illustration and desired output.  Rephrasing from the old thread is below.

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]

Here's how to increment the flow instead of decrementing:

   /* the amount of supply picked up by vehicle k at node i must equal Volume[i]
      if UseNode[i,k] = 1; otherwise, it must equal 0 */
   con FlowBalance {i in NODES diff {depot}, k in VEHICLES}:
       sum {<(i),j> in LOGICAL_ARCS} Flow[i,j,k] - sum {<j,(i)> in LOGICAL_ARCS} Flow[j,i,k]
       = Volume[i] * UseNode[i,k];

   /* each vehicle is empty when it leaves the depot */
   for {<(depot),j> in LOGICAL_ARCS, k in VEHICLES} fix Flow[depot,j,k] = 0;

Here's how to start at any node and always end at the depot, by imposing cost 0 out of the depot:

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

[Santha]

Rob

Thank you. This is great. I was thinking the idea of chaning i and j nodes but was not quite comfortable doing it.  I ran the model with ur changes and it worked perfect. Thanks for your support. One thing tha I did observe that all vehicles always start at Depot even after the dist to impose 0 out of depot.

num dist {<i,j> in ARCS} = (if i ne depot then GEODIST(ModelLat[i],ModelLong[i],ModelLat[j],ModelLong[j],'M') else 0);   

So, i tried to see if the current depot at California is causing it because it is closer to many nodes. To prove this, I tried to change the Depot lat and longitude to Chicago that is far from many nodes, ofcourse i increased my distance limit to 10000 for Chicago for the model to be feasible. Model solved fine.  Still , all vehicles always start at Depot and end at Depot. So the location of the Depot is not a factor for the model to always start from Depot.  Ouptut Attached just inc ase.

When I printed the dist all the distances from Depot 99999 to all nodes is 0 and so it is naturally favouring vehicles to start from Node?  So I tried to change the dist to the old way like below but still the model always starts all vehicles with Depot.

 num dist {<i,j> in ARCS} = (if j ne depot then GEODIST(ModelLat[i],ModelLong[i],ModelLat[j],ModelLong[j],'M') else 0);

Not sure why. It is okay but just for my curiosity i want to understand why it does it.

[RobPratt]

The optimization model requires vehicles to start and end at the depot. To solve your problem variant where the vehicles can start anywhere but must end at the depot, it suffices to change the arc costs to 0 for all arcs out of the depot. In the resulting optimal solution, you can then drop those dummy arcs out of the depot. This is a known optimization modeling trick to convert your problem to a standard form just by changing the data.

[Santha]

Rob

This line below is where the distance from depot j to all i is made 0. distance is the only cost in the model.

num dist {<i,j> in ARCS} = (if i ne depot then GEODIST(ModelLat[i],ModelLong[i],ModelLat[j],ModelLong[j],'M') else 0);

This would mean that all vehicles start from Depot because it is the least distance (zero distance) to any node. But what I need is vehicles do not have to necessarily start from Depot always. I think I am missing something. If the VRO requires vehicle shd start and end at the depot, then I am fine with it . But the trick that you mentioned to cater to my problem variant, I just tried the dist thing above and I still get the same answer of starting from depot. I think I am not understanding fully. Can you pls clarify

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 i ne depot then GEODIST(ModelLat[i],ModelLong[i],ModelLat[j],ModelLong[j],'M') else 0);
 
    /* 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 {LOGICAL_ARCS, 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);

	  /*DISTANCE CONSTRAINT*/
	CON Distance {k in VEHICLES}: 
/* 	SUM {<i,j> in LOGICAL_ARCS: j not in {depot}} (dist[i, j] * UseArc[i, j, k]) <= &dist_limit; */
    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 {i in NODES diff {depot}, k in VEHICLES}:
       sum {<(i),j> in LOGICAL_ARCS} Flow[i,j,k] - sum {<j,(i)> in LOGICAL_ARCS} Flow[j,i,k]
       = Volume[i] * UseNode[i,k];

/* each vehicle is empty when it leaves the depot */
   for {<(depot),j> in LOGICAL_ARCS, k in VEHICLES} fix Flow[depot,j,k] = 0;

/* 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 {<i,j> in LOGICAL_ARCS, k in VEHICLES}:
      Flow[i,j,k] <= Flow[i,j,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[i,k].block = k;
   for {<i,j> in LOGICAL_ARCS, k in VEHICLES} VehicleCapacity[i,j,k].block = k;

  /* solve using decomp (aggregate formulation) */
   
solve with MILP / decomp varsel=ryanfoster presolver=basic relobjgap=0.01;  

[RobPratt]

In the optimization model, vehicles start and end at the depot.  But in the implementation of the resulting optimal solution, the vehicles do not actually leave the depot (that is, do not actually traverse the zero-distance dummy arcs out of the depot).  You can just omit those arcs from the output data set by specifying "i ne depot" as follows, yielding for each vehicle a path that starts at a customer node and ends at the depot:

   create data solution_data from [i j k]=
      {<i,j> in LOGICAL_ARCS, k in VEHICLES: UseArc[i,j,k].sol > 0.5 and i ne depot}
      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';

For a similar problem transformation regarding the traveling salesman problem, see the "A BETTER LOWER BOUND FROM TSP" section in my SAS Global Forum 2014 paper The Traveling Baseball Fan Problem and the OPTMODEL Procedure.

[Santha]

Rob

Cannot thanks a lot for your clarity and patience. Now I completely understand. You are the best.

Thanks