Nesta seção, explicamos como lidar com problemas de roteamento que não têm da solução, devido a restrições. Por exemplo, se você receber um VRP com restrições de capacidade em que a demanda em todos os locais excede a capacidade total os veículos, não há solução possível. Nesses casos, os veículos precisam recusar visitas a alguns locais. O problema é como decidir quais visitas remover.
Para resolver o problema, incluímos novos custos, chamados de penalidades. em todos os locais. Sempre que uma visita a um local cai, a penalidade é somado à distância total percorrida. O solucionador encontra uma rota minimiza a distância total mais a soma das penalidades para todos os pontos em vários locais.
Por exemplo, considere o VRP simples com restrições de capacidade dadas gráfico abaixo, no qual os números ao lado dos três locais (exceto os depósito) são demandas.
Suponha que haja apenas um veículo com capacidade para 50 pessoas. Ele não pode acessar os três
locais, A, B e C, porque a demanda total é de 60. Para resolver o problema,
você atribui uma penalidade grande, digamos 100, a cada local. Depois
detectando que o problema é inviável, o solucionador descarta o local B e
retorna a seguinte rota: Depot -> A -> C -> Depot
Este é o trajeto mais curto que visita dois dos três locais (a distância é 55).
Tamanhos das penalidades
No exemplo acima, escolhemos penalidades maiores do que a soma de todas as distâncias entre locais (excluindo a estação). Por isso, depois de em um local para tornar o problema viável, o solucionador não vai locais adicionais, pois a penalidade seria ultrapassada de redução na distância de deslocamento.
Considerando que você deseja fazer o maior número possível de entregas, isso dá uma satisfatória para o problema.
Se você não precisar fazer o maior número possível de entregas, atribuir penalidades menores. Nesse caso, o solucionador pode remover mais locais do que é necessária para tornar o problema viável. Por exemplo, é possível fazer isso se há custos adicionais, além do custo básico da viagem, para visitar determinados em vários locais.
Exemplo
Em seguida, apresentamos um exemplo maior de VRP que pode ser resolvido com penalidades. O exemplo é semelhante ao anterior exemplo de CVRP, mas desta vez aumentamos algumas da demanda, forçando alguns veículos a abandonar as visitas.
Confira abaixo um gráfico com os locais e as novas demandas.
Resolução do exemplo com ferramentas OR
As seções a seguir explicam como resolver o exemplo com as ferramentas OR.
Criar os dados
Os dados deste exemplo incluem os dados dos grupos exemplo de VRP e adiciona as seguintes demandas: e capacidades:
Python
data["demands"] = [0, 1, 1, 3, 6, 3, 6, 8, 8, 1, 2, 1, 2, 6, 6, 8, 8] data["vehicle_capacities"] = [15, 15, 15, 15]
C++
const std::vector<int64_t> demands{ 0, 1, 1, 3, 6, 3, 6, 8, 8, 1, 2, 1, 2, 6, 6, 8, 8, }; const std::vector<int64_t> vehicle_capacities{15, 15, 15, 15};
Java
public final long[] demands = {0, 1, 1, 3, 6, 3, 6, 8, 8, 1, 2, 1, 2, 6, 6, 8, 8};
public final long[] vehicleCapacities = {15, 15, 15, 15};C#
public long[] Demands = { 0, 1, 1, 3, 6, 3, 6, 8, 8, 1, 2, 1, 2, 6, 6, 8, 8 };
public long[] VehicleCapacities = { 15, 15, 15, 15 };Adicionar as restrições de capacidade e penalidades
O código a seguir adiciona o callback de demanda e as restrições de capacidade
penalidades usando o
AddDisjunction
.
Python
def demand_callback(from_index): """Returns the demand of the node.""" # Convert from routing variable Index to demands NodeIndex. from_node = manager.IndexToNode(from_index) return data["demands"][from_node] demand_callback_index = routing.RegisterUnaryTransitCallback(demand_callback) routing.AddDimensionWithVehicleCapacity( demand_callback_index, 0, # null capacity slack data["vehicle_capacities"], # vehicle maximum capacities True, # start cumul to zero "Capacity", ) # Allow to drop nodes. penalty = 1000 for node in range(1, len(data["distance_matrix"])): routing.AddDisjunction([manager.NodeToIndex(node)], penalty)
C++
const int demand_callback_index = routing.RegisterUnaryTransitCallback( [&data, &manager](const int64_t from_index) -> int64_t { // Convert from routing variable Index to demand NodeIndex. const int from_node = manager.IndexToNode(from_index).value(); return data.demands[from_node]; }); routing.AddDimensionWithVehicleCapacity( demand_callback_index, // transit callback index int64_t{0}, // null capacity slack data.vehicle_capacities, // vehicle maximum capacities true, // start cumul to zero "Capacity"); // Allow to drop nodes. int64_t penalty{1000}; for (int i = 1; i < data.distance_matrix.size(); ++i) { routing.AddDisjunction( {manager.NodeToIndex(RoutingIndexManager::NodeIndex(i))}, penalty); }
Java
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"); // Allow to drop nodes. long penalty = 1000; for (int i = 1; i < data.distanceMatrix.length; ++i) { routing.addDisjunction(new long[] {manager.nodeToIndex(i)}, penalty); }
C#
int demandCallbackIndex = routing.RegisterUnaryTransitCallback((long fromIndex) => { // Convert from routing variable Index to // demand NodeIndex. var 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"); // Allow to drop nodes. long penalty = 1000; for (int i = 1; i < data.DistanceMatrix.GetLength(0); ++i) { routing.AddDisjunction(new long[] { manager.NodeToIndex(i) }, penalty); }
Nesse contexto, uma disjunção é simplesmente uma variável que o solucionador usa para decidir se quer incluir um determinado local na solução. Neste exemplo, adiciona a mesma penalidade a todos os locais, mas, em geral, você pode adicionar penalidades diferentes para locais diferentes.
Adicionar a impressora da solução
A impressora da solução, mostrada abaixo, é semelhante à da exemplo de CVRP, mas também exibe o os locais removidos.
Python
def print_solution(data, manager, routing, assignment): """Prints assignment on console.""" print(f"Objective: {assignment.ObjectiveValue()}") # Display dropped nodes. dropped_nodes = "Dropped nodes:" for node in range(routing.Size()): if routing.IsStart(node) or routing.IsEnd(node): continue if assignment.Value(routing.NextVar(node)) == node: dropped_nodes += f" {manager.IndexToNode(node)}" print(dropped_nodes) # Display routes total_distance = 0 total_load = 0 for vehicle_id in range(data["num_vehicles"]): index = routing.Start(vehicle_id) plan_output = f"Route for vehicle {vehicle_id}:\n" route_distance = 0 route_load = 0 while not routing.IsEnd(index): node_index = manager.IndexToNode(index) route_load += data["demands"][node_index] plan_output += f" {node_index} Load({route_load}) -> " previous_index = index index = assignment.Value(routing.NextVar(index)) route_distance += routing.GetArcCostForVehicle( previous_index, index, vehicle_id ) plan_output += f" {manager.IndexToNode(index)} Load({route_load})\n" plan_output += f"Distance of the route: {route_distance}m\n" plan_output += f"Load of the route: {route_load}\n" print(plan_output) total_distance += route_distance total_load += route_load print(f"Total Distance of all routes: {total_distance}m") print(f"Total Load of all routes: {total_load}")
C++
//! @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) { // Display dropped nodes. std::ostringstream dropped_nodes; for (int64_t node = 0; node < routing.Size(); ++node) { if (routing.IsStart(node) || routing.IsEnd(node)) continue; if (solution.Value(routing.NextVar(node)) == node) { dropped_nodes << " " << manager.IndexToNode(node).value(); } } LOG(INFO) << "Dropped nodes:" << dropped_nodes.str(); // Display routes int64_t total_distance{0}; int64_t total_load{0}; for (int vehicle_id = 0; vehicle_id < data.num_vehicles; ++vehicle_id) { int64_t index = routing.Start(vehicle_id); LOG(INFO) << "Route for Vehicle " << vehicle_id << ":"; int64_t route_distance{0}; int64_t route_load{0}; std::ostringstream route; while (!routing.IsEnd(index)) { const int node_index = manager.IndexToNode(index).value(); route_load += data.demands[node_index]; route << node_index << " Load(" << route_load << ") -> "; const int64_t previous_index = index; index = solution.Value(routing.NextVar(index)); route_distance += routing.GetArcCostForVehicle(previous_index, index, int64_t{vehicle_id}); } LOG(INFO) << route.str() << manager.IndexToNode(index).value(); LOG(INFO) << "Distance of the route: " << route_distance << "m"; LOG(INFO) << "Load of the route: " << route_load; total_distance += route_distance; total_load += route_load; } LOG(INFO) << "Total distance of all routes: " << total_distance << "m"; LOG(INFO) << "Total load of all routes: " << total_load; LOG(INFO) << ""; LOG(INFO) << "Advanced usage:"; LOG(INFO) << "Problem solved in " << routing.solver()->wall_time() << "ms"; }
Java
/// @brief Print the solution. static void printSolution( DataModel data, RoutingModel routing, RoutingIndexManager manager, Assignment solution) { // Solution cost. logger.info("Objective: " + solution.objectiveValue()); // Inspect solution. // Display dropped nodes. String droppedNodes = "Dropped nodes:"; for (int node = 0; node < routing.size(); ++node) { if (routing.isStart(node) || routing.isEnd(node)) { continue; } if (solution.value(routing.nextVar(node)) == node) { droppedNodes += " " + manager.indexToNode(node); } } logger.info(droppedNodes); // Display routes long totalDistance = 0; long totalLoad = 0; for (int i = 0; i < data.vehicleNumber; ++i) { long index = routing.start(i); logger.info("Route for Vehicle " + i + ":"); long routeDistance = 0; long routeLoad = 0; String route = ""; while (!routing.isEnd(index)) { long nodeIndex = manager.indexToNode(index); routeLoad += data.demands[(int) nodeIndex]; route += nodeIndex + " Load(" + routeLoad + ") -> "; long previousIndex = index; index = solution.value(routing.nextVar(index)); routeDistance += routing.getArcCostForVehicle(previousIndex, index, i); } route += manager.indexToNode(routing.end(i)); logger.info(route); logger.info("Distance of the route: " + routeDistance + "m"); totalDistance += routeDistance; totalLoad += routeLoad; } logger.info("Total Distance of all routes: " + totalDistance + "m"); logger.info("Total Load of all routes: " + totalLoad); }
C#
/// <summary> /// Print the solution. /// </summary> static void PrintSolution(in DataModel data, in RoutingModel routing, in RoutingIndexManager manager, in Assignment solution) { Console.WriteLine($"Objective {solution.ObjectiveValue()}:"); // Inspect solution. // Display dropped nodes. string droppedNodes = "Dropped nodes:"; for (int index = 0; index < routing.Size(); ++index) { if (routing.IsStart(index) || routing.IsEnd(index)) { continue; } if (solution.Value(routing.NextVar(index)) == index) { droppedNodes += " " + manager.IndexToNode(index); } } Console.WriteLine("{0}", droppedNodes); // Inspect solution. long totalDistance = 0; long totalLoad = 0; for (int i = 0; i < data.VehicleNumber; ++i) { Console.WriteLine("Route for Vehicle {0}:", i); long routeDistance = 0; long routeLoad = 0; var index = routing.Start(i); while (routing.IsEnd(index) == false) { long nodeIndex = manager.IndexToNode(index); routeLoad += data.Demands[nodeIndex]; Console.Write("{0} Load({1}) -> ", nodeIndex, routeLoad); var previousIndex = index; index = solution.Value(routing.NextVar(index)); routeDistance += routing.GetArcCostForVehicle(previousIndex, index, 0); } Console.WriteLine("{0}", manager.IndexToNode((int)index)); Console.WriteLine("Distance of the route: {0}m", routeDistance); totalDistance += routeDistance; totalLoad += routeLoad; } Console.WriteLine("Total Distance of all routes: {0}m", totalDistance); Console.WriteLine("Total Load of all routes: {0}m", totalLoad); }
Como executar o programa
Quando você executa o programa, ele retorna a seguinte saída mostrada abaixo. Observe que o solucionador descarta os locais 6 e 15.
Objective: 7936 Dropped nodes: 6 15 Route for vehicle 0: 0 Load(0) -> 9 Load(1) -> 14 Load(7) -> 16 Load(15) -> 0 Load(15) Distance of the route: 1324m Load of the route: 15 Route for vehicle 1: 0 Load(0) -> 12 Load(2) -> 11 Load(3) -> 4 Load(9) -> 3 Load(12) -> 1 Load(13) -> 0 Load(13) Distance of the route: 1872m Load of the route: 13 Route for vehicle 2: 0 Load(0) -> 7 Load(8) -> 13 Load(14) -> 0 Load(14) Distance of the route: 868m Load of the route: 14 Route for vehicle 3: 0 Load(0) -> 8 Load(8) -> 10 Load(10) -> 2 Load(11) -> 5 Load(14) -> 0 Load(14) Distance of the route: 1872m Load of the route: 14 Total Distance of all routes: 5936m Total Load of all routes: 56
Este é o diagrama das rotas.
Programas completos
Estes são os programas completos.
Python
"""Capacited Vehicles Routing Problem (CVRP).""" from ortools.constraint_solver import routing_enums_pb2 from ortools.constraint_solver import pywrapcp def create_data_model(): """Stores the data for the problem.""" data = {} data["distance_matrix"] = [ # fmt: off [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], # fmt: on ] data["demands"] = [0, 1, 1, 3, 6, 3, 6, 8, 8, 1, 2, 1, 2, 6, 6, 8, 8] data["vehicle_capacities"] = [15, 15, 15, 15] data["num_vehicles"] = 4 data["depot"] = 0 return data def print_solution(data, manager, routing, assignment): """Prints assignment on console.""" print(f"Objective: {assignment.ObjectiveValue()}") # Display dropped nodes. dropped_nodes = "Dropped nodes:" for node in range(routing.Size()): if routing.IsStart(node) or routing.IsEnd(node): continue if assignment.Value(routing.NextVar(node)) == node: dropped_nodes += f" {manager.IndexToNode(node)}" print(dropped_nodes) # Display routes total_distance = 0 total_load = 0 for vehicle_id in range(data["num_vehicles"]): index = routing.Start(vehicle_id) plan_output = f"Route for vehicle {vehicle_id}:\n" route_distance = 0 route_load = 0 while not routing.IsEnd(index): node_index = manager.IndexToNode(index) route_load += data["demands"][node_index] plan_output += f" {node_index} Load({route_load}) -> " previous_index = index index = assignment.Value(routing.NextVar(index)) route_distance += routing.GetArcCostForVehicle( previous_index, index, vehicle_id ) plan_output += f" {manager.IndexToNode(index)} Load({route_load})\n" plan_output += f"Distance of the route: {route_distance}m\n" plan_output += f"Load of the route: {route_load}\n" print(plan_output) total_distance += route_distance total_load += route_load print(f"Total Distance of all routes: {total_distance}m") print(f"Total Load of all routes: {total_load}") def main(): """Solve the CVRP problem.""" # Instantiate the data problem. data = create_data_model() # Create the routing index manager. manager = pywrapcp.RoutingIndexManager( len(data["distance_matrix"]), data["num_vehicles"], data["depot"] ) # Create Routing Model. routing = pywrapcp.RoutingModel(manager) # Create and register a transit callback. def distance_callback(from_index, to_index): """Returns the distance between the two nodes.""" # Convert from routing variable Index to distance matrix NodeIndex. from_node = manager.IndexToNode(from_index) to_node = manager.IndexToNode(to_index) return data["distance_matrix"][from_node][to_node] transit_callback_index = routing.RegisterTransitCallback(distance_callback) # Define cost of each arc. routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index) # Add Capacity constraint. def demand_callback(from_index): """Returns the demand of the node.""" # Convert from routing variable Index to demands NodeIndex. from_node = manager.IndexToNode(from_index) return data["demands"][from_node] demand_callback_index = routing.RegisterUnaryTransitCallback(demand_callback) routing.AddDimensionWithVehicleCapacity( demand_callback_index, 0, # null capacity slack data["vehicle_capacities"], # vehicle maximum capacities True, # start cumul to zero "Capacity", ) # Allow to drop nodes. penalty = 1000 for node in range(1, len(data["distance_matrix"])): routing.AddDisjunction([manager.NodeToIndex(node)], penalty) # Setting first solution heuristic. search_parameters = pywrapcp.DefaultRoutingSearchParameters() search_parameters.first_solution_strategy = ( routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC ) search_parameters.local_search_metaheuristic = ( routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH ) search_parameters.time_limit.FromSeconds(1) # Solve the problem. assignment = routing.SolveWithParameters(search_parameters) # Print solution on console. if assignment: print_solution(data, manager, routing, assignment) if __name__ == "__main__": main()
C++
#include <cstdint> #include <sstream> #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" namespace operations_research { struct DataModel { const std::vector<std::vector<int64_t>> 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<int64_t> demands{ 0, 1, 1, 3, 6, 3, 6, 8, 8, 1, 2, 1, 2, 6, 6, 8, 8, }; const std::vector<int64_t> vehicle_capacities{15, 15, 15, 15}; const int num_vehicles = 4; 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) { // Display dropped nodes. std::ostringstream dropped_nodes; for (int64_t node = 0; node < routing.Size(); ++node) { if (routing.IsStart(node) || routing.IsEnd(node)) continue; if (solution.Value(routing.NextVar(node)) == node) { dropped_nodes << " " << manager.IndexToNode(node).value(); } } LOG(INFO) << "Dropped nodes:" << dropped_nodes.str(); // Display routes int64_t total_distance{0}; int64_t total_load{0}; for (int vehicle_id = 0; vehicle_id < data.num_vehicles; ++vehicle_id) { int64_t index = routing.Start(vehicle_id); LOG(INFO) << "Route for Vehicle " << vehicle_id << ":"; int64_t route_distance{0}; int64_t route_load{0}; std::ostringstream route; while (!routing.IsEnd(index)) { const int node_index = manager.IndexToNode(index).value(); route_load += data.demands[node_index]; route << node_index << " Load(" << route_load << ") -> "; const int64_t previous_index = index; index = solution.Value(routing.NextVar(index)); route_distance += routing.GetArcCostForVehicle(previous_index, index, int64_t{vehicle_id}); } LOG(INFO) << route.str() << manager.IndexToNode(index).value(); LOG(INFO) << "Distance of the route: " << route_distance << "m"; LOG(INFO) << "Load of the route: " << route_load; total_distance += route_distance; total_load += route_load; } LOG(INFO) << "Total distance of all routes: " << total_distance << "m"; LOG(INFO) << "Total load of all routes: " << total_load; LOG(INFO) << ""; LOG(INFO) << "Advanced usage:"; LOG(INFO) << "Problem solved in " << routing.solver()->wall_time() << "ms"; } void VrpDropNodes() { // 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](const int64_t from_index, const int64_t to_index) -> int64_t { // Convert from routing variable Index to distance matrix NodeIndex. const int from_node = manager.IndexToNode(from_index).value(); const int 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 Capacity constraint. const int demand_callback_index = routing.RegisterUnaryTransitCallback( [&data, &manager](const int64_t from_index) -> int64_t { // Convert from routing variable Index to demand NodeIndex. const int from_node = manager.IndexToNode(from_index).value(); return data.demands[from_node]; }); routing.AddDimensionWithVehicleCapacity( demand_callback_index, // transit callback index int64_t{0}, // null capacity slack data.vehicle_capacities, // vehicle maximum capacities true, // start cumul to zero "Capacity"); // Allow to drop nodes. int64_t penalty{1000}; for (int i = 1; i < data.distance_matrix.size(); ++i) { routing.AddDisjunction( {manager.NodeToIndex(RoutingIndexManager::NodeIndex(i))}, penalty); } // Setting first solution heuristic. RoutingSearchParameters search_parameters = DefaultRoutingSearchParameters(); search_parameters.set_first_solution_strategy( FirstSolutionStrategy::PATH_CHEAPEST_ARC); search_parameters.set_local_search_metaheuristic( LocalSearchMetaheuristic::GUIDED_LOCAL_SEARCH); search_parameters.mutable_time_limit()->set_seconds(1); // Solve the problem. const Assignment* solution = routing.SolveWithParameters(search_parameters); // Print solution on console. PrintSolution(data, manager, routing, *solution); } } // namespace operations_research int main(int /*argc*/, char* /*argv*/[]) { operations_research::VrpDropNodes(); return EXIT_SUCCESS; }
Java
package com.google.ortools.constraintsolver.samples; import com.google.ortools.Loader; import com.google.ortools.constraintsolver.Assignment; import com.google.ortools.constraintsolver.FirstSolutionStrategy; import com.google.ortools.constraintsolver.LocalSearchMetaheuristic; import com.google.ortools.constraintsolver.RoutingIndexManager; import com.google.ortools.constraintsolver.RoutingModel; import com.google.ortools.constraintsolver.RoutingSearchParameters; import com.google.ortools.constraintsolver.main; import com.google.protobuf.Duration; import java.util.logging.Logger; /** Minimal VRP.*/ public class VrpDropNodes { private static final Logger logger = Logger.getLogger(VrpDropNodes.class.getName()); static class DataModel { public final long[][] distanceMatrix = { {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}, }; public final long[] demands = {0, 1, 1, 3, 6, 3, 6, 8, 8, 1, 2, 1, 2, 6, 6, 8, 8}; public final long[] vehicleCapacities = {15, 15, 15, 15}; public final int vehicleNumber = 4; public final int depot = 0; } /// @brief Print the solution. static void printSolution( DataModel data, RoutingModel routing, RoutingIndexManager manager, Assignment solution) { // Solution cost. logger.info("Objective: " + solution.objectiveValue()); // Inspect solution. // Display dropped nodes. String droppedNodes = "Dropped nodes:"; for (int node = 0; node < routing.size(); ++node) { if (routing.isStart(node) || routing.isEnd(node)) { continue; } if (solution.value(routing.nextVar(node)) == node) { droppedNodes += " " + manager.indexToNode(node); } } logger.info(droppedNodes); // Display routes long totalDistance = 0; long totalLoad = 0; for (int i = 0; i < data.vehicleNumber; ++i) { long index = routing.start(i); logger.info("Route for Vehicle " + i + ":"); long routeDistance = 0; long routeLoad = 0; String route = ""; while (!routing.isEnd(index)) { long nodeIndex = manager.indexToNode(index); routeLoad += data.demands[(int) nodeIndex]; route += nodeIndex + " Load(" + routeLoad + ") -> "; long previousIndex = index; index = solution.value(routing.nextVar(index)); routeDistance += routing.getArcCostForVehicle(previousIndex, index, i); } route += manager.indexToNode(routing.end(i)); logger.info(route); logger.info("Distance of the route: " + routeDistance + "m"); totalDistance += routeDistance; totalLoad += routeLoad; } logger.info("Total Distance of all routes: " + totalDistance + "m"); logger.info("Total Load of all routes: " + totalLoad); } public static void main(String[] args) throws Exception { Loader.loadNativeLibraries(); // Instantiate the data problem. final DataModel data = new DataModel(); // 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"); // Allow to drop nodes. long penalty = 1000; for (int i = 1; i < data.distanceMatrix.length; ++i) { routing.addDisjunction(new long[] {manager.nodeToIndex(i)}, penalty); } // 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(1).build()) .build(); // Solve the problem. Assignment solution = routing.solveWithParameters(searchParameters); // Print solution on console. printSolution(data, routing, manager, solution); } }
C#
using System; using System.Collections.Generic; using Google.OrTools.ConstraintSolver; using Google.Protobuf.WellKnownTypes; // Duration /// <summary> /// Minimal Vrp with drop nodes. /// </summary> public class VrpDropNodes { class DataModel { public long[,] DistanceMatrix = { { 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 } }; public long[] Demands = { 0, 1, 1, 3, 6, 3, 6, 8, 8, 1, 2, 1, 2, 6, 6, 8, 8 }; public long[] VehicleCapacities = { 15, 15, 15, 15 }; public int VehicleNumber = 4; public int Depot = 0; }; /// <summary> /// Print the solution. /// </summary> static void PrintSolution(in DataModel data, in RoutingModel routing, in RoutingIndexManager manager, in Assignment solution) { Console.WriteLine($"Objective {solution.ObjectiveValue()}:"); // Inspect solution. // Display dropped nodes. string droppedNodes = "Dropped nodes:"; for (int index = 0; index < routing.Size(); ++index) { if (routing.IsStart(index) || routing.IsEnd(index)) { continue; } if (solution.Value(routing.NextVar(index)) == index) { droppedNodes += " " + manager.IndexToNode(index); } } Console.WriteLine("{0}", droppedNodes); // Inspect solution. long totalDistance = 0; long totalLoad = 0; for (int i = 0; i < data.VehicleNumber; ++i) { Console.WriteLine("Route for Vehicle {0}:", i); long routeDistance = 0; long routeLoad = 0; var index = routing.Start(i); while (routing.IsEnd(index) == false) { long nodeIndex = manager.IndexToNode(index); routeLoad += data.Demands[nodeIndex]; Console.Write("{0} Load({1}) -> ", nodeIndex, routeLoad); var previousIndex = index; index = solution.Value(routing.NextVar(index)); routeDistance += routing.GetArcCostForVehicle(previousIndex, index, 0); } Console.WriteLine("{0}", manager.IndexToNode((int)index)); Console.WriteLine("Distance of the route: {0}m", routeDistance); totalDistance += routeDistance; totalLoad += routeLoad; } Console.WriteLine("Total Distance of all routes: {0}m", totalDistance); Console.WriteLine("Total Load of all routes: {0}m", totalLoad); } public static void Main(String[] args) { // Instantiate the data problem. DataModel data = new DataModel(); // Create Routing Index Manager RoutingIndexManager manager = new RoutingIndexManager(data.DistanceMatrix.GetLength(0), data.VehicleNumber, data.Depot); // Create Routing Model. RoutingModel routing = new RoutingModel(manager); // Create and register a transit callback. int transitCallbackIndex = routing.RegisterTransitCallback((long fromIndex, long toIndex) => { // Convert from routing variable Index to // distance matrix NodeIndex. var fromNode = manager.IndexToNode(fromIndex); var toNode = manager.IndexToNode(toIndex); return data.DistanceMatrix[fromNode, toNode]; }); // Define cost of each arc. routing.SetArcCostEvaluatorOfAllVehicles(transitCallbackIndex); // Add Capacity constraint. int demandCallbackIndex = routing.RegisterUnaryTransitCallback((long fromIndex) => { // Convert from routing variable Index to // demand NodeIndex. var 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"); // Allow to drop nodes. long penalty = 1000; for (int i = 1; i < data.DistanceMatrix.GetLength(0); ++i) { routing.AddDisjunction(new long[] { manager.NodeToIndex(i) }, penalty); } // Setting first solution heuristic. RoutingSearchParameters searchParameters = operations_research_constraint_solver.DefaultRoutingSearchParameters(); searchParameters.FirstSolutionStrategy = FirstSolutionStrategy.Types.Value.PathCheapestArc; searchParameters.LocalSearchMetaheuristic = LocalSearchMetaheuristic.Types.Value.GuidedLocalSearch; searchParameters.TimeLimit = new Duration { Seconds = 1 }; // Solve the problem. Assignment solution = routing.SolveWithParameters(searchParameters); // Print solution on console. PrintSolution(data, routing, manager, solution); } }