في هذا القسم، نتناول وصف برنامج VRP الذي تلتقط فيه كل مركبة عناصر من مواقع مختلفة وتوزعها على مواقع أخرى. تكمن المشكلة في تعيين مسارات للمركبات لاستلام كل العناصر وتسليمها، مع تقليل طول أطول مسار.
مثال على VRP مع خدمات الاستلام والتوصيل
يوضّح المخطّط أدناه مواقع الاستلام والتسليم على شبكة مشابهة للشبكة في مثال VRP السابق. ولكلّ سلعة، هناك حافة محدّدة من الموقع الذي سيتمّ استلام الطلب منه إلى مكان التسليم.
حل المثال باستخدام "أدوات OR"
توضّح الأقسام التالية كيفية حلّ مشكلة "الواقع الافتراضي" باستخدام عمليات الاستلام والتوصيل . تم اشتقاق الكثير من التعليمات البرمجية من مثال 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);
}
}