Different start and end locations in Google OR-Tools

1

I have been playing with the VRP as provided by Google and I wanted to allow different start and end locations in my program. Sounds simple enough... But when I do add the different start and end locations I am given the error as follows:

WARNING: Logging before InitGoogleLogging() is written to STDERR
F00-1 -1:-1:-1.529052 27172 routing.cc:1565] Check failed: kUnassigned != indices[i] (-1 vs. -1) 
*** Check failure stack trace: ***

Process finished with exit code -1073740791 (0xC0000409)

This is my code:

package com.google.ortools.constraintsolver.samples;
import com.google.ortools.Loader;
import com.google.ortools.constraintsolver.*;
import com.google.protobuf.Duration;
import org.json.simple.JSONArray;
import org.json.simple.JSONObject;
import org.json.simple.parser.*;

import java.util.ArrayList;

/** Minimal VRP.*/
public class MultipleStart {

    private static Double[][] computeManhattanDistance (Double[][] locations) {
        Double[][] distanceMatrix = new Double[locations.length][locations.length];
        for( int startNode = 0 ; startNode < locations.length ; startNode++ ) {
            for( int endNode = 0 ; endNode < locations.length ; endNode++ ) {
                distanceMatrix[startNode][endNode] = (Math.abs((locations[startNode][0] - locations[endNode][0])) +
                        Math.abs(locations[startNode][1] - locations[endNode][1]));
            }
        }
        return distanceMatrix;
    }

    /// @brief Print the solution.
    static void printSolution(
            int vehicleNumber, RoutingModel routing, RoutingIndexManager manager, Assignment solution) {
        // Display dropped nodes.
        JSONObject result = new JSONObject();
        ArrayList<String> droppedNodes = new ArrayList<>();
        for (int node = 0; node < routing.size(); ++node) {
            if (routing.isStart(node) || routing.isEnd(node)) {
                continue;
            }
            if (solution.value(routing.nextVar(node)) == node) {
                droppedNodes.add( " " + manager.indexToNode(node) );
            }
        }
        result.put("droppedNodes", droppedNodes);
        // Display routes
        JSONObject routes = new JSONObject();
        ArrayList<JSONObject> routingData = new ArrayList<>();
        long totalDistance = 0;
        for (int i = 0; i < vehicleNumber ; i++) {
            long index = routing.start(i);
            ArrayList<Long> vehicleRoute = new ArrayList<>();

            long routeDistance = 0;
            while (!routing.isEnd(index)) {
                long nodeIndex = manager.indexToNode(index);
                vehicleRoute.add(nodeIndex);
                long previousIndex = index;
                index = solution.value(routing.nextVar(index));
                routeDistance += routing.getArcCostForVehicle(previousIndex, index, i);
            }
            vehicleRoute.add((long)manager.indexToNode(index));
            routes.put("Vehicle " + (i+1), vehicleRoute);
            totalDistance += routeDistance;
        }
        routingData.add(routes);
        result.put("routingData", routingData);

        result.put("Total Distance", totalDistance);
        System.out.println(result);
    }

    public static void main(String[] args) throws Exception {
        Loader.loadNativeLibraries();

        JSONObject data = (JSONObject) new JSONParser().parse(args[0]);

        JSONArray locationData = (JSONArray) data.get("locations");

        Double[][] locations = new Double[locationData.size()][2];

        for(int i=0 ; i<locationData.size() ; i++) {
            JSONArray location = (JSONArray) locationData.get(i);
            locations[i][0] =  Double.valueOf((String) location.get(0));
            locations[i][1] =  Double.valueOf((String) location.get(1));
        }

        Double[][] distanceMatrix = computeManhattanDistance(locations);

        long vehicleNumbers =   (long) data.get("vehicleNumber");
        JSONArray starts    =   (JSONArray) data.get("starts");
        JSONArray ends      =   (JSONArray) data.get("ends");

        long[] starting     =   new long[starts.size()];
        for(int i=0 ; i< starts.size() ; i++)
            starting[i] =   (long) starts.get(i);

        int[] start         =   new int[starting.length];
        for(int i=0 ; i< starting.length ; i++)
            start[i]    =   (int) starting[i];

        long[] endings      =   new long[ends.size()];
        for(int i=0 ; i< ends.size() ; i++)
            endings[i]  =   (long) ends.get(i);

        int[] end   =   new int[endings.length];
        for(int i=0 ; i< endings.length ; i++)
            end[i]  =   (int) endings[i];

        // Create Routing Index Manager
        RoutingIndexManager manager =
                new RoutingIndexManager(distanceMatrix.length, (int) vehicleNumbers, start, end);

        // Create Routing Model.
        RoutingModel routing = new RoutingModel(manager);

        // Create and register a transit callback.
        final int transitCallbackIndex = routing.registerTransitCallback((long fromIndex, long toIndex) -> {
            // Convert from routing variable Index to user NodeIndex.
            int fromNode = manager.indexToNode(fromIndex);
            int toNode = manager.indexToNode(toIndex);
            return (distanceMatrix[fromNode][toNode]).longValue();
        });

        if(data.get("demands") != null && data.get("vehicleCapacities") != null) {
            JSONArray demandArray = (JSONArray) data.get("demands");
            long[] demands = new long[demandArray.size()];

            for(int i=0 ; i<demandArray.size() ; i++) {
                demands[i] = (long) demandArray.get(i);
            }

            // Add Capacity constraint.
            final int demandCallbackIndex = routing.registerUnaryTransitCallback((long fromIndex) -> {
                // Convert from routing variable Index to user NodeIndex.
                int fromNode = manager.indexToNode(fromIndex);
                return demands[fromNode];
            });

            long capacities = (long) data.get("vehicleCapacities");
            long[] vehicleCapacities = new long[(int)vehicleNumbers];
            for(int i=0 ; i<vehicleNumbers ; i++)
                vehicleCapacities[i] = capacities;

            routing.addDimensionWithVehicleCapacity(demandCallbackIndex, 0,
                    vehicleCapacities,
                    true,
                    "Capacity");

            long penalty = 1500;
            for (int i = 1; i < distanceMatrix.length; ++i) {
                routing.addDisjunction(new long[] {manager.nodeToIndex(i)}, penalty);
            }
        }

        // Define cost of each arc.
        routing.setArcCostEvaluatorOfAllVehicles(transitCallbackIndex);

        String priority = (String) data.get("priority");
        // Add Distance constraint.
        routing.addDimension(transitCallbackIndex,
                20,
                3000,
                false, // start cumul to zero
                priority);
        RoutingDimension distanceDimension = routing.getMutableDimension(priority);
        distanceDimension.setGlobalSpanCostCoefficient(100);

        // Define Transportation Requests.
        Solver solver = routing.solver();

        if(data.get("pickupDeliveries") != null) {
            JSONArray indexs = (JSONArray) data.get("pickupDeliveries");
            long [][] pickupsDeliveries = new long[indexs.size()][2];

            for(int i =0 ; i< indexs.size() ; i++) {
                JSONArray temp = (JSONArray) indexs.get(i);
                pickupsDeliveries[i][0] = (long) temp.get(0);
                pickupsDeliveries[i][1] = (long) temp.get(1);
            }

            for (long[] request : pickupsDeliveries) {
                long pickupIndex = manager.nodeToIndex((int)request[0]);
                long deliveryIndex = manager.nodeToIndex((int)request[1]);
                routing.addPickupAndDelivery(pickupIndex, deliveryIndex);
                solver.addConstraint(
                        solver.makeEquality(routing.vehicleVar(pickupIndex), routing.vehicleVar(deliveryIndex)));
                solver.addConstraint(solver.makeLessOrEqual(
                        distanceDimension.cumulVar(pickupIndex), distanceDimension.cumulVar(deliveryIndex)));
            }
        }

        // Setting first solution heuristic.
        RoutingSearchParameters searchParameters =
                main.defaultRoutingSearchParameters()
                        .toBuilder()
                        .setFirstSolutionStrategy(FirstSolutionStrategy.Value.GLOBAL_CHEAPEST_ARC)
                        .setLocalSearchMetaheuristic(LocalSearchMetaheuristic.Value.GUIDED_LOCAL_SEARCH)
                        .setTimeLimit(Duration.newBuilder().setSeconds(30).build())
                        .build();

        // Solve the problem.
        Assignment solution = routing.solveWithParameters(searchParameters);

        // Print solution on console.
        printSolution((int) vehicleNumbers, routing, manager, solution);
    }
}

This is my JSON data:

{
    "locations": [
        [
            "30.718785",
            "76.810374"
        ],
        [
            "30.704649",
            "76.717873"
        ],
        [
            "52.922530",
            "-1.474619"
        ],
        [
            "30.704649",
            "76.717873"
        ],
        [
            "28.638604",
            "77.209890"
        ],
        [
            "23.766164",
            "90.358873"
        ],
        [
            "22.572646",
            "88.363895"
        ],
        [
            "50.674522",
            "-120.327267"
        ],
        [
            "19.220113",
            "72.974845"
        ],
        [
            "30.733315",
            "76.779418"
        ],
        [
            "30.733315",
            "76.779418"
        ],
        [
            "30.733315",
            "76.779418"
        ],
        [
            "30.733315",
            "76.779418"
        ]
    ],
    "pickupDeliveries": [
        [
            0,
            1
        ],
        [
            5,
            6
        ]
    ],
    "demands": [
        1,
        1,
        1,
        1,
        1,
        1,
        1,
        1,
        1,
        0,
        0,
        0,
        0
    ],
    "vehicleNumber": 2,
    "vehicleCapacities": 6,
    "priority": "Distance",
    "starts": [
        9,
        11
    ],
    "ends": [
        10,
        12
    ]
}
java
or-tools
asked on Stack Overflow Mar 16, 2021 by Angad Singh • edited Mar 16, 2021 by mkrieger1

0 Answers

Nobody has answered this question yet.


User contributions licensed under CC BY-SA 3.0