在本部分中，我们介绍了一个 VRP，其中每辆车取物件 然后把它们送到其他地方问题在于分配路由 让车辆能够取走和配送所有物品，同时最大限度地减少 最长路线的长度。
VRP 示例（含自提和配送信息）
下图显示了以类似的网格形式显示的取货和送货地点 与上一个 VRP 示例中的规则相同。对于每个 商品在取货地点与送货地点之间会有指向边缘。
使用 OR 工具解示例
以下部分介绍了如何通过取货和配送来解决 VRP 问题 ，了解所有最新动态。大部分代码都是从 之前的 VRP 示例，因此我们将 重点关注新的部分
创建数据
此问题的数据包含来自上一个 VRP 的距离矩阵
以及包含自提和配送地点对的列表，
data['pickups_deliveries']，对应于图中的定向边
。以下代码定义了自提和送货地点。
Python
data["pickups_deliveries"] = [ [1, 6], [2, 10], [4, 3], [5, 9], [7, 8], [15, 11], [13, 12], [16, 14], ]
C++
const std::vector<std::vector<RoutingIndexManager::NodeIndex>> pickups_deliveries{ {RoutingIndexManager::NodeIndex{1}, RoutingIndexManager::NodeIndex{6}}, {RoutingIndexManager::NodeIndex{2}, RoutingIndexManager::NodeIndex{10}}, {RoutingIndexManager::NodeIndex{4}, RoutingIndexManager::NodeIndex{3}}, {RoutingIndexManager::NodeIndex{5}, RoutingIndexManager::NodeIndex{9}}, {RoutingIndexManager::NodeIndex{7}, RoutingIndexManager::NodeIndex{8}}, {RoutingIndexManager::NodeIndex{15}, RoutingIndexManager::NodeIndex{11}}, {RoutingIndexManager::NodeIndex{13}, RoutingIndexManager::NodeIndex{12}}, {RoutingIndexManager::NodeIndex{16}, RoutingIndexManager::NodeIndex{14}}, };
Java
public final int[][] pickupsDeliveries = {
{1, 6},
{2, 10},
{4, 3},
{5, 9},
{7, 8},
{15, 11},
{13, 12},
{16, 14},
};C#
public int[][] PickupsDeliveries = {
new int[] { 1, 6 }, new int[] { 2, 10 }, new int[] { 4, 3 }, new int[] { 5, 9 },
new int[] { 7, 8 }, new int[] { 15, 11 }, new int[] { 13, 12 }, new int[] { 16, 14 },
};对于每一对，第一个条目是上车地点的索引，第二个条目是 是送货地点的索引。
指定自提和送餐请求
以下代码定义了使用自提和配送选项
data['pickups_deliveries']的送货地点。
Python
for request in data["pickups_deliveries"]: pickup_index = manager.NodeToIndex(request[0]) delivery_index = manager.NodeToIndex(request[1]) routing.AddPickupAndDelivery(pickup_index, delivery_index) routing.solver().Add( routing.VehicleVar(pickup_index) == routing.VehicleVar(delivery_index) ) routing.solver().Add( distance_dimension.CumulVar(pickup_index) <= distance_dimension.CumulVar(delivery_index) )
C++
Solver* const solver = routing.solver(); for (const auto& request : data.pickups_deliveries) { const int64_t pickup_index = manager.NodeToIndex(request[0]); const int64_t delivery_index = manager.NodeToIndex(request[1]); routing.AddPickupAndDelivery(pickup_index, delivery_index); solver->AddConstraint(solver->MakeEquality( routing.VehicleVar(pickup_index), routing.VehicleVar(delivery_index))); solver->AddConstraint( solver->MakeLessOrEqual(distance_dimension->CumulVar(pickup_index), distance_dimension->CumulVar(delivery_index))); }
Java
Solver solver = routing.solver(); for (int[] request : data.pickupsDeliveries) { long pickupIndex = manager.nodeToIndex(request[0]); long deliveryIndex = manager.nodeToIndex(request[1]); routing.addPickupAndDelivery(pickupIndex, deliveryIndex); solver.addConstraint( solver.makeEquality(routing.vehicleVar(pickupIndex), routing.vehicleVar(deliveryIndex))); solver.addConstraint(solver.makeLessOrEqual( distanceDimension.cumulVar(pickupIndex), distanceDimension.cumulVar(deliveryIndex))); }
C#
Solver solver = routing.solver(); for (int i = 0; i < data.PickupsDeliveries.GetLength(0); i++) { long pickupIndex = manager.NodeToIndex(data.PickupsDeliveries[i][0]); long deliveryIndex = manager.NodeToIndex(data.PickupsDeliveries[i][1]); routing.AddPickupAndDelivery(pickupIndex, deliveryIndex); solver.Add(solver.MakeEquality(routing.VehicleVar(pickupIndex), routing.VehicleVar(deliveryIndex))); solver.Add(solver.MakeLessOrEqual(distanceDimension.CumulVar(pickupIndex), distanceDimension.CumulVar(deliveryIndex))); }
对于每一对，命令
routing.AddPickupAndDelivery(pickup_index, delivery_index) 创建了上车点
和送货请求
下面这行代码要求必须选择每件商品 。
routing.solver().Add(
routing.VehicleVar(pickup_index) ==
routing.VehicleVar(delivery_index))最后，我们添加了一个显而易见的要求，即每件商品都必须挑选 。为此，我们要求 车辆在物品上车点的累计距离 不超过其在送货地点的累计距离。
routing.solver().Add(
distance_dimension.CumulVar(pickup_index) <=
distance_dimension.CumulVar(delivery_index))运行程序
有关提供取件和送餐服务的 VRP 的完整计划，请参见 下一部分。 运行该程序时，它会显示以下路由。
Objective: 226116 Route for vehicle 0: 0 -> 13 -> 15 -> 11 -> 12 -> 0 Distance of the route: 1552m Route for vehicle 1: 0 -> 5 -> 2 -> 10 -> 16 -> 14 -> 9 -> 0 Distance of the route: 2192m Route for vehicle 2: 0 -> 4 -> 3 -> 0 Distance of the route: 1392m Route for vehicle 3: 0 -> 7 -> 1 -> 6 -> 8 -> 0 Distance of the route: 1780m Total Distance of all routes: 6916m
下图显示了这些路由：
完成计划
完整的程序如下所示。
Python
"""Simple Pickup Delivery Problem (PDP).""" 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["pickups_deliveries"] = [ [1, 6], [2, 10], [4, 3], [5, 9], [7, 8], [15, 11], [13, 12], [16, 14], ] 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 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 while not routing.IsEnd(index): plan_output += f" {manager.IndexToNode(index)} -> " previous_index = index index = solution.Value(routing.NextVar(index)) route_distance += routing.GetArcCostForVehicle( previous_index, index, vehicle_id ) plan_output += f"{manager.IndexToNode(index)}\n" plan_output += f"Distance of the route: {route_distance}m\n" print(plan_output) total_distance += route_distance print(f"Total Distance of all routes: {total_distance}m") def main(): """Entry point of the program.""" # 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) # Define cost of each arc. def distance_callback(from_index, to_index): """Returns the manhattan 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) routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index) # Add Distance constraint. dimension_name = "Distance" routing.AddDimension( transit_callback_index, 0, # no slack 3000, # vehicle maximum travel distance True, # start cumul to zero dimension_name, ) distance_dimension = routing.GetDimensionOrDie(dimension_name) distance_dimension.SetGlobalSpanCostCoefficient(100) # Define Transportation Requests. for request in data["pickups_deliveries"]: pickup_index = manager.NodeToIndex(request[0]) delivery_index = manager.NodeToIndex(request[1]) routing.AddPickupAndDelivery(pickup_index, delivery_index) routing.solver().Add( routing.VehicleVar(pickup_index) == routing.VehicleVar(delivery_index) ) routing.solver().Add( distance_dimension.CumulVar(pickup_index) <= distance_dimension.CumulVar(delivery_index) ) # Setting first solution heuristic. search_parameters = pywrapcp.DefaultRoutingSearchParameters() search_parameters.first_solution_strategy = ( routing_enums_pb2.FirstSolutionStrategy.PARALLEL_CHEAPEST_INSERTION ) # 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 "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<std::vector<RoutingIndexManager::NodeIndex>> pickups_deliveries{ {RoutingIndexManager::NodeIndex{1}, RoutingIndexManager::NodeIndex{6}}, {RoutingIndexManager::NodeIndex{2}, RoutingIndexManager::NodeIndex{10}}, {RoutingIndexManager::NodeIndex{4}, RoutingIndexManager::NodeIndex{3}}, {RoutingIndexManager::NodeIndex{5}, RoutingIndexManager::NodeIndex{9}}, {RoutingIndexManager::NodeIndex{7}, RoutingIndexManager::NodeIndex{8}}, {RoutingIndexManager::NodeIndex{15}, RoutingIndexManager::NodeIndex{11}}, {RoutingIndexManager::NodeIndex{13}, RoutingIndexManager::NodeIndex{12}}, {RoutingIndexManager::NodeIndex{16}, RoutingIndexManager::NodeIndex{14}}, }; 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}; 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}; std::stringstream route; while (!routing.IsEnd(index)) { route << manager.IndexToNode(index).value() << " -> "; 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"; total_distance += route_distance; } LOG(INFO) << "Total distance of all routes: " << total_distance << "m"; LOG(INFO) << ""; LOG(INFO) << "Advanced usage:"; LOG(INFO) << "Problem solved in " << routing.solver()->wall_time() << "ms"; } void VrpGlobalSpan() { // 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); // Define cost of each arc. 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]; }); routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index); // Add Distance constraint. routing.AddDimension(transit_callback_index, // transit callback 0, // no slack 3000, // vehicle maximum travel distance true, // start cumul to zero "Distance"); RoutingDimension* distance_dimension = routing.GetMutableDimension("Distance"); distance_dimension->SetGlobalSpanCostCoefficient(100); // Define Transportation Requests. Solver* const solver = routing.solver(); for (const auto& request : data.pickups_deliveries) { const int64_t pickup_index = manager.NodeToIndex(request[0]); const int64_t delivery_index = manager.NodeToIndex(request[1]); routing.AddPickupAndDelivery(pickup_index, delivery_index); solver->AddConstraint(solver->MakeEquality( routing.VehicleVar(pickup_index), routing.VehicleVar(delivery_index))); solver->AddConstraint( solver->MakeLessOrEqual(distance_dimension->CumulVar(pickup_index), distance_dimension->CumulVar(delivery_index))); } // Setting first solution heuristic. RoutingSearchParameters searchParameters = DefaultRoutingSearchParameters(); searchParameters.set_first_solution_strategy( FirstSolutionStrategy::PARALLEL_CHEAPEST_INSERTION); // Solve the problem. const Assignment* solution = routing.SolveWithParameters(searchParameters); // Print solution on console. PrintSolution(data, manager, routing, *solution); } } // namespace operations_research int main(int /*argc*/, char* /*argv*/[]) { operations_research::VrpGlobalSpan(); 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.RoutingDimension; import com.google.ortools.constraintsolver.RoutingIndexManager; import com.google.ortools.constraintsolver.RoutingModel; import com.google.ortools.constraintsolver.RoutingSearchParameters; import com.google.ortools.constraintsolver.Solver; import com.google.ortools.constraintsolver.main; import java.util.logging.Logger; /** Minimal Pickup & Delivery Problem (PDP).*/ public class VrpPickupDelivery { private static final Logger logger = Logger.getLogger(VrpPickupDelivery.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 int[][] pickupsDeliveries = { {1, 6}, {2, 10}, {4, 3}, {5, 9}, {7, 8}, {15, 11}, {13, 12}, {16, 14}, }; 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; for (int i = 0; i < data.vehicleNumber; ++i) { long index = routing.start(i); logger.info("Route for Vehicle " + i + ":"); long routeDistance = 0; String route = ""; while (!routing.isEnd(index)) { route += manager.indexToNode(index) + " -> "; long previousIndex = index; index = solution.value(routing.nextVar(index)); routeDistance += routing.getArcCostForVehicle(previousIndex, index, i); } logger.info(route + manager.indexToNode(index)); logger.info("Distance of the route: " + routeDistance + "m"); totalDistance += routeDistance; } logger.info("Total Distance of all routes: " + totalDistance + "m"); } 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 Distance constraint. routing.addDimension(transitCallbackIndex, // transit callback index 0, // no slack 3000, // vehicle maximum travel distance true, // start cumul to zero "Distance"); RoutingDimension distanceDimension = routing.getMutableDimension("Distance"); distanceDimension.setGlobalSpanCostCoefficient(100); // Define Transportation Requests. Solver solver = routing.solver(); for (int[] request : data.pickupsDeliveries) { long pickupIndex = manager.nodeToIndex(request[0]); long deliveryIndex = manager.nodeToIndex(request[1]); routing.addPickupAndDelivery(pickupIndex, deliveryIndex); solver.addConstraint( solver.makeEquality(routing.vehicleVar(pickupIndex), routing.vehicleVar(deliveryIndex))); solver.addConstraint(solver.makeLessOrEqual( distanceDimension.cumulVar(pickupIndex), distanceDimension.cumulVar(deliveryIndex))); } // Setting first solution heuristic. RoutingSearchParameters searchParameters = main.defaultRoutingSearchParameters() .toBuilder() .setFirstSolutionStrategy(FirstSolutionStrategy.Value.PARALLEL_CHEAPEST_INSERTION) .build(); // Solve the problem. Assignment solution = routing.solveWithParameters(searchParameters); // Print solution on console. printSolution(data, routing, manager, solution); } }
C#
using System; using System.Collections.Generic; using Google.OrTools.ConstraintSolver; /// <summary> /// Minimal Pickup & Delivery Problem (PDP). /// </summary> public class VrpPickupDelivery { 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 int[][] PickupsDeliveries = { new int[] { 1, 6 }, new int[] { 2, 10 }, new int[] { 4, 3 }, new int[] { 5, 9 }, new int[] { 7, 8 }, new int[] { 15, 11 }, new int[] { 13, 12 }, new int[] { 16, 14 }, }; 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; for (int i = 0; i < data.VehicleNumber; ++i) { Console.WriteLine("Route for Vehicle {0}:", i); long routeDistance = 0; var index = routing.Start(i); while (routing.IsEnd(index) == false) { Console.Write("{0} -> ", manager.IndexToNode((int)index)); 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; } Console.WriteLine("Total Distance of all routes: {0}m", totalDistance); } 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 Distance constraint. routing.AddDimension(transitCallbackIndex, 0, 3000, true, // start cumul to zero "Distance"); RoutingDimension distanceDimension = routing.GetMutableDimension("Distance"); distanceDimension.SetGlobalSpanCostCoefficient(100); // Define Transportation Requests. Solver solver = routing.solver(); for (int i = 0; i < data.PickupsDeliveries.GetLength(0); i++) { long pickupIndex = manager.NodeToIndex(data.PickupsDeliveries[i][0]); long deliveryIndex = manager.NodeToIndex(data.PickupsDeliveries[i][1]); routing.AddPickupAndDelivery(pickupIndex, deliveryIndex); solver.Add(solver.MakeEquality(routing.VehicleVar(pickupIndex), routing.VehicleVar(deliveryIndex))); solver.Add(solver.MakeLessOrEqual(distanceDimension.CumulVar(pickupIndex), distanceDimension.CumulVar(deliveryIndex))); } // Setting first solution heuristic. RoutingSearchParameters searchParameters = operations_research_constraint_solver.DefaultRoutingSearchParameters(); searchParameters.FirstSolutionStrategy = FirstSolutionStrategy.Types.Value.PathCheapestArc; // Solve the problem. Assignment solution = routing.SolveWithParameters(searchParameters); // Print solution on console. PrintSolution(data, routing, manager, solution); } }