CODEWITHSUNDEEP
or-toolsvehicle-routing
Tamanampudi Sri Rama Reddy
Tamanampudi Sri Rama Reddy

Reputation: 51

Capacitated Vehicle Routing Problem - Google OR tools

I am running VRP with capacity constraints. Here is my code.

        List<Order> orders =. getOrders()
        final DataModel data = new DataModel();
        data.distanceMatrix = distanceMatrix.constructDistanceMatrix(orders);
        data.vehicleNumber = noOfVehicles;
        data.vehicleCapacities = new long[noOfVehicles];
        data.depot = 0;
        data.demands = new long[orders.size() + 1];
        capacityAndDemandMatrix.prefillCapacitiesAndDemands(data.demands, data.getVehicleCapacities(), orders);

        // Create Routing Index Manager
        RoutingIndexManager manager =
                new RoutingIndexManager(data.distanceMatrix.length, data.vehicleNumber, data.depot);

        // 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 data.distanceMatrix[fromNode][toNode];
                });


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

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

        routing.addDimensionWithVehicleCapacity(demandCallbackIndex, 0, // null capacity slack
                                                data.vehicleCapacities, // vehicle maximum capacities
                                                true, // start cumul to zero
                                                "Capacity");

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

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

        // Print solution on console.
        return constructRoutes(data, routing, manager, solution, orders);

Algorithm is working as expected, giving overall shortest paths for given vehicles. If I give more number of orders which can't be fulfilled by no of Vehicles. It is providing "No Solution".

For example, 40 orders and 2 vehicles are there. Each vehicle can carry only 10 orders. Currently, Algorithm not giving any solution in this case. But I need best solution mapping 20 orders for 2 vehicles out of 40.

Is it possible to change something in OR-Tools code, so that it can leave few orders but need to adhere capacity constraints and give possible best solution all the time?

Upvotes: 2

Views: 827

Answers (1)

Mizux
Mizux

Reputation: 9291

You should take a look at "Penalties and Dropping Visits" documentation...

https://developers.google.com/optimization/routing/penalties

Upvotes: 1

Related Questions