キャパシテッド車両ルート決定問題（CVRP）とは、 運搬が限られており、さまざまな場所で商品の集荷や配送を行う必要がある。 アイテムには重量や体積などの数量があり、車両には 最大容量。問題は集荷または配達で 最小のコストでアイテムを販売し、車両の積載量を超えることはありません。
次の例では、すべての商品アイテムを受け取っていると仮定しています。 この問題を解決するプログラムは、すべてのアイテムが配送されている場合にも機能します。 この場合、容量の制約は 基地が完全に埋まった状態になっています。しかし、容量の制約 どちらの場合も同じ方法で実装されます。
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");
2 つの位置を入力として受け取る距離コールバックとは異なり、
デマンド コールバックは、配達の場所（from_node）にのみ依存します。
定員の制約には車両の積荷の重量が含まれるため、 運搬（ルート上で蓄積される数量）の 次のように、容量のディメンションを作成します。 は、前の単語の距離次元に VRP の例。
この例では
AddDimensionWithVehicleCapacity
これは容量のベクトルを受け取ります。
この例の車両の定員はすべて同じなので、
AddDimension
メソッドを呼び出し、すべての車両数量の上限を 1 つ受け取ります。しかし、
AddDimensionWithVehicleCapacity は、次のような、より一般的なケースを処理します。
車両ごとに容量が異なります。
複数の貨物の種類と容量に関する問題
より複雑な CVRP では、各車両が数種類の異なる貨物を運ぶことがある で定義され、タイプごとに最大容量が設定されています。 たとえば、燃料配送トラックは複数の種類の燃料を輸送し、 容量の異なる複数のタンクに 接続されていますこのような問題に対処するには、 貨物のタイプごとに異なる容量のコールバックと寸法を作成します（ 一意の名前を付けてください）。
ソリューション プリンタを追加
ソリューション プリンタは、各車両のルートと 累積積載量: 車両が停車時に輸送している車両の総積 routes:
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。 すべてのアイテムが収まるように、 マルチナップサック問題です