محدودیت های ظرفیت

مشکل مسیریابی خودروی ظرفیت دار (CVRP) یک VRP است که در آن وسایل نقلیه با ظرفیت حمل محدود باید اقلام را در مکان های مختلف تحویل بگیرند یا تحویل دهند. اقلام دارای مقداری مانند وزن یا حجم هستند و وسایل نقلیه دارای حداکثر ظرفیتی هستند که می توانند حمل کنند. مشکل این است که اقلام را با کمترین هزینه تحویل بگیرید، در حالی که هرگز از ظرفیت وسایل نقلیه تجاوز نکنید.

در مثال زیر، فرض می کنیم که همه اقلام در حال برداشت هستند. برنامه ای که این مشکل را حل می کند در صورت تحویل همه موارد نیز کار می کند: در این مورد، می توانید به محدودیت ظرفیت فکر کنید که وقتی وسایل نقلیه با بارگیری کامل از انبار خارج می شوند. اما محدودیت های ظرفیت در هر دو مورد به یک شکل اجرا می شوند.

توجه: برای مثال مرتبطی که در آن هم تحویل و هم تحویل وجود دارد، به تحویل و تحویل مراجعه کنید.

مثال CVRP

در مرحله بعد، نمونه ای از VRP با محدودیت ظرفیت را شرح می دهیم. مثال مثال قبلی VRP را گسترش می دهد و الزامات زیر را اضافه می کند. در هر مکان یک تقاضای مربوط به مقدار کالایی که باید برداشت شود وجود دارد. همچنین ظرفیت هر خودرو حداکثر 15 دستگاه است.

شبکه زیر مکان های بازدید را با رنگ آبی و مکان شرکت را با رنگ مشکی نشان می دهد. خواسته ها در سمت راست پایین هر مکان نشان داده شده است. مختصات مکان را در بخش VRP برای جزئیات بیشتر در مورد نحوه تعریف مکان ها ببینید.

مشکل این است که مسیرهایی را برای وسایل نقلیه ای پیدا کنیم که کمترین مسافت کلی را داشته باشند، و به گونه ای که کل مقداری که یک وسیله نقلیه حمل می کند هرگز از ظرفیت آن بیشتر نشود.

حل مثال CVRP با OR-Tools

در بخش های زیر نحوه حل مثال CVRP با OR-Tools توضیح داده می شود.

داده ها را ایجاد کنید

داده‌های این مثال شامل داده‌های مثال قبلی VRP است و تقاضاها و ظرفیت‌های خودروی زیر را اضافه می‌کند:

پایتون

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};

سی شارپ

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 تعریف شده است.

محدودیت های تقاضا و پاسخ به تماس را اضافه کنید

علاوه بر تماس پاسخ فاصله، حل کننده همچنین به یک درخواست پاسخ نیاز دارد که تقاضا را در هر مکان و یک بعد برای محدودیت های ظرفیت برمی گرداند. کد زیر اینها را ایجاد می کند.

پایتون

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");

سی شارپ

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 های پیچیده تر، هر وسیله نقلیه ممکن است چندین نوع بار مختلف را با حداکثر ظرفیت برای هر نوع حمل کند. به عنوان مثال، یک کامیون تحویل سوخت ممکن است چندین نوع سوخت را با استفاده از چندین مخزن با ظرفیت های مختلف حمل کند. برای رسیدگی به مشکلاتی از این دست، کافی است یک ظرفیت و ابعاد متفاوت برای هر نوع محموله ایجاد کنید (مطمئن شوید که نام‌های منحصربه‌فرد برای آن‌ها تعیین کنید).

چاپگر محلول را اضافه کنید

چاپگر راه حل مسیر هر وسیله نقلیه را به همراه بار تجمعی آن نشان می دهد: کل مقداری که وسیله نقلیه در توقف در مسیرهای خود حمل می کند.

پایتون

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);
}

سی شارپ

/// <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

برای هر مکان در یک مسیر، خروجی نشان می دهد:

• شاخص مکان.

• کل بار حمل شده توسط وسیله نقلیه هنگام خروج از محل.

• مسیرها در زیر نشان داده شده است.

برنامه های کامل

برنامه های کامل برای مشکل مسیریابی خودرو با ظرفیت در زیر نشان داده شده است.

پایتون

"""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() {}
}

سی شارپ

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 که در آن تقاضای کل از ظرفیت کل تجاوز نمی کند، تعیین اینکه آیا همه اقلام در وسایل نقلیه جا می شوند یا نه نسخه ای از مشکل کوله پشتی چندگانه است.