Skip to content

Instantly share code, notes, and snippets.

@julienroubieu

julienroubieu/VehicleStartEndLocationsBug.java

Created March 9, 2017 18:55
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save julienroubieu/12e2eb137b815aa9593e7e17c7db2c23 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save julienroubieu/12e2eb137b815aa9593e7e17c7db2c23 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. julienroubieu created this gist Mar 9, 2017.
    222 changes: 222 additions & 0 deletions VehicleStartEndLocationsBug.java
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,222 @@
    //
    // Copyright 2012 Google
    //
    // Licensed 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 services;

    import com.google.ortools.constraintsolver.*;

    import java.util.ArrayList;
    import java.util.List;
    import java.util.Random;
    import java.util.logging.Logger;

    // A pair class

    class Pair<K, V> {
    final K first;
    final V second;

    public static <K, V> Pair<K, V> of(K element0, V element1) {
    return new Pair<K, V>(element0, element1);
    }

    public Pair(K element0, V element1) {
    this.first = element0;
    this.second = element1;
    }
    }

    /**
    * Sample showing that vehicle start and end locations are not taken from
    * the arrays passed to RoutingModel constructor but sequential.
    */
    public class VehicleStartEndLocationsBug {

    static {
    System.out.println("java.library.path = " + System.getProperty("java.library.path"));
    System.loadLibrary("jniortools");
    }

    private static Logger logger =
    Logger.getLogger(VehicleStartEndLocationsBug.class.getName());

    private List<Pair<Integer, Integer>> locations = new ArrayList();
    private List<Integer> vehicleEndTime = new ArrayList();
    // Vehicle start and end indices. They have to be implemented as int[] due
    // to the available SWIG-ed interface.
    private int vehicleStarts[];
    private int vehicleEnds[];

    // Random number generator to produce data.
    private final Random randomGenerator = new Random(0xBEEF);

    /**
    * Constructs a capacitated vehicle routing problem with time windows.
    */
    public VehicleStartEndLocationsBug() {}

    /**
    * Creates order data. Location of the order is random, as well as its
    * demand (quantity), time window and penalty.
    *
    * @param numberOfOrders number of orders to build.
    * @param xMax maximum x coordinate in which orders are located.
    * @param yMax maximum y coordinate in which orders are located.
    */
    public void buildOrders(int numberOfOrders,
    int xMax, int yMax) {
    logger.info("Building orders.");
    for (int order = 0; order < numberOfOrders; ++order) {
    locations.add(Pair.of(randomGenerator.nextInt(xMax + 1),
    randomGenerator.nextInt(yMax + 1)));
    }
    }

    /**
    * Creates fleet data. Vehicle starting and ending locations are random, as
    * well as vehicle costs per distance unit.
    *
    * @param numberOfVehicles
    * @param xMax maximum x coordinate in which orders are located.
    * @param yMax maximum y coordinate in which orders are located.
    * @param endTime latest end time of a tour of a vehicle.
    * (mimimum is 1),
    */
    public void buildFleet(int numberOfVehicles,
    int xMax, int yMax,
    int endTime) {
    logger.info("Building fleet.");
    vehicleStarts = new int[numberOfVehicles];
    vehicleEnds = new int[numberOfVehicles];
    for (int vehicle = 0; vehicle < numberOfVehicles; ++vehicle) {
    vehicleStarts[vehicle] = locations.size();
    locations.add(Pair.of(randomGenerator.nextInt(xMax + 1),
    randomGenerator.nextInt(yMax + 1)));
    vehicleEnds[vehicle] = locations.size();
    locations.add(Pair.of(randomGenerator.nextInt(xMax + 1),
    randomGenerator.nextInt(yMax + 1)));
    vehicleEndTime.add(endTime);
    }
    }

    /**
    * Solves the current routing problem.
    */
    public void solve(final int numberOfOrders, final int numberOfVehicles) {
    logger.info("Creating model with " + numberOfOrders + " orders and " +
    numberOfVehicles + " vehicles.");
    // Finalizing model
    final int numberOfLocations = locations.size();

    // logger.info("vehicleStarts: " + Arrays.toString(vehicleStarts));
    // logger.info("vehicleEnds: " + Arrays.toString(vehicleEnds));
    RoutingModel model =
    new RoutingModel(numberOfLocations, numberOfVehicles, vehicleStarts, vehicleEnds);

    // Setting up dimensions
    final int bigNumber = 100000;
    NodeEvaluator2 manhattanCallback = new NodeEvaluator2(){
    @Override
    public long run(int firstIndex, int secondIndex) {
    try {
    Pair<Integer, Integer> firstLocation = locations.get(firstIndex);
    Pair<Integer, Integer> secondLocation = locations.get(secondIndex);
    return Math.abs(firstLocation.first - secondLocation.first) +
    Math.abs(firstLocation.second - secondLocation.second);
    } catch (Throwable throwed) {
    logger.warning(throwed.getMessage());
    return 0;
    }
    }
    };
    model.addDimension(manhattanCallback, bigNumber, bigNumber, false, "time");

    // Setting up vehicles
    for (int vehicle = 0; vehicle < numberOfVehicles; ++vehicle) {
    NodeEvaluator2 manhattanCostCallback = new NodeEvaluator2() {
    @Override
    public long run(int firstIndex, int secondIndex) {
    try {
    Pair<Integer, Integer> firstLocation = locations.get(firstIndex);
    Pair<Integer, Integer> secondLocation = locations.get(secondIndex);
    return (Math.abs(firstLocation.first - secondLocation.first) +
    Math.abs(firstLocation.second - secondLocation.second));
    } catch (Throwable throwed) {
    logger.warning(throwed.getMessage());
    return 0;
    }
    }
    };
    model.setArcCostEvaluatorOfVehicle(manhattanCostCallback, vehicle);
    model.cumulVar(model.end(vehicle), "time").setMax(vehicleEndTime.get(vehicle));
    }

    // Setting up orders
    for (int order = 0; order < numberOfOrders; ++order) {
    int[] orders = {order};
    int fixedPenalty = 50;
    model.addDisjunction(orders, fixedPenalty);
    }

    // Solving
    RoutingSearchParameters parameters =
    RoutingSearchParameters.newBuilder()
    .mergeFrom(RoutingModel.defaultSearchParameters())
    .setFirstSolutionStrategy(FirstSolutionStrategy.Value.ALL_UNPERFORMED)
    .build();

    logger.info("Search");
    Assignment solution = model.solveWithParameters(parameters);

    if (solution != null) {
    String output = "Total cost: " + solution.objectiveValue() + "\n";
    // Routes
    for (int vehicle = 0; vehicle < numberOfVehicles; ++vehicle) {
    String route = "Vehicle " + vehicle + ": ";
    long order = model.start(vehicle);
    if (model.isEnd(solution.value(model.nextVar(order)))) {
    route += "Empty";
    } else {
    route += "From #" + order;
    while (!model.isEnd(order)) {
    order = solution.value(model.nextVar(order));
    }
    route += " to #" + order;
    }
    output += route + "\n";
    }
    logger.info(output);
    }
    }

    public static void main(String[] args) throws Exception {
    VehicleStartEndLocationsBug problem =
    new VehicleStartEndLocationsBug();
    final int xMax = 20;
    final int yMax = 20;
    final int endTime = 24 * 60;
    final int orders = 50;
    final int vehicles = 10;

    problem.buildOrders(orders,
    xMax,
    yMax);
    problem.buildFleet(vehicles,
    xMax,
    yMax,
    endTime);
    problem.solve(orders, vehicles);
    }
    }