مشكلة توجيه المركبة المتنقلة (CVRP) هي نقطة وصول افتراضي (VRP) حيث يمكن للمركبات ذات قدرة استيعاب محدودة تحتاج إلى التقاط أو تسليم العناصر في مواقع مختلفة. تحتوي السلع على كمية، مثل الوزن أو الحجم، وتُحمل المركبات الحدّ الأقصى للسعة التي يمكنهم حملها تكمن المشكلة في استلام أو تسليم العناصر بأقل تكلفة، مع عدم تجاوز سعة المركبات أبدًا.
في المثال التالي، نفترض أنّه تمّ اختيار كل السلع. يعمل البرنامج الذي يحل هذه المشكلة أيضًا في حالة تسليم جميع العناصر: في هذه الحالة، يمكنك التفكير في قيد السعة الذي يتم تطبيقه عند تغادر المركبات المستودع محمّلة بالكامل. لكن قيود القدرات يتم تنفيذها بنفس الطريقة في كلتا الحالتين.
مثال على CVRP
بعد ذلك، سنصف مثالاً على VRP مع قيود السعة. المثال تُوسّع مثال VRP السابق وتضيف المتطلبات التالية. في كل موقع جغرافي هناك طلب يتوافق مع كمية العنصر التي سيتم استلامها. أيضًا، تحتوي كل مركبة على حد أقصى بسعة 15. (لا نحدد وحدات للطلبات أو السعة.)
تعرض الشبكة أدناه المواقع الجغرافية لزيارتها باللون الأزرق والموقع الجغرافي للشركة في أسود. تظهر الطلبات في أسفل يسار كلّ موقع جغرافي. عرض إحداثيات الموقع في VRP لمزيد من التفاصيل حول كيفية تحديد المواقع.
تكمن المشكلة في إيجاد تخصيص للمسارات للمركبات الأقصر بحيث لا يكون إجمالي المسافة التي ستنقلها أي مركبة يتجاوز السعة.
حل مثال CVRP باستخدام OR-أدوات
تشرح الأقسام التالية كيفية حل مثال CVRP باستخدام OR-أدوات.
إنشاء البيانات
تتضمن البيانات في هذا المثال البيانات الموجودة في العمود السابق مثال على "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 };
العناصر الجديدة في البيانات هي:
- الطلبات: لكلّ موقع جغرافي طلب يقابل الكمية — مثل وزن أو حجم السلعة التي سيتم استلامها
- السعة: تبلغ كل مركبة السعة: وهي أقصى الكمية التي يمكن للمركبة استيعابه. وبينما تسير أي مركبة على مسارها، يكون إجمالي الكمية لا يمكن أبدًا أن تتجاوز سعة العناصر التي تحملها سعتها.
إضافة معاودة الاتصال للمسافة
استدعاء المسافة - الدالة التي تُرجع المسافة بين أي موقعين—بنفس الطريقة كما في السابق مثال على "VRP"
إضافة قيود معاودة الاتصال والسعة للطلب
بالإضافة إلى استدعاء المسافة، تتطلب أداة الحلّ أيضًا معاودة الاتصال للطلب ، والتي تُرجع الطلب في كل موقع جغرافي، وسمة للسعة القيود. تُنشئ التعليمة البرمجية التالية هذه.
Python
def demand_callback(from_index):
"""Returns the demand of the node."""
# Convert from routing variable Index to demands NodeIndex.
from_node = manager.IndexToNode(from_index)
return data["demands"][from_node]
demand_callback_index = routing.RegisterUnaryTransitCallback(demand_callback)
routing.AddDimensionWithVehicleCapacity(
demand_callback_index,
0, # null capacity slack
data["vehicle_capacities"], # vehicle maximum capacities
True, # start cumul to zero
"Capacity",
)
C++
const int demand_callback_index = routing.RegisterUnaryTransitCallback(
[&data, &manager](const int64_t from_index) -> int64_t {
// Convert from routing variable Index to demand NodeIndex.
const int from_node = manager.IndexToNode(from_index).value();
return data.demands[from_node];
});
routing.AddDimensionWithVehicleCapacity(
demand_callback_index, // transit callback index
int64_t{0}, // null capacity slack
data.vehicle_capacities, // vehicle maximum capacities
true, // start cumul to zero
"Capacity");
Java
final int demandCallbackIndex = routing.registerUnaryTransitCallback((long fromIndex) -> {
// Convert from routing variable Index to user NodeIndex.
int fromNode = manager.indexToNode(fromIndex);
return data.demands[fromNode];
});
routing.addDimensionWithVehicleCapacity(demandCallbackIndex, 0, // null capacity slack
data.vehicleCapacities, // vehicle maximum capacities
true, // start cumul to zero
"Capacity");
#C
int demandCallbackIndex = routing.RegisterUnaryTransitCallback((long fromIndex) =>
{
// Convert from routing variable Index to
// demand NodeIndex.
var fromNode =
manager.IndexToNode(fromIndex);
return data.Demands[fromNode];
});
routing.AddDimensionWithVehicleCapacity(demandCallbackIndex, 0, // null capacity slack
data.VehicleCapacities, // vehicle maximum capacities
true, // start cumul to zero
"Capacity");
بخلاف استدعاء المسافة، الذي يأخذ موقعين كمدخلات،
يعتمد طلب معاودة الاتصال فقط على موقع التسليم (from_node).
نظرًا لأن قيود السعة تتضمن وزن الحمولة، الشحن - الكمية التي تتراكم فوق المسار - نحتاج إلى إنشاء سمة للسعات، على بُعد المسافة في الخطوة السابقة مثال على "VRP"
في هذه الحالة، نستخدم دالة الرسم
AddDimensionWithVehicleCapacity
والتي تتخذ الخط المتجه للسعات.
نظرًا لأن جميع سعات المركبات في هذا المثال متطابقة، يمكنك استخدام
AddDimension
والتي تأخذ حدًا أعلى واحدًا لجميع كميات المركبات. لَكِنْ
تعالج الدالة AddDimensionWithVehicleCapacity الحالة الأكثر عمومية والتي
المركبات المختلفة لها سعات مختلفة.
المشاكل المتعلّقة بأنواع الشحن والسعات المتعددة
في CVRP الأكثر تعقيدًا، قد تحمل كل مركبة عدة أنواع مختلفة من الشحنات ، مع حدّ أقصى لكلّ نوع. على سبيل المثال، قد تحمل شاحنة توصيل الوقود عدة أنواع من الوقود، حيث تستخدم خزانات متعددة ذات سعات مختلفة. للتعامل مع مشكلات مثل هذه، فقط إنشاء سعة اتصال وبُعد مختلفتين لسعة كل نوع شحن (إجراء تأكد من تعيين أسماء فريدة لها).
إضافة طابعة الحل
تعرض طابعة الحلول مسار كل مركبة، إلى جانب التحميل التراكمي: إجمالي المبلغ الذي تحمله المركبة عند محطة توقفها والمسارات.
Python
def print_solution(data, manager, routing, solution):
"""Prints solution on console."""
print(f"Objective: {solution.ObjectiveValue()}")
total_distance = 0
total_load = 0
for vehicle_id in range(data["num_vehicles"]):
index = routing.Start(vehicle_id)
plan_output = f"Route for vehicle {vehicle_id}:\n"
route_distance = 0
route_load = 0
while not routing.IsEnd(index):
node_index = manager.IndexToNode(index)
route_load += data["demands"][node_index]
plan_output += f" {node_index} Load({route_load}) -> "
previous_index = index
index = solution.Value(routing.NextVar(index))
route_distance += routing.GetArcCostForVehicle(
previous_index, index, vehicle_id
)
plan_output += f" {manager.IndexToNode(index)} Load({route_load})\n"
plan_output += f"Distance of the route: {route_distance}m\n"
plan_output += f"Load of the route: {route_load}\n"
print(plan_output)
total_distance += route_distance
total_load += route_load
print(f"Total distance of all routes: {total_distance}m")
print(f"Total load of all routes: {total_load}")
C++
//! @brief Print the solution.
//! @param[in] data Data of the problem.
//! @param[in] manager Index manager used.
//! @param[in] routing Routing solver used.
//! @param[in] solution Solution found by the solver.
void PrintSolution(const DataModel& data, const RoutingIndexManager& manager,
const RoutingModel& routing, const Assignment& solution) {
int64_t total_distance = 0;
int64_t total_load = 0;
for (int vehicle_id = 0; vehicle_id < data.num_vehicles; ++vehicle_id) {
int64_t index = routing.Start(vehicle_id);
LOG(INFO) << "Route for Vehicle " << vehicle_id << ":";
int64_t route_distance = 0;
int64_t route_load = 0;
std::stringstream route;
while (!routing.IsEnd(index)) {
const int node_index = manager.IndexToNode(index).value();
route_load += data.demands[node_index];
route << node_index << " Load(" << route_load << ") -> ";
const int64_t previous_index = index;
index = solution.Value(routing.NextVar(index));
route_distance += routing.GetArcCostForVehicle(previous_index, index,
int64_t{vehicle_id});
}
LOG(INFO) << route.str() << manager.IndexToNode(index).value();
LOG(INFO) << "Distance of the route: " << route_distance << "m";
LOG(INFO) << "Load of the route: " << route_load;
total_distance += route_distance;
total_load += route_load;
}
LOG(INFO) << "Total distance of all routes: " << total_distance << "m";
LOG(INFO) << "Total load of all routes: " << total_load;
LOG(INFO) << "";
LOG(INFO) << "Advanced usage:";
LOG(INFO) << "Problem solved in " << routing.solver()->wall_time() << "ms";
}
Java
/// @brief Print the solution.
static void printSolution(
DataModel data, RoutingModel routing, RoutingIndexManager manager, Assignment solution) {
// Solution cost.
logger.info("Objective: " + solution.objectiveValue());
// Inspect solution.
long totalDistance = 0;
long totalLoad = 0;
for (int i = 0; i < data.vehicleNumber; ++i) {
long index = routing.start(i);
logger.info("Route for Vehicle " + i + ":");
long routeDistance = 0;
long routeLoad = 0;
String route = "";
while (!routing.isEnd(index)) {
long nodeIndex = manager.indexToNode(index);
routeLoad += data.demands[(int) nodeIndex];
route += nodeIndex + " Load(" + routeLoad + ") -> ";
long previousIndex = index;
index = solution.value(routing.nextVar(index));
routeDistance += routing.getArcCostForVehicle(previousIndex, index, i);
}
route += manager.indexToNode(routing.end(i));
logger.info(route);
logger.info("Distance of the route: " + routeDistance + "m");
totalDistance += routeDistance;
totalLoad += routeLoad;
}
logger.info("Total distance of all routes: " + totalDistance + "m");
logger.info("Total load of all routes: " + totalLoad);
}
#C
/// <summary>
/// Print the solution.
/// </summary>
static void PrintSolution(in DataModel data, in RoutingModel routing, in RoutingIndexManager manager,
in Assignment solution)
{
Console.WriteLine($"Objective {solution.ObjectiveValue()}:");
// Inspect solution.
long totalDistance = 0;
long totalLoad = 0;
for (int i = 0; i < data.VehicleNumber; ++i)
{
Console.WriteLine("Route for Vehicle {0}:", i);
long routeDistance = 0;
long routeLoad = 0;
var index = routing.Start(i);
while (routing.IsEnd(index) == false)
{
long nodeIndex = manager.IndexToNode(index);
routeLoad += data.Demands[nodeIndex];
Console.Write("{0} Load({1}) -> ", nodeIndex, routeLoad);
var previousIndex = index;
index = solution.Value(routing.NextVar(index));
routeDistance += routing.GetArcCostForVehicle(previousIndex, index, 0);
}
Console.WriteLine("{0}", manager.IndexToNode((int)index));
Console.WriteLine("Distance of the route: {0}m", routeDistance);
totalDistance += routeDistance;
totalLoad += routeLoad;
}
Console.WriteLine("Total distance of all routes: {0}m", totalDistance);
Console.WriteLine("Total load of all routes: {0}m", totalLoad);
}
الوظيفة الرئيسية
تتشابه الوظيفة الرئيسية لهذا المثال إلى حد كبير مع الوظيفة الخاصة مثال لمقدّم خدمة الرموز المميّزة، لكنّها تضيف أيضًا سمة الطلبات والسعة الموضّحة أعلاه
تشغيل البرنامج
يمكنك الاطّلاع على البرنامج الكامل في القسم التالي. عند تشغيل البرنامج، يعرض الناتج التالي:
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 الذي لا يتجاوز فيه إجمالي الطلب السعة الإجمالية، لتحديد ما إذا كان جميع العناصر التي تلائم المركبات هي نسخة من مشكلة متعددة في حقيبة الظهر.