電容式車輛路線規劃問題 (CVRP) 是一種 VRP,在載客能力有限的車輛上必須在不同地點自取或送貨。 這些項目具有重量或體積等數量,而且車輛可容納的最大容量。問題在於,以最低的費用接送或交付商品,而且絕對不會超過車輛的容量。
在以下範例中,我們假設系統已擷取所有項目。如果傳送所有項目時,解決這個問題的程式也能正常運作:在這種情況下,您可以考慮在車輛容器完全卸載儲存區時套用容量限制。但是在這兩種情況下,容量限制的實作方式都相同。
CVRP 範例
接下來,我們會說明一個具有容量限制的 VRP 範例。該範例擴充了先前的 VRP 範例,並新增了下列需求。在每個位置都有一個需求,可對應到要取貨的項目數量。此外,每輛車的最大容量為 15。(我們不會為需求或容量指定單位)。
下方的格狀清單會以藍色顯示要造訪的地點,並以黑色顯示公司位置。這些需求會顯示在每個地點右下角。請參閱 VRP 一節中的位置座標,進一步瞭解位置定義。
問題在於,要找出總路線最短的汽車路線指定,且車輛所載的車輛總量不會超過其容量。
使用 OR-Tools 解決 CVRP 範例
以下各節說明如何使用 OR-Tools 解決 CVRP 範例。
建立資料
這個範例的資料包含上一個 VRP 範例中的資料,並包含下列需求和車輛容量:
Python
data["demands"] = [0, 1, 1, 2, 4, 2, 4, 8, 8, 1, 2, 1, 2, 4, 4, 8, 8] data["vehicle_capacities"] = [15, 15, 15, 15]
C++
const std::vector<int64_t> demands{ 0, 1, 1, 2, 4, 2, 4, 8, 8, 1, 2, 1, 2, 4, 4, 8, 8, }; const std::vector<int64_t> vehicle_capacities{15, 15, 15, 15};
Java
public final long[] demands = {0, 1, 1, 2, 4, 2, 4, 8, 8, 1, 2, 1, 2, 4, 4, 8, 8}; public final long[] vehicleCapacities = {15, 15, 15, 15};
C#
public long[] Demands = { 0, 1, 1, 2, 4, 2, 4, 8, 8, 1, 2, 1, 2, 4, 4, 8, 8 }; public long[] VehicleCapacities = { 15, 15, 15, 15 };
資料中的新項目如下:
- 需求:每個地點都有一個需求,對應到要取貨的商品的數量 (例如重量或體積)。
- 容量:每輛車都有「容量」:車輛可以可容納的最大容量。當車輛沿著路線行駛時,其所載物品的總數量絕不會超過其容量。
新增距離回呼
距離回呼 (會傳回兩個位置之間的距離) 的函式定義與先前的 VRP 範例相同。
新增需求回呼和容量限制條件
除了距離回呼之外,解題工具也需要需求回呼,以傳回每個位置的需求以及容量限制的維度。以下程式碼會建立這些項目。
Python
def demand_callback(from_index): """Returns the demand of the node.""" # Convert from routing variable Index to demands NodeIndex. from_node = manager.IndexToNode(from_index) return data["demands"][from_node] demand_callback_index = routing.RegisterUnaryTransitCallback(demand_callback) routing.AddDimensionWithVehicleCapacity( demand_callback_index, 0, # null capacity slack data["vehicle_capacities"], # vehicle maximum capacities True, # start cumul to zero "Capacity", )
C++
const int demand_callback_index = routing.RegisterUnaryTransitCallback( [&data, &manager](const int64_t from_index) -> int64_t { // Convert from routing variable Index to demand NodeIndex. const int from_node = manager.IndexToNode(from_index).value(); return data.demands[from_node]; }); routing.AddDimensionWithVehicleCapacity( demand_callback_index, // transit callback index int64_t{0}, // null capacity slack data.vehicle_capacities, // vehicle maximum capacities true, // start cumul to zero "Capacity");
Java
final int demandCallbackIndex = routing.registerUnaryTransitCallback((long fromIndex) -> { // Convert from routing variable Index to user NodeIndex. int fromNode = manager.indexToNode(fromIndex); return data.demands[fromNode]; }); routing.addDimensionWithVehicleCapacity(demandCallbackIndex, 0, // null capacity slack data.vehicleCapacities, // vehicle maximum capacities true, // start cumul to zero "Capacity");
C#
int demandCallbackIndex = routing.RegisterUnaryTransitCallback((long fromIndex) => { // Convert from routing variable Index to // demand NodeIndex. var fromNode = manager.IndexToNode(fromIndex); return data.Demands[fromNode]; }); routing.AddDimensionWithVehicleCapacity(demandCallbackIndex, 0, // null capacity slack data.VehicleCapacities, // vehicle maximum capacities true, // start cumul to zero "Capacity");
與距離回呼 (將一對位置作為輸入內容) 不同,需求回呼僅取決於提供位置 (from_node
)。
由於容量限制涉及車輛承載的負載重量 (在路徑上所累積的數量),因此我們必須針對容量建立維度,類似之前的 VRP 範例。
在本範例中,我們使用 AddDimensionWithVehicleCapacity
方法,該方法採用一個容量的向量。
由於本範例中所有車輛容量相同,因此您可以使用 AddDimension
方法,這會針對所有車輛數量採用單一上限。不過,AddDimensionWithVehicleCapacity
可處理更常見的情況,也就是不同車輛有不同的容量。
多種貨物類型和容量相關問題
在更複雜的 CVRP 中,每輛車可能可攜帶多種不同類型的貨物, 每種車型都有最大容量。 舉例來說,某輛油箱貨運可能使用多種容量不同的油箱來運送多種類型的燃料。如要處理這類問題,只要為每個貨物類型建立不同的容量回呼和維度 (請務必為其指派不重複的名稱)。
新增解決方案印表機
解決方案印表機會顯示每輛車的路線及其累計「負載」:車輛在路線上停靠的總金額。
Python
def print_solution(data, manager, routing, solution): """Prints solution on console.""" print(f"Objective: {solution.ObjectiveValue()}") total_distance = 0 total_load = 0 for vehicle_id in range(data["num_vehicles"]): index = routing.Start(vehicle_id) plan_output = f"Route for vehicle {vehicle_id}:\n" route_distance = 0 route_load = 0 while not routing.IsEnd(index): node_index = manager.IndexToNode(index) route_load += data["demands"][node_index] plan_output += f" {node_index} Load({route_load}) -> " previous_index = index index = solution.Value(routing.NextVar(index)) route_distance += routing.GetArcCostForVehicle( previous_index, index, vehicle_id ) plan_output += f" {manager.IndexToNode(index)} Load({route_load})\n" plan_output += f"Distance of the route: {route_distance}m\n" plan_output += f"Load of the route: {route_load}\n" print(plan_output) total_distance += route_distance total_load += route_load print(f"Total distance of all routes: {total_distance}m") print(f"Total load of all routes: {total_load}")
C++
//! @brief Print the solution. //! @param[in] data Data of the problem. //! @param[in] manager Index manager used. //! @param[in] routing Routing solver used. //! @param[in] solution Solution found by the solver. void PrintSolution(const DataModel& data, const RoutingIndexManager& manager, const RoutingModel& routing, const Assignment& solution) { int64_t total_distance = 0; int64_t total_load = 0; for (int vehicle_id = 0; vehicle_id < data.num_vehicles; ++vehicle_id) { int64_t index = routing.Start(vehicle_id); LOG(INFO) << "Route for Vehicle " << vehicle_id << ":"; int64_t route_distance = 0; int64_t route_load = 0; std::stringstream route; while (!routing.IsEnd(index)) { const int node_index = manager.IndexToNode(index).value(); route_load += data.demands[node_index]; route << node_index << " Load(" << route_load << ") -> "; const int64_t previous_index = index; index = solution.Value(routing.NextVar(index)); route_distance += routing.GetArcCostForVehicle(previous_index, index, int64_t{vehicle_id}); } LOG(INFO) << route.str() << manager.IndexToNode(index).value(); LOG(INFO) << "Distance of the route: " << route_distance << "m"; LOG(INFO) << "Load of the route: " << route_load; total_distance += route_distance; total_load += route_load; } LOG(INFO) << "Total distance of all routes: " << total_distance << "m"; LOG(INFO) << "Total load of all routes: " << total_load; LOG(INFO) << ""; LOG(INFO) << "Advanced usage:"; LOG(INFO) << "Problem solved in " << routing.solver()->wall_time() << "ms"; }
Java
/// @brief Print the solution. static void printSolution( DataModel data, RoutingModel routing, RoutingIndexManager manager, Assignment solution) { // Solution cost. logger.info("Objective: " + solution.objectiveValue()); // Inspect solution. long totalDistance = 0; long totalLoad = 0; for (int i = 0; i < data.vehicleNumber; ++i) { long index = routing.start(i); logger.info("Route for Vehicle " + i + ":"); long routeDistance = 0; long routeLoad = 0; String route = ""; while (!routing.isEnd(index)) { long nodeIndex = manager.indexToNode(index); routeLoad += data.demands[(int) nodeIndex]; route += nodeIndex + " Load(" + routeLoad + ") -> "; long previousIndex = index; index = solution.value(routing.nextVar(index)); routeDistance += routing.getArcCostForVehicle(previousIndex, index, i); } route += manager.indexToNode(routing.end(i)); logger.info(route); logger.info("Distance of the route: " + routeDistance + "m"); totalDistance += routeDistance; totalLoad += routeLoad; } logger.info("Total distance of all routes: " + totalDistance + "m"); logger.info("Total load of all routes: " + totalLoad); }
C#
/// <summary> /// Print the solution. /// </summary> static void PrintSolution(in DataModel data, in RoutingModel routing, in RoutingIndexManager manager, in Assignment solution) { Console.WriteLine($"Objective {solution.ObjectiveValue()}:"); // Inspect solution. long totalDistance = 0; long totalLoad = 0; for (int i = 0; i < data.VehicleNumber; ++i) { Console.WriteLine("Route for Vehicle {0}:", i); long routeDistance = 0; long routeLoad = 0; var index = routing.Start(i); while (routing.IsEnd(index) == false) { long nodeIndex = manager.IndexToNode(index); routeLoad += data.Demands[nodeIndex]; Console.Write("{0} Load({1}) -> ", nodeIndex, routeLoad); var previousIndex = index; index = solution.Value(routing.NextVar(index)); routeDistance += routing.GetArcCostForVehicle(previousIndex, index, 0); } Console.WriteLine("{0}", manager.IndexToNode((int)index)); Console.WriteLine("Distance of the route: {0}m", routeDistance); totalDistance += routeDistance; totalLoad += routeLoad; } Console.WriteLine("Total distance of all routes: {0}m", totalDistance); Console.WriteLine("Total load of all routes: {0}m", totalLoad); }
主函式
這個範例的主要函式與 TSP 範例的功能非常類似,但也會新增上述的需求和容量維度。
執行程式
完整計畫請參閱下一節。當您執行該程式時,會顯示下列輸出:
Objective: 6208 Route for vehicle 0: 0 Load(0) -> 4 Load(0) -> 3 Load(4) -> 1 Load(6) -> 7 Load(7) -> 0 Load(15) Distance of the route: 1552m Load of the route: 15 Route for vehicle 1: 0 Load(0) -> 14 Load(0) -> 16 Load(4) -> 10 Load(12) -> 9 Load(14) -> 0 Load(15) Distance of the route: 1552m Load of the route: 15 Route for vehicle 2: 0 Load(0) -> 12 Load(0) -> 11 Load(2) -> 15 Load(3) -> 13 Load(11) -> 0 Load(15) Distance of the route: 1552m Load of the route: 15 Route for vehicle 3: 0 Load(0) -> 8 Load(0) -> 2 Load(8) -> 6 Load(9) -> 5 Load(13) -> 0 Load(15) Distance of the route: 1552m Load of the route: 15 Total Distance of all routes: 6208m Total Load of all routes: 60
路徑中的每個位置都會顯示輸出結果:
- 地點的索引。
車輛離開地點時承載的總負載。
路線如下。
完成計畫
下方顯示了電動車路線規劃問題的完整程式。
Python
"""Capacited Vehicles Routing Problem (CVRP).""" from ortools.constraint_solver import routing_enums_pb2 from ortools.constraint_solver import pywrapcp def create_data_model(): """Stores the data for the problem.""" data = {} data["distance_matrix"] = [ # fmt: off [0, 548, 776, 696, 582, 274, 502, 194, 308, 194, 536, 502, 388, 354, 468, 776, 662], [548, 0, 684, 308, 194, 502, 730, 354, 696, 742, 1084, 594, 480, 674, 1016, 868, 1210], [776, 684, 0, 992, 878, 502, 274, 810, 468, 742, 400, 1278, 1164, 1130, 788, 1552, 754], [696, 308, 992, 0, 114, 650, 878, 502, 844, 890, 1232, 514, 628, 822, 1164, 560, 1358], [582, 194, 878, 114, 0, 536, 764, 388, 730, 776, 1118, 400, 514, 708, 1050, 674, 1244], [274, 502, 502, 650, 536, 0, 228, 308, 194, 240, 582, 776, 662, 628, 514, 1050, 708], [502, 730, 274, 878, 764, 228, 0, 536, 194, 468, 354, 1004, 890, 856, 514, 1278, 480], [194, 354, 810, 502, 388, 308, 536, 0, 342, 388, 730, 468, 354, 320, 662, 742, 856], [308, 696, 468, 844, 730, 194, 194, 342, 0, 274, 388, 810, 696, 662, 320, 1084, 514], [194, 742, 742, 890, 776, 240, 468, 388, 274, 0, 342, 536, 422, 388, 274, 810, 468], [536, 1084, 400, 1232, 1118, 582, 354, 730, 388, 342, 0, 878, 764, 730, 388, 1152, 354], [502, 594, 1278, 514, 400, 776, 1004, 468, 810, 536, 878, 0, 114, 308, 650, 274, 844], [388, 480, 1164, 628, 514, 662, 890, 354, 696, 422, 764, 114, 0, 194, 536, 388, 730], [354, 674, 1130, 822, 708, 628, 856, 320, 662, 388, 730, 308, 194, 0, 342, 422, 536], [468, 1016, 788, 1164, 1050, 514, 514, 662, 320, 274, 388, 650, 536, 342, 0, 764, 194], [776, 868, 1552, 560, 674, 1050, 1278, 742, 1084, 810, 1152, 274, 388, 422, 764, 0, 798], [662, 1210, 754, 1358, 1244, 708, 480, 856, 514, 468, 354, 844, 730, 536, 194, 798, 0], # fmt: on ] data["demands"] = [0, 1, 1, 2, 4, 2, 4, 8, 8, 1, 2, 1, 2, 4, 4, 8, 8] data["vehicle_capacities"] = [15, 15, 15, 15] 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()}") total_distance = 0 total_load = 0 for vehicle_id in range(data["num_vehicles"]): index = routing.Start(vehicle_id) plan_output = f"Route for vehicle {vehicle_id}:\n" route_distance = 0 route_load = 0 while not routing.IsEnd(index): node_index = manager.IndexToNode(index) route_load += data["demands"][node_index] plan_output += f" {node_index} Load({route_load}) -> " previous_index = index index = solution.Value(routing.NextVar(index)) route_distance += routing.GetArcCostForVehicle( previous_index, index, vehicle_id ) plan_output += f" {manager.IndexToNode(index)} Load({route_load})\n" plan_output += f"Distance of the route: {route_distance}m\n" plan_output += f"Load of the route: {route_load}\n" print(plan_output) total_distance += route_distance total_load += route_load print(f"Total distance of all routes: {total_distance}m") print(f"Total load of all routes: {total_load}") def main(): """Solve the CVRP problem.""" # Instantiate the data problem. data = create_data_model() # Create the routing index manager. manager = pywrapcp.RoutingIndexManager( len(data["distance_matrix"]), data["num_vehicles"], data["depot"] ) # Create Routing Model. routing = pywrapcp.RoutingModel(manager) # Create and register a transit callback. def distance_callback(from_index, to_index): """Returns the distance between the two nodes.""" # Convert from routing variable Index to distance matrix NodeIndex. from_node = manager.IndexToNode(from_index) to_node = manager.IndexToNode(to_index) return data["distance_matrix"][from_node][to_node] transit_callback_index = routing.RegisterTransitCallback(distance_callback) # Define cost of each arc. routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index) # Add Capacity constraint. def demand_callback(from_index): """Returns the demand of the node.""" # Convert from routing variable Index to demands NodeIndex. from_node = manager.IndexToNode(from_index) return data["demands"][from_node] demand_callback_index = routing.RegisterUnaryTransitCallback(demand_callback) routing.AddDimensionWithVehicleCapacity( demand_callback_index, 0, # null capacity slack data["vehicle_capacities"], # vehicle maximum capacities True, # start cumul to zero "Capacity", ) # Setting first solution heuristic. search_parameters = pywrapcp.DefaultRoutingSearchParameters() search_parameters.first_solution_strategy = ( routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC ) search_parameters.local_search_metaheuristic = ( routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH ) search_parameters.time_limit.FromSeconds(1) # Solve the problem. solution = routing.SolveWithParameters(search_parameters) # Print solution on console. if solution: print_solution(data, manager, routing, solution) if __name__ == "__main__": main()
C++
#include <cstdint> #include <sstream> #include <vector> #include "google/protobuf/duration.pb.h" #include "ortools/constraint_solver/routing.h" #include "ortools/constraint_solver/routing_enums.pb.h" #include "ortools/constraint_solver/routing_index_manager.h" #include "ortools/constraint_solver/routing_parameters.h" namespace operations_research { struct DataModel { const std::vector<std::vector<int64_t>> distance_matrix{ {0, 548, 776, 696, 582, 274, 502, 194, 308, 194, 536, 502, 388, 354, 468, 776, 662}, {548, 0, 684, 308, 194, 502, 730, 354, 696, 742, 1084, 594, 480, 674, 1016, 868, 1210}, {776, 684, 0, 992, 878, 502, 274, 810, 468, 742, 400, 1278, 1164, 1130, 788, 1552, 754}, {696, 308, 992, 0, 114, 650, 878, 502, 844, 890, 1232, 514, 628, 822, 1164, 560, 1358}, {582, 194, 878, 114, 0, 536, 764, 388, 730, 776, 1118, 400, 514, 708, 1050, 674, 1244}, {274, 502, 502, 650, 536, 0, 228, 308, 194, 240, 582, 776, 662, 628, 514, 1050, 708}, {502, 730, 274, 878, 764, 228, 0, 536, 194, 468, 354, 1004, 890, 856, 514, 1278, 480}, {194, 354, 810, 502, 388, 308, 536, 0, 342, 388, 730, 468, 354, 320, 662, 742, 856}, {308, 696, 468, 844, 730, 194, 194, 342, 0, 274, 388, 810, 696, 662, 320, 1084, 514}, {194, 742, 742, 890, 776, 240, 468, 388, 274, 0, 342, 536, 422, 388, 274, 810, 468}, {536, 1084, 400, 1232, 1118, 582, 354, 730, 388, 342, 0, 878, 764, 730, 388, 1152, 354}, {502, 594, 1278, 514, 400, 776, 1004, 468, 810, 536, 878, 0, 114, 308, 650, 274, 844}, {388, 480, 1164, 628, 514, 662, 890, 354, 696, 422, 764, 114, 0, 194, 536, 388, 730}, {354, 674, 1130, 822, 708, 628, 856, 320, 662, 388, 730, 308, 194, 0, 342, 422, 536}, {468, 1016, 788, 1164, 1050, 514, 514, 662, 320, 274, 388, 650, 536, 342, 0, 764, 194}, {776, 868, 1552, 560, 674, 1050, 1278, 742, 1084, 810, 1152, 274, 388, 422, 764, 0, 798}, {662, 1210, 754, 1358, 1244, 708, 480, 856, 514, 468, 354, 844, 730, 536, 194, 798, 0}, }; const std::vector<int64_t> demands{ 0, 1, 1, 2, 4, 2, 4, 8, 8, 1, 2, 1, 2, 4, 4, 8, 8, }; const std::vector<int64_t> vehicle_capacities{15, 15, 15, 15}; const int num_vehicles = 4; const RoutingIndexManager::NodeIndex depot{0}; }; //! @brief Print the solution. //! @param[in] data Data of the problem. //! @param[in] manager Index manager used. //! @param[in] routing Routing solver used. //! @param[in] solution Solution found by the solver. void PrintSolution(const DataModel& data, const RoutingIndexManager& manager, const RoutingModel& routing, const Assignment& solution) { int64_t total_distance = 0; int64_t total_load = 0; for (int vehicle_id = 0; vehicle_id < data.num_vehicles; ++vehicle_id) { int64_t index = routing.Start(vehicle_id); LOG(INFO) << "Route for Vehicle " << vehicle_id << ":"; int64_t route_distance = 0; int64_t route_load = 0; std::stringstream route; while (!routing.IsEnd(index)) { const int node_index = manager.IndexToNode(index).value(); route_load += data.demands[node_index]; route << node_index << " Load(" << route_load << ") -> "; const int64_t previous_index = index; index = solution.Value(routing.NextVar(index)); route_distance += routing.GetArcCostForVehicle(previous_index, index, int64_t{vehicle_id}); } LOG(INFO) << route.str() << manager.IndexToNode(index).value(); LOG(INFO) << "Distance of the route: " << route_distance << "m"; LOG(INFO) << "Load of the route: " << route_load; total_distance += route_distance; total_load += route_load; } LOG(INFO) << "Total distance of all routes: " << total_distance << "m"; LOG(INFO) << "Total load of all routes: " << total_load; LOG(INFO) << ""; LOG(INFO) << "Advanced usage:"; LOG(INFO) << "Problem solved in " << routing.solver()->wall_time() << "ms"; } void VrpCapacity() { // Instantiate the data problem. DataModel data; // Create Routing Index Manager RoutingIndexManager manager(data.distance_matrix.size(), data.num_vehicles, data.depot); // Create Routing Model. RoutingModel routing(manager); // Create and register a transit callback. const int transit_callback_index = routing.RegisterTransitCallback( [&data, &manager](const int64_t from_index, const int64_t to_index) -> int64_t { // Convert from routing variable Index to distance matrix NodeIndex. const int from_node = manager.IndexToNode(from_index).value(); const int to_node = manager.IndexToNode(to_index).value(); return data.distance_matrix[from_node][to_node]; }); // Define cost of each arc. routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index); // Add Capacity constraint. const int demand_callback_index = routing.RegisterUnaryTransitCallback( [&data, &manager](const int64_t from_index) -> int64_t { // Convert from routing variable Index to demand NodeIndex. const int from_node = manager.IndexToNode(from_index).value(); return data.demands[from_node]; }); routing.AddDimensionWithVehicleCapacity( demand_callback_index, // transit callback index int64_t{0}, // null capacity slack data.vehicle_capacities, // vehicle maximum capacities true, // start cumul to zero "Capacity"); // Setting first solution heuristic. RoutingSearchParameters search_parameters = DefaultRoutingSearchParameters(); search_parameters.set_first_solution_strategy( FirstSolutionStrategy::PATH_CHEAPEST_ARC); search_parameters.set_local_search_metaheuristic( LocalSearchMetaheuristic::GUIDED_LOCAL_SEARCH); search_parameters.mutable_time_limit()->set_seconds(1); // Solve the problem. const Assignment* solution = routing.SolveWithParameters(search_parameters); // Print solution on console. PrintSolution(data, manager, routing, *solution); } } // namespace operations_research int main(int /*argc*/, char* /*argv*/[]) { operations_research::VrpCapacity(); return EXIT_SUCCESS; }
Java
package com.google.ortools.constraintsolver.samples; import com.google.ortools.Loader; import com.google.ortools.constraintsolver.Assignment; import com.google.ortools.constraintsolver.FirstSolutionStrategy; import com.google.ortools.constraintsolver.LocalSearchMetaheuristic; import com.google.ortools.constraintsolver.RoutingIndexManager; import com.google.ortools.constraintsolver.RoutingModel; import com.google.ortools.constraintsolver.RoutingSearchParameters; import com.google.ortools.constraintsolver.main; import com.google.protobuf.Duration; import java.util.logging.Logger; /** Minimal VRP. */ public final class VrpCapacity { private static final Logger logger = Logger.getLogger(VrpCapacity.class.getName()); static class DataModel { public final long[][] distanceMatrix = { {0, 548, 776, 696, 582, 274, 502, 194, 308, 194, 536, 502, 388, 354, 468, 776, 662}, {548, 0, 684, 308, 194, 502, 730, 354, 696, 742, 1084, 594, 480, 674, 1016, 868, 1210}, {776, 684, 0, 992, 878, 502, 274, 810, 468, 742, 400, 1278, 1164, 1130, 788, 1552, 754}, {696, 308, 992, 0, 114, 650, 878, 502, 844, 890, 1232, 514, 628, 822, 1164, 560, 1358}, {582, 194, 878, 114, 0, 536, 764, 388, 730, 776, 1118, 400, 514, 708, 1050, 674, 1244}, {274, 502, 502, 650, 536, 0, 228, 308, 194, 240, 582, 776, 662, 628, 514, 1050, 708}, {502, 730, 274, 878, 764, 228, 0, 536, 194, 468, 354, 1004, 890, 856, 514, 1278, 480}, {194, 354, 810, 502, 388, 308, 536, 0, 342, 388, 730, 468, 354, 320, 662, 742, 856}, {308, 696, 468, 844, 730, 194, 194, 342, 0, 274, 388, 810, 696, 662, 320, 1084, 514}, {194, 742, 742, 890, 776, 240, 468, 388, 274, 0, 342, 536, 422, 388, 274, 810, 468}, {536, 1084, 400, 1232, 1118, 582, 354, 730, 388, 342, 0, 878, 764, 730, 388, 1152, 354}, {502, 594, 1278, 514, 400, 776, 1004, 468, 810, 536, 878, 0, 114, 308, 650, 274, 844}, {388, 480, 1164, 628, 514, 662, 890, 354, 696, 422, 764, 114, 0, 194, 536, 388, 730}, {354, 674, 1130, 822, 708, 628, 856, 320, 662, 388, 730, 308, 194, 0, 342, 422, 536}, {468, 1016, 788, 1164, 1050, 514, 514, 662, 320, 274, 388, 650, 536, 342, 0, 764, 194}, {776, 868, 1552, 560, 674, 1050, 1278, 742, 1084, 810, 1152, 274, 388, 422, 764, 0, 798}, {662, 1210, 754, 1358, 1244, 708, 480, 856, 514, 468, 354, 844, 730, 536, 194, 798, 0}, }; public final long[] demands = {0, 1, 1, 2, 4, 2, 4, 8, 8, 1, 2, 1, 2, 4, 4, 8, 8}; public final long[] vehicleCapacities = {15, 15, 15, 15}; public final int vehicleNumber = 4; public final int depot = 0; } /// @brief Print the solution. static void printSolution( DataModel data, RoutingModel routing, RoutingIndexManager manager, Assignment solution) { // Solution cost. logger.info("Objective: " + solution.objectiveValue()); // Inspect solution. long totalDistance = 0; long totalLoad = 0; for (int i = 0; i < data.vehicleNumber; ++i) { long index = routing.start(i); logger.info("Route for Vehicle " + i + ":"); long routeDistance = 0; long routeLoad = 0; String route = ""; while (!routing.isEnd(index)) { long nodeIndex = manager.indexToNode(index); routeLoad += data.demands[(int) nodeIndex]; route += nodeIndex + " Load(" + routeLoad + ") -> "; long previousIndex = index; index = solution.value(routing.nextVar(index)); routeDistance += routing.getArcCostForVehicle(previousIndex, index, i); } route += manager.indexToNode(routing.end(i)); logger.info(route); logger.info("Distance of the route: " + routeDistance + "m"); totalDistance += routeDistance; totalLoad += routeLoad; } logger.info("Total distance of all routes: " + totalDistance + "m"); logger.info("Total load of all routes: " + totalLoad); } public static void main(String[] args) throws Exception { Loader.loadNativeLibraries(); // Instantiate the data problem. final DataModel data = new DataModel(); // Create Routing Index Manager RoutingIndexManager manager = new RoutingIndexManager(data.distanceMatrix.length, data.vehicleNumber, data.depot); // Create Routing Model. RoutingModel routing = new RoutingModel(manager); // Create and register a transit callback. final int transitCallbackIndex = routing.registerTransitCallback((long fromIndex, long toIndex) -> { // Convert from routing variable Index to user NodeIndex. int fromNode = manager.indexToNode(fromIndex); int toNode = manager.indexToNode(toIndex); return data.distanceMatrix[fromNode][toNode]; }); // Define cost of each arc. routing.setArcCostEvaluatorOfAllVehicles(transitCallbackIndex); // Add Capacity constraint. final int demandCallbackIndex = routing.registerUnaryTransitCallback((long fromIndex) -> { // Convert from routing variable Index to user NodeIndex. int fromNode = manager.indexToNode(fromIndex); return data.demands[fromNode]; }); routing.addDimensionWithVehicleCapacity(demandCallbackIndex, 0, // null capacity slack data.vehicleCapacities, // vehicle maximum capacities true, // start cumul to zero "Capacity"); // Setting first solution heuristic. RoutingSearchParameters searchParameters = main.defaultRoutingSearchParameters() .toBuilder() .setFirstSolutionStrategy(FirstSolutionStrategy.Value.PATH_CHEAPEST_ARC) .setLocalSearchMetaheuristic(LocalSearchMetaheuristic.Value.GUIDED_LOCAL_SEARCH) .setTimeLimit(Duration.newBuilder().setSeconds(1).build()) .build(); // Solve the problem. Assignment solution = routing.solveWithParameters(searchParameters); // Print solution on console. printSolution(data, routing, manager, solution); } private VrpCapacity() {} }
C#
using System; using System.Collections.Generic; using Google.OrTools.ConstraintSolver; using Google.Protobuf.WellKnownTypes; // Duration /// <summary> /// Minimal TSP using distance matrix. /// </summary> public class VrpCapacity { class DataModel { public long[,] DistanceMatrix = { { 0, 548, 776, 696, 582, 274, 502, 194, 308, 194, 536, 502, 388, 354, 468, 776, 662 }, { 548, 0, 684, 308, 194, 502, 730, 354, 696, 742, 1084, 594, 480, 674, 1016, 868, 1210 }, { 776, 684, 0, 992, 878, 502, 274, 810, 468, 742, 400, 1278, 1164, 1130, 788, 1552, 754 }, { 696, 308, 992, 0, 114, 650, 878, 502, 844, 890, 1232, 514, 628, 822, 1164, 560, 1358 }, { 582, 194, 878, 114, 0, 536, 764, 388, 730, 776, 1118, 400, 514, 708, 1050, 674, 1244 }, { 274, 502, 502, 650, 536, 0, 228, 308, 194, 240, 582, 776, 662, 628, 514, 1050, 708 }, { 502, 730, 274, 878, 764, 228, 0, 536, 194, 468, 354, 1004, 890, 856, 514, 1278, 480 }, { 194, 354, 810, 502, 388, 308, 536, 0, 342, 388, 730, 468, 354, 320, 662, 742, 856 }, { 308, 696, 468, 844, 730, 194, 194, 342, 0, 274, 388, 810, 696, 662, 320, 1084, 514 }, { 194, 742, 742, 890, 776, 240, 468, 388, 274, 0, 342, 536, 422, 388, 274, 810, 468 }, { 536, 1084, 400, 1232, 1118, 582, 354, 730, 388, 342, 0, 878, 764, 730, 388, 1152, 354 }, { 502, 594, 1278, 514, 400, 776, 1004, 468, 810, 536, 878, 0, 114, 308, 650, 274, 844 }, { 388, 480, 1164, 628, 514, 662, 890, 354, 696, 422, 764, 114, 0, 194, 536, 388, 730 }, { 354, 674, 1130, 822, 708, 628, 856, 320, 662, 388, 730, 308, 194, 0, 342, 422, 536 }, { 468, 1016, 788, 1164, 1050, 514, 514, 662, 320, 274, 388, 650, 536, 342, 0, 764, 194 }, { 776, 868, 1552, 560, 674, 1050, 1278, 742, 1084, 810, 1152, 274, 388, 422, 764, 0, 798 }, { 662, 1210, 754, 1358, 1244, 708, 480, 856, 514, 468, 354, 844, 730, 536, 194, 798, 0 } }; public long[] Demands = { 0, 1, 1, 2, 4, 2, 4, 8, 8, 1, 2, 1, 2, 4, 4, 8, 8 }; public long[] VehicleCapacities = { 15, 15, 15, 15 }; public int VehicleNumber = 4; public int Depot = 0; }; /// <summary> /// Print the solution. /// </summary> static void PrintSolution(in DataModel data, in RoutingModel routing, in RoutingIndexManager manager, in Assignment solution) { Console.WriteLine($"Objective {solution.ObjectiveValue()}:"); // Inspect solution. long totalDistance = 0; long totalLoad = 0; for (int i = 0; i < data.VehicleNumber; ++i) { Console.WriteLine("Route for Vehicle {0}:", i); long routeDistance = 0; long routeLoad = 0; var index = routing.Start(i); while (routing.IsEnd(index) == false) { long nodeIndex = manager.IndexToNode(index); routeLoad += data.Demands[nodeIndex]; Console.Write("{0} Load({1}) -> ", nodeIndex, routeLoad); var previousIndex = index; index = solution.Value(routing.NextVar(index)); routeDistance += routing.GetArcCostForVehicle(previousIndex, index, 0); } Console.WriteLine("{0}", manager.IndexToNode((int)index)); Console.WriteLine("Distance of the route: {0}m", routeDistance); totalDistance += routeDistance; totalLoad += routeLoad; } Console.WriteLine("Total distance of all routes: {0}m", totalDistance); Console.WriteLine("Total load of all routes: {0}m", totalLoad); } public static void Main(String[] args) { // Instantiate the data problem. DataModel data = new DataModel(); // Create Routing Index Manager RoutingIndexManager manager = new RoutingIndexManager(data.DistanceMatrix.GetLength(0), data.VehicleNumber, data.Depot); // Create Routing Model. RoutingModel routing = new RoutingModel(manager); // Create and register a transit callback. int transitCallbackIndex = routing.RegisterTransitCallback((long fromIndex, long toIndex) => { // Convert from routing variable Index to // distance matrix NodeIndex. var fromNode = manager.IndexToNode(fromIndex); var toNode = manager.IndexToNode(toIndex); return data.DistanceMatrix[fromNode, toNode]; }); // Define cost of each arc. routing.SetArcCostEvaluatorOfAllVehicles(transitCallbackIndex); // Add Capacity constraint. int demandCallbackIndex = routing.RegisterUnaryTransitCallback((long fromIndex) => { // Convert from routing variable Index to // demand NodeIndex. var fromNode = manager.IndexToNode(fromIndex); return data.Demands[fromNode]; }); routing.AddDimensionWithVehicleCapacity(demandCallbackIndex, 0, // null capacity slack data.VehicleCapacities, // vehicle maximum capacities true, // start cumul to zero "Capacity"); // Setting first solution heuristic. RoutingSearchParameters searchParameters = operations_research_constraint_solver.DefaultRoutingSearchParameters(); searchParameters.FirstSolutionStrategy = FirstSolutionStrategy.Types.Value.PathCheapestArc; searchParameters.LocalSearchMetaheuristic = LocalSearchMetaheuristic.Types.Value.GuidedLocalSearch; searchParameters.TimeLimit = new Duration { Seconds = 1 }; // Solve the problem. Assignment solution = routing.SolveWithParameters(searchParameters); // Print solution on console. PrintSolution(data, routing, manager, solution); } }
在 GitHub 上,針對其他類型限制的車輛轉送問題有幾個範例 (請尋找名稱中含有「vrp」的範例)。
如果問題沒有解決方式,該怎麼辦?
設有限制的轉送問題 (例如 CVRP) 可能沒有可行的解決方案,例如,如果傳輸的項目總數超過車輛的總數。當您嘗試解決這類問題時,解題工具可能會執行詳盡的搜尋,且最終必須等待較長的時間,才能放棄並中斷程式。
這通常不是問題。但下列幾種方法可以防止您的程式在問題未解決時執行很長的時間:
- 為程式設定「時間限制」。即使沒有找到任何解決方案,系統也會停止搜尋。不過請注意,如果解決方案需要執行時間較長的搜尋,程式可能會在達到解決方案前達到時間限制。
- 設定停靠點以降低造訪地點的次數。如此就能讓解題工具傳回不解所有位置的「解決方案」,以解決無法解決的問題。請參閱「懲罰與掉落的來訪」一文。
一般來說,我們很難判別某個問題有解決方法。即使 ZRP 的總需求量不會超過總容量,仍可以判斷所有項目是否適用於車輛,是多重刀擊模式問題。