Please provide a timeline on fixing issue #1730

[juntek]

I need to know whether issue #1730 will be fixed shortly so I can wait until it is fixed, or not. I cannot wait a year or so.
Without vehicle breaks, there is no use for me of the OR-Tools routing library at all, and I would have to search for other options.

[juntek]

Below is the code in C++ that illustrates the issue. The solver can't find the solution once you uncomment the vehicle breaks section.

#include <iostream>
#include <string>
#include <vector>

#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"

namespace ort = operations_research;

struct DataModel {
    const std::vector<std::vector<int64>> time_matrix = {	// values are in seconds
        {0, 205, 200, 257, 606, 638, 1031, 1186, 1187, 1018, 953, 17, 290, 279, 910, 895, 884, 888, 682, 672, 967},
        {283, 0, 41, 97, 524, 556, 949, 1104, 1105, 936, 871, 279, 431, 420, 1028, 1013, 1002, 1006, 804, 813, 1085},
        {276, 105, 0, 56, 511, 543, 928, 1084, 1084, 916, 850, 273, 491, 481, 1076, 1061, 1050, 1054, 853, 866, 1134},
        {298, 244, 239, 0, 455, 487, 872, 1027, 1028, 860, 794, 294, 539, 529, 1056, 1041, 1030, 1034, 832, 845, 1113},
        {642, 548, 543, 483, 0, 99, 586, 868, 866, 749, 683, 654, 726, 715, 1106, 1091, 1080, 1084, 882, 896, 1164},
        {676, 582, 578, 517, 104, 0, 487, 769, 767, 668, 689, 688, 760, 750, 1141, 1126, 1115, 1119, 917, 930, 1198},
        {1024, 952, 947, 849, 706, 602, 0, 334, 332, 233, 202, 1020, 1129, 1119, 1510, 1495, 1484, 1488, 1286, 1300, 1567},
        {1175, 1103, 1098, 1000, 902, 844, 310, 0, 102, 187, 402, 1171, 1281, 1270, 1661, 1646, 1635, 1639, 1437, 1451, 1719},
        {1218, 1146, 1142, 1044, 945, 875, 341, 78, 0, 231, 446, 1215, 1324, 1314, 1705, 1690, 1679, 1683, 1481, 1494, 1762},
        {1021, 949, 945, 847, 748, 748, 227, 202, 203, 0, 249, 1018, 1127, 1117, 1508, 1493, 1482, 1486, 1284, 1297, 1565},
        {962, 890, 885, 787, 689, 688, 216, 437, 437, 269, 0, 959, 1068, 1057, 1448, 1433, 1422, 1426, 1225, 1238, 1506},
        {20, 198, 194, 250, 626, 658, 1051, 1206, 1207, 1038, 973, 0, 310, 299, 930, 915, 904, 908, 702, 692, 987},
        {292, 372, 368, 424, 697, 729, 1122, 1277, 1278, 1109, 1044, 308, 0, 10, 629, 684, 659, 601, 392, 382, 716},
        {281, 362, 358, 414, 687, 719, 1112, 1267, 1267, 1099, 1034, 298, 10, 0, 639, 694, 670, 611, 403, 393, 727},
        {938, 1025, 1021, 1054, 1137, 1170, 1563, 1718, 1718, 1550, 1485, 955, 765, 775, 0, 65, 106, 68, 365, 355, 163},
        {938, 1026, 1021, 1054, 1138, 1170, 1563, 1718, 1719, 1550, 1485, 955, 824, 834, 154, 0, 70, 120, 424, 414, 175},
        {979, 1066, 1062, 1094, 1178, 1210, 1603, 1759, 1759, 1591, 1525, 995, 802, 813, 127, 40, 0, 105, 403, 393, 200},
        {960, 1047, 1043, 1075, 1159, 1191, 1584, 1739, 1740, 1572, 1506, 976, 710, 721, 43, 92, 67, 0, 311, 301, 124},
        {712, 800, 795, 828, 912, 944, 1337, 1492, 1493, 1324, 1259, 729, 477, 488, 315, 370, 346, 287, 0, 49, 402},
        {800, 888, 884, 916, 1000, 1032, 1425, 1580, 1581, 1413, 1347, 817, 542, 552, 354, 408, 384, 325, 131, 0, 441},
        {954, 1042, 1037, 1070, 1154, 1186, 1579, 1734, 1734, 1566, 1501, 971, 885, 896, 280, 330, 310, 252, 486, 476, 0}
    };

    const std::vector<std::pair<int64, int64>> time_windows = { // values are in seconds
        {0, 3600},    // depot
        {0, 28800},{0, 28800},{0, 28800},{0, 28800},{0, 28800},{0, 28800},{0, 28800},{0, 28800},{0, 28800},{0, 28800},
        {0, 28800},{0, 28800},{0, 28800},{0, 28800},{0, 28800},{0, 28800},{0, 28800},{0, 28800},{0, 28800},{0, 28800}
    };

    const std::vector<int64> service_times = { // values are in seconds
        0,	// depot
        4200,  1800, 2400, 1800, 1800, 1800, 1800, 1800, 1800, 1800,
        4200, 5100, 1800, 2400, 2700, 5100, 2700, 1800, 5100, 1800
    };

    const int num_vehicles = 2;

    const ort::RoutingIndexManager::NodeIndex depot{ 0 };
};

const std::string KTime{ "Time" };

void PrintSolution(const DataModel& data, const ort::RoutingIndexManager& manager, const ort::RoutingModel& routing, const ort::Assignment& solution) {
    const ort::RoutingDimension& time_dimension = routing.GetDimensionOrDie(KTime);
    int64 total_time{ 0 };
    for (int vehicle_id = 0; vehicle_id < data.num_vehicles; ++vehicle_id) {
        int64 index = routing.Start(vehicle_id);
        LOG(INFO) << "Route for vehicle " << vehicle_id << ":";
        std::ostringstream route;
        while (routing.IsEnd(index) == false) {
            auto time_var = time_dimension.CumulVar(index);
            route << manager.IndexToNode(index).value() << " Time("
                << solution.Min(time_var) / 60.0 << ", " << solution.Max(time_var) / 60.0
                << ") -> ";
            index = solution.Value(routing.NextVar(index));
        }
        auto time_var = time_dimension.CumulVar(index);
        LOG(INFO) << route.str() << manager.IndexToNode(index).value() << " Time("
            << solution.Min(time_var) / 60.0 << ", " << solution.Max(time_var) / 60.0 << ")";
        LOG(INFO) << "Time of the route: " << solution.Min(time_var) / 60.0 << "min";
        total_time += solution.Min(time_var);
    }
    LOG(INFO) << "Total time of all routes: " << total_time / 60.0 << "min";
    LOG(INFO) << "Problem solved in " << routing.solver()->wall_time() << "ms";
}

int main(int argc, char* argv[])
{
    DataModel data;

    ort::RoutingIndexManager manager(data.time_matrix.size(), data.num_vehicles, data.depot);
    ort::RoutingModel routingModel(manager);

    const int transit_callback_index = routingModel.RegisterTransitCallback(
        [&data, &manager](int64 from_index, int64 to_index) -> int64 {
            auto from_node = manager.IndexToNode(from_index).value();
            auto to_node = manager.IndexToNode(to_index).value();
            return data.service_times[from_node] + data.time_matrix[from_node][to_node];
        }
    );

    routingModel.SetArcCostEvaluatorOfAllVehicles(transit_callback_index);

    routingModel.AddDimension(transit_callback_index,
        int64{ 1 * 3600 }, // An upper bound for slack (the wait times at the locations)
        int64{ 10 * 3600 }, // Maximum time per vehicle (an upper bound for the total time over each vehicle's route)
        false, // Don't force start cumul to zero
        KTime);

    ort::RoutingDimension* timeDimension = routingModel.GetMutableDimension(KTime);

    // Add time window constraints for each location except depot
    for (int i = 1; i < data.time_windows.size(); ++i) {
        int64 index = manager.NodeToIndex(ort::RoutingIndexManager::NodeIndex(i));
        timeDimension->CumulVar(index)->SetRange(data.time_windows[i].first, data.time_windows[i].second);
    }

    // Add time window constraints for each vehicle start node
    for (int vehicle = 0; vehicle < data.num_vehicles; ++vehicle) {
        int64 index = routingModel.Start(vehicle);
        timeDimension->CumulVar(index)->SetRange(data.time_windows[0].first, data.time_windows[0].second);
    }

    // Instantiate route start and end times to produce feasible times
    for (int vehicle = 0; vehicle < data.num_vehicles; ++vehicle) {
        routingModel.AddVariableMinimizedByFinalizer(timeDimension->CumulVar(routingModel.Start(vehicle)));
        routingModel.AddVariableMinimizedByFinalizer(timeDimension->CumulVar(routingModel.End(vehicle)));
    }

    // Add vehicle breaks: 45 min between 1:00 and 3:00
/*  uncomment this  
    ort::Solver* solver = routingModel.solver();
    for (int vehicle = 0; vehicle < data.num_vehicles; ++vehicle) {
        std::stringstream ss;
        ss << "Break on vehicle " << vehicle;
        ort::IntervalVar* break_interval = solver->MakeFixedDurationIntervalVar(1*3600, 3*3600, 45*60, false, ss.str());
        timeDimension->SetBreakIntervalsOfVehicle({break_interval}, vehicle, data.service_times);
    } */

    ort::RoutingSearchParameters parameters = ort::DefaultRoutingSearchParameters();
    parameters.set_first_solution_strategy(ort::FirstSolutionStrategy::PATH_CHEAPEST_ARC);

    const ort::Assignment* solution = routingModel.SolveWithParameters(parameters);
    if (solution != nullptr) {
        PrintSolution(data, manager, routingModel, *solution);
    } else {
        std::cout << "No solution found" << std::endl;
    }

    return EXIT_SUCCESS;
}