OSRM Transport Costs for use with jsprit

osrm-jsprit-example.java

/*******************************************************************************
 * Copyright (C) 2014  Stefan Schroeder
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 3.0 of the License, or (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public 
 * License along with this library.  If not, see <http://www.gnu.org/licenses/>.
 ******************************************************************************/
package se.dotnetmentor.jsprittest;

import java.io.File;
import java.io.IOException;
import java.net.URL;
import java.util.Collection;

import jsprit.analysis.toolbox.GraphStreamViewer;
import jsprit.analysis.toolbox.GraphStreamViewer.Label;
import jsprit.core.algorithm.VehicleRoutingAlgorithm;
import jsprit.core.algorithm.box.SchrimpfFactory;
import jsprit.core.problem.Location;
import jsprit.core.problem.VehicleRoutingProblem;
import jsprit.core.problem.cost.VehicleRoutingTransportCosts;
import jsprit.core.problem.io.VrpXMLWriter;
import jsprit.core.problem.job.Service;
import jsprit.core.problem.solution.VehicleRoutingProblemSolution;
import jsprit.core.problem.vehicle.VehicleImpl;
import jsprit.core.problem.vehicle.VehicleImpl.Builder;
import jsprit.core.problem.vehicle.VehicleType;
import jsprit.core.problem.vehicle.VehicleTypeImpl;
import jsprit.core.reporting.SolutionPrinter;
import jsprit.core.util.Solutions;


public class SimpleExample {
	
	
	
	public static void main(String[] args) throws IOException {
		/*
		 * some preparation - create output folder
		 */
		File dir = new File("output");
		// if the directory does not exist, create it
		if (!dir.exists()){
			System.out.println("creating directory ./output");
			boolean result = dir.mkdir();  
			if(result) System.out.println("./output created");  
		}
		
		/*
		 * get a vehicle type-builder and build a type with the typeId "vehicleType" and one capacity dimension, i.e. weight, and capacity dimension value of 2
		 */
		final int WEIGHT_INDEX = 0;
		VehicleTypeImpl.Builder vehicleTypeBuilder = VehicleTypeImpl.Builder.newInstance("vehicleType").addCapacityDimension(WEIGHT_INDEX, 2);
		VehicleType vehicleType = vehicleTypeBuilder.build();
		
		/*
		 * get a vehicle-builder and build a vehicle located at (10,10) with type "vehicleType"
		 */
		Builder vehicleBuilder = VehicleImpl.Builder.newInstance("vehicle");
		Location startLocation = Location.newInstance(11.947364, 57.699676);
		vehicleBuilder.setStartLocation(startLocation);
		vehicleBuilder.setType(vehicleType);
		VehicleImpl vehicle = vehicleBuilder.build();
		
		/*
		 * build services at the required locations, each with a capacity-demand of 1.
		 */
		Service service1 = Service.Builder.newInstance("1").addSizeDimension(WEIGHT_INDEX, 1).setLocation(Location.newInstance(11.941967, 57.731812)).build();
		Service service2 = Service.Builder.newInstance("2").addSizeDimension(WEIGHT_INDEX, 1).setLocation(Location.newInstance(11.944757, 57.697016)).build();
		
		Service service3 = Service.Builder.newInstance("3").addSizeDimension(WEIGHT_INDEX, 1).setLocation(Location.newInstance(11.992629, 57.70456)).build();
		Service service4 = Service.Builder.newInstance("4").addSizeDimension(WEIGHT_INDEX, 1).setLocation(Location.newInstance(12.028248, 57.656589)).build();
		
		OsrmTransportCostsMatrix.Builder builder = OsrmTransportCostsMatrix.Builder.newInstance(new URL("http://router.project-osrm.org/table"));
		builder
			.addLocation(startLocation)
			.addLocation(service1.getLocation())
			.addLocation(service2.getLocation())
			.addLocation(service3.getLocation())
			.addLocation(service4.getLocation());
		VehicleRoutingTransportCosts transportCosts = new OsrmTransportCostsMatrix(builder);
		
		VehicleRoutingProblem.Builder vrpBuilder = VehicleRoutingProblem.Builder.newInstance();
		vrpBuilder.setRoutingCost(transportCosts);
		vrpBuilder.addVehicle(vehicle);
		vrpBuilder.addJob(service1).addJob(service2).addJob(service3).addJob(service4);

		VehicleRoutingProblem problem = vrpBuilder.build();
		
		/*
		 * get the algorithm out-of-the-box. 
		 */
		VehicleRoutingAlgorithm algorithm = new SchrimpfFactory().createAlgorithm(problem);
		
		/*
		 * and search a solution
		 */
		Collection<VehicleRoutingProblemSolution> solutions = algorithm.searchSolutions();
		
		/*
		 * get the best 
		 */
		VehicleRoutingProblemSolution bestSolution = Solutions.bestOf(solutions);
		
		new VrpXMLWriter(problem, solutions).write("output/problem-with-solution.xml");
		
		SolutionPrinter.print(problem, bestSolution, SolutionPrinter.Print.VERBOSE);
		
		/*
		 * plot
		 */
//		SolutionPlotter.plotSolutionAsPNG(problem, bestSolution, "output/solution.png", "solution");
		
		new GraphStreamViewer(problem, bestSolution).labelWith(Label.ID).setRenderDelay(200).display();
	}

}

OsrmTransportCostsMatrix.java

import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.net.URL;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

import jsprit.core.problem.Location;
import jsprit.core.problem.cost.AbstractForwardVehicleRoutingTransportCosts;
import jsprit.core.problem.driver.Driver;
import jsprit.core.problem.vehicle.Vehicle;
import jsprit.core.problem.vehicle.VehicleTypeImpl.VehicleCostParams;
import jsprit.core.util.Coordinate;

import com.google.gson.JsonArray;
import com.google.gson.JsonElement;
import com.google.gson.JsonParser;

public class OsrmTransportCostsMatrix extends AbstractForwardVehicleRoutingTransportCosts {
	public static class Builder {
		private List<Location> locations = new ArrayList<Location>();
		private URL osrmDistanceTableUrl;
		
		public Builder(URL osrmDistanceTableUrl) {
			this.osrmDistanceTableUrl = osrmDistanceTableUrl;
		}
		
		public static Builder newInstance(URL osrmDistanceTableUrl) {
			return new Builder(osrmDistanceTableUrl);
		}
		
		public Builder addLocation(Location location) {
			locations.add(location);
			return this;
		}
	}

	private int[][] distanceTableMatrix;
	private Map<String, Integer> locationIndices = new HashMap<String, Integer>();
	
	public OsrmTransportCostsMatrix(Builder builder) throws IOException {
		distanceTableMatrix = getDistanceTableMatrix(builder.osrmDistanceTableUrl, builder.locations);
		for (int i = 0; i < builder.locations.size(); i++) {
			locationIndices.put(builder.locations.get(i).getId(), i);
		}
	}
	
	private int[][] getDistanceTableMatrix(URL osrmDistanceTableUrl,
			List<Location> locations) throws IOException {
		StringBuilder builder = new StringBuilder();
		boolean first = true;
		for (Location l : locations) {
			if (!first) {
				builder.append('&');
			} else {
				first = false;
			}
			Coordinate coord = l.getCoordinate();
			builder
				.append("loc=")
				.append(coord.getY())
				.append(',')
				.append(coord.getX());
		}
		
		URL url = new URL(osrmDistanceTableUrl.toString() + "?" + builder.toString());
		
		InputStream stream = url.openStream();
		JsonParser parser = new JsonParser();
		JsonElement root = parser.parse(new InputStreamReader(stream));
		JsonArray array = root.getAsJsonObject().get("distance_table").getAsJsonArray();
		
		int[][] distances = new int[array.size()][];
		for (int i = 0; i < array.size(); i++) {
			JsonArray innerArray = array.get(i).getAsJsonArray();
			distances[i] = new int[innerArray.size()];
			for (int j = 0; j < innerArray.size(); j++) {
				distances[i][j] = innerArray.get(j).getAsInt();
			}
		}
		
		return distances;
	}

	@Override
	public double getTransportTime(Location from, Location to,
			double departureTime, Driver driver, Vehicle vehicle) {
		return distanceTableMatrix[locationIndices.get(from.getId())][locationIndices.get(to.getId())];
	}

	@Override
	public double getTransportCost(Location from, Location to,
			double departureTime, Driver driver, Vehicle vehicle) {
		if(vehicle == null) return getTransportTime(from, to, departureTime, driver, vehicle);
		VehicleCostParams costParams = vehicle.getType().getVehicleCostParams();
		return costParams.perTimeUnit*getTransportTime(from, to, departureTime, driver, vehicle);
	}

}