정전식 차량 라우팅 문제(CVRP)는 운송 용량이 제한된 차량이 다양한 위치에서 상품을 수령하거나 배송해야 하는 VRP입니다. 항목에는 용량 또는 부피와 같은 수량이 있으며, 차량에는 담을 수 있는 최대 용량이 있습니다. 문제는 차량의 용량을 초과하지 않으면서 가장 저렴한 비용으로 상품을 수령하거나 배송하는 것입니다.
다음 예에서는 모든 항목이 선택되어 있다고 가정합니다. 이 문제를 해결하는 프로그램은 모든 항목이 전달되는 경우에도 작동합니다. 이 경우 차량이 창고를 완전히 로드한 상태에서 나갈 때 적용되는 용량 제약을 생각할 수 있습니다. 하지만 용량 제약조건은 두 경우 모두 동일한 방식으로 구현됩니다.
CVRP 예시
다음으로 용량 제약이 있는 VRP의 예를 살펴보겠습니다. 예에서는 이전 VRP 예를 확장하고 다음 요구사항을 추가합니다. 각 위치에는 수령할 상품의 수량에 해당하는 수요가 있습니다. 또한 각 차량의 최대 용량은 15입니다. (수요 또는 용량에 대한 단위는 지정하지 않습니다.)
아래 그리드에 파란색으로 표시된 위치와 회사 위치가 검은색으로 표시됩니다. 수요는 각 위치의 오른쪽 하단에 표시됩니다. 위치가 정의되는 방식에 관한 자세한 내용은 VRP 섹션의 위치 좌표를 참고하세요.
문제는 총 거리가 가장 짧은 차량에 경로를 할당하고 차량이 운반하는 총 금액이 용량을 초과하지 않도록 하는 것입니다.
OR 도구로 CVRP 예시 해결
다음 섹션에서는 OR 도구를 사용하여 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};
자바
public final long[] demands = {0, 1, 1, 2, 4, 2, 4, 8, 8, 1, 2, 1, 2, 4, 4, 8, 8}; public final long[] vehicleCapacities = {15, 15, 15, 15};
C#
public long[] Demands = { 0, 1, 1, 2, 4, 2, 4, 8, 8, 1, 2, 1, 2, 4, 4, 8, 8 }; public long[] VehicleCapacities = { 15, 15, 15, 15 };
데이터의 새 항목은 다음과 같습니다.
- 수요: 각 위치에는 수령할 상품의 수량(예: 중량 또는 부피)에 해당하는 수요가 있습니다.
- 수용 인원: 각 차량은 용량(차량이 보유할 수 있는 최대 수량)을 갖습니다. 차량이 경로를 따라 이동할 때 운송하는 총 물품 수량은 용량을 초과할 수 없습니다.
거리 콜백 추가
두 위치 간의 거리를 반환하는 함수인 거리 콜백은 이전 VRP 예와 동일한 방식으로 정의됩니다.
수요 콜백 및 용량 제약조건 추가
솔버는 거리 콜백 외에도 각 위치의 수요와 용량 제약 조건의 크기를 반환하는 수요 콜백도 필요합니다. 다음 코드는 이를 생성합니다.
Python
def demand_callback(from_index): """Returns the demand of the node.""" # Convert from routing variable Index to demands NodeIndex. from_node = manager.IndexToNode(from_index) return data["demands"][from_node] demand_callback_index = routing.RegisterUnaryTransitCallback(demand_callback) routing.AddDimensionWithVehicleCapacity( demand_callback_index, 0, # null capacity slack data["vehicle_capacities"], # vehicle maximum capacities True, # start cumul to zero "Capacity", )
C++
const int demand_callback_index = routing.RegisterUnaryTransitCallback( [&data, &manager](const int64_t from_index) -> int64_t { // Convert from routing variable Index to demand NodeIndex. const int from_node = manager.IndexToNode(from_index).value(); return data.demands[from_node]; }); routing.AddDimensionWithVehicleCapacity( demand_callback_index, // transit callback index int64_t{0}, // null capacity slack data.vehicle_capacities, // vehicle maximum capacities true, // start cumul to zero "Capacity");
자바
final int demandCallbackIndex = routing.registerUnaryTransitCallback((long fromIndex) -> { // Convert from routing variable Index to user NodeIndex. int fromNode = manager.indexToNode(fromIndex); return data.demands[fromNode]; }); routing.addDimensionWithVehicleCapacity(demandCallbackIndex, 0, // null capacity slack data.vehicleCapacities, // vehicle maximum capacities true, // start cumul to zero "Capacity");
C#
int demandCallbackIndex = routing.RegisterUnaryTransitCallback((long fromIndex) => { // Convert from routing variable Index to // demand NodeIndex. var fromNode = manager.IndexToNode(fromIndex); return data.Demands[fromNode]; }); routing.AddDimensionWithVehicleCapacity(demandCallbackIndex, 0, // null capacity slack data.VehicleCapacities, // vehicle maximum capacities true, // start cumul to zero "Capacity");
위치 쌍을 입력으로 사용하는 거리 콜백과 달리 수요 콜백은 배달의 위치 (from_node
)에만 종속됩니다.
용량 제약은 경로상에 누적되는 수량인 차량 화물의 무게와 관련이 있으므로 용량에 대한 측정기준을 이전 VRP 예의 거리 차원과 유사하게 만들어야 합니다.
이 경우 용량 벡터를 사용하는 AddDimensionWithVehicleCapacity
메서드를 사용합니다.
이 예의 모든 차량 용량은 동일하므로 모든 차량 수량에 대한 단일 상한값을 사용하는 AddDimension
메서드를 사용할 수 있습니다. 그러나 AddDimensionWithVehicleCapacity
는 차량에 수용량이 다른 더 일반적인 사례를 처리합니다.
여러 화물 유형 및 용량 관련 문제
더 복잡한 CVRP에서는 각 차량이 여러 유형의 화물을 운송할 수 있으며 각 유형의 화물은 최대 용량으로 운송할 수 있습니다. 예를 들어, 연료 공급 트럭은 용량이 다른 여러 탱크를 사용하여 여러 유형의 연료를 운반할 수 있습니다. 이러한 문제를 처리하려면 화물 유형마다 다른 용량 콜백 및 크기를 만드세요. 고유한 이름을 지정해야 합니다.
솔루션 프린터 추가
솔루션 프린터에는 각 차량의 경로 및 누적 부하(차량이 이동 중에 정차하는 총 금액)가 표시됩니다.
Python
def print_solution(data, manager, routing, solution): """Prints solution on console.""" print(f"Objective: {solution.ObjectiveValue()}") total_distance = 0 total_load = 0 for vehicle_id in range(data["num_vehicles"]): index = routing.Start(vehicle_id) plan_output = f"Route for vehicle {vehicle_id}:\n" route_distance = 0 route_load = 0 while not routing.IsEnd(index): node_index = manager.IndexToNode(index) route_load += data["demands"][node_index] plan_output += f" {node_index} Load({route_load}) -> " previous_index = index index = solution.Value(routing.NextVar(index)) route_distance += routing.GetArcCostForVehicle( previous_index, index, vehicle_id ) plan_output += f" {manager.IndexToNode(index)} Load({route_load})\n" plan_output += f"Distance of the route: {route_distance}m\n" plan_output += f"Load of the route: {route_load}\n" print(plan_output) total_distance += route_distance total_load += route_load print(f"Total distance of all routes: {total_distance}m") print(f"Total load of all routes: {total_load}")
C++
//! @brief Print the solution. //! @param[in] data Data of the problem. //! @param[in] manager Index manager used. //! @param[in] routing Routing solver used. //! @param[in] solution Solution found by the solver. void PrintSolution(const DataModel& data, const RoutingIndexManager& manager, const RoutingModel& routing, const Assignment& solution) { int64_t total_distance = 0; int64_t total_load = 0; for (int vehicle_id = 0; vehicle_id < data.num_vehicles; ++vehicle_id) { int64_t index = routing.Start(vehicle_id); LOG(INFO) << "Route for Vehicle " << vehicle_id << ":"; int64_t route_distance = 0; int64_t route_load = 0; std::stringstream route; while (!routing.IsEnd(index)) { const int node_index = manager.IndexToNode(index).value(); route_load += data.demands[node_index]; route << node_index << " Load(" << route_load << ") -> "; const int64_t previous_index = index; index = solution.Value(routing.NextVar(index)); route_distance += routing.GetArcCostForVehicle(previous_index, index, int64_t{vehicle_id}); } LOG(INFO) << route.str() << manager.IndexToNode(index).value(); LOG(INFO) << "Distance of the route: " << route_distance << "m"; LOG(INFO) << "Load of the route: " << route_load; total_distance += route_distance; total_load += route_load; } LOG(INFO) << "Total distance of all routes: " << total_distance << "m"; LOG(INFO) << "Total load of all routes: " << total_load; LOG(INFO) << ""; LOG(INFO) << "Advanced usage:"; LOG(INFO) << "Problem solved in " << routing.solver()->wall_time() << "ms"; }
자바
/// @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; }
자바
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의 경우에도 모든 항목이 차량에 적합한지 결정하는 것은 다중 배낭 문제의 한 버전입니다.