בקטעים הבאים מוסבר איך לבצע כמה משימות נפוצות שקשורות לפתרון בעיות לניתוב הרכב.
מגבלות חיפוש
פתרון בעיות בתכנון מסלול לרכב עם מיקומים רבים עשוי להימשך זמן רב. עבור כדאי להגדיר מגבלת חיפוש, כדי לסיים חיפוש אחרי פרק זמן שצוין או מספר הפתרונות שהוחזרו.
מגבלות זמן
הדוגמאות הבאות מראות איך להגדיר לחיפוש מגבלת זמן של 30 שניות.
Python
search_parameters = pywrapcp.DefaultRoutingSearchParameters() search_parameters.time_limit.seconds = 30
C++
RoutingSearchParameters searchParameters = DefaultRoutingSearchParameters(); searchParameters.mutable_time_limit()->set_seconds(30);
Java
מוסיפים את 'ייבוא' הבא בתחילת התוכנה:import com.google.protobuf.Duration;
RoutingSearchParameters searchParameters =
main.defaultRoutingSearchParameters()
.toBuilder()
.setTimeLimit(Duration.newBuilder().setSeconds(30).build())
.build();C#
מוסיפים את השורה הבאה בתחילת התוכנית:using Google.Protobuf.WellKnownTypes; // Duration
RoutingSearchParameters searchParameters = operations_research_constraint_solver.DefaultRoutingSearchParameters(); searchParameters.TimeLimit = new Duration { Seconds = 10 };
צפייה שינוי של אסטרטגיית החיפוש של דוגמה להגדרת מגבלת זמן.
מגבלות של פתרונות
הדוגמאות הבאות מראות איך להגדיר מגבלת פתרונות של 100 לחיפוש.
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);
הגדרת מסלולים ראשוניים לחיפוש
במקרים מסוימים, כדאי לציין קבוצה של מסלולים ראשוניים ל-VRP, במקום לאפשר לפותר למצוא פתרון ראשוני — לדוגמה, אם כבר מצאתם פתרון טוב לבעיה, ואתם רוצים להשתמש בו לנקודת ההתחלה לפתרון בעיה ששונתה.
כדי ליצור את המסלולים הראשוניים, צריך לבצע את השלבים הבאים:
- להגדיר מערך שמכיל את הנתיבים הראשוניים.
- יוצרים את הפתרון הראשוני באמצעות השיטה
ReadAssignmentFromRoutes.
הקוד הבא מגדיר את הנתיבים הראשוניים בנתונים.
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 },
};הקוד הבא יוצר את הפתרון הראשוני מהמסלולים ואז מבצע חיפוש שמתחיל מהפתרון הראשוני.
התוכנית מציגה גם את הפתרון הראשוני וגם את הפתרון שנמצא בחיפוש.
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);
כשמוסיפים את הקוד הזה תוכנית VRP ולהריץ את התוכנית, מציגה את הפלט הבא:
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
אלו התוכניות המלאות שמגדירות מסלולים ראשוניים.
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); } }
הגדרת מיקומי התחלה וסיום למסלולים
עד עכשיו, ההנחה שלנו היא שכל כלי הרכב התחילו והסתיימו באותו מיקום, התחנה. אפשר גם להגדיר נקודות התחלה וסיום שונות לכל רכב ב: את הבעיה. לשם כך, מעבירים שני וקטורים שכוללים את האינדקסים של ההתחלה והסיום במיקומים שונים, בתור קלטים RoutingModel בפונקציה הראשית. כך יוצרים וקטורים של התחלה וסיום קטע הנתונים של התוכנה:
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 };בהמשך מפורטות התוכניות המלאות שמגדירות את מיקומי ההתחלה והסיום באופן הזה.
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); } }
כשמריצים תוכנית, מקבלים את הפלט הבא, שבו המסלולים מתחילים ומסתיימים במיקומים שמצוינים:
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
המרחק הכולל קצר יותר מאשר בדוגמה הקודמת, כי כלי הרכב לא חייבים להתחיל או להסתיים בתחנה.
הפעלה של מיקומי התחלה וסיום שרירותיים
בגרסאות אחרות של בעיית המסלול לרכב, מותר להתניע את כלי הרכב ומסתיימים במיקומים שרירותיים. כדי להגדיר את הבעיה בדרך הזו, צריך פשוט לשנות את מטריצת המרחק כך שהמרחק מהתחנה לכל מיקום אחר הוא 0, באמצעות הגדרת השורה הראשונה והעמודה הראשונה במטריצה כך שכל אפסים יופיעו. הפעולה הזו הופכת את התחנה למיקום דמה שאין לו השפעה על המסלולים האופטימליים.
הנה דוגמה שבה מטריצת המרחק הדוגמה של VRP שונתה כדי המרחק מהתחנה לכל הצמתים האחרים, 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 ], ]
כשמפעילים את תוכנית VRP עם את מטריצת המרחקים ששונתה (ומשנה את מדפסת הפתרון כך שתשמיט את המאגר) , התוכנית מציגה את המסלולים הבאים:
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