Các phần sau giải thích cách thực hiện một số công việc phổ biến liên quan đến việc giải quyết sự cố định tuyến xe.
Giới hạn tìm kiếm
Các vấn đề về định tuyến xe ở nhiều vị trí có thể mất nhiều thời gian để giải quyết. Cho các vấn đề như vậy, bạn nên đặt giới hạn tìm kiếm để chấm dứt tìm kiếm sau một khoảng thời gian chỉ định hoặc số lượng đáp án được trả về.
Giới hạn thời gian
Các ví dụ bên dưới minh hoạ cách đặt giới hạn thời gian là 30 giây cho một lượt tìm kiếm.
Python
search_parameters = pywrapcp.DefaultRoutingSearchParameters() search_parameters.time_limit.seconds = 30
C++
RoutingSearchParameters searchParameters = DefaultRoutingSearchParameters(); searchParameters.mutable_time_limit()->set_seconds(30);
Java
Thêm lệnh "nhập" sau vào đầu chương trình:import com.google.protobuf.Duration;
RoutingSearchParameters searchParameters =
main.defaultRoutingSearchParameters()
.toBuilder()
.setTimeLimit(Duration.newBuilder().setSeconds(30).build())
.build();C#
Hãy thêm dòng sau vào đầu chương trình:using Google.Protobuf.WellKnownTypes; // Duration
RoutingSearchParameters searchParameters = operations_research_constraint_solver.DefaultRoutingSearchParameters(); searchParameters.TimeLimit = new Duration { Seconds = 10 };
Xem Thay đổi chiến lược tìm kiếm cho một ví dụ về cách đặt giới hạn thời gian.
Hạn mức của giải pháp
Các ví dụ bên dưới minh hoạ cách đặt giới hạn giải pháp là 100 cho một lượt tìm kiếm.
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);
Đặt tuyến đường ban đầu cho một tìm kiếm
Đối với một số vấn đề, bạn có thể muốn chỉ định một tập hợp các tuyến ban đầu cho VRP, thay vì để người giải tìm cách giải ban đầu, ví dụ: nếu bạn đã tìm ra một giải pháp hay cho một vấn đề và muốn sử dụng giải pháp đó làm một điểm xuất phát để giải bài toán đã sửa đổi.
Để tạo các tuyến ban đầu, hãy làm theo các bước sau:
- Xác định một mảng chứa các tuyến ban đầu.
- Tạo giải pháp ban đầu bằng phương thức
ReadAssignmentFromRoutes.
Mã sau đây xác định các tuyến ban đầu trong dữ liệu.
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ạn mã sau đây tạo giải pháp ban đầu từ các tuyến đường và sau đó thực hiện tìm kiếm bắt đầu với giải pháp ban đầu.
Chương trình này cho thấy cả đáp án ban đầu và đáp án khi tìm kiếm.
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);
Khi bạn thêm mã này vào chương trình VRP và chạy chương trình. cho thấy kết quả sau:
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
Sau đây là các chương trình hoàn chỉnh thiết lập lộ trình ban đầu.
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); } }
Thiết lập vị trí bắt đầu và kết thúc cho tuyến đường
Cho đến nay, chúng tôi giả định rằng tất cả các phương tiện đều bắt đầu và kết thúc tại một vị trí, kho hàng. Bạn cũng có thể đặt các vị trí bắt đầu và kết thúc có thể khác nhau cho mỗi chiếc xe trong sự cố. Để thực hiện việc này, hãy truyền hai vectơ, chứa chỉ mục của điểm bắt đầu và chỉ mục kết thúc làm thông tin đầu vào cho RoutingModel trong hàm chính. Dưới đây là cách tạo vectơ bắt đầu và vectơ kết thúc trong phần dữ liệu của chương trình:
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 };Sau đây là các chương trình hoàn chỉnh đã thiết lập vị trí bắt đầu và kết thúc theo cách này.
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); } }
Khi chạy chương trình, bạn sẽ nhận được kết quả sau đây, trong đó các tuyến bắt đầu và kết thúc tại các vị trí được chỉ định:
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
Tổng quãng đường ngắn hơn trong ví dụ trước vì các phương tiện di chuyển không bắt buộc phải bắt đầu hoặc kết thúc tại kho.
Cho phép vị trí bắt đầu và kết thúc tuỳ ý
Trong các phiên bản khác của bài toán định tuyến xe, các phương tiện được phép khởi động và kết thúc tại các vị trí tuỳ ý. Để thiết lập sự cố theo cách này, bạn chỉ cần sửa đổi ma trận khoảng cách sao cho khoảng cách từ kho đến bất kỳ vị trí nào khác bằng 0, bằng cách đặt hàng và cột đầu tiên của ma trận có tất cả các giá trị bằng 0. Điều này sẽ biến kho hàng thành một vị trí giả không ảnh hưởng đến các tuyến đường tối ưu.
Dưới đây là một ví dụ, trong đó ma trận khoảng cách từ Ví dụ về VRP đã được sửa đổi để làm cho khoảng cách từ kho đến tất cả các nút khác bằng 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 ], ]
Khi bạn chạy chương trình VRP bằng ma trận khoảng cách đã sửa đổi (và sửa đổi máy in giải pháp để bỏ qua kho) , chương trình sẽ hiển thị các tuyến sau:
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