مشکل مسیریابی خودرو با تایم ویندوز

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

این مشکلات به عنوان مشکلات مسیریابی خودرو با پنجره های زمانی (VRPTWs) شناخته می شوند.

مثال VRPTW

در این صفحه، مثالی را مرور خواهیم کرد که نحوه حل یک VRPTW را نشان می دهد. از آنجایی که مشکل شامل پنجره‌های زمانی می‌شود، داده‌ها شامل یک ماتریس زمانی است که شامل زمان‌های سفر بین مکان‌ها است (به جای ماتریس فاصله مانند مثال‌های قبلی).

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

هدف این است که کل زمان سفر وسایل نقلیه را به حداقل برسانیم.

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

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

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

تابع زیر داده های مشکل را ایجاد می کند.

پایتون

def create_data_model():
    """Stores the data for the problem."""
    data = {}
    data["time_matrix"] = [
        [0, 6, 9, 8, 7, 3, 6, 2, 3, 2, 6, 6, 4, 4, 5, 9, 7],
        [6, 0, 8, 3, 2, 6, 8, 4, 8, 8, 13, 7, 5, 8, 12, 10, 14],
        [9, 8, 0, 11, 10, 6, 3, 9, 5, 8, 4, 15, 14, 13, 9, 18, 9],
        [8, 3, 11, 0, 1, 7, 10, 6, 10, 10, 14, 6, 7, 9, 14, 6, 16],
        [7, 2, 10, 1, 0, 6, 9, 4, 8, 9, 13, 4, 6, 8, 12, 8, 14],
        [3, 6, 6, 7, 6, 0, 2, 3, 2, 2, 7, 9, 7, 7, 6, 12, 8],
        [6, 8, 3, 10, 9, 2, 0, 6, 2, 5, 4, 12, 10, 10, 6, 15, 5],
        [2, 4, 9, 6, 4, 3, 6, 0, 4, 4, 8, 5, 4, 3, 7, 8, 10],
        [3, 8, 5, 10, 8, 2, 2, 4, 0, 3, 4, 9, 8, 7, 3, 13, 6],
        [2, 8, 8, 10, 9, 2, 5, 4, 3, 0, 4, 6, 5, 4, 3, 9, 5],
        [6, 13, 4, 14, 13, 7, 4, 8, 4, 4, 0, 10, 9, 8, 4, 13, 4],
        [6, 7, 15, 6, 4, 9, 12, 5, 9, 6, 10, 0, 1, 3, 7, 3, 10],
        [4, 5, 14, 7, 6, 7, 10, 4, 8, 5, 9, 1, 0, 2, 6, 4, 8],
        [4, 8, 13, 9, 8, 7, 10, 3, 7, 4, 8, 3, 2, 0, 4, 5, 6],
        [5, 12, 9, 14, 12, 6, 6, 7, 3, 3, 4, 7, 6, 4, 0, 9, 2],
        [9, 10, 18, 6, 8, 12, 15, 8, 13, 9, 13, 3, 4, 5, 9, 0, 9],
        [7, 14, 9, 16, 14, 8, 5, 10, 6, 5, 4, 10, 8, 6, 2, 9, 0],
    ]
    data["time_windows"] = [
        (0, 5),  # depot
        (7, 12),  # 1
        (10, 15),  # 2
        (16, 18),  # 3
        (10, 13),  # 4
        (0, 5),  # 5
        (5, 10),  # 6
        (0, 4),  # 7
        (5, 10),  # 8
        (0, 3),  # 9
        (10, 16),  # 10
        (10, 15),  # 11
        (0, 5),  # 12
        (5, 10),  # 13
        (7, 8),  # 14
        (10, 15),  # 15
        (11, 15),  # 16
    ]
    data["num_vehicles"] = 4
    data["depot"] = 0
    return data
داده ها شامل موارد زیر است:
  • data['time_matrix'] : آرایه ای از زمان سفر بین مکان ها. توجه داشته باشید که این با مثال های قبلی که از ماتریس فاصله استفاده می کنند متفاوت است. اگر همه وسایل نقلیه با سرعت یکسانی حرکت کنند، اگر از ماتریس فاصله یا ماتریس زمان استفاده کنید، راه حل یکسانی دریافت خواهید کرد، زیرا مسافت سفر مضرب ثابت زمان سفر است.
  • data['time_windows'] : آرایه‌ای از پنجره‌های زمانی برای مکان‌ها، که می‌توانید به عنوان زمان‌های درخواستی برای بازدید در نظر بگیرید. وسایل نقلیه باید از یک مکان در بازه زمانی خود بازدید کنند.
  • data['num_vehicles'] : تعداد وسایل نقلیه در ناوگان.
  • data['depot'] : نمایه انبار.

C++

struct DataModel {
  const std::vector<std::vector<int64_t>> time_matrix{
      {0, 6, 9, 8, 7, 3, 6, 2, 3, 2, 6, 6, 4, 4, 5, 9, 7},
      {6, 0, 8, 3, 2, 6, 8, 4, 8, 8, 13, 7, 5, 8, 12, 10, 14},
      {9, 8, 0, 11, 10, 6, 3, 9, 5, 8, 4, 15, 14, 13, 9, 18, 9},
      {8, 3, 11, 0, 1, 7, 10, 6, 10, 10, 14, 6, 7, 9, 14, 6, 16},
      {7, 2, 10, 1, 0, 6, 9, 4, 8, 9, 13, 4, 6, 8, 12, 8, 14},
      {3, 6, 6, 7, 6, 0, 2, 3, 2, 2, 7, 9, 7, 7, 6, 12, 8},
      {6, 8, 3, 10, 9, 2, 0, 6, 2, 5, 4, 12, 10, 10, 6, 15, 5},
      {2, 4, 9, 6, 4, 3, 6, 0, 4, 4, 8, 5, 4, 3, 7, 8, 10},
      {3, 8, 5, 10, 8, 2, 2, 4, 0, 3, 4, 9, 8, 7, 3, 13, 6},
      {2, 8, 8, 10, 9, 2, 5, 4, 3, 0, 4, 6, 5, 4, 3, 9, 5},
      {6, 13, 4, 14, 13, 7, 4, 8, 4, 4, 0, 10, 9, 8, 4, 13, 4},
      {6, 7, 15, 6, 4, 9, 12, 5, 9, 6, 10, 0, 1, 3, 7, 3, 10},
      {4, 5, 14, 7, 6, 7, 10, 4, 8, 5, 9, 1, 0, 2, 6, 4, 8},
      {4, 8, 13, 9, 8, 7, 10, 3, 7, 4, 8, 3, 2, 0, 4, 5, 6},
      {5, 12, 9, 14, 12, 6, 6, 7, 3, 3, 4, 7, 6, 4, 0, 9, 2},
      {9, 10, 18, 6, 8, 12, 15, 8, 13, 9, 13, 3, 4, 5, 9, 0, 9},
      {7, 14, 9, 16, 14, 8, 5, 10, 6, 5, 4, 10, 8, 6, 2, 9, 0},
  };
  const std::vector<std::pair<int64_t, int64_t>> time_windows{
      {0, 5},    // depot
      {7, 12},   // 1
      {10, 15},  // 2
      {16, 18},  // 3
      {10, 13},  // 4
      {0, 5},    // 5
      {5, 10},   // 6
      {0, 4},    // 7
      {5, 10},   // 8
      {0, 3},    // 9
      {10, 16},  // 10
      {10, 15},  // 11
      {0, 5},    // 12
      {5, 10},   // 13
      {7, 8},    // 14
      {10, 15},  // 15
      {11, 15},  // 16
  };
  const int num_vehicles = 4;
  const RoutingIndexManager::NodeIndex depot{0};
};
داده ها شامل موارد زیر است:
  • time_matrix : آرایه ای از زمان های سفر بین مکان ها. توجه داشته باشید که این با مثال های قبلی که از ماتریس فاصله استفاده می کنند متفاوت است. اگر همه وسایل نقلیه با سرعت یکسانی حرکت کنند، اگر از ماتریس فاصله یا ماتریس زمان استفاده کنید، راه حل یکسانی دریافت خواهید کرد، زیرا مسافت سفر مضرب ثابت زمان سفر است.
  • time_windows : آرایه ای از پنجره های زمانی برای مکان ها، که می توانید آنها را به عنوان زمان های درخواستی برای بازدید در نظر بگیرید. وسایل نقلیه باید از یک مکان در بازه زمانی خود بازدید کنند.
  • num_vehicles : تعداد وسایل نقلیه در ناوگان.
  • depot : شاخص انبار.

جاوا

static class DataModel {
  public final long[][] timeMatrix = {
      {0, 6, 9, 8, 7, 3, 6, 2, 3, 2, 6, 6, 4, 4, 5, 9, 7},
      {6, 0, 8, 3, 2, 6, 8, 4, 8, 8, 13, 7, 5, 8, 12, 10, 14},
      {9, 8, 0, 11, 10, 6, 3, 9, 5, 8, 4, 15, 14, 13, 9, 18, 9},
      {8, 3, 11, 0, 1, 7, 10, 6, 10, 10, 14, 6, 7, 9, 14, 6, 16},
      {7, 2, 10, 1, 0, 6, 9, 4, 8, 9, 13, 4, 6, 8, 12, 8, 14},
      {3, 6, 6, 7, 6, 0, 2, 3, 2, 2, 7, 9, 7, 7, 6, 12, 8},
      {6, 8, 3, 10, 9, 2, 0, 6, 2, 5, 4, 12, 10, 10, 6, 15, 5},
      {2, 4, 9, 6, 4, 3, 6, 0, 4, 4, 8, 5, 4, 3, 7, 8, 10},
      {3, 8, 5, 10, 8, 2, 2, 4, 0, 3, 4, 9, 8, 7, 3, 13, 6},
      {2, 8, 8, 10, 9, 2, 5, 4, 3, 0, 4, 6, 5, 4, 3, 9, 5},
      {6, 13, 4, 14, 13, 7, 4, 8, 4, 4, 0, 10, 9, 8, 4, 13, 4},
      {6, 7, 15, 6, 4, 9, 12, 5, 9, 6, 10, 0, 1, 3, 7, 3, 10},
      {4, 5, 14, 7, 6, 7, 10, 4, 8, 5, 9, 1, 0, 2, 6, 4, 8},
      {4, 8, 13, 9, 8, 7, 10, 3, 7, 4, 8, 3, 2, 0, 4, 5, 6},
      {5, 12, 9, 14, 12, 6, 6, 7, 3, 3, 4, 7, 6, 4, 0, 9, 2},
      {9, 10, 18, 6, 8, 12, 15, 8, 13, 9, 13, 3, 4, 5, 9, 0, 9},
      {7, 14, 9, 16, 14, 8, 5, 10, 6, 5, 4, 10, 8, 6, 2, 9, 0},
  };
  public final long[][] timeWindows = {
      {0, 5}, // depot
      {7, 12}, // 1
      {10, 15}, // 2
      {16, 18}, // 3
      {10, 13}, // 4
      {0, 5}, // 5
      {5, 10}, // 6
      {0, 4}, // 7
      {5, 10}, // 8
      {0, 3}, // 9
      {10, 16}, // 10
      {10, 15}, // 11
      {0, 5}, // 12
      {5, 10}, // 13
      {7, 8}, // 14
      {10, 15}, // 15
      {11, 15}, // 16
  };
  public final int vehicleNumber = 4;
  public final int depot = 0;
}
داده ها شامل موارد زیر است:
  • timeMatrix : آرایه ای از زمان های سفر بین مکان ها. توجه داشته باشید که این با مثال های قبلی که از ماتریس فاصله استفاده می کنند متفاوت است. اگر همه وسایل نقلیه با سرعت یکسانی حرکت کنند، اگر از ماتریس فاصله یا ماتریس زمان استفاده کنید، راه حل یکسانی دریافت خواهید کرد، زیرا مسافت سفر مضرب ثابت زمان سفر است.
  • timeWindows : آرایه ای از پنجره های زمانی برای مکان ها، که می توانید آنها را به عنوان زمان های درخواستی برای بازدید در نظر بگیرید. وسایل نقلیه باید از یک مکان در بازه زمانی خود بازدید کنند.
  • vehicleNumber : تعداد وسایل نقلیه موجود در ناوگان.
  • depot : شاخص انبار.

سی شارپ

class DataModel
{
    public long[,] TimeMatrix = {
        { 0, 6, 9, 8, 7, 3, 6, 2, 3, 2, 6, 6, 4, 4, 5, 9, 7 },
        { 6, 0, 8, 3, 2, 6, 8, 4, 8, 8, 13, 7, 5, 8, 12, 10, 14 },
        { 9, 8, 0, 11, 10, 6, 3, 9, 5, 8, 4, 15, 14, 13, 9, 18, 9 },
        { 8, 3, 11, 0, 1, 7, 10, 6, 10, 10, 14, 6, 7, 9, 14, 6, 16 },
        { 7, 2, 10, 1, 0, 6, 9, 4, 8, 9, 13, 4, 6, 8, 12, 8, 14 },
        { 3, 6, 6, 7, 6, 0, 2, 3, 2, 2, 7, 9, 7, 7, 6, 12, 8 },
        { 6, 8, 3, 10, 9, 2, 0, 6, 2, 5, 4, 12, 10, 10, 6, 15, 5 },
        { 2, 4, 9, 6, 4, 3, 6, 0, 4, 4, 8, 5, 4, 3, 7, 8, 10 },
        { 3, 8, 5, 10, 8, 2, 2, 4, 0, 3, 4, 9, 8, 7, 3, 13, 6 },
        { 2, 8, 8, 10, 9, 2, 5, 4, 3, 0, 4, 6, 5, 4, 3, 9, 5 },
        { 6, 13, 4, 14, 13, 7, 4, 8, 4, 4, 0, 10, 9, 8, 4, 13, 4 },
        { 6, 7, 15, 6, 4, 9, 12, 5, 9, 6, 10, 0, 1, 3, 7, 3, 10 },
        { 4, 5, 14, 7, 6, 7, 10, 4, 8, 5, 9, 1, 0, 2, 6, 4, 8 },
        { 4, 8, 13, 9, 8, 7, 10, 3, 7, 4, 8, 3, 2, 0, 4, 5, 6 },
        { 5, 12, 9, 14, 12, 6, 6, 7, 3, 3, 4, 7, 6, 4, 0, 9, 2 },
        { 9, 10, 18, 6, 8, 12, 15, 8, 13, 9, 13, 3, 4, 5, 9, 0, 9 },
        { 7, 14, 9, 16, 14, 8, 5, 10, 6, 5, 4, 10, 8, 6, 2, 9, 0 },
    };
    public long[,] TimeWindows = {
        { 0, 5 },   // depot
        { 7, 12 },  // 1
        { 10, 15 }, // 2
        { 16, 18 }, // 3
        { 10, 13 }, // 4
        { 0, 5 },   // 5
        { 5, 10 },  // 6
        { 0, 4 },   // 7
        { 5, 10 },  // 8
        { 0, 3 },   // 9
        { 10, 16 }, // 10
        { 10, 15 }, // 11
        { 0, 5 },   // 12
        { 5, 10 },  // 13
        { 7, 8 },   // 14
        { 10, 15 }, // 15
        { 11, 15 }, // 16
    };
    public int VehicleNumber = 4;
    public int Depot = 0;
};
داده ها شامل موارد زیر است:
  • TimeMatrix : آرایه ای از زمان های سفر بین مکان ها. توجه داشته باشید که این با مثال های قبلی که از ماتریس فاصله استفاده می کنند متفاوت است. اگر همه وسایل نقلیه با سرعت یکسانی حرکت کنند، اگر از ماتریس فاصله یا ماتریس زمان استفاده کنید، راه حل یکسانی دریافت خواهید کرد، زیرا مسافت سفر مضرب ثابت زمان سفر است.
  • TimeWindows : آرایه ای از پنجره های زمانی برای مکان ها، که می توانید آنها را به عنوان زمان های درخواستی برای بازدید در نظر بگیرید. وسایل نقلیه باید از یک مکان در بازه زمانی خود بازدید کنند.
  • VehicleNumber : تعداد وسایل نقلیه در ناوگان.
  • Depot : شاخص انبار.

زمان پاسخ به تماس

تابع زیر زمان تماس را ایجاد می کند و آن را به حل کننده ارسال می کند. همچنین هزینه های قوس را که هزینه سفر را تعیین می کند، به عنوان زمان سفر بین مکان ها تعیین می کند.

پایتون

def time_callback(from_index, to_index):
    """Returns the travel time between the two nodes."""
    # Convert from routing variable Index to time matrix NodeIndex.
    from_node = manager.IndexToNode(from_index)
    to_node = manager.IndexToNode(to_index)
    return data["time_matrix"][from_node][to_node]

transit_callback_index = routing.RegisterTransitCallback(time_callback)
routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)

C++

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 time matrix NodeIndex.
      const int from_node = manager.IndexToNode(from_index).value();
      const int to_node = manager.IndexToNode(to_index).value();
      return data.time_matrix[from_node][to_node];
    });
routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index);

جاوا

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.timeMatrix[fromNode][toNode];
    });
routing.setArcCostEvaluatorOfAllVehicles(transitCallbackIndex);

سی شارپ

int transitCallbackIndex = routing.RegisterTransitCallback((long fromIndex, long toIndex) =>
                                                           {
                                                               // Convert from routing variable Index to time
                                                               // matrix NodeIndex.
                                                               var fromNode = manager.IndexToNode(fromIndex);
                                                               var toNode = manager.IndexToNode(toIndex);
                                                               return data.TimeMatrix[fromNode, toNode];
                                                           });
routing.SetArcCostEvaluatorOfAllVehicles(transitCallbackIndex);

محدودیت های پنجره زمانی را اضافه کنید

کد زیر محدودیت های پنجره زمانی را برای همه مکان ها اضافه می کند.

پایتون

time = "Time"
routing.AddDimension(
    transit_callback_index,
    30,  # allow waiting time
    30,  # maximum time per vehicle
    False,  # Don't force start cumul to zero.
    time,
)
time_dimension = routing.GetDimensionOrDie(time)
# Add time window constraints for each location except depot.
for location_idx, time_window in enumerate(data["time_windows"]):
    if location_idx == data["depot"]:
        continue
    index = manager.NodeToIndex(location_idx)
    time_dimension.CumulVar(index).SetRange(time_window[0], time_window[1])
# Add time window constraints for each vehicle start node.
depot_idx = data["depot"]
for vehicle_id in range(data["num_vehicles"]):
    index = routing.Start(vehicle_id)
    time_dimension.CumulVar(index).SetRange(
        data["time_windows"][depot_idx][0], data["time_windows"][depot_idx][1]
    )
for i in range(data["num_vehicles"]):
    routing.AddVariableMinimizedByFinalizer(
        time_dimension.CumulVar(routing.Start(i))
    )
    routing.AddVariableMinimizedByFinalizer(time_dimension.CumulVar(routing.End(i)))

C++

const std::string time = "Time";
routing.AddDimension(transit_callback_index,  // transit callback index
                     int64_t{30},             // allow waiting time
                     int64_t{30},             // maximum time per vehicle
                     false,  // Don't force start cumul to zero
                     time);
const RoutingDimension& time_dimension = routing.GetDimensionOrDie(time);
// Add time window constraints for each location except depot.
for (int i = 1; i < data.time_windows.size(); ++i) {
  const int64_t index =
      manager.NodeToIndex(RoutingIndexManager::NodeIndex(i));
  time_dimension.CumulVar(index)->SetRange(data.time_windows[i].first,
                                           data.time_windows[i].second);
}
// Add time window constraints for each vehicle start node.
for (int i = 0; i < data.num_vehicles; ++i) {
  const int64_t index = routing.Start(i);
  time_dimension.CumulVar(index)->SetRange(data.time_windows[0].first,
                                           data.time_windows[0].second);
}
for (int i = 0; i < data.num_vehicles; ++i) {
  routing.AddVariableMinimizedByFinalizer(
      time_dimension.CumulVar(routing.Start(i)));
  routing.AddVariableMinimizedByFinalizer(
      time_dimension.CumulVar(routing.End(i)));
}

جاوا

routing.addDimension(transitCallbackIndex, // transit callback
    30, // allow waiting time
    30, // vehicle maximum capacities
    false, // start cumul to zero
    "Time");
RoutingDimension timeDimension = routing.getMutableDimension("Time");
// Add time window constraints for each location except depot.
for (int i = 1; i < data.timeWindows.length; ++i) {
  long index = manager.nodeToIndex(i);
  timeDimension.cumulVar(index).setRange(data.timeWindows[i][0], data.timeWindows[i][1]);
}
// Add time window constraints for each vehicle start node.
for (int i = 0; i < data.vehicleNumber; ++i) {
  long index = routing.start(i);
  timeDimension.cumulVar(index).setRange(data.timeWindows[0][0], data.timeWindows[0][1]);
}
for (int i = 0; i < data.vehicleNumber; ++i) {
  routing.addVariableMinimizedByFinalizer(timeDimension.cumulVar(routing.start(i)));
  routing.addVariableMinimizedByFinalizer(timeDimension.cumulVar(routing.end(i)));
}

سی شارپ

routing.AddDimension(transitCallbackIndex, // transit callback
                     30,                   // allow waiting time
                     30,                   // vehicle maximum capacities
                     false,                // start cumul to zero
                     "Time");
RoutingDimension timeDimension = routing.GetMutableDimension("Time");
// Add time window constraints for each location except depot.
for (int i = 1; i < data.TimeWindows.GetLength(0); ++i)
{
    long index = manager.NodeToIndex(i);
    timeDimension.CumulVar(index).SetRange(data.TimeWindows[i, 0], data.TimeWindows[i, 1]);
}
// Add time window constraints for each vehicle start node.
for (int i = 0; i < data.VehicleNumber; ++i)
{
    long index = routing.Start(i);
    timeDimension.CumulVar(index).SetRange(data.TimeWindows[0, 0], data.TimeWindows[0, 1]);
}
for (int i = 0; i < data.VehicleNumber; ++i)
{
    routing.AddVariableMinimizedByFinalizer(timeDimension.CumulVar(routing.Start(i)));
    routing.AddVariableMinimizedByFinalizer(timeDimension.CumulVar(routing.End(i)));
}

این کد یک بعد برای زمان سفر وسایل نقلیه ایجاد می کند، مشابه ابعاد مسافت سفر یا تقاضا در مثال های قبلی. ابعاد، مقادیری را که در مسیر یک وسیله نقلیه جمع می‌شوند، ردیابی می‌کنند. در کد بالا، time_dimension.CumulVar(index) زمان سفر تجمعی است که یک وسیله نقلیه به مکان با index داده شده می رسد.

بعد با استفاده از متد AddDimension ایجاد می شود که دارای آرگومان های زیر است:

  • شاخص زمان سفر برگشت به تماس: transit_callback_index
  • حد بالایی برای سستی (زمان انتظار در مکان ها): 30 . در حالی که در مثال CVRP روی 0 تنظیم شده بود، VRPTW باید به دلیل محدودیت‌های پنجره زمانی، زمان انتظار مثبت را مجاز کند.
  • حد بالایی برای کل زمان در مسیر هر وسیله نقلیه: 30
  • یک متغیر بولی که مشخص می کند آیا متغیر تجمعی در شروع مسیر هر وسیله نقلیه روی صفر تنظیم شده است یا خیر.
  • نام ابعاد.

بعد، خطوط

پایتون

for location_idx, time_window in enumerate(data["time_windows"]):
    if location_idx == data["depot"]:
        continue
    index = manager.NodeToIndex(location_idx)
    time_dimension.CumulVar(index).SetRange(time_window[0], time_window[1])

C++

for (int i = 1; i < data.time_windows.size(); ++i) {
  const int64_t index =
      manager.NodeToIndex(RoutingIndexManager::NodeIndex(i));
  time_dimension.CumulVar(index)->SetRange(data.time_windows[i].first,
                                           data.time_windows[i].second);
}

جاوا

for (int i = 1; i < data.timeWindows.length; ++i) {
  long index = manager.nodeToIndex(i);
  timeDimension.cumulVar(index).setRange(data.timeWindows[i][0], data.timeWindows[i][1]);
}

سی شارپ

for (int i = 1; i < data.TimeWindows.GetLength(0); ++i)
{
    long index = manager.NodeToIndex(i);
    timeDimension.CumulVar(index).SetRange(data.TimeWindows[i, 0], data.TimeWindows[i, 1]);
}

نیاز است که یک وسیله نقلیه باید از یک مکان در طول پنجره زمانی مکان بازدید کند.

تنظیم پارامترهای جستجو

کد زیر پارامترهای جستجوی پیش فرض و یک روش اکتشافی را برای یافتن اولین راه حل تنظیم می کند:

پایتون

search_parameters = pywrapcp.DefaultRoutingSearchParameters()
search_parameters.first_solution_strategy = (
    routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC
)

C++

RoutingSearchParameters searchParameters = DefaultRoutingSearchParameters();
searchParameters.set_first_solution_strategy(
    FirstSolutionStrategy::PATH_CHEAPEST_ARC);

جاوا

RoutingSearchParameters searchParameters =
    main.defaultRoutingSearchParameters()
        .toBuilder()
        .setFirstSolutionStrategy(FirstSolutionStrategy.Value.PATH_CHEAPEST_ARC)
        .build();

سی شارپ

RoutingSearchParameters searchParameters =
    operations_research_constraint_solver.DefaultRoutingSearchParameters();
searchParameters.FirstSolutionStrategy = FirstSolutionStrategy.Types.Value.PathCheapestArc;

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

تابعی که راه حل را نمایش می دهد در زیر نشان داده شده است.

پایتون

def print_solution(data, manager, routing, solution):
    """Prints solution on console."""
    print(f"Objective: {solution.ObjectiveValue()}")
    time_dimension = routing.GetDimensionOrDie("Time")
    total_time = 0
    for vehicle_id in range(data["num_vehicles"]):
        index = routing.Start(vehicle_id)
        plan_output = f"Route for vehicle {vehicle_id}:\n"
        while not routing.IsEnd(index):
            time_var = time_dimension.CumulVar(index)
            plan_output += (
                f"{manager.IndexToNode(index)}"
                f" Time({solution.Min(time_var)},{solution.Max(time_var)})"
                " -> "
            )
            index = solution.Value(routing.NextVar(index))
        time_var = time_dimension.CumulVar(index)
        plan_output += (
            f"{manager.IndexToNode(index)}"
            f" Time({solution.Min(time_var)},{solution.Max(time_var)})\n"
        )
        plan_output += f"Time of the route: {solution.Min(time_var)}min\n"
        print(plan_output)
        total_time += solution.Min(time_var)
    print(f"Total time of all routes: {total_time}min")

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) {
  const RoutingDimension& time_dimension = routing.GetDimensionOrDie("Time");
  int64_t total_time{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 << ":";
    std::ostringstream route;
    while (!routing.IsEnd(index)) {
      auto time_var = time_dimension.CumulVar(index);
      route << manager.IndexToNode(index).value() << " Time("
            << solution.Min(time_var) << ", " << solution.Max(time_var)
            << ") -> ";
      index = solution.Value(routing.NextVar(index));
    }
    auto time_var = time_dimension.CumulVar(index);
    LOG(INFO) << route.str() << manager.IndexToNode(index).value() << " Time("
              << solution.Min(time_var) << ", " << solution.Max(time_var)
              << ")";
    LOG(INFO) << "Time of the route: " << solution.Min(time_var) << "min";
    total_time += solution.Min(time_var);
  }
  LOG(INFO) << "Total time of all routes: " << total_time << "min";
  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.
  RoutingDimension timeDimension = routing.getMutableDimension("Time");
  long totalTime = 0;
  for (int i = 0; i < data.vehicleNumber; ++i) {
    long index = routing.start(i);
    logger.info("Route for Vehicle " + i + ":");
    String route = "";
    while (!routing.isEnd(index)) {
      IntVar timeVar = timeDimension.cumulVar(index);
      route += manager.indexToNode(index) + " Time(" + solution.min(timeVar) + ","
          + solution.max(timeVar) + ") -> ";
      index = solution.value(routing.nextVar(index));
    }
    IntVar timeVar = timeDimension.cumulVar(index);
    route += manager.indexToNode(index) + " Time(" + solution.min(timeVar) + ","
        + solution.max(timeVar) + ")";
    logger.info(route);
    logger.info("Time of the route: " + solution.min(timeVar) + "min");
    totalTime += solution.min(timeVar);
  }
  logger.info("Total time of all routes: " + totalTime + "min");
}

سی شارپ

/// <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.
    RoutingDimension timeDimension = routing.GetMutableDimension("Time");
    long totalTime = 0;
    for (int i = 0; i < data.VehicleNumber; ++i)
    {
        Console.WriteLine("Route for Vehicle {0}:", i);
        var index = routing.Start(i);
        while (routing.IsEnd(index) == false)
        {
            var timeVar = timeDimension.CumulVar(index);
            Console.Write("{0} Time({1},{2}) -> ", manager.IndexToNode(index), solution.Min(timeVar),
                          solution.Max(timeVar));
            index = solution.Value(routing.NextVar(index));
        }
        var endTimeVar = timeDimension.CumulVar(index);
        Console.WriteLine("{0} Time({1},{2})", manager.IndexToNode(index), solution.Min(endTimeVar),
                          solution.Max(endTimeVar));
        Console.WriteLine("Time of the route: {0}min", solution.Min(endTimeVar));
        totalTime += solution.Min(endTimeVar);
    }
    Console.WriteLine("Total time of all routes: {0}min", totalTime);
}

راه حل مسیرهای وسیله نقلیه و پنجره راه حل را در هر مکان نشان می دهد، همانطور که در بخش بعدی توضیح داده شد.

راه حل ویندوز

پنجره راه حل در یک مکان، فاصله زمانی است که طی آن یک وسیله نقلیه باید به مقصد برسد، تا در برنامه بماند.

در تابع چاپگر حل بالا، پنجره راه حل با (assignment.Min(time_var), assignment.Max(time_var) که در آن time_var = time_dimension.CumulVar(index) زمان سفر تجمعی وسیله نقلیه در مکان است، برگردانده می شود.

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

بخش اجرای برنامه پنجره های راه حل را برای این مثال توضیح می دهد.

حل

تابع اصلی برای این مثال مشابه عملکرد مثال TSP است.

پایتون

solution = routing.SolveWithParameters(search_parameters)

C++

const Assignment* solution = routing.SolveWithParameters(searchParameters);

جاوا

Assignment solution = routing.solveWithParameters(searchParameters);

سی شارپ

Assignment solution = routing.SolveWithParameters(searchParameters);

اجرای برنامه

وقتی برنامه را اجرا می کنید، خروجی زیر را نمایش می دهد:

Route for vehicle 0:
 0 Time(0,0) ->  9 Time(2,3) ->  14 Time(7,8) -> 16 Time(11,11) ->  0 Time(18,18)
Time of the route: 18min

Route for vehicle 1:
 0 Time(0,0) -> 7 Time(2,4) -> 1 Time(7,11) -> 4 Time(10,13) -> 3 Time(16,16) -> 0 Time(24,24)
Time of the route: 24min

Route for vehicle 2:
 0 Time(0,0) -> 12 Time(4,4) -> 13 Time(6,6) -> 15 Time(11,11) -> 11 Time(14,14) -> 0 Time(20,20)
Time of the route: 20min

Route for vehicle 3:
 0 Time(0,0) -> 5 Time(3,3) -> 8 Time(5,5) -> 6 Time(7,7) -> 2 Time(10,10) -> 10 Time(14,14) ->
 0 Time(20,20)
Time of the route: 20min

Total time of all routes: 82min

برای هر مکان در یک مسیر، Time(a,b) پنجره راه حل است: وسیله نقلیه ای که از مکان بازدید می کند باید این کار را در آن بازه زمانی انجام دهد تا در برنامه بماند.

به عنوان مثال، به قسمت زیر از مسیر برای وسیله نقلیه 0 نگاهی بیندازید.

0 Time(0,0) -> 9 Time(2,3) -> 14 Time(7,8)

در مکان 9، پنجره راه حل Time(2,3) است، به این معنی که وسیله نقلیه باید بین زمان های 2 و 3 به آنجا برسد. توجه داشته باشید که پنجره راه حل در پنجره زمان محدودیت در آن مکان موجود است، (0,&nbsp;3) ، در داده های مشکل آورده شده است. پنجره حل در زمان 2 شروع می شود زیرا 2 واحد زمان (ورودی 0، 9 ماتریس زمان ) طول می کشد تا از انبار به مکان 9 برسد.

چرا وسیله نقلیه می تواند از مکان 9 در هر زمان بین ساعت 2 و 3 حرکت کند؟ دلیل آن این است که از آنجایی که زمان سفر از مکان 9 تا مکان 14 3 است، اگر وسیله نقلیه هر زمانی قبل از ساعت 3 حرکت کند، قبل از ساعت 6 به مکان 14 می رسد که برای بازدید آن خیلی زود است. بنابراین وسیله نقلیه باید جایی منتظر بماند، به عنوان مثال، راننده می تواند تصمیم بگیرد که در مکان 9 تا زمان 3 بدون تاخیر در تکمیل مسیر منتظر بماند.

ممکن است متوجه شده باشید که برخی از پنجره های راه حل (مثلاً در مکان های 9 و 14) زمان شروع و پایان متفاوتی دارند، اما برخی دیگر (مثلاً در مسیرهای 2 و 3) زمان شروع و پایان یکسانی دارند. در حالت اول، وسایل نقلیه می توانند قبل از حرکت تا انتهای پنجره منتظر بمانند، در حالی که در مورد دوم، باید به محض رسیدن حرکت کنند.

پنجره های راه حل را در یک لیست یا آرایه ذخیره کنید

بخش TSP نحوه ذخیره مسیرها را در یک راه حل برای یک لیست یا آرایه نشان می دهد. برای یک VRPTW، می توانید راه حل ویندوز را نیز ذخیره کنید. توابع زیر پنجره های راه حل را در یک لیست (Python) یا یک آرایه (C++) ذخیره می کنند.

پایتون

def get_cumul_data(solution, routing, dimension):
  """Get cumulative data from a dimension and store it in an array."""
  # Returns an array cumul_data whose i,j entry contains the minimum and
  # maximum of CumulVar for the dimension at the jth node on route :
  # - cumul_data[i][j][0] is the minimum.
  # - cumul_data[i][j][1] is the maximum.

  cumul_data = []
  for route_nbr in range(routing.vehicles()):
    route_data = []
    index = routing.Start(route_nbr)
    dim_var = dimension.CumulVar(index)
    route_data.append([solution.Min(dim_var), solution.Max(dim_var)])
    while not routing.IsEnd(index):
      index = solution.Value(routing.NextVar(index))
      dim_var = dimension.CumulVar(index)
      route_data.append([solution.Min(dim_var), solution.Max(dim_var)])
    cumul_data.append(route_data)
  return cumul_data

C++

std::vector<std::vector<std::pair<int64_t, int64_t>>> GetCumulData(
    const Assignment& solution, const RoutingModel& routing,
    const RoutingDimension& dimension) {
  // Returns an array cumul_data, whose i, j entry is a pair containing
  // the minimum and maximum of CumulVar for the dimension.:
  // - cumul_data[i][j].first is the minimum.
  // - cumul_data[i][j].second is the maximum.
  std::vector<std::vector<std::pair<int64_t, int64_t>>> cumul_data(
      routing.vehicles());

  for (int vehicle_id = 0; vehicle_id < routing.vehicles(); ++vehicle_id) {
    int64_t index = routing.Start(vehicle_id);
    IntVar* dim_var = dimension.CumulVar(index);
    cumul_data[vehicle_id].emplace_back(solution.Min(dim_var),
                                        solution.Max(dim_var));
    while (!routing.IsEnd(index)) {
      index = solution.Value(routing.NextVar(index));
      IntVar* dim_var = dimension.CumulVar(index);
      cumul_data[vehicle_id].emplace_back(solution.Min(dim_var),
                                          solution.Max(dim_var));
    }
  }
  return cumul_data;
}

توابع حداقل و حداکثر مقادیر داده های تجمعی را برای هر بعد (نه فقط زمان) ذخیره می کنند. در مثال فعلی، این مقادیر کران های پایین و بالایی پنجره حل هستند و بعد ارسال شده به تابع time_dimension است.

توابع زیر راه حل را از مسیرها و داده های تجمعی چاپ می کنند.

پایتون

def print_solution(routes, cumul_data):
  """Print the solution."""
  total_time = 0
  route_str = ""
  for i, route in enumerate(routes):
    route_str += "Route " + str(i) + ":\n"
    start_time = cumul_data[i][0][0]
    end_time = cumul_data[i][0][1]
    route_str += (
        "  "
        + str(route[0])
        + " Time("
        + str(start_time)
        + ", "
        + str(end_time)
        + ")"
    )
    for j in range(1, len(route)):
      start_time = cumul_data[i][j][0]
      end_time = cumul_data[i][j][1]
      route_str += (
          " -> "
          + str(route[j])
          + " Time("
          + str(start_time)
          + ", "
          + str(end_time)
          + ")"
      )
    route_str += f"\n  Route time: {start_time}min\n\n"
    total_time += cumul_data[i][len(route) - 1][0]
  route_str += f"Total time: {total_time}min"
  print(route_str)

C++

void PrintSolution(
    const std::vector<std::vector<int>> routes,
    std::vector<std::vector<std::pair<int64_t, int64_t>>> cumul_data) {
  int64_t total_time{0};
  std::ostringstream route;
  for (int vehicle_id = 0; vehicle_id < routes.size(); ++vehicle_id) {
    route << "\nRoute " << vehicle_id << ": \n";

    route << "  " << routes[vehicle_id][0] << " Time("
          << cumul_data[vehicle_id][0].first << ", "
          << cumul_data[vehicle_id][0].second << ") ";
    for (int j = 1; j < routes[vehicle_id].size(); ++j) {
      route << "-> " << routes[vehicle_id][j] << " Time("
            << cumul_data[vehicle_id][j].first << ", "
            << cumul_data[vehicle_id][j].second << ") ";
    }
    route << "\n  Route time: "
          << cumul_data[vehicle_id][routes[vehicle_id].size() - 1].first
          << " minutes\n";

    total_time += cumul_data[vehicle_id][routes[vehicle_id].size() - 1].first;
  }
  route << "\nTotal travel time: " << total_time << " minutes";
  LOG(INFO) << route.str();
}

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

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

پایتون

"""Vehicles Routing Problem (VRP) with Time Windows."""

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["time_matrix"] = [
        [0, 6, 9, 8, 7, 3, 6, 2, 3, 2, 6, 6, 4, 4, 5, 9, 7],
        [6, 0, 8, 3, 2, 6, 8, 4, 8, 8, 13, 7, 5, 8, 12, 10, 14],
        [9, 8, 0, 11, 10, 6, 3, 9, 5, 8, 4, 15, 14, 13, 9, 18, 9],
        [8, 3, 11, 0, 1, 7, 10, 6, 10, 10, 14, 6, 7, 9, 14, 6, 16],
        [7, 2, 10, 1, 0, 6, 9, 4, 8, 9, 13, 4, 6, 8, 12, 8, 14],
        [3, 6, 6, 7, 6, 0, 2, 3, 2, 2, 7, 9, 7, 7, 6, 12, 8],
        [6, 8, 3, 10, 9, 2, 0, 6, 2, 5, 4, 12, 10, 10, 6, 15, 5],
        [2, 4, 9, 6, 4, 3, 6, 0, 4, 4, 8, 5, 4, 3, 7, 8, 10],
        [3, 8, 5, 10, 8, 2, 2, 4, 0, 3, 4, 9, 8, 7, 3, 13, 6],
        [2, 8, 8, 10, 9, 2, 5, 4, 3, 0, 4, 6, 5, 4, 3, 9, 5],
        [6, 13, 4, 14, 13, 7, 4, 8, 4, 4, 0, 10, 9, 8, 4, 13, 4],
        [6, 7, 15, 6, 4, 9, 12, 5, 9, 6, 10, 0, 1, 3, 7, 3, 10],
        [4, 5, 14, 7, 6, 7, 10, 4, 8, 5, 9, 1, 0, 2, 6, 4, 8],
        [4, 8, 13, 9, 8, 7, 10, 3, 7, 4, 8, 3, 2, 0, 4, 5, 6],
        [5, 12, 9, 14, 12, 6, 6, 7, 3, 3, 4, 7, 6, 4, 0, 9, 2],
        [9, 10, 18, 6, 8, 12, 15, 8, 13, 9, 13, 3, 4, 5, 9, 0, 9],
        [7, 14, 9, 16, 14, 8, 5, 10, 6, 5, 4, 10, 8, 6, 2, 9, 0],
    ]
    data["time_windows"] = [
        (0, 5),  # depot
        (7, 12),  # 1
        (10, 15),  # 2
        (16, 18),  # 3
        (10, 13),  # 4
        (0, 5),  # 5
        (5, 10),  # 6
        (0, 4),  # 7
        (5, 10),  # 8
        (0, 3),  # 9
        (10, 16),  # 10
        (10, 15),  # 11
        (0, 5),  # 12
        (5, 10),  # 13
        (7, 8),  # 14
        (10, 15),  # 15
        (11, 15),  # 16
    ]
    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()}")
    time_dimension = routing.GetDimensionOrDie("Time")
    total_time = 0
    for vehicle_id in range(data["num_vehicles"]):
        index = routing.Start(vehicle_id)
        plan_output = f"Route for vehicle {vehicle_id}:\n"
        while not routing.IsEnd(index):
            time_var = time_dimension.CumulVar(index)
            plan_output += (
                f"{manager.IndexToNode(index)}"
                f" Time({solution.Min(time_var)},{solution.Max(time_var)})"
                " -> "
            )
            index = solution.Value(routing.NextVar(index))
        time_var = time_dimension.CumulVar(index)
        plan_output += (
            f"{manager.IndexToNode(index)}"
            f" Time({solution.Min(time_var)},{solution.Max(time_var)})\n"
        )
        plan_output += f"Time of the route: {solution.Min(time_var)}min\n"
        print(plan_output)
        total_time += solution.Min(time_var)
    print(f"Total time of all routes: {total_time}min")


def main():
    """Solve the VRP with time windows."""
    # Instantiate the data problem.
    data = create_data_model()

    # Create the routing index manager.
    manager = pywrapcp.RoutingIndexManager(
        len(data["time_matrix"]), data["num_vehicles"], data["depot"]
    )

    # Create Routing Model.
    routing = pywrapcp.RoutingModel(manager)

    # Create and register a transit callback.
    def time_callback(from_index, to_index):
        """Returns the travel time between the two nodes."""
        # Convert from routing variable Index to time matrix NodeIndex.
        from_node = manager.IndexToNode(from_index)
        to_node = manager.IndexToNode(to_index)
        return data["time_matrix"][from_node][to_node]

    transit_callback_index = routing.RegisterTransitCallback(time_callback)

    # Define cost of each arc.
    routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)

    # Add Time Windows constraint.
    time = "Time"
    routing.AddDimension(
        transit_callback_index,
        30,  # allow waiting time
        30,  # maximum time per vehicle
        False,  # Don't force start cumul to zero.
        time,
    )
    time_dimension = routing.GetDimensionOrDie(time)
    # Add time window constraints for each location except depot.
    for location_idx, time_window in enumerate(data["time_windows"]):
        if location_idx == data["depot"]:
            continue
        index = manager.NodeToIndex(location_idx)
        time_dimension.CumulVar(index).SetRange(time_window[0], time_window[1])
    # Add time window constraints for each vehicle start node.
    depot_idx = data["depot"]
    for vehicle_id in range(data["num_vehicles"]):
        index = routing.Start(vehicle_id)
        time_dimension.CumulVar(index).SetRange(
            data["time_windows"][depot_idx][0], data["time_windows"][depot_idx][1]
        )

    # Instantiate route start and end times to produce feasible times.
    for i in range(data["num_vehicles"]):
        routing.AddVariableMinimizedByFinalizer(
            time_dimension.CumulVar(routing.Start(i))
        )
        routing.AddVariableMinimizedByFinalizer(time_dimension.CumulVar(routing.End(i)))

    # Setting first solution heuristic.
    search_parameters = pywrapcp.DefaultRoutingSearchParameters()
    search_parameters.first_solution_strategy = (
        routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC
    )

    # 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 <string>
#include <utility>
#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>> time_matrix{
      {0, 6, 9, 8, 7, 3, 6, 2, 3, 2, 6, 6, 4, 4, 5, 9, 7},
      {6, 0, 8, 3, 2, 6, 8, 4, 8, 8, 13, 7, 5, 8, 12, 10, 14},
      {9, 8, 0, 11, 10, 6, 3, 9, 5, 8, 4, 15, 14, 13, 9, 18, 9},
      {8, 3, 11, 0, 1, 7, 10, 6, 10, 10, 14, 6, 7, 9, 14, 6, 16},
      {7, 2, 10, 1, 0, 6, 9, 4, 8, 9, 13, 4, 6, 8, 12, 8, 14},
      {3, 6, 6, 7, 6, 0, 2, 3, 2, 2, 7, 9, 7, 7, 6, 12, 8},
      {6, 8, 3, 10, 9, 2, 0, 6, 2, 5, 4, 12, 10, 10, 6, 15, 5},
      {2, 4, 9, 6, 4, 3, 6, 0, 4, 4, 8, 5, 4, 3, 7, 8, 10},
      {3, 8, 5, 10, 8, 2, 2, 4, 0, 3, 4, 9, 8, 7, 3, 13, 6},
      {2, 8, 8, 10, 9, 2, 5, 4, 3, 0, 4, 6, 5, 4, 3, 9, 5},
      {6, 13, 4, 14, 13, 7, 4, 8, 4, 4, 0, 10, 9, 8, 4, 13, 4},
      {6, 7, 15, 6, 4, 9, 12, 5, 9, 6, 10, 0, 1, 3, 7, 3, 10},
      {4, 5, 14, 7, 6, 7, 10, 4, 8, 5, 9, 1, 0, 2, 6, 4, 8},
      {4, 8, 13, 9, 8, 7, 10, 3, 7, 4, 8, 3, 2, 0, 4, 5, 6},
      {5, 12, 9, 14, 12, 6, 6, 7, 3, 3, 4, 7, 6, 4, 0, 9, 2},
      {9, 10, 18, 6, 8, 12, 15, 8, 13, 9, 13, 3, 4, 5, 9, 0, 9},
      {7, 14, 9, 16, 14, 8, 5, 10, 6, 5, 4, 10, 8, 6, 2, 9, 0},
  };
  const std::vector<std::pair<int64_t, int64_t>> time_windows{
      {0, 5},    // depot
      {7, 12},   // 1
      {10, 15},  // 2
      {16, 18},  // 3
      {10, 13},  // 4
      {0, 5},    // 5
      {5, 10},   // 6
      {0, 4},    // 7
      {5, 10},   // 8
      {0, 3},    // 9
      {10, 16},  // 10
      {10, 15},  // 11
      {0, 5},    // 12
      {5, 10},   // 13
      {7, 8},    // 14
      {10, 15},  // 15
      {11, 15},  // 16
  };
  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) {
  const RoutingDimension& time_dimension = routing.GetDimensionOrDie("Time");
  int64_t total_time{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 << ":";
    std::ostringstream route;
    while (!routing.IsEnd(index)) {
      auto time_var = time_dimension.CumulVar(index);
      route << manager.IndexToNode(index).value() << " Time("
            << solution.Min(time_var) << ", " << solution.Max(time_var)
            << ") -> ";
      index = solution.Value(routing.NextVar(index));
    }
    auto time_var = time_dimension.CumulVar(index);
    LOG(INFO) << route.str() << manager.IndexToNode(index).value() << " Time("
              << solution.Min(time_var) << ", " << solution.Max(time_var)
              << ")";
    LOG(INFO) << "Time of the route: " << solution.Min(time_var) << "min";
    total_time += solution.Min(time_var);
  }
  LOG(INFO) << "Total time of all routes: " << total_time << "min";
  LOG(INFO) << "";
  LOG(INFO) << "Advanced usage:";
  LOG(INFO) << "Problem solved in " << routing.solver()->wall_time() << "ms";
}

void VrpTimeWindows() {
  // Instantiate the data problem.
  DataModel data;

  // Create Routing Index Manager
  RoutingIndexManager manager(data.time_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 time matrix NodeIndex.
        const int from_node = manager.IndexToNode(from_index).value();
        const int to_node = manager.IndexToNode(to_index).value();
        return data.time_matrix[from_node][to_node];
      });

  // Define cost of each arc.
  routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index);

  // Add Time constraint.
  const std::string time = "Time";
  routing.AddDimension(transit_callback_index,  // transit callback index
                       int64_t{30},             // allow waiting time
                       int64_t{30},             // maximum time per vehicle
                       false,  // Don't force start cumul to zero
                       time);
  const RoutingDimension& time_dimension = routing.GetDimensionOrDie(time);
  // Add time window constraints for each location except depot.
  for (int i = 1; i < data.time_windows.size(); ++i) {
    const int64_t index =
        manager.NodeToIndex(RoutingIndexManager::NodeIndex(i));
    time_dimension.CumulVar(index)->SetRange(data.time_windows[i].first,
                                             data.time_windows[i].second);
  }
  // Add time window constraints for each vehicle start node.
  for (int i = 0; i < data.num_vehicles; ++i) {
    const int64_t index = routing.Start(i);
    time_dimension.CumulVar(index)->SetRange(data.time_windows[0].first,
                                             data.time_windows[0].second);
  }

  // Instantiate route start and end times to produce feasible times.
  for (int i = 0; i < data.num_vehicles; ++i) {
    routing.AddVariableMinimizedByFinalizer(
        time_dimension.CumulVar(routing.Start(i)));
    routing.AddVariableMinimizedByFinalizer(
        time_dimension.CumulVar(routing.End(i)));
  }

  // Setting first solution heuristic.
  RoutingSearchParameters searchParameters = DefaultRoutingSearchParameters();
  searchParameters.set_first_solution_strategy(
      FirstSolutionStrategy::PATH_CHEAPEST_ARC);

  // 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::VrpTimeWindows();
  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.IntVar;
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.main;
import java.util.logging.Logger;

/** VRPTW. */
public class VrpTimeWindows {
  private static final Logger logger = Logger.getLogger(VrpTimeWindows.class.getName());
  static class DataModel {
    public final long[][] timeMatrix = {
        {0, 6, 9, 8, 7, 3, 6, 2, 3, 2, 6, 6, 4, 4, 5, 9, 7},
        {6, 0, 8, 3, 2, 6, 8, 4, 8, 8, 13, 7, 5, 8, 12, 10, 14},
        {9, 8, 0, 11, 10, 6, 3, 9, 5, 8, 4, 15, 14, 13, 9, 18, 9},
        {8, 3, 11, 0, 1, 7, 10, 6, 10, 10, 14, 6, 7, 9, 14, 6, 16},
        {7, 2, 10, 1, 0, 6, 9, 4, 8, 9, 13, 4, 6, 8, 12, 8, 14},
        {3, 6, 6, 7, 6, 0, 2, 3, 2, 2, 7, 9, 7, 7, 6, 12, 8},
        {6, 8, 3, 10, 9, 2, 0, 6, 2, 5, 4, 12, 10, 10, 6, 15, 5},
        {2, 4, 9, 6, 4, 3, 6, 0, 4, 4, 8, 5, 4, 3, 7, 8, 10},
        {3, 8, 5, 10, 8, 2, 2, 4, 0, 3, 4, 9, 8, 7, 3, 13, 6},
        {2, 8, 8, 10, 9, 2, 5, 4, 3, 0, 4, 6, 5, 4, 3, 9, 5},
        {6, 13, 4, 14, 13, 7, 4, 8, 4, 4, 0, 10, 9, 8, 4, 13, 4},
        {6, 7, 15, 6, 4, 9, 12, 5, 9, 6, 10, 0, 1, 3, 7, 3, 10},
        {4, 5, 14, 7, 6, 7, 10, 4, 8, 5, 9, 1, 0, 2, 6, 4, 8},
        {4, 8, 13, 9, 8, 7, 10, 3, 7, 4, 8, 3, 2, 0, 4, 5, 6},
        {5, 12, 9, 14, 12, 6, 6, 7, 3, 3, 4, 7, 6, 4, 0, 9, 2},
        {9, 10, 18, 6, 8, 12, 15, 8, 13, 9, 13, 3, 4, 5, 9, 0, 9},
        {7, 14, 9, 16, 14, 8, 5, 10, 6, 5, 4, 10, 8, 6, 2, 9, 0},
    };
    public final long[][] timeWindows = {
        {0, 5}, // depot
        {7, 12}, // 1
        {10, 15}, // 2
        {16, 18}, // 3
        {10, 13}, // 4
        {0, 5}, // 5
        {5, 10}, // 6
        {0, 4}, // 7
        {5, 10}, // 8
        {0, 3}, // 9
        {10, 16}, // 10
        {10, 15}, // 11
        {0, 5}, // 12
        {5, 10}, // 13
        {7, 8}, // 14
        {10, 15}, // 15
        {11, 15}, // 16
    };
    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.
    RoutingDimension timeDimension = routing.getMutableDimension("Time");
    long totalTime = 0;
    for (int i = 0; i < data.vehicleNumber; ++i) {
      long index = routing.start(i);
      logger.info("Route for Vehicle " + i + ":");
      String route = "";
      while (!routing.isEnd(index)) {
        IntVar timeVar = timeDimension.cumulVar(index);
        route += manager.indexToNode(index) + " Time(" + solution.min(timeVar) + ","
            + solution.max(timeVar) + ") -> ";
        index = solution.value(routing.nextVar(index));
      }
      IntVar timeVar = timeDimension.cumulVar(index);
      route += manager.indexToNode(index) + " Time(" + solution.min(timeVar) + ","
          + solution.max(timeVar) + ")";
      logger.info(route);
      logger.info("Time of the route: " + solution.min(timeVar) + "min");
      totalTime += solution.min(timeVar);
    }
    logger.info("Total time of all routes: " + totalTime + "min");
  }

  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.timeMatrix.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.timeMatrix[fromNode][toNode];
        });

    // Define cost of each arc.
    routing.setArcCostEvaluatorOfAllVehicles(transitCallbackIndex);

    // Add Time constraint.
    routing.addDimension(transitCallbackIndex, // transit callback
        30, // allow waiting time
        30, // vehicle maximum capacities
        false, // start cumul to zero
        "Time");
    RoutingDimension timeDimension = routing.getMutableDimension("Time");
    // Add time window constraints for each location except depot.
    for (int i = 1; i < data.timeWindows.length; ++i) {
      long index = manager.nodeToIndex(i);
      timeDimension.cumulVar(index).setRange(data.timeWindows[i][0], data.timeWindows[i][1]);
    }
    // Add time window constraints for each vehicle start node.
    for (int i = 0; i < data.vehicleNumber; ++i) {
      long index = routing.start(i);
      timeDimension.cumulVar(index).setRange(data.timeWindows[0][0], data.timeWindows[0][1]);
    }

    // Instantiate route start and end times to produce feasible times.
    for (int i = 0; i < data.vehicleNumber; ++i) {
      routing.addVariableMinimizedByFinalizer(timeDimension.cumulVar(routing.start(i)));
      routing.addVariableMinimizedByFinalizer(timeDimension.cumulVar(routing.end(i)));
    }

    // Setting first solution heuristic.
    RoutingSearchParameters searchParameters =
        main.defaultRoutingSearchParameters()
            .toBuilder()
            .setFirstSolutionStrategy(FirstSolutionStrategy.Value.PATH_CHEAPEST_ARC)
            .build();

    // Solve the problem.
    Assignment solution = routing.solveWithParameters(searchParameters);

    // Print solution on console.
    printSolution(data, routing, manager, solution);
  }
}
// [END_program_part1]

سی شارپ

using System;
using System.Collections.Generic;
using Google.OrTools.ConstraintSolver;

/// <summary>
///   Vehicles Routing Problem (VRP) with Time Windows.
/// </summary>
public class VrpTimeWindows
{
    class DataModel
    {
        public long[,] TimeMatrix = {
            { 0, 6, 9, 8, 7, 3, 6, 2, 3, 2, 6, 6, 4, 4, 5, 9, 7 },
            { 6, 0, 8, 3, 2, 6, 8, 4, 8, 8, 13, 7, 5, 8, 12, 10, 14 },
            { 9, 8, 0, 11, 10, 6, 3, 9, 5, 8, 4, 15, 14, 13, 9, 18, 9 },
            { 8, 3, 11, 0, 1, 7, 10, 6, 10, 10, 14, 6, 7, 9, 14, 6, 16 },
            { 7, 2, 10, 1, 0, 6, 9, 4, 8, 9, 13, 4, 6, 8, 12, 8, 14 },
            { 3, 6, 6, 7, 6, 0, 2, 3, 2, 2, 7, 9, 7, 7, 6, 12, 8 },
            { 6, 8, 3, 10, 9, 2, 0, 6, 2, 5, 4, 12, 10, 10, 6, 15, 5 },
            { 2, 4, 9, 6, 4, 3, 6, 0, 4, 4, 8, 5, 4, 3, 7, 8, 10 },
            { 3, 8, 5, 10, 8, 2, 2, 4, 0, 3, 4, 9, 8, 7, 3, 13, 6 },
            { 2, 8, 8, 10, 9, 2, 5, 4, 3, 0, 4, 6, 5, 4, 3, 9, 5 },
            { 6, 13, 4, 14, 13, 7, 4, 8, 4, 4, 0, 10, 9, 8, 4, 13, 4 },
            { 6, 7, 15, 6, 4, 9, 12, 5, 9, 6, 10, 0, 1, 3, 7, 3, 10 },
            { 4, 5, 14, 7, 6, 7, 10, 4, 8, 5, 9, 1, 0, 2, 6, 4, 8 },
            { 4, 8, 13, 9, 8, 7, 10, 3, 7, 4, 8, 3, 2, 0, 4, 5, 6 },
            { 5, 12, 9, 14, 12, 6, 6, 7, 3, 3, 4, 7, 6, 4, 0, 9, 2 },
            { 9, 10, 18, 6, 8, 12, 15, 8, 13, 9, 13, 3, 4, 5, 9, 0, 9 },
            { 7, 14, 9, 16, 14, 8, 5, 10, 6, 5, 4, 10, 8, 6, 2, 9, 0 },
        };
        public long[,] TimeWindows = {
            { 0, 5 },   // depot
            { 7, 12 },  // 1
            { 10, 15 }, // 2
            { 16, 18 }, // 3
            { 10, 13 }, // 4
            { 0, 5 },   // 5
            { 5, 10 },  // 6
            { 0, 4 },   // 7
            { 5, 10 },  // 8
            { 0, 3 },   // 9
            { 10, 16 }, // 10
            { 10, 15 }, // 11
            { 0, 5 },   // 12
            { 5, 10 },  // 13
            { 7, 8 },   // 14
            { 10, 15 }, // 15
            { 11, 15 }, // 16
        };
        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.
        RoutingDimension timeDimension = routing.GetMutableDimension("Time");
        long totalTime = 0;
        for (int i = 0; i < data.VehicleNumber; ++i)
        {
            Console.WriteLine("Route for Vehicle {0}:", i);
            var index = routing.Start(i);
            while (routing.IsEnd(index) == false)
            {
                var timeVar = timeDimension.CumulVar(index);
                Console.Write("{0} Time({1},{2}) -> ", manager.IndexToNode(index), solution.Min(timeVar),
                              solution.Max(timeVar));
                index = solution.Value(routing.NextVar(index));
            }
            var endTimeVar = timeDimension.CumulVar(index);
            Console.WriteLine("{0} Time({1},{2})", manager.IndexToNode(index), solution.Min(endTimeVar),
                              solution.Max(endTimeVar));
            Console.WriteLine("Time of the route: {0}min", solution.Min(endTimeVar));
            totalTime += solution.Min(endTimeVar);
        }
        Console.WriteLine("Total time of all routes: {0}min", totalTime);
    }

    public static void Main(String[] args)
    {
        // Instantiate the data problem.
        DataModel data = new DataModel();

        // Create Routing Index Manager
        RoutingIndexManager manager =
            new RoutingIndexManager(data.TimeMatrix.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 time
                                                                       // matrix NodeIndex.
                                                                       var fromNode = manager.IndexToNode(fromIndex);
                                                                       var toNode = manager.IndexToNode(toIndex);
                                                                       return data.TimeMatrix[fromNode, toNode];
                                                                   });

        // Define cost of each arc.
        routing.SetArcCostEvaluatorOfAllVehicles(transitCallbackIndex);

        // Add Time constraint.
        routing.AddDimension(transitCallbackIndex, // transit callback
                             30,                   // allow waiting time
                             30,                   // vehicle maximum capacities
                             false,                // start cumul to zero
                             "Time");
        RoutingDimension timeDimension = routing.GetMutableDimension("Time");
        // Add time window constraints for each location except depot.
        for (int i = 1; i < data.TimeWindows.GetLength(0); ++i)
        {
            long index = manager.NodeToIndex(i);
            timeDimension.CumulVar(index).SetRange(data.TimeWindows[i, 0], data.TimeWindows[i, 1]);
        }
        // Add time window constraints for each vehicle start node.
        for (int i = 0; i < data.VehicleNumber; ++i)
        {
            long index = routing.Start(i);
            timeDimension.CumulVar(index).SetRange(data.TimeWindows[0, 0], data.TimeWindows[0, 1]);
        }

        // Instantiate route start and end times to produce feasible times.
        for (int i = 0; i < data.VehicleNumber; ++i)
        {
            routing.AddVariableMinimizedByFinalizer(timeDimension.CumulVar(routing.Start(i)));
            routing.AddVariableMinimizedByFinalizer(timeDimension.CumulVar(routing.End(i)));
        }

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