Service with Multiple locations, each location having their own multiple time windows

Aflred · January 12, 2019, 9:20pm

What is the best way to solve the type of problem where you have a service that has:

Multiple locations
Each location has one or more time windows.

I mean, Joe goes to work from 8:00 to 17:00 during workdays. Then he is home from 18:00 to 22:00.
Then on weekends he is always home from 11:00 to 22:00.

He needs his ‘shampoos’ delivered to him during that period. Simple, hope people understand my point.

I couldnt find anything on google about this.
I have a couple of theories of how this can be done and I will post my solution later tomorrow.
I hope, in the meantime, a jsprit expert posts what the standard way to approach this problem is as, i figure
, this is a very common problem.

Aflred · January 14, 2019, 2:43am

I got inspired by this: https://stackoverflow.com/questions/24447451/related-jobs-in-jsprit
Note i am using Jsprit 1.72.

Here is my solution, i will do further testing in the days coming, but initially it seems to be working.

Note that i am randoming the transport times everytime for the matrix.

    package com.jspritexample.jspritexample;

import static org.junit.Assert.assertNotNull;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.net.URL;
import java.nio.file.Files;
import java.nio.file.Paths;
import java.util.Collection;
import java.util.List;
import java.util.Random;
import java.util.stream.Collectors;
import com.fasterxml.jackson.core.JsonGenerationException;
import com.fasterxml.jackson.core.JsonParseException;
import com.fasterxml.jackson.databind.JsonMappingException;
import com.fasterxml.jackson.databind.ObjectMapper;
import com.graphhopper.jsprit.analysis.toolbox.AlgorithmSearchProgressChartListener;
import com.graphhopper.jsprit.analysis.toolbox.GraphStreamViewer;
import com.graphhopper.jsprit.analysis.toolbox.Plotter;
import com.graphhopper.jsprit.analysis.toolbox.Plotter.Label;
import com.graphhopper.jsprit.core.algorithm.AlgorithmUtil;
import com.graphhopper.jsprit.core.algorithm.SearchStrategyManager;
import com.graphhopper.jsprit.core.algorithm.VehicleRoutingAlgorithm;
import com.graphhopper.jsprit.core.algorithm.box.Jsprit;
import com.graphhopper.jsprit.core.algorithm.box.Jsprit.Builder;
import com.graphhopper.jsprit.core.algorithm.box.Jsprit.Parameter;
import com.graphhopper.jsprit.core.algorithm.state.InternalStates;
import com.graphhopper.jsprit.core.algorithm.state.StateManager;
import com.graphhopper.jsprit.core.algorithm.state.StateUpdater;
import com.graphhopper.jsprit.core.problem.Location;
import com.graphhopper.jsprit.core.problem.VehicleRoutingProblem;
import com.graphhopper.jsprit.core.problem.VehicleRoutingProblem.FleetSize;
import com.graphhopper.jsprit.core.problem.constraint.ConstraintManager;
import com.graphhopper.jsprit.core.problem.constraint.HardActivityConstraint;
import com.graphhopper.jsprit.core.problem.constraint.SoftRouteConstraint;
import com.graphhopper.jsprit.core.problem.constraint.ConstraintManager.Priority;
import com.graphhopper.jsprit.core.problem.cost.VehicleRoutingTransportCosts;
import com.graphhopper.jsprit.core.problem.job.Job;
import com.graphhopper.jsprit.core.problem.job.Service;
import com.graphhopper.jsprit.core.problem.misc.JobInsertionContext;
import com.graphhopper.jsprit.core.problem.solution.SolutionCostCalculator;
import com.graphhopper.jsprit.core.problem.solution.VehicleRoutingProblemSolution;
import com.graphhopper.jsprit.core.problem.solution.route.VehicleRoute;
import com.graphhopper.jsprit.core.problem.solution.route.activity.ActivityVisitor;
import com.graphhopper.jsprit.core.problem.solution.route.activity.TimeWindow;
import com.graphhopper.jsprit.core.problem.solution.route.activity.TourActivity;
import com.graphhopper.jsprit.core.problem.solution.route.activity.TourActivity.JobActivity;
import com.graphhopper.jsprit.core.problem.vehicle.Vehicle;
import com.graphhopper.jsprit.core.problem.vehicle.VehicleImpl;
import com.graphhopper.jsprit.core.problem.vehicle.VehicleType;
import com.graphhopper.jsprit.core.problem.vehicle.VehicleTypeImpl;
import com.graphhopper.jsprit.core.reporting.SolutionPrinter;
import com.graphhopper.jsprit.core.reporting.SolutionPrinter.Print;
import com.graphhopper.jsprit.core.util.Coordinate;
import com.graphhopper.jsprit.core.util.Solutions;
import com.graphhopper.jsprit.core.util.VehicleRoutingTransportCostsMatrix;
import com.graphhopper.jsprit.io.problem.VrpXMLReader;
import com.jspritexample.jspritutils.JsPritUtils;


public class App 
{

static class JobsInRouteMemorizer implements StateUpdater, ActivityVisitor {

	private StateManager stateManager;
	private VehicleRoute route;
	public int timesAssigned= 0;
	
	public JobsInRouteMemorizer(StateManager stateManager) {
		super();
		this.stateManager = stateManager;
	}

	@Override
	public void begin(VehicleRoute route) {
		this.route=route;
	}

	@Override
	public void visit(TourActivity activity) {
		if(activity instanceof JobActivity){
			String jobId = ((JobActivity) activity).getJob().getId();
	
			// the job was assigned, then put it inside statemanager.
			stateManager.putProblemState(stateManager.createStateId(jobId), String.class, jobId);
		}
	}

	@Override
	public void finish() {}
	
}

static class EitherS2OrS3 implements HardActivityConstraint {
	
	private StateManager stateManager;
	
	public EitherS2OrS3(StateManager stateManager) {
		super();
		this.stateManager = stateManager;
	}
	
	@Override
	public ConstraintsStatus fulfilled(JobInsertionContext iFacts, TourActivity prevAct, TourActivity newAct,
			TourActivity nextAct, double prevActDepTime) {
		
			String currentJobId = iFacts.getJob().getId();
		
			
			
		
			String s2Job = stateManager.getProblemState(stateManager.createStateId("s2"), String.class);
					
			// if job s2 was assigned and we are inserting s3 then we cannot do that.
			if( s2Job != null && currentJobId == "s3"){ 
				return ConstraintsStatus.NOT_FULFILLED;
			}
			
		    String s3Job = stateManager.getProblemState(stateManager.createStateId("s3"), String.class);
			
			//if job s3 was assigned and we are inserting s2 then we cannot do that.
			if( s3Job != null && currentJobId == "s2"){ 
				return ConstraintsStatus.NOT_FULFILLED;
			}
			
			
			
			return ConstraintsStatus.FULFILLED;
	}


}





public static void main( String[] args ) 
{       


	
	
	JsPritUtils.createOutputFolder();

    VehicleType type = VehicleTypeImpl.Builder.newInstance("type").build();        
    
    Location l0 =  Location.Builder.newInstance().setId("0").setName("Local0").setCoordinate(Coordinate.newInstance(23.1, 22.2)).build();
    Location l1 =  Location.Builder.newInstance().setId("1").setName("Local1").setCoordinate(Coordinate.newInstance(23, 24)).build();
    Location l2 =  Location.Builder.newInstance().setId("2").setName("Local2").setCoordinate(Coordinate.newInstance(21, 25)).build();
    Location l3 =  Location.Builder.newInstance().setId("3").setName("Local3").setCoordinate(Coordinate.newInstance(22.5, 23.5)).build();
    
    VehicleImpl vehicle = VehicleImpl.Builder.newInstance("myOwn")
    		
    		.setStartLocation(l0).setType(type).build();
    		
    Service s1 = Service.Builder.newInstance("s1").setLocation(l1).build();
    Service s2 = Service.Builder.newInstance("s2").setLocation(l2).addTimeWindow(new TimeWindow(0,20)).build(); 
    Service s3 = Service.Builder.newInstance("s3").setLocation(l3).addTimeWindow(new TimeWindow(20,40)).build();
  
    
    VehicleRoutingTransportCostsMatrix.Builder costMatrixBuilder = VehicleRoutingTransportCostsMatrix.Builder.newInstance(true);


    Random rand = new Random();

    int number = rand.nextInt(50) + 1;
    
    costMatrixBuilder.addTransportTime("0", "1", rand.nextInt(50) + 1);
    costMatrixBuilder.addTransportTime("0", "2", rand.nextInt(50) + 1);
    costMatrixBuilder.addTransportTime("1", "0", rand.nextInt(50) + 1);
    costMatrixBuilder.addTransportTime("2", "0", rand.nextInt(50) + 1);
  
  
    costMatrixBuilder.addTransportTime("1", "0", rand.nextInt(50) + 1);
    costMatrixBuilder.addTransportTime("1", "2", rand.nextInt(50) + 1);        
    costMatrixBuilder.addTransportTime("0", "1", rand.nextInt(50) + 1);
    costMatrixBuilder.addTransportTime("2", "1", rand.nextInt(50) + 1);
    
    
    costMatrixBuilder.addTransportTime("2", "0", rand.nextInt(50) + 1);
    costMatrixBuilder.addTransportTime("2", "1", rand.nextInt(50) + 1);        
    costMatrixBuilder.addTransportTime("0", "2", rand.nextInt(50) + 1);
    costMatrixBuilder.addTransportTime("1", "2", rand.nextInt(50) + 1);
    
    costMatrixBuilder.addTransportTime("2", "0", rand.nextInt(50) + 1);
    costMatrixBuilder.addTransportTime("2", "1", rand.nextInt(50) + 1);        
    costMatrixBuilder.addTransportTime("0", "2", rand.nextInt(50) + 1);
    costMatrixBuilder.addTransportTime("1", "2", rand.nextInt(50) + 1);
 
    costMatrixBuilder.addTransportTime("0", "3", rand.nextInt(50) + 1);
    costMatrixBuilder.addTransportTime("1", "3", rand.nextInt(50) + 1);        
    costMatrixBuilder.addTransportTime("2", "3", rand.nextInt(50) + 1);      
    costMatrixBuilder.addTransportTime("3", "1", rand.nextInt(50) + 1);
    costMatrixBuilder.addTransportTime("3", "2", rand.nextInt(50) + 1);        
    costMatrixBuilder.addTransportTime("3", "3", rand.nextInt(50) + 1);

    

    VehicleRoutingTransportCosts costMatrix = costMatrixBuilder.build();


   
    VehicleRoutingProblem vrp = VehicleRoutingProblem.Builder.newInstance().setFleetSize(FleetSize.FINITE).setRoutingCost(costMatrix)
        .addVehicle(vehicle)
        .addJob(s1).addJob(s2).addJob(s3)   
        .build();
    
    /// OK THE UPPER IS SETUP
	
	final StateManager stateManager = new StateManager(vrp);	
	JobsInRouteMemorizer jm = new JobsInRouteMemorizer(stateManager);
	stateManager.addStateUpdater(jm);
	
	ConstraintManager constraintManager = new ConstraintManager(vrp,stateManager);	
	constraintManager.addConstraint(new EitherS2OrS3(stateManager), Priority.CRITICAL);
	
	
	//
	//final RewardAndPenaltiesThroughSoftConstraints softConstraintContributionToOverallObjective = new RewardAndPenaltiesThroughSoftConstraints(vrp);
	SolutionCostCalculator costCalculator = new SolutionCostCalculator() {
		
		 @Override
            public double getCosts(VehicleRoutingProblemSolution solution) {
                double costs = 0.0;
                for (VehicleRoute r : solution.getRoutes()) {
                	costs += stateManager.getRouteState(r, InternalStates.COSTS, Double.class);
                	costs += getFixedCosts(r.getVehicle());
                //    costs +=softConstraintContributionToOverallObjective.getCosts(r); 
                }
                costs += solution.getUnassignedJobs().size() * costs * .1;
                return costs;
            }

            private double getFixedCosts(Vehicle vehicle) {
                if (vehicle == null) return 0.0;
                if (vehicle.getType() == null) return 0.0;
                return vehicle.getType().getVehicleCostParams().fix;
            }
	};
	
	
	 
	Builder builder = Jsprit.Builder.newInstance(vrp);
	
    builder.setObjectiveFunction(costCalculator);
	builder.setStateAndConstraintManager(stateManager,constraintManager);

	builder.setProperty(Parameter.ITERATIONS.toString(), "2000");
	
	VehicleRoutingAlgorithm vra = builder.buildAlgorithm();
	
	
	
	Collection<VehicleRoutingProblemSolution> solutions = vra.searchSolutions();
	
	SolutionPrinter.print(vrp, Solutions.bestOf(solutions), Print.VERBOSE);
	
	new Plotter(vrp,Solutions.bestOf(solutions)).setLabel(Label.ID).plot("output/jsprit_vrpnc1_noConstraints", "jsprit: noConstraints");
	System.out.println(jm.timesAssigned);
	GraphStreamViewer streamViewer =  new GraphStreamViewer(vrp, Solutions.bestOf(solutions));
	streamViewer.labelWith(GraphStreamViewer.Label.ID);
	streamViewer.setRenderDelay(500).display();
	
}

public static String getResourceFileAsString(String fileName) {
    ClassLoader classLoader = ClassLoader.getSystemClassLoader();
    InputStream is = classLoader.getResourceAsStream(fileName);
    if (is != null) {
        BufferedReader reader = new BufferedReader(new InputStreamReader(is));
        return reader.lines().collect(Collectors.joining(System.lineSeparator()));
    }
    return null;
}

}

pom.txt (1.9 KB)

Here is my pom file for future references

Aflred · January 15, 2019, 1:57am

I updated my answer with a feasible solution and added comments.

One thing to note here is the the statemanager only hods the state for each iteration, after an iteration is done, the state manager gets emptied.