キャパシティ付き車両ルーティング問題(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 };
データの新しい項目は次のとおりです。
- 需要: 各ロケーションには、集荷する商品アイテムの数量(重量や数量など)に対応する需要があります。
- 収容人数: 各車両に容量(車両が格納できる最大数)があります。ルートを走行する車両の総容量はその容量を超えることはできません。
距離のコールバックを追加する
距離コールバック(任意の 2 つの地点間の距離を返す関数)は、前の 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
メソッドを使用できます。このメソッドはすべての車両数量の上限を 1 つ取ります。ただし、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 などの制約があるルーティング問題では、たとえば、輸送される物品の総量が車両の総容量を超過する場合など、現実的な解決策が得られない可能性があります。このような問題を解決しようとすると、ソルバーが網羅的な検索を実行することもあります。網羅的な検索には非常に時間がかかるため、結果的にプログラムをあきらめて中断する必要があります。
通常は問題ありません。ただし、問題が解決しない場合にプログラムが長時間実行されないようにする方法がいくつかあります。
- プログラムに時間制限を設定します。これにより、解決策が見つからなくても検索が停止されます。ただし、時間のかかる検索を必要とするソリューションが問題にある場合、プログラムはソリューションを見つける前に時間制限に達する可能性があることに注意してください。
- 店舗への来店数を減らすペナルティを設定します。これにより、解法で問題が発生した場合に、すべての拠点を訪れるわけではない「解決策」を返すことができます。ペナルティとアクセスの減少をご覧ください。
一般的に、特定の問題の解決策が見つかりにくいことがあります。総需要が合計容量を超えない CVRP であっても、すべてのアイテムが車両に適合するかどうかは、複数のナップサック問題のバージョンです。