Problem with vrp_global_span.cc (C++, Ubuntu 16)

[Van-NguyenPham]

Hello everyone,
I tried this example but it did not work as I thought: https://developers.google.com/optimization/routing/vrp
Its goal is to minimize longest single route. As I understand, the best solution achieved when number of vehicles equals number of customers. On changing variable "num_vehicles" from 4 to larger value, I got the same result as 4 vehicles. Do I misunderstand anything or this is a bug.
Thank you.

[Mizux]

this example minimize the total travel as well as try to minimize THE longest route.
Also in this sample the first strategy manage to find a good solution so we didn't use the LNS (Local Neighborhood Search).

So we were "lucky" (ed and tweak data), You can try to enable LNS see #550 (comment) but since there is a trade off between the global span cost and the sum of all arc cost you must have a very big coef to make the glabal span the dominant factor and still there is no guarantee that solver find this solution in a reasonable time.

VRP is NP-Hard so unless you brute force all solutions (which is impracticable) it's difficult to reach optimality in any situation...

[Mizux]

After playing a bit with the model, if we add an initial solution

   data['initial_routes'] = [
        [1], [2], [3], [4],
        [5], [6], [7], [8],
        [9], [10], [11], [12],
        [13], [14], [15], [16],
    ]

then

    initial_solution = routing.ReadAssignmentFromRoutes(data['initial_routes'], True)
    print('Initial solution:')
    print_solution(data, manager, routing, initial_solution)

you'll see:

Initial solution:
Route for vehicle 0:
 0 ->  1 -> 0
Distance of the route: 1096m
Route for vehicle 1:
 0 ->  2 -> 0
Distance of the route: 1552m
Route for vehicle 2:
 0 ->  3 -> 0
Distance of the route: 1392m
Route for vehicle 3:
 0 ->  4 -> 0
Distance of the route: 1164m
Route for vehicle 4:
 0 ->  5 -> 0
Distance of the route: 548m
Route for vehicle 5:
 0 ->  6 -> 0
Distance of the route: 1004m
Route for vehicle 6:
 0 ->  7 -> 0
Distance of the route: 388m
Route for vehicle 7:
 0 ->  8 -> 0
Distance of the route: 616m
Route for vehicle 8:
 0 ->  9 -> 0
Distance of the route: 388m
Route for vehicle 9:
 0 ->  10 -> 0
Distance of the route: 1072m
Route for vehicle 10:
 0 ->  11 -> 0
Distance of the route: 1004m
Route for vehicle 11:
 0 ->  12 -> 0
Distance of the route: 776m
Route for vehicle 12:
 0 ->  13 -> 0
Distance of the route: 708m
Route for vehicle 13:
 0 ->  14 -> 0
Distance of the route: 936m
Route for vehicle 14:
 0 ->  15 -> 0
Distance of the route: 1552m
Route for vehicle 15:
 0 ->  16 -> 0
Distance of the route: 1324m
Route for vehicle 16:
 0 -> 0
Distance of the route: 0m
Route for vehicle 17:
 0 -> 0
Distance of the route: 0m
Route for vehicle 18:
 0 -> 0
Distance of the route: 0m
Route for vehicle 19:
 0 -> 0
Distance of the route: 0m

So you can see vehicle 1 0->2->0 : 1552m since we are using Manhattan distance one vehicle can serve several nodes and still have a span of 1552 i.e. not increasing the global span but serve several nodes i.e. reducing the total sum of all arcs...

[Van-NguyenPham]

Thank you for your help, Mizux. You are really helpful.

[Van-NguyenPham]

Sorry, Mizux, but after trying your suggestions, it still does not work. I changed "num_vehicles" to 19 and do following steps but the solution only use 4 vehicles.

1. Change global coefficient:
2. Use local search
3. Add initial solution (what you print is your initial solution, not solution found by solver)
4. Here is full script:

#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 operations_research {
struct DataModel {
  const std::vector<std::vector<int64>> distance_matrix{
      {0, 548, 776, 696, 582, 274, 502, 194, 308, 194, 536, 502, 388, 354, 468,
       776, 662},
      {548, 0, 684, 308, 194, 502, 730, 354, 696, 742, 1084, 594, 480, 674,
       1016, 868, 1210},
      {776, 684, 0, 992, 878, 502, 274, 810, 468, 742, 400, 1278, 1164, 1130,
       788, 1552, 754},
      {696, 308, 992, 0, 114, 650, 878, 502, 844, 890, 1232, 514, 628, 822,
       1164, 560, 1358},
      {582, 194, 878, 114, 0, 536, 764, 388, 730, 776, 1118, 400, 514, 708,
       1050, 674, 1244},
      {274, 502, 502, 650, 536, 0, 228, 308, 194, 240, 582, 776, 662, 628, 514,
       1050, 708},
      {502, 730, 274, 878, 764, 228, 0, 536, 194, 468, 354, 1004, 890, 856, 514,
       1278, 480},
      {194, 354, 810, 502, 388, 308, 536, 0, 342, 388, 730, 468, 354, 320, 662,
       742, 856},
      {308, 696, 468, 844, 730, 194, 194, 342, 0, 274, 388, 810, 696, 662, 320,
       1084, 514},
      {194, 742, 742, 890, 776, 240, 468, 388, 274, 0, 342, 536, 422, 388, 274,
       810, 468},
      {536, 1084, 400, 1232, 1118, 582, 354, 730, 388, 342, 0, 878, 764, 730,
       388, 1152, 354},
      {502, 594, 1278, 514, 400, 776, 1004, 468, 810, 536, 878, 0, 114, 308,
       650, 274, 844},
      {388, 480, 1164, 628, 514, 662, 890, 354, 696, 422, 764, 114, 0, 194, 536,
       388, 730},
      {354, 674, 1130, 822, 708, 628, 856, 320, 662, 388, 730, 308, 194, 0, 342,
       422, 536},
      {468, 1016, 788, 1164, 1050, 514, 514, 662, 320, 274, 388, 650, 536, 342,
       0, 764, 194},
      {776, 868, 1552, 560, 674, 1050, 1278, 742, 1084, 810, 1152, 274, 388,
       422, 764, 0, 798},
      {662, 1210, 754, 1358, 1244, 708, 480, 856, 514, 468, 354, 844, 730, 536,
       194, 798, 0},
  };
  const std::vector<std::vector<int64>> initial_routes{
      {1,},
      {2},
      {3},
      {4},
      {5},
      {6},
      {7},
      {8},
      {9},
      {10},
      {11},
      {12},
      {13},
      {14},
      {15},
      {16},
      {17},
      {18},
      {19},
  };
  const int num_vehicles = 19;
  const RoutingIndexManager::NodeIndex depot{0};
};

//! @brief Print the solution.
//! @param[in] data Data of the problem.
//! @param[in] manager Index manager used.
//! @param[in] routing Routing solver used.
//! @param[in] solution Solution found by the solver.
void PrintSolution(const DataModel& data, const RoutingIndexManager& manager,
                   const RoutingModel& routing, const Assignment& solution) {
  int64 max_route_distance{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 << ":";
    int64 route_distance{0};
    std::stringstream route;
    while (routing.IsEnd(index) == false) {
      route << manager.IndexToNode(index).value() << " -> ";
      int64 previous_index = index;
      index = solution.Value(routing.NextVar(index));
      route_distance += routing.GetArcCostForVehicle(previous_index, index,
                                                     int64{vehicle_id});
    }
    LOG(INFO) << route.str() << manager.IndexToNode(index).value();
    LOG(INFO) << "Distance of the route: " << route_distance << "m";
    max_route_distance = std::max(route_distance, max_route_distance);
  }
  LOG(INFO) << "Maximum of the route distances: " << max_route_distance << "m";
  LOG(INFO) << "";
  LOG(INFO) << "Problem solved in " << routing.solver()->wall_time() << "ms";
}

void VrpGlobalSpan() {
  // Instantiate the data problem.
  DataModel data;

  // Create Routing Index Manager
  RoutingIndexManager manager(data.distance_matrix.size(), data.num_vehicles,
                              data.depot);

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

  // Create and register a transit callback.
  const int transit_callback_index = routing.RegisterTransitCallback(
      [&data, &manager](int64 from_index, int64 to_index) -> int64 {
        // Convert from routing variable Index to distance matrix NodeIndex.
        auto from_node = manager.IndexToNode(from_index).value();
        auto to_node = manager.IndexToNode(to_index).value();
        return data.distance_matrix[from_node][to_node];
      });

  // Define cost of each arc.
  routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index);

  // Add Distance constraint.
  routing.AddDimension(transit_callback_index, 0, 3000,
                       true,  // start cumul to zero
                       "Distance");
  routing.GetMutableDimension("Distance")->SetGlobalSpanCostCoefficient(100000000);
  // add initial solution
  const Assignment* initial_solution =
      routing.ReadAssignmentFromRoutes(data.initial_routes, true);
  
  RoutingSearchParameters searchParameters = DefaultRoutingSearchParameters();
  // enable local search
  searchParameters.set_local_search_metaheuristic(
    LocalSearchMetaheuristic::GUIDED_LOCAL_SEARCH);
  searchParameters.mutable_time_limit()->set_seconds(30);
	searchParameters.set_log_search(false);
	
	// Setting first solution heuristic.
  searchParameters.set_first_solution_strategy(
      FirstSolutionStrategy::PATH_CHEAPEST_ARC);
  
  
  // Solve the problem.
  const Assignment* solution = routing.SolveWithParameters(searchParameters);
  

  // Print solution on console.
  PrintSolution(data, manager, routing, *solution);
}
}  // namespace operations_research

int main(int argc, char** argv) {
  operations_research::VrpGlobalSpan();
  return EXIT_SUCCESS;
}

[Mizux]

As I said this is manhattan distance and as you can see 0 -> 2 -> 0 is the same distance than 0 -> 8 -> 2 -> 6 -> 5 -> 0 i.e. 1552m so global span remain the same BUT it better to use less vehicle to reduce the sum of all vehicle span, i.e. here we have a special case

So yes, I displayed the first solution to figure out this (i.e. visiting several node cost the same travel distance than visiting one).

You can try to add an unary callback to count stop and add a globalspan constraint on this counter dimension, see the last discussion on our discord...

[Van-NguyenPham]

Thank you Mizux.