本節將說明如何處理沒有可行的轉送問題 解決方案。例如，若您為 設有容量限制的 VRP 所有位置的總需求超過 我們沒有可能的解決辦法 在這種情況下，車輛必須造訪部分地點。問題是 如何決定要捨棄的造訪次數。
為瞭解決這個問題，我們增加了新的成本，稱為懲罰 。每次造訪地點遺失時， 會計入所行移動總距離。接著，解題工具會找出 以盡量縮短總距離加上所有拖放的罰則總和 或位置。
舉個例子，想想 下方圖表顯示了三個位置旁邊數字 (除了 債務) 為需求量。
假設目前只有一輛車的容量為 50 人，絕對無法造訪這三個
位置，因為總需求為 60要解決這個問題
。更新後
與此同時，解題工具將著手找出問題所在
傳回以下路徑：Depot -> A -> C -> Depot
這是前往三個地點其中兩個 (兩者之間的距離) 的最短路線 55)。
處分期大小
在上述範例中，我們選擇的處分金額大於所有 位置之間的距離 (不含庫)。因此，在掉層 發生問題時，解題工具 不會遺漏任何程式碼 其他地點的罰則，因為這類行為的罰則可能會超過 減少移動距離。
假設您想盡量多提供商品 滿意的解決方案
如果不需要盡量多提交商品，您可能會希望 減小的懲處，在這種情況下，解題工具可能會捨棄較多位置 才能處理問題舉例來說， 支付特定費用，或是超過基本旅遊費用等 或位置。
範例
接下來，我們將呈現更大型的 VRP 示例，運用處分即可解決。 這個示例與上一個 CVRP 範例，不過這次我們增加了 導致某些車輛必須放棄造訪
以下圖表顯示地區和新需求。
使用 OR-Tools 來解決範例
以下各節說明如何使用 OR-Tools 解決範例。
建立資料
這個範例中的資料包含先前 VRP 示例並新增下列需求 和容量：
Python
data["demands"] = [0, 1, 1, 3, 6, 3, 6, 8, 8, 1, 2, 1, 2, 6, 6, 8, 8] data["vehicle_capacities"] = [15, 15, 15, 15]
C++
const std::vector<int64_t> demands{ 0, 1, 1, 3, 6, 3, 6, 8, 8, 1, 2, 1, 2, 6, 6, 8, 8, }; const std::vector<int64_t> vehicle_capacities{15, 15, 15, 15};
Java
public final long[] demands = {0, 1, 1, 3, 6, 3, 6, 8, 8, 1, 2, 1, 2, 6, 6, 8, 8};
public final long[] vehicleCapacities = {15, 15, 15, 15};C#
public long[] Demands = { 0, 1, 1, 3, 6, 3, 6, 8, 8, 1, 2, 1, 2, 6, 6, 8, 8 };
public long[] VehicleCapacities = { 15, 15, 15, 15 };新增容量限制和懲罰
下列程式碼會新增需求回呼和容量限制，
懲罰
AddDisjunction敬上
方法。
Python
def demand_callback(from_index): """Returns the demand of the node.""" # Convert from routing variable Index to demands NodeIndex. from_node = manager.IndexToNode(from_index) return data["demands"][from_node] demand_callback_index = routing.RegisterUnaryTransitCallback(demand_callback) routing.AddDimensionWithVehicleCapacity( demand_callback_index, 0, # null capacity slack data["vehicle_capacities"], # vehicle maximum capacities True, # start cumul to zero "Capacity", ) # Allow to drop nodes. penalty = 1000 for node in range(1, len(data["distance_matrix"])): routing.AddDisjunction([manager.NodeToIndex(node)], penalty)
C++
const int demand_callback_index = routing.RegisterUnaryTransitCallback( [&data, &manager](const int64_t from_index) -> int64_t { // Convert from routing variable Index to demand NodeIndex. const int from_node = manager.IndexToNode(from_index).value(); return data.demands[from_node]; }); routing.AddDimensionWithVehicleCapacity( demand_callback_index, // transit callback index int64_t{0}, // null capacity slack data.vehicle_capacities, // vehicle maximum capacities true, // start cumul to zero "Capacity"); // Allow to drop nodes. int64_t penalty{1000}; for (int i = 1; i < data.distance_matrix.size(); ++i) { routing.AddDisjunction( {manager.NodeToIndex(RoutingIndexManager::NodeIndex(i))}, penalty); }
Java
final int demandCallbackIndex = routing.registerUnaryTransitCallback((long fromIndex) -> { // Convert from routing variable Index to user NodeIndex. int fromNode = manager.indexToNode(fromIndex); return data.demands[fromNode]; }); routing.addDimensionWithVehicleCapacity(demandCallbackIndex, 0, // null capacity slack data.vehicleCapacities, // vehicle maximum capacities true, // start cumul to zero "Capacity"); // Allow to drop nodes. long penalty = 1000; for (int i = 1; i < data.distanceMatrix.length; ++i) { routing.addDisjunction(new long[] {manager.nodeToIndex(i)}, penalty); }
C#
int demandCallbackIndex = routing.RegisterUnaryTransitCallback((long fromIndex) => { // Convert from routing variable Index to // demand NodeIndex. var fromNode = manager.IndexToNode(fromIndex); return data.Demands[fromNode]; }); routing.AddDimensionWithVehicleCapacity(demandCallbackIndex, 0, // null capacity slack data.VehicleCapacities, // vehicle maximum capacities true, // start cumul to zero "Capacity"); // Allow to drop nodes. long penalty = 1000; for (int i = 1; i < data.DistanceMatrix.GetLength(0); ++i) { routing.AddDisjunction(new long[] { manager.NodeToIndex(i) }, penalty); }
在這種情況下，disjunction 只是解題工具，用來 決定是否要在解決方案中加入特定位置。在這個範例中， 此方法會為每個位置新增相同的罰則，但一般而言， 受到不同懲處
新增解決方案印表機
下方顯示的解決方案印表機與 CVRP 範例，但也包含 資源遭捨棄的位置。
Python
def print_solution(data, manager, routing, assignment): """Prints assignment on console.""" print(f"Objective: {assignment.ObjectiveValue()}") # Display dropped nodes. dropped_nodes = "Dropped nodes:" for node in range(routing.Size()): if routing.IsStart(node) or routing.IsEnd(node): continue if assignment.Value(routing.NextVar(node)) == node: dropped_nodes += f" {manager.IndexToNode(node)}" print(dropped_nodes) # Display routes total_distance = 0 total_load = 0 for vehicle_id in range(data["num_vehicles"]): index = routing.Start(vehicle_id) plan_output = f"Route for vehicle {vehicle_id}:\n" route_distance = 0 route_load = 0 while not routing.IsEnd(index): node_index = manager.IndexToNode(index) route_load += data["demands"][node_index] plan_output += f" {node_index} Load({route_load}) -> " previous_index = index index = assignment.Value(routing.NextVar(index)) route_distance += routing.GetArcCostForVehicle( previous_index, index, vehicle_id ) plan_output += f" {manager.IndexToNode(index)} Load({route_load})\n" plan_output += f"Distance of the route: {route_distance}m\n" plan_output += f"Load of the route: {route_load}\n" print(plan_output) total_distance += route_distance total_load += route_load print(f"Total Distance of all routes: {total_distance}m") print(f"Total Load of all routes: {total_load}")
C++
//! @brief Print the solution. //! @param[in] data Data of the problem. //! @param[in] manager Index manager used. //! @param[in] routing Routing solver used. //! @param[in] solution Solution found by the solver. void PrintSolution(const DataModel& data, const RoutingIndexManager& manager, const RoutingModel& routing, const Assignment& solution) { // Display dropped nodes. std::ostringstream dropped_nodes; for (int64_t node = 0; node < routing.Size(); ++node) { if (routing.IsStart(node) || routing.IsEnd(node)) continue; if (solution.Value(routing.NextVar(node)) == node) { dropped_nodes << " " << manager.IndexToNode(node).value(); } } LOG(INFO) << "Dropped nodes:" << dropped_nodes.str(); // Display routes int64_t total_distance{0}; int64_t total_load{0}; for (int vehicle_id = 0; vehicle_id < data.num_vehicles; ++vehicle_id) { int64_t index = routing.Start(vehicle_id); LOG(INFO) << "Route for Vehicle " << vehicle_id << ":"; int64_t route_distance{0}; int64_t route_load{0}; std::ostringstream route; while (!routing.IsEnd(index)) { const int node_index = manager.IndexToNode(index).value(); route_load += data.demands[node_index]; route << node_index << " Load(" << route_load << ") -> "; const int64_t previous_index = index; index = solution.Value(routing.NextVar(index)); route_distance += routing.GetArcCostForVehicle(previous_index, index, int64_t{vehicle_id}); } LOG(INFO) << route.str() << manager.IndexToNode(index).value(); LOG(INFO) << "Distance of the route: " << route_distance << "m"; LOG(INFO) << "Load of the route: " << route_load; total_distance += route_distance; total_load += route_load; } LOG(INFO) << "Total distance of all routes: " << total_distance << "m"; LOG(INFO) << "Total load of all routes: " << total_load; LOG(INFO) << ""; LOG(INFO) << "Advanced usage:"; LOG(INFO) << "Problem solved in " << routing.solver()->wall_time() << "ms"; }
Java
/// @brief Print the solution. static void printSolution( DataModel data, RoutingModel routing, RoutingIndexManager manager, Assignment solution) { // Solution cost. logger.info("Objective: " + solution.objectiveValue()); // Inspect solution. // Display dropped nodes. String droppedNodes = "Dropped nodes:"; for (int node = 0; node < routing.size(); ++node) { if (routing.isStart(node) || routing.isEnd(node)) { continue; } if (solution.value(routing.nextVar(node)) == node) { droppedNodes += " " + manager.indexToNode(node); } } logger.info(droppedNodes); // Display routes long totalDistance = 0; long totalLoad = 0; for (int i = 0; i < data.vehicleNumber; ++i) { long index = routing.start(i); logger.info("Route for Vehicle " + i + ":"); long routeDistance = 0; long routeLoad = 0; String route = ""; while (!routing.isEnd(index)) { long nodeIndex = manager.indexToNode(index); routeLoad += data.demands[(int) nodeIndex]; route += nodeIndex + " Load(" + routeLoad + ") -> "; long previousIndex = index; index = solution.value(routing.nextVar(index)); routeDistance += routing.getArcCostForVehicle(previousIndex, index, i); } route += manager.indexToNode(routing.end(i)); logger.info(route); logger.info("Distance of the route: " + routeDistance + "m"); totalDistance += routeDistance; totalLoad += routeLoad; } logger.info("Total Distance of all routes: " + totalDistance + "m"); logger.info("Total Load of all routes: " + totalLoad); }
C#
/// <summary> /// Print the solution. /// </summary> static void PrintSolution(in DataModel data, in RoutingModel routing, in RoutingIndexManager manager, in Assignment solution) { Console.WriteLine($"Objective {solution.ObjectiveValue()}:"); // Inspect solution. // Display dropped nodes. string droppedNodes = "Dropped nodes:"; for (int index = 0; index < routing.Size(); ++index) { if (routing.IsStart(index) || routing.IsEnd(index)) { continue; } if (solution.Value(routing.NextVar(index)) == index) { droppedNodes += " " + manager.IndexToNode(index); } } Console.WriteLine("{0}", droppedNodes); // Inspect solution. long totalDistance = 0; long totalLoad = 0; for (int i = 0; i < data.VehicleNumber; ++i) { Console.WriteLine("Route for Vehicle {0}:", i); long routeDistance = 0; long routeLoad = 0; var index = routing.Start(i); while (routing.IsEnd(index) == false) { long nodeIndex = manager.IndexToNode(index); routeLoad += data.Demands[nodeIndex]; Console.Write("{0} Load({1}) -> ", nodeIndex, routeLoad); var previousIndex = index; index = solution.Value(routing.NextVar(index)); routeDistance += routing.GetArcCostForVehicle(previousIndex, index, 0); } Console.WriteLine("{0}", manager.IndexToNode((int)index)); Console.WriteLine("Distance of the route: {0}m", routeDistance); totalDistance += routeDistance; totalLoad += routeLoad; } Console.WriteLine("Total Distance of all routes: {0}m", totalDistance); Console.WriteLine("Total Load of all routes: {0}m", totalLoad); }
執行程式
執行程式時，程式會傳回下列輸出內容。請注意， 解開了位置 6 和 15 的位置。
Objective: 7936 Dropped nodes: 6 15 Route for vehicle 0: 0 Load(0) -> 9 Load(1) -> 14 Load(7) -> 16 Load(15) -> 0 Load(15) Distance of the route: 1324m Load of the route: 15 Route for vehicle 1: 0 Load(0) -> 12 Load(2) -> 11 Load(3) -> 4 Load(9) -> 3 Load(12) -> 1 Load(13) -> 0 Load(13) Distance of the route: 1872m Load of the route: 13 Route for vehicle 2: 0 Load(0) -> 7 Load(8) -> 13 Load(14) -> 0 Load(14) Distance of the route: 868m Load of the route: 14 Route for vehicle 3: 0 Load(0) -> 8 Load(8) -> 10 Load(10) -> 2 Load(11) -> 5 Load(14) -> 0 Load(14) Distance of the route: 1872m Load of the route: 14 Total Distance of all routes: 5936m Total Load of all routes: 56
這是路徑圖。
完成計畫
以下是完整的計畫。
Python
"""Capacited Vehicles Routing Problem (CVRP).""" from ortools.constraint_solver import routing_enums_pb2 from ortools.constraint_solver import pywrapcp def create_data_model(): """Stores the data for the problem.""" data = {} data["distance_matrix"] = [ # fmt: off [0, 548, 776, 696, 582, 274, 502, 194, 308, 194, 536, 502, 388, 354, 468, 776, 662], [548, 0, 684, 308, 194, 502, 730, 354, 696, 742, 1084, 594, 480, 674, 1016, 868, 1210], [776, 684, 0, 992, 878, 502, 274, 810, 468, 742, 400, 1278, 1164, 1130, 788, 1552, 754], [696, 308, 992, 0, 114, 650, 878, 502, 844, 890, 1232, 514, 628, 822, 1164, 560, 1358], [582, 194, 878, 114, 0, 536, 764, 388, 730, 776, 1118, 400, 514, 708, 1050, 674, 1244], [274, 502, 502, 650, 536, 0, 228, 308, 194, 240, 582, 776, 662, 628, 514, 1050, 708], [502, 730, 274, 878, 764, 228, 0, 536, 194, 468, 354, 1004, 890, 856, 514, 1278, 480], [194, 354, 810, 502, 388, 308, 536, 0, 342, 388, 730, 468, 354, 320, 662, 742, 856], [308, 696, 468, 844, 730, 194, 194, 342, 0, 274, 388, 810, 696, 662, 320, 1084, 514], [194, 742, 742, 890, 776, 240, 468, 388, 274, 0, 342, 536, 422, 388, 274, 810, 468], [536, 1084, 400, 1232, 1118, 582, 354, 730, 388, 342, 0, 878, 764, 730, 388, 1152, 354], [502, 594, 1278, 514, 400, 776, 1004, 468, 810, 536, 878, 0, 114, 308, 650, 274, 844], [388, 480, 1164, 628, 514, 662, 890, 354, 696, 422, 764, 114, 0, 194, 536, 388, 730], [354, 674, 1130, 822, 708, 628, 856, 320, 662, 388, 730, 308, 194, 0, 342, 422, 536], [468, 1016, 788, 1164, 1050, 514, 514, 662, 320, 274, 388, 650, 536, 342, 0, 764, 194], [776, 868, 1552, 560, 674, 1050, 1278, 742, 1084, 810, 1152, 274, 388, 422, 764, 0, 798], [662, 1210, 754, 1358, 1244, 708, 480, 856, 514, 468, 354, 844, 730, 536, 194, 798, 0], # fmt: on ] data["demands"] = [0, 1, 1, 3, 6, 3, 6, 8, 8, 1, 2, 1, 2, 6, 6, 8, 8] data["vehicle_capacities"] = [15, 15, 15, 15] data["num_vehicles"] = 4 data["depot"] = 0 return data def print_solution(data, manager, routing, assignment): """Prints assignment on console.""" print(f"Objective: {assignment.ObjectiveValue()}") # Display dropped nodes. dropped_nodes = "Dropped nodes:" for node in range(routing.Size()): if routing.IsStart(node) or routing.IsEnd(node): continue if assignment.Value(routing.NextVar(node)) == node: dropped_nodes += f" {manager.IndexToNode(node)}" print(dropped_nodes) # Display routes total_distance = 0 total_load = 0 for vehicle_id in range(data["num_vehicles"]): index = routing.Start(vehicle_id) plan_output = f"Route for vehicle {vehicle_id}:\n" route_distance = 0 route_load = 0 while not routing.IsEnd(index): node_index = manager.IndexToNode(index) route_load += data["demands"][node_index] plan_output += f" {node_index} Load({route_load}) -> " previous_index = index index = assignment.Value(routing.NextVar(index)) route_distance += routing.GetArcCostForVehicle( previous_index, index, vehicle_id ) plan_output += f" {manager.IndexToNode(index)} Load({route_load})\n" plan_output += f"Distance of the route: {route_distance}m\n" plan_output += f"Load of the route: {route_load}\n" print(plan_output) total_distance += route_distance total_load += route_load print(f"Total Distance of all routes: {total_distance}m") print(f"Total Load of all routes: {total_load}") def main(): """Solve the CVRP problem.""" # Instantiate the data problem. data = create_data_model() # Create the routing index manager. manager = pywrapcp.RoutingIndexManager( len(data["distance_matrix"]), data["num_vehicles"], data["depot"] ) # Create Routing Model. routing = pywrapcp.RoutingModel(manager) # Create and register a transit callback. def distance_callback(from_index, to_index): """Returns the distance between the two nodes.""" # Convert from routing variable Index to distance matrix NodeIndex. from_node = manager.IndexToNode(from_index) to_node = manager.IndexToNode(to_index) return data["distance_matrix"][from_node][to_node] transit_callback_index = routing.RegisterTransitCallback(distance_callback) # Define cost of each arc. routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index) # Add Capacity constraint. def demand_callback(from_index): """Returns the demand of the node.""" # Convert from routing variable Index to demands NodeIndex. from_node = manager.IndexToNode(from_index) return data["demands"][from_node] demand_callback_index = routing.RegisterUnaryTransitCallback(demand_callback) routing.AddDimensionWithVehicleCapacity( demand_callback_index, 0, # null capacity slack data["vehicle_capacities"], # vehicle maximum capacities True, # start cumul to zero "Capacity", ) # Allow to drop nodes. penalty = 1000 for node in range(1, len(data["distance_matrix"])): routing.AddDisjunction([manager.NodeToIndex(node)], penalty) # Setting first solution heuristic. search_parameters = pywrapcp.DefaultRoutingSearchParameters() search_parameters.first_solution_strategy = ( routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC ) search_parameters.local_search_metaheuristic = ( routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH ) search_parameters.time_limit.FromSeconds(1) # Solve the problem. assignment = routing.SolveWithParameters(search_parameters) # Print solution on console. if assignment: print_solution(data, manager, routing, assignment) if __name__ == "__main__": main()
C++
#include <cstdint> #include <sstream> #include <vector> #include "google/protobuf/duration.pb.h" #include "ortools/constraint_solver/routing.h" #include "ortools/constraint_solver/routing_enums.pb.h" #include "ortools/constraint_solver/routing_index_manager.h" #include "ortools/constraint_solver/routing_parameters.h" namespace operations_research { struct DataModel { const std::vector<std::vector<int64_t>> distance_matrix{ {0, 548, 776, 696, 582, 274, 502, 194, 308, 194, 536, 502, 388, 354, 468, 776, 662}, {548, 0, 684, 308, 194, 502, 730, 354, 696, 742, 1084, 594, 480, 674, 1016, 868, 1210}, {776, 684, 0, 992, 878, 502, 274, 810, 468, 742, 400, 1278, 1164, 1130, 788, 1552, 754}, {696, 308, 992, 0, 114, 650, 878, 502, 844, 890, 1232, 514, 628, 822, 1164, 560, 1358}, {582, 194, 878, 114, 0, 536, 764, 388, 730, 776, 1118, 400, 514, 708, 1050, 674, 1244}, {274, 502, 502, 650, 536, 0, 228, 308, 194, 240, 582, 776, 662, 628, 514, 1050, 708}, {502, 730, 274, 878, 764, 228, 0, 536, 194, 468, 354, 1004, 890, 856, 514, 1278, 480}, {194, 354, 810, 502, 388, 308, 536, 0, 342, 388, 730, 468, 354, 320, 662, 742, 856}, {308, 696, 468, 844, 730, 194, 194, 342, 0, 274, 388, 810, 696, 662, 320, 1084, 514}, {194, 742, 742, 890, 776, 240, 468, 388, 274, 0, 342, 536, 422, 388, 274, 810, 468}, {536, 1084, 400, 1232, 1118, 582, 354, 730, 388, 342, 0, 878, 764, 730, 388, 1152, 354}, {502, 594, 1278, 514, 400, 776, 1004, 468, 810, 536, 878, 0, 114, 308, 650, 274, 844}, {388, 480, 1164, 628, 514, 662, 890, 354, 696, 422, 764, 114, 0, 194, 536, 388, 730}, {354, 674, 1130, 822, 708, 628, 856, 320, 662, 388, 730, 308, 194, 0, 342, 422, 536}, {468, 1016, 788, 1164, 1050, 514, 514, 662, 320, 274, 388, 650, 536, 342, 0, 764, 194}, {776, 868, 1552, 560, 674, 1050, 1278, 742, 1084, 810, 1152, 274, 388, 422, 764, 0, 798}, {662, 1210, 754, 1358, 1244, 708, 480, 856, 514, 468, 354, 844, 730, 536, 194, 798, 0}, }; const std::vector<int64_t> demands{ 0, 1, 1, 3, 6, 3, 6, 8, 8, 1, 2, 1, 2, 6, 6, 8, 8, }; const std::vector<int64_t> vehicle_capacities{15, 15, 15, 15}; const int num_vehicles = 4; const RoutingIndexManager::NodeIndex depot{0}; }; //! @brief Print the solution. //! @param[in] data Data of the problem. //! @param[in] manager Index manager used. //! @param[in] routing Routing solver used. //! @param[in] solution Solution found by the solver. void PrintSolution(const DataModel& data, const RoutingIndexManager& manager, const RoutingModel& routing, const Assignment& solution) { // Display dropped nodes. std::ostringstream dropped_nodes; for (int64_t node = 0; node < routing.Size(); ++node) { if (routing.IsStart(node) || routing.IsEnd(node)) continue; if (solution.Value(routing.NextVar(node)) == node) { dropped_nodes << " " << manager.IndexToNode(node).value(); } } LOG(INFO) << "Dropped nodes:" << dropped_nodes.str(); // Display routes int64_t total_distance{0}; int64_t total_load{0}; for (int vehicle_id = 0; vehicle_id < data.num_vehicles; ++vehicle_id) { int64_t index = routing.Start(vehicle_id); LOG(INFO) << "Route for Vehicle " << vehicle_id << ":"; int64_t route_distance{0}; int64_t route_load{0}; std::ostringstream route; while (!routing.IsEnd(index)) { const int node_index = manager.IndexToNode(index).value(); route_load += data.demands[node_index]; route << node_index << " Load(" << route_load << ") -> "; const int64_t previous_index = index; index = solution.Value(routing.NextVar(index)); route_distance += routing.GetArcCostForVehicle(previous_index, index, int64_t{vehicle_id}); } LOG(INFO) << route.str() << manager.IndexToNode(index).value(); LOG(INFO) << "Distance of the route: " << route_distance << "m"; LOG(INFO) << "Load of the route: " << route_load; total_distance += route_distance; total_load += route_load; } LOG(INFO) << "Total distance of all routes: " << total_distance << "m"; LOG(INFO) << "Total load of all routes: " << total_load; LOG(INFO) << ""; LOG(INFO) << "Advanced usage:"; LOG(INFO) << "Problem solved in " << routing.solver()->wall_time() << "ms"; } void VrpDropNodes() { // Instantiate the data problem. DataModel data; // Create Routing Index Manager RoutingIndexManager manager(data.distance_matrix.size(), data.num_vehicles, data.depot); // Create Routing Model. RoutingModel routing(manager); // Create and register a transit callback. const int transit_callback_index = routing.RegisterTransitCallback( [&data, &manager](const int64_t from_index, const int64_t to_index) -> int64_t { // Convert from routing variable Index to distance matrix NodeIndex. const int from_node = manager.IndexToNode(from_index).value(); const int to_node = manager.IndexToNode(to_index).value(); return data.distance_matrix[from_node][to_node]; }); // Define cost of each arc. routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index); // Add Capacity constraint. const int demand_callback_index = routing.RegisterUnaryTransitCallback( [&data, &manager](const int64_t from_index) -> int64_t { // Convert from routing variable Index to demand NodeIndex. const int from_node = manager.IndexToNode(from_index).value(); return data.demands[from_node]; }); routing.AddDimensionWithVehicleCapacity( demand_callback_index, // transit callback index int64_t{0}, // null capacity slack data.vehicle_capacities, // vehicle maximum capacities true, // start cumul to zero "Capacity"); // Allow to drop nodes. int64_t penalty{1000}; for (int i = 1; i < data.distance_matrix.size(); ++i) { routing.AddDisjunction( {manager.NodeToIndex(RoutingIndexManager::NodeIndex(i))}, penalty); } // Setting first solution heuristic. RoutingSearchParameters search_parameters = DefaultRoutingSearchParameters(); search_parameters.set_first_solution_strategy( FirstSolutionStrategy::PATH_CHEAPEST_ARC); search_parameters.set_local_search_metaheuristic( LocalSearchMetaheuristic::GUIDED_LOCAL_SEARCH); search_parameters.mutable_time_limit()->set_seconds(1); // Solve the problem. const Assignment* solution = routing.SolveWithParameters(search_parameters); // Print solution on console. PrintSolution(data, manager, routing, *solution); } } // namespace operations_research int main(int /*argc*/, char* /*argv*/[]) { operations_research::VrpDropNodes(); return EXIT_SUCCESS; }
Java
package com.google.ortools.constraintsolver.samples; import com.google.ortools.Loader; import com.google.ortools.constraintsolver.Assignment; import com.google.ortools.constraintsolver.FirstSolutionStrategy; import com.google.ortools.constraintsolver.LocalSearchMetaheuristic; import com.google.ortools.constraintsolver.RoutingIndexManager; import com.google.ortools.constraintsolver.RoutingModel; import com.google.ortools.constraintsolver.RoutingSearchParameters; import com.google.ortools.constraintsolver.main; import com.google.protobuf.Duration; import java.util.logging.Logger; /** Minimal VRP.*/ public class VrpDropNodes { private static final Logger logger = Logger.getLogger(VrpDropNodes.class.getName()); static class DataModel { public final long[][] distanceMatrix = { {0, 548, 776, 696, 582, 274, 502, 194, 308, 194, 536, 502, 388, 354, 468, 776, 662}, {548, 0, 684, 308, 194, 502, 730, 354, 696, 742, 1084, 594, 480, 674, 1016, 868, 1210}, {776, 684, 0, 992, 878, 502, 274, 810, 468, 742, 400, 1278, 1164, 1130, 788, 1552, 754}, {696, 308, 992, 0, 114, 650, 878, 502, 844, 890, 1232, 514, 628, 822, 1164, 560, 1358}, {582, 194, 878, 114, 0, 536, 764, 388, 730, 776, 1118, 400, 514, 708, 1050, 674, 1244}, {274, 502, 502, 650, 536, 0, 228, 308, 194, 240, 582, 776, 662, 628, 514, 1050, 708}, {502, 730, 274, 878, 764, 228, 0, 536, 194, 468, 354, 1004, 890, 856, 514, 1278, 480}, {194, 354, 810, 502, 388, 308, 536, 0, 342, 388, 730, 468, 354, 320, 662, 742, 856}, {308, 696, 468, 844, 730, 194, 194, 342, 0, 274, 388, 810, 696, 662, 320, 1084, 514}, {194, 742, 742, 890, 776, 240, 468, 388, 274, 0, 342, 536, 422, 388, 274, 810, 468}, {536, 1084, 400, 1232, 1118, 582, 354, 730, 388, 342, 0, 878, 764, 730, 388, 1152, 354}, {502, 594, 1278, 514, 400, 776, 1004, 468, 810, 536, 878, 0, 114, 308, 650, 274, 844}, {388, 480, 1164, 628, 514, 662, 890, 354, 696, 422, 764, 114, 0, 194, 536, 388, 730}, {354, 674, 1130, 822, 708, 628, 856, 320, 662, 388, 730, 308, 194, 0, 342, 422, 536}, {468, 1016, 788, 1164, 1050, 514, 514, 662, 320, 274, 388, 650, 536, 342, 0, 764, 194}, {776, 868, 1552, 560, 674, 1050, 1278, 742, 1084, 810, 1152, 274, 388, 422, 764, 0, 798}, {662, 1210, 754, 1358, 1244, 708, 480, 856, 514, 468, 354, 844, 730, 536, 194, 798, 0}, }; public final long[] demands = {0, 1, 1, 3, 6, 3, 6, 8, 8, 1, 2, 1, 2, 6, 6, 8, 8}; public final long[] vehicleCapacities = {15, 15, 15, 15}; public final int vehicleNumber = 4; public final int depot = 0; } /// @brief Print the solution. static void printSolution( DataModel data, RoutingModel routing, RoutingIndexManager manager, Assignment solution) { // Solution cost. logger.info("Objective: " + solution.objectiveValue()); // Inspect solution. // Display dropped nodes. String droppedNodes = "Dropped nodes:"; for (int node = 0; node < routing.size(); ++node) { if (routing.isStart(node) || routing.isEnd(node)) { continue; } if (solution.value(routing.nextVar(node)) == node) { droppedNodes += " " + manager.indexToNode(node); } } logger.info(droppedNodes); // Display routes long totalDistance = 0; long totalLoad = 0; for (int i = 0; i < data.vehicleNumber; ++i) { long index = routing.start(i); logger.info("Route for Vehicle " + i + ":"); long routeDistance = 0; long routeLoad = 0; String route = ""; while (!routing.isEnd(index)) { long nodeIndex = manager.indexToNode(index); routeLoad += data.demands[(int) nodeIndex]; route += nodeIndex + " Load(" + routeLoad + ") -> "; long previousIndex = index; index = solution.value(routing.nextVar(index)); routeDistance += routing.getArcCostForVehicle(previousIndex, index, i); } route += manager.indexToNode(routing.end(i)); logger.info(route); logger.info("Distance of the route: " + routeDistance + "m"); totalDistance += routeDistance; totalLoad += routeLoad; } logger.info("Total Distance of all routes: " + totalDistance + "m"); logger.info("Total Load of all routes: " + totalLoad); } public static void main(String[] args) throws Exception { Loader.loadNativeLibraries(); // Instantiate the data problem. final DataModel data = new DataModel(); // Create Routing Index Manager RoutingIndexManager manager = new RoutingIndexManager(data.distanceMatrix.length, data.vehicleNumber, data.depot); // Create Routing Model. RoutingModel routing = new RoutingModel(manager); // Create and register a transit callback. final int transitCallbackIndex = routing.registerTransitCallback((long fromIndex, long toIndex) -> { // Convert from routing variable Index to user NodeIndex. int fromNode = manager.indexToNode(fromIndex); int toNode = manager.indexToNode(toIndex); return data.distanceMatrix[fromNode][toNode]; }); // Define cost of each arc. routing.setArcCostEvaluatorOfAllVehicles(transitCallbackIndex); // Add Capacity constraint. final int demandCallbackIndex = routing.registerUnaryTransitCallback((long fromIndex) -> { // Convert from routing variable Index to user NodeIndex. int fromNode = manager.indexToNode(fromIndex); return data.demands[fromNode]; }); routing.addDimensionWithVehicleCapacity(demandCallbackIndex, 0, // null capacity slack data.vehicleCapacities, // vehicle maximum capacities true, // start cumul to zero "Capacity"); // Allow to drop nodes. long penalty = 1000; for (int i = 1; i < data.distanceMatrix.length; ++i) { routing.addDisjunction(new long[] {manager.nodeToIndex(i)}, penalty); } // Setting first solution heuristic. RoutingSearchParameters searchParameters = main.defaultRoutingSearchParameters() .toBuilder() .setFirstSolutionStrategy(FirstSolutionStrategy.Value.PATH_CHEAPEST_ARC) .setLocalSearchMetaheuristic(LocalSearchMetaheuristic.Value.GUIDED_LOCAL_SEARCH) .setTimeLimit(Duration.newBuilder().setSeconds(1).build()) .build(); // Solve the problem. Assignment solution = routing.solveWithParameters(searchParameters); // Print solution on console. printSolution(data, routing, manager, solution); } }
C#
using System; using System.Collections.Generic; using Google.OrTools.ConstraintSolver; using Google.Protobuf.WellKnownTypes; // Duration /// <summary> /// Minimal Vrp with drop nodes. /// </summary> public class VrpDropNodes { class DataModel { public long[,] DistanceMatrix = { { 0, 548, 776, 696, 582, 274, 502, 194, 308, 194, 536, 502, 388, 354, 468, 776, 662 }, { 548, 0, 684, 308, 194, 502, 730, 354, 696, 742, 1084, 594, 480, 674, 1016, 868, 1210 }, { 776, 684, 0, 992, 878, 502, 274, 810, 468, 742, 400, 1278, 1164, 1130, 788, 1552, 754 }, { 696, 308, 992, 0, 114, 650, 878, 502, 844, 890, 1232, 514, 628, 822, 1164, 560, 1358 }, { 582, 194, 878, 114, 0, 536, 764, 388, 730, 776, 1118, 400, 514, 708, 1050, 674, 1244 }, { 274, 502, 502, 650, 536, 0, 228, 308, 194, 240, 582, 776, 662, 628, 514, 1050, 708 }, { 502, 730, 274, 878, 764, 228, 0, 536, 194, 468, 354, 1004, 890, 856, 514, 1278, 480 }, { 194, 354, 810, 502, 388, 308, 536, 0, 342, 388, 730, 468, 354, 320, 662, 742, 856 }, { 308, 696, 468, 844, 730, 194, 194, 342, 0, 274, 388, 810, 696, 662, 320, 1084, 514 }, { 194, 742, 742, 890, 776, 240, 468, 388, 274, 0, 342, 536, 422, 388, 274, 810, 468 }, { 536, 1084, 400, 1232, 1118, 582, 354, 730, 388, 342, 0, 878, 764, 730, 388, 1152, 354 }, { 502, 594, 1278, 514, 400, 776, 1004, 468, 810, 536, 878, 0, 114, 308, 650, 274, 844 }, { 388, 480, 1164, 628, 514, 662, 890, 354, 696, 422, 764, 114, 0, 194, 536, 388, 730 }, { 354, 674, 1130, 822, 708, 628, 856, 320, 662, 388, 730, 308, 194, 0, 342, 422, 536 }, { 468, 1016, 788, 1164, 1050, 514, 514, 662, 320, 274, 388, 650, 536, 342, 0, 764, 194 }, { 776, 868, 1552, 560, 674, 1050, 1278, 742, 1084, 810, 1152, 274, 388, 422, 764, 0, 798 }, { 662, 1210, 754, 1358, 1244, 708, 480, 856, 514, 468, 354, 844, 730, 536, 194, 798, 0 } }; public long[] Demands = { 0, 1, 1, 3, 6, 3, 6, 8, 8, 1, 2, 1, 2, 6, 6, 8, 8 }; public long[] VehicleCapacities = { 15, 15, 15, 15 }; public int VehicleNumber = 4; public int Depot = 0; }; /// <summary> /// Print the solution. /// </summary> static void PrintSolution(in DataModel data, in RoutingModel routing, in RoutingIndexManager manager, in Assignment solution) { Console.WriteLine($"Objective {solution.ObjectiveValue()}:"); // Inspect solution. // Display dropped nodes. string droppedNodes = "Dropped nodes:"; for (int index = 0; index < routing.Size(); ++index) { if (routing.IsStart(index) || routing.IsEnd(index)) { continue; } if (solution.Value(routing.NextVar(index)) == index) { droppedNodes += " " + manager.IndexToNode(index); } } Console.WriteLine("{0}", droppedNodes); // Inspect solution. long totalDistance = 0; long totalLoad = 0; for (int i = 0; i < data.VehicleNumber; ++i) { Console.WriteLine("Route for Vehicle {0}:", i); long routeDistance = 0; long routeLoad = 0; var index = routing.Start(i); while (routing.IsEnd(index) == false) { long nodeIndex = manager.IndexToNode(index); routeLoad += data.Demands[nodeIndex]; Console.Write("{0} Load({1}) -> ", nodeIndex, routeLoad); var previousIndex = index; index = solution.Value(routing.NextVar(index)); routeDistance += routing.GetArcCostForVehicle(previousIndex, index, 0); } Console.WriteLine("{0}", manager.IndexToNode((int)index)); Console.WriteLine("Distance of the route: {0}m", routeDistance); totalDistance += routeDistance; totalLoad += routeLoad; } Console.WriteLine("Total Distance of all routes: {0}m", totalDistance); Console.WriteLine("Total Load of all routes: {0}m", totalLoad); } public static void Main(String[] args) { // Instantiate the data problem. DataModel data = new DataModel(); // Create Routing Index Manager RoutingIndexManager manager = new RoutingIndexManager(data.DistanceMatrix.GetLength(0), data.VehicleNumber, data.Depot); // Create Routing Model. RoutingModel routing = new RoutingModel(manager); // Create and register a transit callback. int transitCallbackIndex = routing.RegisterTransitCallback((long fromIndex, long toIndex) => { // Convert from routing variable Index to // distance matrix NodeIndex. var fromNode = manager.IndexToNode(fromIndex); var toNode = manager.IndexToNode(toIndex); return data.DistanceMatrix[fromNode, toNode]; }); // Define cost of each arc. routing.SetArcCostEvaluatorOfAllVehicles(transitCallbackIndex); // Add Capacity constraint. int demandCallbackIndex = routing.RegisterUnaryTransitCallback((long fromIndex) => { // Convert from routing variable Index to // demand NodeIndex. var fromNode = manager.IndexToNode(fromIndex); return data.Demands[fromNode]; }); routing.AddDimensionWithVehicleCapacity(demandCallbackIndex, 0, // null capacity slack data.VehicleCapacities, // vehicle maximum capacities true, // start cumul to zero "Capacity"); // Allow to drop nodes. long penalty = 1000; for (int i = 1; i < data.DistanceMatrix.GetLength(0); ++i) { routing.AddDisjunction(new long[] { manager.NodeToIndex(i) }, penalty); } // Setting first solution heuristic. RoutingSearchParameters searchParameters = operations_research_constraint_solver.DefaultRoutingSearchParameters(); searchParameters.FirstSolutionStrategy = FirstSolutionStrategy.Types.Value.PathCheapestArc; searchParameters.LocalSearchMetaheuristic = LocalSearchMetaheuristic.Types.Value.GuidedLocalSearch; searchParameters.TimeLimit = new Duration { Seconds = 1 }; // Solve the problem. Assignment solution = routing.SolveWithParameters(searchParameters); // Print solution on console. PrintSolution(data, routing, manager, solution); } }