Tính đến nay, chúng tôi đã xem xét các vấn đề về định tuyến với những ràng buộc áp dụng trong quá trình di chuyển của xe. Tiếp theo, chúng tôi trình bày một VRPTW cũng có những hạn chế ở kho: tất cả các xe đều cần phải được tải trước khi ra mắt kho hàng và huỷ tải khi trả lại hàng. Vì chỉ có hai đế tải hiện có, nên bạn có thể tải hoặc huỷ tải tối đa hai xe cùng lúc. Do đó, một số xe phải chờ các xe khác được tải, trì hoãn việc khởi hành từ kho hàng. Vấn đề là tìm các tuyến đường xe tối ưu cho VRPTW cũng đáp ứng được các điều kiện tải và tải hàng tại kho.
Ví dụ về VRPTW với các hạn chế về tài nguyên
Sơ đồ dưới đây cho thấy một VRPTW có các hạn chế về tài nguyên.
Giải quyết ví dụ bằng OR-Tools
Các phần sau đây cho biết cách giải quyết VRPTW bằng những hạn chế về tài nguyên bằng cách sử dụng OR-Công cụ. Một số mã cho ví dụ giống như trong ví dụ VRPTW trước, vì vậy chúng tôi sẽ chỉ mô tả các phần mới.
Tạo dữ liệu
Mã sau đây tạo dữ liệu cho ví dụ.
Python
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
(5, 14), # 3
(5, 13), # 4
(0, 5), # 5
(5, 10), # 6
(0, 10), # 7
(5, 10), # 8
(0, 5), # 9
(10, 16), # 10
(10, 15), # 11
(0, 5), # 12
(5, 10), # 13
(7, 12), # 14
(10, 15), # 15
(5, 15), # 16
]
data["num_vehicles"] = 4
data["vehicle_load_time"] = 5
data["vehicle_unload_time"] = 5
data["depot_capacity"] = 2
data["depot"] = 0
return data
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
{5, 14}, // 3
{5, 13}, // 4
{0, 5}, // 5
{5, 10}, // 6
{0, 10}, // 7
{5, 10}, // 8
{0, 5}, // 9
{10, 16}, // 10
{10, 15}, // 11
{0, 5}, // 12
{5, 10}, // 13
{7, 12}, // 14
{10, 15}, // 15
{5, 15}, // 16
};
const int num_vehicles = 4;
const int vehicle_load_time = 5;
const int vehicle_unload_time = 5;
const int depot_capacity = 2;
const RoutingIndexManager::NodeIndex depot{0};
};
Java
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
{5, 14}, // 3
{5, 13}, // 4
{0, 5}, // 5
{5, 10}, // 6
{0, 10}, // 7
{5, 10}, // 8
{0, 5}, // 9
{10, 16}, // 10
{10, 15}, // 11
{0, 5}, // 12
{5, 10}, // 13
{7, 12}, // 14
{10, 15}, // 15
{5, 15}, // 16
};
public final int vehicleNumber = 4;
public final int vehicleLoadTime = 5;
public final int vehicleUnloadTime = 5;
public final int depotCapacity = 2;
public final int depot = 0;
}
C#
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
{ 5, 14 }, // 3
{ 5, 13 }, // 4
{ 0, 5 }, // 5
{ 5, 10 }, // 6
{ 0, 10 }, // 7
{ 5, 10 }, // 8
{ 0, 5 }, // 9
{ 10, 16 }, // 10
{ 10, 15 }, // 11
{ 0, 5 }, // 12
{ 5, 10 }, // 13
{ 7, 12 }, // 14
{ 10, 15 }, // 15
{ 5, 15 }, // 16
};
public int VehicleNumber = 4;
public int VehicleLoadTime = 5;
public int VehicleUnloadTime = 5;
public int DepotCapacity = 2;
public int Depot = 0;
};
Các dữ liệu này bao gồm:
time_matrix: Một loạt các thời gian di chuyển giữa các vị trí.time_windows: Một loạt các khoảng thời gian cho các lượt ghé thăm các vị trí đã yêu cầu.vehicle_load_time: Thời gian cần thiết để tải một chiếc xe.vehicle_unload_time: Thời gian cần thiết để gỡ tải xe.depot_capacity: Số lượng xe tối đa có thể tải hoặc tải cùng lúc.
Thêm khung thời gian để tải và hủy tải
Mã sau đây thêm khung thời gian để tải và gỡ tải xe tại
kho hàng.
Các cửa sổ này, được tạo bằng phương thức FixedDurationIntervalVar, là
các khoảng thời gian thay đổi, có nghĩa là các cửa sổ đó không có thời gian bắt đầu và kết thúc cố định
(không giống như các khoảng thời gian tại các vị trí). Chiều rộng của cửa sổ
được vehicle_load_time và vehicle_unload_time chỉ định,
giống trong ví dụ này.
Python
solver = routing.solver()
intervals = []
for i in range(data["num_vehicles"]):
# Add time windows at start of routes
intervals.append(
solver.FixedDurationIntervalVar(
time_dimension.CumulVar(routing.Start(i)),
data["vehicle_load_time"],
"depot_interval",
)
)
# Add time windows at end of routes.
intervals.append(
solver.FixedDurationIntervalVar(
time_dimension.CumulVar(routing.End(i)),
data["vehicle_unload_time"],
"depot_interval",
)
)
C++
Solver* solver = routing.solver();
std::vector<IntervalVar*> intervals;
for (int i = 0; i < data.num_vehicles; ++i) {
// Add load duration at start of routes
intervals.push_back(solver->MakeFixedDurationIntervalVar(
time_dimension.CumulVar(routing.Start(i)), data.vehicle_load_time,
"depot_interval"));
// Add unload duration at end of routes.
intervals.push_back(solver->MakeFixedDurationIntervalVar(
time_dimension.CumulVar(routing.End(i)), data.vehicle_unload_time,
"depot_interval"));
}
Java
Solver solver = routing.solver();
IntervalVar[] intervals = new IntervalVar[data.vehicleNumber * 2];
for (int i = 0; i < data.vehicleNumber; ++i) {
// Add load duration at start of routes
intervals[2 * i] = solver.makeFixedDurationIntervalVar(
timeDimension.cumulVar(routing.start(i)), data.vehicleLoadTime, "depot_interval");
// Add unload duration at end of routes.
intervals[2 * i + 1] = solver.makeFixedDurationIntervalVar(
timeDimension.cumulVar(routing.end(i)), data.vehicleUnloadTime, "depot_interval");
}
C#
Solver solver = routing.solver();
IntervalVar[] intervals = new IntervalVar[data.VehicleNumber * 2];
for (int i = 0; i < data.VehicleNumber; ++i)
{
// Add load duration at start of routes
intervals[2 * i] = solver.MakeFixedDurationIntervalVar(timeDimension.CumulVar(routing.Start(i)),
data.VehicleLoadTime, "depot_interval");
// Add unload duration at end of routes.
intervals[2 * i + 1] = solver.MakeFixedDurationIntervalVar(timeDimension.CumulVar(routing.End(i)),
data.VehicleUnloadTime, "depot_interval");
}
Thêm các điều kiện ràng buộc về tài nguyên tại kho lưu trữ
Mã sau đây tạo ra quy tắc ràng buộc rằng tối đa 2 xe có thể tải hoặc huỷ tải cùng lúc.
Python
depot_usage = [1 for _ in range(len(intervals))]
solver.Add(
solver.Cumulative(intervals, depot_usage, data["depot_capacity"], "depot")
)
C++
std::vector<int64_t> depot_usage(intervals.size(), 1);
solver->AddConstraint(solver->MakeCumulative(intervals, depot_usage,
data.depot_capacity, "depot"));
Java
long[] depotUsage = new long[intervals.length];
Arrays.fill(depotUsage, 1);
solver.addConstraint(solver.makeCumulative(intervals, depotUsage, data.depotCapacity, "depot"));
C#
long[] depot_usage = Enumerable.Repeat<long>(1, intervals.Length).ToArray();
solver.Add(solver.MakeCumulative(intervals, depot_usage, data.DepotCapacity, "depot"));
depot_capacity là số lượng xe tối đa có thể tải hoặc
tải cùng lúc, trong ví dụ này là 2.
depot_usage là một vectơ chứa lượng dung lượng tương đối mà mỗi phương tiện cần
trong khi tải (hoặc khi huỷ tải). Trong ví dụ này, chúng tôi giả định tất cả các xe đều yêu cầu cùng một không gian, vì vậy, depot_usage chứa tất cả xe.
Điều này có nghĩa là số lượng xe tối đa có thể tải cùng lúc là 2.
Chạy chương trình
Phần sau đây cho thấy kết quả của chương trình.
Route for vehicle 0: 0 Time(5,5) -> 8 Time(8,8) -> 14 Time(11,11) -> 16 Time(13,13) -> 0 Time(20,20) Time of the route: 20min Route for vehicle 1: 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 2: 0 Time(5,5) -> 7 Time(7,7) -> 1 Time(11,11) -> 4 Time(13,13) -> 3 Time(14,14) -> 0 Time(25,25) Time of the route: 25min Route for vehicle 3: 0 Time(0,0) -> 9 Time(2,3) -> 5 Time(4,5) -> 6 Time(6,9) -> 2 Time(10,12) -> 10 Time(14,16) -> 0 Time(25,25) Time of the route: 25min Total time of all routes: 90min
Hãy xem ví dụ về VRPTW trước để biết nội dung giải thích về kết quả.
Lưu ý rằng xe 1 và 3 khởi hành kho tại thời điểm 0. Xe 0 và 2 phải tải các xe khác khởi hành lúc 5, giá trị vehicle_load_time.
Sơ đồ dưới đây cho thấy giải pháp.
Hoàn thành chương trình
Dưới đây là danh sách chương trình hoàn chỉnh cho vấn đề về việc định tuyến xe điện dung có các hạn chế về tài nguyên.
Python
"""Vehicles Routing Problem (VRP) with Resource Constraints."""
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
(5, 14), # 3
(5, 13), # 4
(0, 5), # 5
(5, 10), # 6
(0, 10), # 7
(5, 10), # 8
(0, 5), # 9
(10, 16), # 10
(10, 15), # 11
(0, 5), # 12
(5, 10), # 13
(7, 12), # 14
(10, 15), # 15
(5, 15), # 16
]
data["num_vehicles"] = 4
data["vehicle_load_time"] = 5
data["vehicle_unload_time"] = 5
data["depot_capacity"] = 2
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,
60, # allow waiting time
60, # 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 == 0:
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.
for vehicle_id in range(data["num_vehicles"]):
index = routing.Start(vehicle_id)
time_dimension.CumulVar(index).SetRange(
data["time_windows"][0][0], data["time_windows"][0][1]
)
# Add resource constraints at the depot.
solver = routing.solver()
intervals = []
for i in range(data["num_vehicles"]):
# Add time windows at start of routes
intervals.append(
solver.FixedDurationIntervalVar(
time_dimension.CumulVar(routing.Start(i)),
data["vehicle_load_time"],
"depot_interval",
)
)
# Add time windows at end of routes.
intervals.append(
solver.FixedDurationIntervalVar(
time_dimension.CumulVar(routing.End(i)),
data["vehicle_unload_time"],
"depot_interval",
)
)
depot_usage = [1 for _ in range(len(intervals))]
solver.Add(
solver.Cumulative(intervals, depot_usage, data["depot_capacity"], "depot")
)
# 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)
else:
print("No solution found !")
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
{5, 14}, // 3
{5, 13}, // 4
{0, 5}, // 5
{5, 10}, // 6
{0, 10}, // 7
{5, 10}, // 8
{0, 5}, // 9
{10, 16}, // 10
{10, 15}, // 11
{0, 5}, // 12
{5, 10}, // 13
{7, 12}, // 14
{10, 15}, // 15
{5, 15}, // 16
};
const int num_vehicles = 4;
const int vehicle_load_time = 5;
const int vehicle_unload_time = 5;
const int depot_capacity = 2;
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);
}
// Add resource constraints at the depot.
Solver* solver = routing.solver();
std::vector<IntervalVar*> intervals;
for (int i = 0; i < data.num_vehicles; ++i) {
// Add load duration at start of routes
intervals.push_back(solver->MakeFixedDurationIntervalVar(
time_dimension.CumulVar(routing.Start(i)), data.vehicle_load_time,
"depot_interval"));
// Add unload duration at end of routes.
intervals.push_back(solver->MakeFixedDurationIntervalVar(
time_dimension.CumulVar(routing.End(i)), data.vehicle_unload_time,
"depot_interval"));
}
std::vector<int64_t> depot_usage(intervals.size(), 1);
solver->AddConstraint(solver->MakeCumulative(intervals, depot_usage,
data.depot_capacity, "depot"));
// 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;
}
Java
package com.google.ortools.constraintsolver.samples;
import com.google.ortools.Loader;
import com.google.ortools.constraintsolver.Assignment;
import com.google.ortools.constraintsolver.FirstSolutionStrategy;
import com.google.ortools.constraintsolver.IntVar;
import com.google.ortools.constraintsolver.IntervalVar;
import com.google.ortools.constraintsolver.RoutingDimension;
import com.google.ortools.constraintsolver.RoutingIndexManager;
import com.google.ortools.constraintsolver.RoutingModel;
import com.google.ortools.constraintsolver.RoutingSearchParameters;
import com.google.ortools.constraintsolver.Solver;
import com.google.ortools.constraintsolver.main;
import java.util.Arrays;
import java.util.logging.Logger;
/** Minimal VRP with Resource Constraints.*/
public class VrpResources {
private static final Logger logger = Logger.getLogger(VrpResources.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
{5, 14}, // 3
{5, 13}, // 4
{0, 5}, // 5
{5, 10}, // 6
{0, 10}, // 7
{5, 10}, // 8
{0, 5}, // 9
{10, 16}, // 10
{10, 15}, // 11
{0, 5}, // 12
{5, 10}, // 13
{7, 12}, // 14
{10, 15}, // 15
{5, 15}, // 16
};
public final int vehicleNumber = 4;
public final int vehicleLoadTime = 5;
public final int vehicleUnloadTime = 5;
public final int depotCapacity = 2;
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]);
}
// Add resource constraints at the depot.
Solver solver = routing.solver();
IntervalVar[] intervals = new IntervalVar[data.vehicleNumber * 2];
for (int i = 0; i < data.vehicleNumber; ++i) {
// Add load duration at start of routes
intervals[2 * i] = solver.makeFixedDurationIntervalVar(
timeDimension.cumulVar(routing.start(i)), data.vehicleLoadTime, "depot_interval");
// Add unload duration at end of routes.
intervals[2 * i + 1] = solver.makeFixedDurationIntervalVar(
timeDimension.cumulVar(routing.end(i)), data.vehicleUnloadTime, "depot_interval");
}
long[] depotUsage = new long[intervals.length];
Arrays.fill(depotUsage, 1);
solver.addConstraint(solver.makeCumulative(intervals, depotUsage, data.depotCapacity, "depot"));
// 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);
}
}
C#
using System;
using System.Linq;
using System.Collections.Generic;
using Google.OrTools.ConstraintSolver;
/// <summary>
/// Vehicles Routing Problem (VRP) with Resource Constraints.
/// </summary>
public class VrpResources
{
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
{ 5, 14 }, // 3
{ 5, 13 }, // 4
{ 0, 5 }, // 5
{ 5, 10 }, // 6
{ 0, 10 }, // 7
{ 5, 10 }, // 8
{ 0, 5 }, // 9
{ 10, 16 }, // 10
{ 10, 15 }, // 11
{ 0, 5 }, // 12
{ 5, 10 }, // 13
{ 7, 12 }, // 14
{ 10, 15 }, // 15
{ 5, 15 }, // 16
};
public int VehicleNumber = 4;
public int VehicleLoadTime = 5;
public int VehicleUnloadTime = 5;
public int DepotCapacity = 2;
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
// distance 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 Distance 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]);
}
// Add resource constraints at the depot.
Solver solver = routing.solver();
IntervalVar[] intervals = new IntervalVar[data.VehicleNumber * 2];
for (int i = 0; i < data.VehicleNumber; ++i)
{
// Add load duration at start of routes
intervals[2 * i] = solver.MakeFixedDurationIntervalVar(timeDimension.CumulVar(routing.Start(i)),
data.VehicleLoadTime, "depot_interval");
// Add unload duration at end of routes.
intervals[2 * i + 1] = solver.MakeFixedDurationIntervalVar(timeDimension.CumulVar(routing.End(i)),
data.VehicleUnloadTime, "depot_interval");
}
long[] depot_usage = Enumerable.Repeat<long>(1, intervals.Length).ToArray();
solver.Add(solver.MakeCumulative(intervals, depot_usage, data.DepotCapacity, "depot"));
// 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);
}
}