How to use JSprit to solve VRP whose shipment has some available deliver locations?

Masa-74 · January 12, 2016, 5:50pm

Hi JSprit team,

I have been trying to solve VRP problem with JSprit.
Here’s the problem,

There’s finite number of trucks to pick up garbage from each bins in a city and deliver to a landfill.
All truck start from the same place(depot) and come back the same place in the end.
There are some types of garbage and each trucks can pick up any of them, but can’t deliver different types in the same time.
There are some landfills where each type of garbage can be delivered.
e.g. “Type A” can be delivered Landfill1 or Landfill2 or Landfill3, and truck driver can choose clothest landfill from them.

I try to solve it by the way below but the result became wrong.

Implement Shipment which pickup location is bin and deliver location is landfill.
To keep truck from carrying different waste type, create HardActivityConstraint([Constraint1] in MyConstraint.java)
Create shipments as many as its possible landfills number in each bins. (e.g. In above “Type A” case, create 3 shipment in each bins. If there is bin1 whose waste type is “Type A”, I create:

 Shipment1(bin1->Landfill1),
 Shipment2(bin1->Landfill2), 
 Shipment3(bin1->Landfill3).

In this case, if route would be below, cost would be incorrect. (Cost is calculated by distance between each location)

 Start Location -> bin1pickup(Shipment1)  -> bin1pickup(Shipment2) -> bin1pickup(Shipment3) ->
  Landfill1(Shipment1) -> Landfill2(Shipment2) -> Landfill3(Shipment3) -> End Location

To make truck come back to the first deliver location (In this case, Landfill1(Shipment1)), make distance between each Landfills “0” value, and create “Dummy Shipment” and create constraints to work like below.
e.g. In this case:

  
 Define Dummy1(PickupLocation is “Landfill1”, DeliverLocation is “Landfill1”), 
 Dummy2(PickupLocation is “Landfill2”, DeliverLocation is “Landfill2”),
 Dummy3(PickupLocation is “Landfill3”, DeliverLocation is “Landfill3”)

and create constraints to make route order below:

 Start Location -> bin1pickup(Shipment1)  -> bin1pickup(Shipment2) -> bin1pickup(Shipment3) -> 
 Landfill1(Shipment1) -> Landfill2(Shipment2) -> Landfill3(Shipment3) -> 
 Dummy3 Pickup -> Dummy3 Deliver -> 
 Dummy2 Pickup -> Dummy2 Deliver -> 
 Dummy1 Pickup -> Dummy1 Deliver -> End Location

(In this case, Real suggested route is Start Location -> bin1pickup(Shipment1) -> Landfill1(Shipment1) -> End Location )

I think it is because constrains are too complicated .
Could you advise me or if you can, could you show me sample source codes?

Class implements HardActivityConstraints

      @Override
      public ConstraintsStatus fulfilled(JobInsertionContext context, TourActivity prevAct, TourActivity newAct, TourActivity nextAct, double v) {
      	Capacity loadAtPrevAct = getLoadAtPreviousAct(prevAct);
          if (isPickup(newAct)) {
              if (isPickedUpViolate(newAct, loadAtPrevAct)) {
                  return ConstraintsStatus.NOT_FULFILLED;
              }
              if (isPickedUpViolate(newAct, nextAct)) {
                  return ConstraintsStatus.NOT_FULFILLED;
              }
              return ConstraintsStatus.FULFILLED;
          }
      
          if (isDelivery(newAct)) {
              if (isDeliveredViolate(newAct, loadAtPrevAct)) {
                  return ConstraintsStatus.NOT_FULFILLED_BREAK; // if so constraint is broken forever -> break here
              }
              return ConstraintsStatus.FULFILLED;
          }
  
      	if(newAct instanceof JobActivity){
  			if(((JobActivity)newAct).getJob().getName().equals("Dummy") 
  					&& newAct.getName().equals("pickupShipment")){
  				if(!prevAct.getName().equals("deliverShipment")){
                      return ConstraintsStatus.NOT_FULFILLED;
  				}
  			}else if(!((JobActivity)newAct).getJob().getName().equals("Dummy") 
  					&& newAct.getName().equals("pickupShipment")){
  				if(prevAct instanceof JobActivity){
  					if(!((JobActivity)prevAct).getJob().getName().equals("Dummy") &&
  							prevAct.getName().equals("deliverShipment")){
  	                    return ConstraintsStatus.NOT_FULFILLED;
  					}
  				}
  				if(nextAct instanceof JobActivity){
  	            	if(((JobActivity)nextAct).getJob().getName().equals("Dummy") &&
  	            			nextAct.getName().equals("deliverShipment") &&
  	            			((JobActivity)newAct).getJob().getId().equals(((JobActivity)nextAct).getJob().getId())
  	            			){
  		            }else{
  		                return ConstraintsStatus.NOT_FULFILLED;
  		            }
  				}
  			}
      	           }
  
          if (newAct instanceof JobActivity) {
              if (((JobActivity)newAct).getJob().getName().equals("Dummy") \
          ){
              	for(int i=0; i < loadAtPrevAct.getNuOfDimensions(); i++){
              		if(loadAtPrevAct.get(i) > 0){
                          return ConstraintsStatus.NOT_FULFILLED;
              		}
              	}
              }
           }
  
          if(newAct instanceof JobActivity && nextAct instanceof JobActivity ) {
              if (((JobActivity)newAct).getJob().getName().equals("Dummy") &&
              		newAct.getName().equals("pickupShipment")) {
              	if(((JobActivity)nextAct).getJob().getName().equals("Dummy") &&
              			nextAct.getName().equals("deliverShipment") &&
              		((JobActivity)newAct).getJob().getId().equals(((JobActivity)nextAct).getJob().getId())
              			){
  	            }else{
  	                return ConstraintsStatus.NOT_FULFILLED;
  	            }
          	}
            }
      	    return ConstraintsStatus.FULFILLED;
            }
  
  
      public static boolean isPickedUpViolate(TourActivity act1, Capacity prevCap){
      	FractionType curFraction = null;
          for (FractionType num : FractionType.values()) {
          	if(act1.getSize().get(num.getId()) > 0){
          		curFraction = num;
          	}
          }
          if(curFraction == null){
          	return false;
          }else{
  	        for (FractionType count : FractionType.values()) {
  	        	if(!count.equals(curFraction)){
  		        	if(prevCap.get(count.getId()) > 0){
  		        		return true;
  		        	}
  	        	}
  	        }
          }
          return false;
      }
      
      public static boolean isDeliveredViolate(TourActivity act1, Capacity prevCap){
      	FractionType curFraction = null;
          for (FractionType num : FractionType.values()) {
          	if(act1.getSize().get(num.getId()) < 0){
          		curFraction = num;
          	}
          }
          if(curFraction == null){
          	return false;
          }else{
  	        for (FractionType count : FractionType.values()) {
  	        	if(!count.equals(curFraction)){
  		        	if(prevCap.get(count.getId()) > 0){
  		        		return true;
  		        	}
  	        	}
  	        }
          }
          return false;
      	
      }
  	
      public static boolean isPickedUpViolate(TourActivity act1, TourActivity act2){
          for (FractionType num : FractionType.values()) {
          	if(act1.getSize().get(num.getId()) > 0){
          		if(isOtherTypePickedUp(act2, num)){
          			return true;
          		}
          	}
          }
          return false;
      }
      
  	public static boolean isOtherTypePickedUp(TourActivity act, FractionType num){
          for (FractionType ft : FractionType.values()) {
          	if(!ft.equals(num)){
          		if(act.getSize().get(ft.getId()) > 0){
          			return true;
          		}
          	}
          }
          return false;
  	}
  	
      public static boolean isDeliveredViolate(TourActivity act1, TourActivity act2){
          for (FractionType num : FractionType.values()) {
          	if(act1.getSize().get(num.getId()) < 0){
          		if(isOtherTypeDelivered(act2, num)){
          			return true;
          		}
          	}
          }
          return false;
      }
      
  	public static boolean isOtherTypeDelivered(TourActivity act, FractionType num){
          for (FractionType ft : FractionType.values()) {
          	if(!ft.equals(num)){
          		if(act.getSize().get(ft.getId()) < 0){
          			return true;
          		}
          	}
          }
          return false;
  	}
  	
      private boolean isPickup(TourActivity newAct) {
          return newAct.getName().equals("pickupShipment");
      }
  
      private boolean isDelivery(TourActivity newAct) {
          return newAct.getName().equals("deliverShipment");
      }
  
      private Capacity getLoadAtPreviousAct(TourActivity prevAct) {
      	Capacity prevLoad = stateManager.getActivityState(prevAct, InternalStates.LOAD, Capacity.class); //1.3.2-SNAPSHOT & upcoming release v1.4
      	if (prevLoad != null) return prevLoad;
      	else return Capacity.Builder.newInstance().build();
        }

Class implements SoftActivityConstraints

  	@Override
  	public double getCosts(JobInsertionContext iFacts,TourActivity prevAct, TourActivity newAct,TourActivity nextAct, double prevActDepTime) {
  
  		List tourList = iFacts.getRoute().getTourActivities().getActivities();
  
      	LinkedList deliverStack = new LinkedList();
          boolean nonDummyFl = false;
  		TourActivity firstDelivery = null;
          Iterator tourListIterator = tourList.iterator();
          ArrayList tourHistory = new ArrayList();
          TourActivity curActivity = null;
          
          while(tourListIterator.hasNext()){
          	 curActivity = tourListIterator.next();
          	
          	if(curActivity instanceof JobActivity){
              	Job curJob = ((JobActivity)curActivity).getJob();
              	
              	if(!curJob.getName().equals("Dummy")){
              		nonDummyFl = true;
              	}
  
   	        	if(!curJob.getName().equals("Dummy")){
          			if(!tourHistory.contains(
      					curJob.getId() + "Dummy")){
          		    	return FalseValue;
          			}
  	        	}else if(curJob.getName().equals("Dummy")){
          			if(!tourHistory.contains(
      					curJob.getId().subSequence(0, curJob.getId().length()-"Dummy".length()))){
          		    	return FalseValue;
          			}
  	        	}
  
  	        	if(!curJob.getName().equals("Dummy") &&
  	        			curActivity.getName().equals("deliverShipment")){
  	        		deliverStack.addLast(curJob);
  	        		
  	        	}else if(curJob.getName().equals("Dummy") &&
  	        			curActivity.getName().equals("pickupShipment")){
  	        		if(deliverStack.size() == 0){
          		    	return FalseValue;
  	        		}
  	        		if(!curJob.getId().equals(deliverStack.getLast().getId() + "Dummy")){
          		    	return FalseValue;
  	        		}else{
  	        			deliverStack.removeLast();
  	        		}
  	        		
  	        	}
  	        	
  	        	tourHistory.add(curJob.getId());
          	}
          }
          
          if(!nonDummyFl){
  	    	return FalseValue;        	
          }
          if(curActivity != null){
          	if(((JobActivity)curActivity).getJob().getName().equals("Dummy")){
          		if(firstDelivery == null){
      		    	return FalseValue;
          			
          		}
          		
          	}	
          }
  		
          return 0;
  	}

stefan · January 22, 2016, 6:12am

Hi,

Look at this example. It might help you solving your problem.

Best, Stefan

bitinc · May 17, 2017, 10:19am

Hi,

This link doesn’t seem to work anymore, might there be another one?

Thanks!

jie31best · May 18, 2017, 2:31am

github.com

graphhopper/jsprit/blob/master/jsprit-examples/src/main/java/com/graphhopper/jsprit/examples/MultipleProductsWithLoadConstraintExample.java

/*
 * Licensed to GraphHopper GmbH under one or more contributor
 * license agreements. See the NOTICE file distributed with this work for
 * additional information regarding copyright ownership.
 *
 * GraphHopper GmbH licenses this file to you under the Apache License,
 * Version 2.0 (the "License"); you may not use this file except in
 * compliance with the License. You may obtain a copy of the License at
 *
 *       http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package com.graphhopper.jsprit.examples;

This file has been truncated. show original