As seções a seguir explicam como realizar algumas tarefas comuns relacionadas à solução de problemas problemas de roteamento de veículos.
Limites de pesquisa
Problemas de trajeto de veículos com muitos locais podem levar muito tempo para serem resolvidos. Para problemas, é uma boa ideia definir um limite de pesquisa, o que encerra pesquisa após um período de tempo especificado ou número de soluções retornadas.
Limites de tempo
Os exemplos abaixo mostram como definir um limite de tempo de 30 segundos para uma pesquisa.
Python
search_parameters = pywrapcp.DefaultRoutingSearchParameters() search_parameters.time_limit.seconds = 30
C++
RoutingSearchParameters searchParameters = DefaultRoutingSearchParameters(); searchParameters.mutable_time_limit()->set_seconds(30);
Java
Adicione o comando "import" abaixo no início do programa:import com.google.protobuf.Duration;
RoutingSearchParameters searchParameters =
main.defaultRoutingSearchParameters()
.toBuilder()
.setTimeLimit(Duration.newBuilder().setSeconds(30).build())
.build();C#
Adicione a seguinte linha no início do programa:using Google.Protobuf.WellKnownTypes; // Duration
RoutingSearchParameters searchParameters = operations_research_constraint_solver.DefaultRoutingSearchParameters(); searchParameters.TimeLimit = new Duration { Seconds = 10 };
Consulte Alterar a estratégia de pesquisa de uma que define um limite de tempo.
Limites da solução
Os exemplos abaixo mostram como definir um limite de 100 soluções para uma pesquisa.
Python
search_parameters = pywrapcp.DefaultRoutingSearchParameters() search_parameters.solution_limit = 100
C++
RoutingSearchParameters searchParameters = DefaultRoutingSearchParameters(); searchParameters.set_solution_limit(100);
Java
RoutingSearchParameters searchParameters =
main.defaultRoutingSearchParameters()
.toBuilder()
.setSolutionLimit(100)
.build();C#
RoutingSearchParameters searchParameters = operations_research_constraint_solver.DefaultRoutingSearchParameters(); searchParameters.SolutionLimit(100);
Como definir rotas iniciais para uma pesquisa
Em alguns problemas, pode ser necessário especificar um conjunto de rotas iniciais para um VRP, em vez de deixar o solucionador encontrar uma solução inicial, por exemplo, se você já encontrou uma boa solução para um problema e quer usá-la como um ponto de partida para resolver um problema modificado.
Para criar as rotas iniciais, siga estas etapas:
- Defina uma matriz que contenha as rotas iniciais.
- Crie a solução inicial usando o método
ReadAssignmentFromRoutes.
O código a seguir define os trajetos iniciais nos dados.
Python
data["initial_routes"] = [ # fmt: off [8, 16, 14, 13, 12, 11], [3, 4, 9, 10], [15, 1], [7, 5, 2, 6], # fmt: on ]
C++
const std::vector<std::vector<int64_t>> initial_routes{ {8, 16, 14, 13, 12, 11}, {3, 4, 9, 10}, {15, 1}, {7, 5, 2, 6}, };
Java
public final long[][] initialRoutes = {
{8, 16, 14, 13, 12, 11},
{3, 4, 9, 10},
{15, 1},
{7, 5, 2, 6},
};C#
public long[][] InitialRoutes = {
new long[] { 8, 16, 14, 13, 12, 11 },
new long[] { 3, 4, 9, 10 },
new long[] { 15, 1 },
new long[] { 7, 5, 2, 6 },
};O código a seguir cria a solução inicial com base nas rotas e depois realiza uma pesquisa começando pela solução inicial.
O programa exibe a solução inicial e a solução encontrada pela pesquisa.
Python
initial_solution = routing.ReadAssignmentFromRoutes(data["initial_routes"], True) print("Initial solution:") print_solution(data, manager, routing, initial_solution)
C++
const Assignment* initial_solution = routing.ReadAssignmentFromRoutes(data.initial_routes, true); // Print initial solution on console. LOG(INFO) << "Initial solution: "; PrintSolution(data, manager, routing, *initial_solution);
Java
Assignment initialSolution = routing.readAssignmentFromRoutes(data.initialRoutes, true); logger.info("Initial solution:"); printSolution(data, routing, manager, initialSolution);
C#
Assignment initialSolution = routing.ReadAssignmentFromRoutes(data.InitialRoutes, true); // Print initial solution on console. Console.WriteLine("Initial solution:"); PrintSolution(data, routing, manager, initialSolution);
Quando você adiciona esse código VRP e executar o programa, exibe a seguinte saída:
Initial solution: Route for vehicle 0: 0 -> 8 -> 16 -> 14 -> 13 -> 12 -> 11 -> 0 Distance of the route: 2168m Route for vehicle 1: 0 -> 3 -> 4 -> 9 -> 10 -> 0 Distance of the route: 2464m Route for vehicle 2: 0 -> 15 -> 1 -> 0 Distance of the route: 2192m Route for vehicle 3: 0 -> 7 -> 5 -> 2 -> 6 -> 0 Distance of the route: 1780m Maximum of the route distances: 2464m Solution after search: Route for vehicle 0: 0 -> 9 -> 10 -> 16 -> 14 -> 0 Distance of the route: 1552m Route for vehicle 1: 0 -> 12 -> 11 -> 15 -> 13 -> 0 Distance of the route: 1552 Route for vehicle 2: 0 -> 3 -> 4 -> 1 -> 7 -> 0 Distance of the route: 1552 Route for vehicle 3: 0 -> 5 -> 2 -> 6 -> 8 -> 0 Distance of the route: 1552 Maximum of the route distances: 1552
Estes são os programas completos que definem rotas iniciais.
Python
"""Vehicles Routing Problem (VRP).""" 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["initial_routes"] = [ # fmt: off [8, 16, 14, 13, 12, 11], [3, 4, 9, 10], [15, 1], [7, 5, 2, 6], # fmt: on ] data["num_vehicles"] = 4 data["depot"] = 0 return data def print_solution(data, manager, routing, solution): """Prints solution on console.""" print(f"Objective: {solution.ObjectiveValue()}") max_route_distance = 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 while not routing.IsEnd(index): plan_output += f" {manager.IndexToNode(index)} -> " previous_index = index index = solution.Value(routing.NextVar(index)) route_distance += routing.GetArcCostForVehicle( previous_index, index, vehicle_id ) plan_output += f"{manager.IndexToNode(index)}\n" plan_output += f"Distance of the route: {route_distance}m\n" print(plan_output) max_route_distance = max(route_distance, max_route_distance) print(f"Maximum of the route distances: {max_route_distance}m") 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 Distance constraint. dimension_name = "Distance" routing.AddDimension( transit_callback_index, 0, # no slack 3000, # vehicle maximum travel distance True, # start cumul to zero dimension_name, ) distance_dimension = routing.GetDimensionOrDie(dimension_name) distance_dimension.SetGlobalSpanCostCoefficient(100) # Close model with the custom search parameters. 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(5) # When an initial solution is given for search, the model will be closed with # the default search parameters unless it is explicitly closed with the custom # search parameters. routing.CloseModelWithParameters(search_parameters) # Get initial solution from routes after closing the model. initial_solution = routing.ReadAssignmentFromRoutes(data["initial_routes"], True) print("Initial solution:") print_solution(data, manager, routing, initial_solution) # Solve the problem. solution = routing.SolveFromAssignmentWithParameters( initial_solution, search_parameters ) # Print solution on console. if solution: print("Solution after search:") print_solution(data, manager, routing, solution) if __name__ == "__main__": main()
C++
#include <algorithm> #include <cstdint> #include <cstdlib> #include <sstream> #include <vector> #include "google/protobuf/duration.pb.h" #include "ortools/base/logging.h" #include "ortools/constraint_solver/constraint_solver.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<std::vector<int64_t>> initial_routes{ {8, 16, 14, 13, 12, 11}, {3, 4, 9, 10}, {15, 1}, {7, 5, 2, 6}, }; 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) { LOG(INFO) << "Objective: " << solution.ObjectiveValue(); int64_t max_route_distance{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}; std::stringstream route; while (!routing.IsEnd(index)) { route << manager.IndexToNode(index).value() << " -> "; 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"; 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 VrpInitialRoutes() { // 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 Distance constraint. routing.AddDimension(transit_callback_index, 0, 3000, true, // start cumul to zero "Distance"); routing.GetMutableDimension("Distance")->SetGlobalSpanCostCoefficient(100); // Close model with the custom search parameters RoutingSearchParameters searchParameters = DefaultRoutingSearchParameters(); searchParameters.set_first_solution_strategy( FirstSolutionStrategy::PATH_CHEAPEST_ARC); searchParameters.set_local_search_metaheuristic( LocalSearchMetaheuristic::GUIDED_LOCAL_SEARCH); searchParameters.mutable_time_limit()->set_seconds(5); // When an initial solution is given for search, the model will be closed with // the default search parameters unless it is explicitly closed with the // custom search parameters. routing.CloseModelWithParameters(searchParameters); // Get initial solution from routes after closing the model. const Assignment* initial_solution = routing.ReadAssignmentFromRoutes(data.initial_routes, true); // Print initial solution on console. LOG(INFO) << "Initial solution: "; PrintSolution(data, manager, routing, *initial_solution); // Solve from initial solution. const Assignment* solution = routing.SolveFromAssignmentWithParameters( initial_solution, searchParameters); // Print solution on console. LOG(INFO) << ""; LOG(INFO) << "Solution from search: "; PrintSolution(data, manager, routing, *solution); } } // namespace operations_research int main(int /*argc*/, char* /*argv*/[]) { operations_research::VrpInitialRoutes(); 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.RoutingDimension; 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 java.util.logging.Logger; /** Minimal VRP. */ public class VrpInitialRoutes { private static final Logger logger = Logger.getLogger(VrpInitialRoutes.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[][] initialRoutes = { {8, 16, 14, 13, 12, 11}, {3, 4, 9, 10}, {15, 1}, {7, 5, 2, 6}, }; 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. long maxRouteDistance = 0; for (int i = 0; i < data.vehicleNumber; ++i) { long index = routing.start(i); logger.info("Route for Vehicle " + i + ":"); long routeDistance = 0; String route = ""; while (!routing.isEnd(index)) { route += manager.indexToNode(index) + " -> "; long previousIndex = index; index = solution.value(routing.nextVar(index)); routeDistance += routing.getArcCostForVehicle(previousIndex, index, i); } logger.info(route + manager.indexToNode(index)); logger.info("Distance of the route: " + routeDistance + "m"); maxRouteDistance = Math.max(routeDistance, maxRouteDistance); } logger.info("Maximum of the route distances: " + maxRouteDistance + "m"); } 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 Distance constraint. routing.addDimension(transitCallbackIndex, 0, 3000, true, // start cumul to zero "Distance"); RoutingDimension distanceDimension = routing.getMutableDimension("Distance"); distanceDimension.setGlobalSpanCostCoefficient(100); Assignment initialSolution = routing.readAssignmentFromRoutes(data.initialRoutes, true); logger.info("Initial solution:"); printSolution(data, routing, manager, initialSolution); // Setting first solution heuristic. RoutingSearchParameters searchParameters = main.defaultRoutingSearchParameters(); // Solve the problem. Assignment solution = routing.solveFromAssignmentWithParameters( initialSolution, searchParameters); // Print solution on console. logger.info("Solution after search:"); printSolution(data, routing, manager, solution); } }
C#
// Copyright 2010-2024 Google LLC // Licensed under the Apache License, Version 2.0 (the "License"); // you may not use this file except in compliance with the License. // You may obtain a copy of the License at // // http://www.apache.org/licenses/LICENSE-2.0 // // Unless required by applicable law or agreed to in writing, software // distributed under the License is distributed on an "AS IS" BASIS, // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. // See the License for the specific language governing permissions and // limitations under the License. using System; using System.Collections.Generic; using Google.OrTools.ConstraintSolver; /// <summary> /// VRP with initial routes. /// </summary> public class InitialRoutes { 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[][] InitialRoutes = { new long[] { 8, 16, 14, 13, 12, 11 }, new long[] { 3, 4, 9, 10 }, new long[] { 15, 1 }, new long[] { 7, 5, 2, 6 }, }; 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. long maxRouteDistance = 0; for (int i = 0; i < data.VehicleNumber; ++i) { Console.WriteLine("Route for Vehicle {0}:", i); long routeDistance = 0; var index = routing.Start(i); while (routing.IsEnd(index) == false) { Console.Write("{0} -> ", manager.IndexToNode((int)index)); 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}", routeDistance); maxRouteDistance = Math.Max(routeDistance, maxRouteDistance); } Console.WriteLine("Maximum distance of the routes: {0}", maxRouteDistance); } 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 Distance constraint. routing.AddDimension(transitCallbackIndex, 0, 3000, true, // start cumul to zero "Distance"); RoutingDimension distanceDimension = routing.GetMutableDimension("Distance"); distanceDimension.SetGlobalSpanCostCoefficient(100); // Get initial solution from routes. Assignment initialSolution = routing.ReadAssignmentFromRoutes(data.InitialRoutes, true); // Print initial solution on console. Console.WriteLine("Initial solution:"); PrintSolution(data, routing, manager, initialSolution); // Setting first solution heuristic. RoutingSearchParameters searchParameters = operations_research_constraint_solver.DefaultRoutingSearchParameters(); // Solve the problem. Assignment solution = routing.SolveFromAssignmentWithParameters( initialSolution, searchParameters); // Print solution on console. Console.WriteLine("Solution after search:"); PrintSolution(data, routing, manager, solution); } }
Definir locais de início e término dos trajetos
Até agora, assumimos que todos os veículos começam e terminam em um único local, no depósito. Você também pode definir locais de partida e chegada diferentes para cada veículo em o problema. Para isso, transmita dois vetores, contendo os índices do início e do fim as localizações, como entradas RoutingModel na função principal. Veja como criar os vetores de início e fim na seção de dados do programa:
Python
data["starts"] = [1, 2, 15, 16] data["ends"] = [0, 0, 0, 0]
C++
const std::vector<RoutingIndexManager::NodeIndex> starts{ RoutingIndexManager::NodeIndex{1}, RoutingIndexManager::NodeIndex{2}, RoutingIndexManager::NodeIndex{15}, RoutingIndexManager::NodeIndex{16}, }; const std::vector<RoutingIndexManager::NodeIndex> ends{ RoutingIndexManager::NodeIndex{0}, RoutingIndexManager::NodeIndex{0}, RoutingIndexManager::NodeIndex{0}, RoutingIndexManager::NodeIndex{0}, };
Java
public final int[] starts = {1, 2, 15, 16};
public final int[] ends = {0, 0, 0, 0};C#
public int[] Starts = { 1, 2, 15, 16 };
public int[] Ends = { 0, 0, 0, 0 };Estes são os programas completos que definem os locais de início e término dessa maneira.
Python
"""Simple Vehicles Routing Problem.""" 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["num_vehicles"] = 4 data["starts"] = [1, 2, 15, 16] data["ends"] = [0, 0, 0, 0] return data def print_solution(data, manager, routing, solution): """Prints solution on console.""" print(f"Objective: {solution.ObjectiveValue()}") max_route_distance = 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 while not routing.IsEnd(index): plan_output += f" {manager.IndexToNode(index)} -> " previous_index = index index = solution.Value(routing.NextVar(index)) route_distance += routing.GetArcCostForVehicle( previous_index, index, vehicle_id ) plan_output += f"{manager.IndexToNode(index)}\n" plan_output += f"Distance of the route: {route_distance}m\n" print(plan_output) max_route_distance = max(route_distance, max_route_distance) print(f"Maximum of the route distances: {max_route_distance}m") def main(): """Entry point of the program.""" # Instantiate the data problem. data = create_data_model() # Create the routing index manager. manager = pywrapcp.RoutingIndexManager( len(data["distance_matrix"]), data["num_vehicles"], data["starts"], data["ends"] ) # 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 Distance constraint. dimension_name = "Distance" routing.AddDimension( transit_callback_index, 0, # no slack 2000, # vehicle maximum travel distance True, # start cumul to zero dimension_name, ) distance_dimension = routing.GetDimensionOrDie(dimension_name) distance_dimension.SetGlobalSpanCostCoefficient(100) # Setting first solution heuristic. search_parameters = pywrapcp.DefaultRoutingSearchParameters() search_parameters.first_solution_strategy = ( routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC ) # Solve the problem. solution = routing.SolveWithParameters(search_parameters) # Print solution on console. if solution: print_solution(data, manager, routing, solution) if __name__ == "__main__": main()
C++
#include <algorithm> #include <cstdint> #include <sstream> #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_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 int num_vehicles = 4; const std::vector<RoutingIndexManager::NodeIndex> starts{ RoutingIndexManager::NodeIndex{1}, RoutingIndexManager::NodeIndex{2}, RoutingIndexManager::NodeIndex{15}, RoutingIndexManager::NodeIndex{16}, }; const std::vector<RoutingIndexManager::NodeIndex> ends{ RoutingIndexManager::NodeIndex{0}, RoutingIndexManager::NodeIndex{0}, RoutingIndexManager::NodeIndex{0}, RoutingIndexManager::NodeIndex{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_t max_route_distance{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}; std::stringstream route; while (!routing.IsEnd(index)) { route << manager.IndexToNode(index).value() << " -> "; 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"; 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 VrpStartsEnds() { // Instantiate the data problem. DataModel data; // Create Routing Index Manager RoutingIndexManager manager(data.distance_matrix.size(), data.num_vehicles, data.starts, data.ends); // 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 Distance constraint. routing.AddDimension(transit_callback_index, 0, 2000, /*fix_start_cumul_to_zero=*/true, "Distance"); routing.GetMutableDimension("Distance")->SetGlobalSpanCostCoefficient(100); // Setting first solution heuristic. RoutingSearchParameters searchParameters = DefaultRoutingSearchParameters(); 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::VrpStartsEnds(); 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.RoutingDimension; 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 java.util.logging.Logger; /** Minimal VRP.*/ public class VrpStartsEnds { private static final Logger logger = Logger.getLogger(VrpStartsEnds.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 int vehicleNumber = 4; public final int[] starts = {1, 2, 15, 16}; public final int[] ends = {0, 0, 0, 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. long maxRouteDistance = 0; for (int i = 0; i < data.vehicleNumber; ++i) { long index = routing.start(i); logger.info("Route for Vehicle " + i + ":"); long routeDistance = 0; String route = ""; while (!routing.isEnd(index)) { route += manager.indexToNode(index) + " -> "; long previousIndex = index; index = solution.value(routing.nextVar(index)); routeDistance += routing.getArcCostForVehicle(previousIndex, index, i); } logger.info(route + manager.indexToNode(index)); logger.info("Distance of the route: " + routeDistance + "m"); maxRouteDistance = Math.max(routeDistance, maxRouteDistance); } logger.info("Maximum of the route distances: " + maxRouteDistance + "m"); } 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.starts, data.ends); // 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 Distance constraint. routing.addDimension(transitCallbackIndex, 0, 2000, true, // start cumul to zero "Distance"); RoutingDimension distanceDimension = routing.getMutableDimension("Distance"); distanceDimension.setGlobalSpanCostCoefficient(100); // Setting first solution heuristic. RoutingSearchParameters searchParameters = main.defaultRoutingSearchParameters() .toBuilder() .setFirstSolutionStrategy(FirstSolutionStrategy.Value.PATH_CHEAPEST_ARC) .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; /// <summary> /// Minimal TSP using distance matrix. /// </summary> public class VrpStartsEnds { 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 int VehicleNumber = 4; public int[] Starts = { 1, 2, 15, 16 }; public int[] Ends = { 0, 0, 0, 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. long maxRouteDistance = 0; for (int i = 0; i < data.VehicleNumber; ++i) { Console.WriteLine("Route for Vehicle {0}:", i); long routeDistance = 0; var index = routing.Start(i); while (routing.IsEnd(index) == false) { Console.Write("{0} -> ", manager.IndexToNode((int)index)); 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); maxRouteDistance = Math.Max(routeDistance, maxRouteDistance); } Console.WriteLine("Maximum distance of the routes: {0}m", maxRouteDistance); } 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.Starts, data.Ends); // 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 Distance constraint. routing.AddDimension(transitCallbackIndex, 0, 2000, true, // start cumul to zero "Distance"); RoutingDimension distanceDimension = routing.GetMutableDimension("Distance"); distanceDimension.SetGlobalSpanCostCoefficient(100); // Setting first solution heuristic. RoutingSearchParameters searchParameters = operations_research_constraint_solver.DefaultRoutingSearchParameters(); searchParameters.FirstSolutionStrategy = FirstSolutionStrategy.Types.Value.PathCheapestArc; // Solve the problem. Assignment solution = routing.SolveWithParameters(searchParameters); // Print solution on console. PrintSolution(data, routing, manager, solution); } }
Ao executar o programa, você recebe a seguinte saída, na qual as rotas começam e terminam nos locais especificados:
Route for vehicle 0: 1 -> 4 -> 3 -> 7 -> 0 Distance of the route: 1004m Route for vehicle 1: 2 -> 6 -> 8 -> 5 -> 0 Distance of the route: 936m Route for vehicle 2: 15 -> 11 -> 12 -> 13 -> 0 Distance of the route: 936m Route for vehicle 3: 16 -> 14 -> 10 -> 9 -> 0 Distance of the route: 1118m Total distance of all routes: 3994m
A distância total é menor que no exemplo anterior porque os veículos não precisam começar ou terminar no depósito.
Permitir locais arbitrários de início e término
Em outras versões do problema de roteamento de veículos, os veículos podem ligar e terminam em locais arbitrários. Para configurar o problema dessa forma, basta modificar a matriz de distância, de modo que a distância do depósito até qualquer outro local seja 0, definindo que a primeira linha e coluna da matriz têm todos zeros. Isso transforma a estação em um local fictício que não afeta os trajetos ideais.
Este é um exemplo em que a matriz de distância do O exemplo de VRP foi modificado para tornar distância do depósito até todos os outros nós 0.
data['distance_matrix'] = [ [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ], [ 0, 0, 684, 308, 194, 502, 730, 354, 696, 742, 1084, 594, 480, 674, 1016, 868, 1210 ], [ 0, 684, 0, 992, 878, 502, 274, 810, 468, 742, 400, 1278, 1164, 1130, 788, 1552, 754 ], [ 0, 308, 992, 0, 114, 650, 878, 502, 844, 890, 1232, 514, 628, 822, 1164, 560, 1358 ], [ 0, 194, 878, 114, 0, 536, 764, 388, 730, 776, 1118, 400, 514, 708, 1050, 674, 1244 ], [ 0, 502, 502, 650, 536, 0, 228, 308, 194, 240, 582, 776, 662, 628, 514, 1050, 708 ], [ 0, 730, 274, 878, 764, 228, 0, 536, 194, 468, 354, 1004, 890, 856, 514, 1278, 480 ], [ 0, 354, 810, 502, 388, 308, 536, 0, 342, 388, 730, 468, 354, 320, 662, 742, 856 ], [ 0, 696, 468, 844, 730, 194, 194, 342, 0, 274, 388, 810, 696, 662, 0, 1084, 514 ], [ 0, 742, 742, 890, 776, 240, 468, 388, 274, 0, 342, 536, 422, 388, 0, 810, 468 ], [ 0, 1084, 400, 1232, 1118, 582, 354, 730, 388, 342, 0, 878, 764, 730, 388, 1152, 354 ], [ 0, 594, 1278, 514, 400, 776, 1004, 468, 810, 536, 878, 0, 114, 308, 650, 274, 844 ], [ 0, 480, 1164, 628, 514, 662, 890, 354, 696, 422, 764, 114, 0, 194, 536, 388, 730 ], [ 0, 674, 1130, 822, 708, 628, 856, 320, 662, 388, 730, 308, 194, 0, 342, 422, 536 ], [ 0, 1016, 788, 1164, 1050, 514, 514, 662, 320, 274, 388, 650, 536, 342, 0, 764, 194 ], [ 0, 868, 1552, 560, 674, 1050, 1278, 742, 1084, 810, 1152, 274, 388, 422, 764, 0, 798 ], [ 0, 1210, 754, 1358, 1244, 708, 480, 856, 514, 468, 354, 844, 730, 536, 194, 798, 0 ], ]
Quando você executar o programa VRP com a matriz de distância modificada (e modificar a impressora da solução para omitir o depósito) , o programa exibirá as seguintes rotas:
Route for vehicle 0: 5 -> 8 -> 6 -> 2 Distance of the route: 662m Route for vehicle 1: 7 -> 1 -> 4 -> 3 Distance of the route: 662m Route for vehicle 2: 16 -> 14 -> 13 -> 15 Distance of the route: 958m Route for vehicle 3: 10 -> 9 -> 12 -> 11 Distance of the route: 878m Maximum of the route distances: 958m