VRP: constraint on sum of cumul vars

[Michal Burda]

Dear ORTools discussion forum,

For my VRP problem, I try to implement the following contraint: for a selected set of vehicles (not all vehicles), the sum of their total distances has to be below some threshold. I have implemented it in C++ by adding the following constraint to the solver:

 std::vector<IntVar*> cumulVars;
    for (int i = 0; i < selectedVehicles; ++i) {
        cumulVars.push_back(distDimension->CumulVar(routing.End(i)));
    }
    solver->AddConstraint(solver->MakeSumLessOrEqual(cumulVars, limit));

This works well on small problems, however, the solver often fails to find any initial solution on large problems regardless of which First Solution Strategy I use. Please, could anybody suggest some solution of how to force the constraint to be respected but still being able to obtain a solution even for large problems?

Thank you, in advance.

The full toy example code working on small problems is as follows:

#include <vector>

#include "google/protobuf/duration.pb.h"
#include "ortools/constraint_solver/routing.h"
#include "ortools/constraint_solver/routing_enums.pb.h"
#include "ortools/constraint_solver/routing_index_manager.h"
#include "ortools/constraint_solver/routing_parameters.h"

using int64 = int64_t;

using namespace operations_research;

void printSolution(const int vehicleCount, const RoutingIndexManager& manager,
                   const RoutingModel& routing, const Assignment& solution)
{
    int64 total_distance{0};
    for (int vehicle_id = 0; vehicle_id < vehicleCount; ++vehicle_id) {
        int64 index = routing.Start(vehicle_id);
        LOG(INFO) << "Route for Vehicle " << vehicle_id << ":";
        int64 route_distance{0};
        std::stringstream route;
        while (routing.IsEnd(index) == false) {
            int64 nodeIndex = manager.IndexToNode(index).value();
            route << nodeIndex << " -> ";
            int64 previousIndex = index;
            index = solution.Value(routing.NextVar(index));
            route_distance += routing.GetArcCostForVehicle(previousIndex, index,
                                                           int64{vehicle_id});
        }
        LOG(INFO) << route.str() << manager.IndexToNode(index).value();
        LOG(INFO) << "Distance of the route: " << route_distance << "m";
        total_distance += route_distance;
    }
    LOG(INFO) << "Total distance of all routes: " << total_distance << "m";
    LOG(INFO) << "Problem solved in " << routing.solver()->wall_time() << "ms";
}

int main(int argc, char** argv)
{
    const std::vector<std::vector<int64>> distMatrix {
        { 0, 2, 2, 2, 2, 2 },
        { 2, 0, 2, 2, 2, 2 },
        { 2, 2, 0, 2, 2, 2 },
        { 2, 2, 2, 0, 2, 2 },
        { 2, 2, 2, 2, 0, 2 },
        { 2, 2, 2, 2, 2, 0 },
    };

    const std::vector<RoutingIndexManager::NodeIndex> starts {
        RoutingIndexManager::NodeIndex{0},
        RoutingIndexManager::NodeIndex{0},
        RoutingIndexManager::NodeIndex{0},
        RoutingIndexManager::NodeIndex{0},
    };

    const std::vector<RoutingIndexManager::NodeIndex> ends {
        RoutingIndexManager::NodeIndex{1},
        RoutingIndexManager::NodeIndex{1},
        RoutingIndexManager::NodeIndex{1},
        RoutingIndexManager::NodeIndex{1},
    };

    const std::vector<int64> capacities { 2, 2, 2, 1 };
    const int vehicleCount = capacities.size();

    RoutingIndexManager manager(distMatrix.size(), vehicleCount, starts, ends);
    RoutingModel routing(manager);

    // Create and register a transit callback.
    const int transitCallback = routing.RegisterTransitCallback(
                [&distMatrix, &manager](int64 fromIndex, int64 toIndex) -> int64 {
        int fromNode = manager.IndexToNode(fromIndex).value();
        int toNode = manager.IndexToNode(toIndex).value();

        if (fromNode == 0 && toNode == 1) {
            return 0;
        }

        return distMatrix[fromNode][toNode];
    });

    routing.AddDimension(
        transitCallback,    // transit callback index
        int64{0},                 // null capacity slack
        int64{1000},  // vehicle maximum vehicleCapacities
        true,                     // start cumul to zero
        "Distance"
    );

    routing.SetArcCostEvaluatorOfAllVehicles(transitCallback);

    // Add Capacity constraint.
    const int demand_callback_index = routing.RegisterUnaryTransitCallback(
        [&manager](int64 from_index) -> int64 {
            int from_node = manager.IndexToNode(from_index).value();
           
            return (from_node <= 1) ? 0 : 1;
        }
    );
   
    routing.AddDimensionWithVehicleCapacity(
        demand_callback_index,    // transit callback index
        int64{0},                 // null capacity slack
        capacities,  // vehicle maximum vehicleCapacities
        true,                     // start cumul to zero
        "Capacity"
    );

    Solver *solver = routing.solver();
    RoutingDimension *distDimension = routing.GetMutableDimension("Distance");
    const int64 limit = 10;

    // Hard constraint:
    std::vector<IntVar*> cumulVars;
    for (int i = 0; i < vehicleCount - 1; ++i) {
        cumulVars.push_back(distDimension->CumulVar(routing.End(i)));
    }
    solver->AddConstraint(solver->MakeSumLessOrEqual(cumulVars, limit));

    RoutingSearchParameters searchParams = DefaultRoutingSearchParameters();
    searchParams.mutable_time_limit()->set_seconds(1);

    const Assignment* solution = routing.SolveWithParameters(searchParams);
    printSolution(vehicleCount, manager, routing, *solution);

    return 0;
}