Nhiều vấn đề về việc định tuyến xe liên quan đến việc lên lịch ghé thăm những khách hàng chỉ có mặt trong khoảng thời gian cụ thể.
Những sự cố này được gọi là sự cố định tuyến xe với khoảng thời gian (VRPTW).
Ví dụ về VRPTW
Trên trang này, chúng tôi sẽ đưa ra một ví dụ cho thấy cách giải quyết vấn đề về VRPTW. Vì vấn đề này liên quan đến cửa sổ thời gian, nên dữ liệu sẽ bao gồm một ma trận thời gian, trong đó chứa thời gian di chuyển giữa các vị trí (thay vì ma trận khoảng cách như trong các ví dụ trước).
Biểu đồ bên dưới hiển thị các địa điểm tham quan có màu xanh lam và kho hàng màu đen. Khung thời gian được hiển thị phía trên mỗi vị trí. Xem Tọa độ vị trí trong phần VRP để biết thêm thông tin chi tiết về cách xác định các vị trí.
Mục tiêu là giảm thiểu tổng thời gian di chuyển của xe.
Giải quyết ví dụ về VRPTW bằng OR-Tools
Các phần sau đây mô tả cách giải quyết ví dụ về VRPTW bằng công cụ OR.
Tạo dữ liệu
Hàm sau đây tạo dữ liệu cho bài toán.
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
(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
Dữ liệu bao gồm:
-
data['time_matrix']: Mảng thời gian di chuyển giữa các vị trí. Lưu ý rằng trường hợp này khác với các ví dụ trước (sử dụng ma trận khoảng cách). Nếu tất cả các phương tiện đều di chuyển ở cùng tốc độ, thì bạn sẽ nhận được giải pháp tương tự nếu sử dụng ma trận khoảng cách hoặc ma trận thời gian, vì quãng đường đi được là bội số không đổi của thời gian di chuyển. -
data['time_windows']: Một mảng khoảng thời gian của các địa điểm, mà bạn có thể coi là thời gian mà bạn yêu cầu ghé thăm. Các phương tiện phải ghé thăm một địa điểm trong khung thời gian của địa điểm đó. -
data['num_vehicles']: Số lượng xe trong đội phương tiện. -
data['depot']: Chỉ mục của kho hàng.
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};
};
Dữ liệu bao gồm:
-
time_matrix: Mảng thời gian di chuyển giữa các vị trí. Lưu ý rằng trường hợp này khác với các ví dụ trước (sử dụng ma trận khoảng cách). Nếu tất cả các phương tiện đều di chuyển ở cùng tốc độ, thì bạn sẽ nhận được giải pháp tương tự nếu sử dụng ma trận khoảng cách hoặc ma trận thời gian, vì quãng đường đi được là bội số không đổi của thời gian di chuyển. -
time_windows: Một mảng khoảng thời gian của các địa điểm, mà bạn có thể coi là thời gian mà bạn yêu cầu ghé thăm. Các phương tiện phải ghé thăm một địa điểm trong khung thời gian của địa điểm đó. -
num_vehicles: Số lượng xe trong đội phương tiện. -
depot: Chỉ mục của kho hàng.
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
{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;
}
Dữ liệu bao gồm:
-
timeMatrix: Mảng thời gian di chuyển giữa các vị trí. Lưu ý rằng trường hợp này khác với các ví dụ trước (sử dụng ma trận khoảng cách). Nếu tất cả các phương tiện đều di chuyển ở cùng tốc độ, thì bạn sẽ nhận được giải pháp tương tự nếu sử dụng ma trận khoảng cách hoặc ma trận thời gian, vì quãng đường đi được là bội số không đổi của thời gian di chuyển. -
timeWindows: Một mảng khoảng thời gian của các địa điểm, mà bạn có thể coi là thời gian mà bạn yêu cầu ghé thăm. Các phương tiện phải ghé thăm một địa điểm trong khung thời gian của địa điểm đó. -
vehicleNumber: Số lượng xe trong đội phương tiện. -
depot: Chỉ mục của kho hàng.
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
{ 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;
};
Dữ liệu bao gồm:
-
TimeMatrix: Mảng thời gian di chuyển giữa các vị trí. Lưu ý rằng trường hợp này khác với các ví dụ trước (sử dụng ma trận khoảng cách). Nếu tất cả các phương tiện đều di chuyển ở cùng tốc độ, thì bạn sẽ nhận được giải pháp tương tự nếu sử dụng ma trận khoảng cách hoặc ma trận thời gian, vì quãng đường đi được là bội số không đổi của thời gian di chuyển. -
TimeWindows: Một mảng khoảng thời gian của các địa điểm, mà bạn có thể coi là thời gian mà bạn yêu cầu ghé thăm. Các phương tiện phải ghé thăm một địa điểm trong khung thời gian của địa điểm đó. -
VehicleNumber: Số lượng xe trong đội phương tiện. -
Depot: Chỉ mục của kho hàng.
Lệnh gọi lại thời gian
Hàm sau đây tạo lệnh gọi lại thời gian và truyền nó đến trình giải. Thuộc tính này cũng đặt chi phí vòng cung (xác định chi phí đi lại) là thời gian di chuyển giữa các vị trí.
Python
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);
Java
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);
C#
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);
Thêm các điều kiện ràng buộc về khoảng thời gian
Đoạn mã sau đây thêm các giới hạn về khoảng thời gian cho tất cả vị trí.
Python
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)));
}
Java
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)));
}
C#
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)));
}
Mã này sẽ tạo một phương diện cho thời gian di chuyển của xe, tương tự như các phương diện cho quãng đường đi lại hoặc nhu cầu trong các ví dụ trước. Phương diện theo dõi số lượng tích luỹ trên tuyến đường của xe. Trong mã trên, time_dimension.CumulVar(index) là thời gian di chuyển tích luỹ khi xe đến địa điểm bằng index đã cho.
Kích thước này được tạo bằng phương thức AddDimension, có các đối số sau:
- Chỉ mục cho lệnh gọi lại thời gian di chuyển:
transit_callback_index - Giới hạn trên cho độ trễ (thời gian chờ tại các vị trí):
30. Mặc dù giá trị này đã được đặt thành 0 trong ví dụ về CVRP, nhưng VRPTW phải cho phép thời gian chờ tích cực do có các giới hạn về khoảng thời gian. - Giới hạn trên cho tổng thời gian trên tuyến đường của mỗi xe:
30 - Biến boolean chỉ định xem biến tích luỹ có được đặt về 0 khi bắt đầu tuyến đường của mỗi xe hay không.
- Tên của phương diện.
Tiếp theo, các dòng
Python
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);
}
Java
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]);
}
C#
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]);
}
yêu cầu xe phải ghé qua một địa điểm trong khoảng thời gian của địa điểm đó.
Thiết lập thông số tìm kiếm
Đoạn mã sau đây đặt các tham số tìm kiếm mặc định và phương thức phỏng đoán để tìm giải pháp đầu tiên:
Python
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);
Java
RoutingSearchParameters searchParameters =
main.defaultRoutingSearchParameters()
.toBuilder()
.setFirstSolutionStrategy(FirstSolutionStrategy.Value.PATH_CHEAPEST_ARC)
.build();
C#
RoutingSearchParameters searchParameters =
operations_research_constraint_solver.DefaultRoutingSearchParameters();
searchParameters.FirstSolutionStrategy = FirstSolutionStrategy.Types.Value.PathCheapestArc;
Thêm máy in giải pháp
Hàm hiển thị lời giải được cho thấy dưới đây.
Python
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";
}
Java
/// @brief Print the solution.
static void printSolution(
DataModel data, RoutingModel routing, RoutingIndexManager manager, Assignment solution) {
// Solution cost.
logger.info("Objective : " + solution.objectiveValue());
// Inspect solution.
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");
}
C#
/// <summary>
/// Print the solution.
/// </summary>
static void PrintSolution(in DataModel data, in RoutingModel routing, in RoutingIndexManager manager,
in Assignment solution)
{
Console.WriteLine($"Objective {solution.ObjectiveValue()}:");
// Inspect solution.
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);
}
Giải pháp này hiển thị các tuyến đường của xe và cửa sổ giải pháp tại mỗi vị trí, như giải thích trong phần tiếp theo.
Thời lượng giải pháp
Khoảng thời gian giải pháp tại một vị trí là khoảng thời gian mà xe phải đến để duy trì đúng tiến độ.Cửa sổ giải pháp này nằm trong và thường nhỏ hơn khoảng thời gian giới hạn tại vị trí đó.
Trong hàm in giải pháp ở trên, cửa sổ giải pháp sẽ được (assignment.Min(time_var), assignment.Max(time_var) trả về, trong đó time_var = time_dimension.CumulVar(index) là thời gian di chuyển tích luỹ của xe tại vị trí đó.
Nếu giá trị tối thiểu và tối đa của time_var là như nhau, thì khoảng thời gian giải pháp sẽ là một thời điểm duy nhất, có nghĩa là xe phải khởi hành từ vị trí đó ngay khi đến. Mặt khác, nếu mức tối thiểu nhỏ hơn mức tối đa, xe có thể đợi trước khi khởi hành.
Phần Chạy chương trình mô tả các cửa sổ giải pháp cho ví dụ này.
Giải
Hàm chính trong ví dụ này tương tự như hàm trong ví dụ về TSP.
Python
solution = routing.SolveWithParameters(search_parameters)
C++
const Assignment* solution = routing.SolveWithParameters(searchParameters);
Java
Assignment solution = routing.solveWithParameters(searchParameters);
C#
Assignment solution = routing.SolveWithParameters(searchParameters);
Chạy chương trình
Khi chạy chương trình, bạn sẽ thấy kết quả sau:
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
Đối với mỗi vị trí trên một tuyến đường, Time(a,b) là khoảng thời gian giải pháp: phương tiện ghé qua vị trí đó phải thực hiện việc này trong khoảng thời gian đó để luôn đúng tiến độ.
Ví dụ: hãy xem phần sau đây của tuyến đường cho xe 0.
0 Time(0,0) -> 9 Time(2,3) -> 14 Time(7,8)
Tại vị trí 9, cửa sổ giải pháp là Time(2,3), có nghĩa là xe phải đến đó trong khoảng thời gian từ 2 đến 3. Lưu ý rằng cửa sổ giải pháp nằm trong cửa sổ thời gian ràng buộc tại vị trí đó, (0, 3), đã cho trong dữ liệu sự cố. Cửa sổ giải pháp bắt đầu tại thời điểm 2 vì phải mất 2 đơn vị thời gian (mục nhập 0, 9 của ma trận thời gian) để đi từ kho hàng đến vị trí 9.
Tại sao xe có thể khởi hành vị trí số 9 bất cứ lúc nào trong khoảng thời gian từ ngày 2 đến ngày 3? Lý do là vì thời gian di chuyển từ vị trí 9 đến vị trí 14 là 3, nên nếu xe khởi hành bất cứ lúc nào trước 3, thì xe sẽ đến vị trí 14 trước thời điểm 6, tức là quá sớm để ghé qua. Vì vậy, xe phải đợi ở nơi nào đó, chẳng hạn như người lái xe có thể quyết định đợi tại vị trí 9 cho đến lần 3 mà không bị trì hoãn việc hoàn thành tuyến đường.
Bạn có thể nhận thấy rằng một số khoảng thời gian giải pháp (ví dụ: tại vị trí 9 và 14) có thời gian bắt đầu và kết thúc khác nhau, nhưng một số khác (ví dụ: trên các tuyến 2 và 3) có cùng thời gian bắt đầu và kết thúc. Trong trường hợp trước, phương tiện có thể đợi đến cuối cửa sổ trước khi khởi hành, còn ở trường hợp sau, xe phải khởi hành ngay khi đến nơi.
Lưu cửa sổ giải pháp vào một danh sách hoặc mảng
Phần TSP cho biết cách lưu các tuyến trong giải pháp cho một danh sách hoặc mảng. Đối với VRPTW, bạn cũng có thể lưu thời lượng giải pháp. Các hàm dưới đây lưu cửa sổ giải pháp vào một danh sách (Python) hoặc một mảng (C++).
Python
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;
}
Các hàm lưu giá trị tối thiểu và tối đa của dữ liệu tích luỹ cho mọi phương diện (không chỉ thời gian).
Trong ví dụ hiện tại, các giá trị này là giới hạn dưới và giới hạn trên của cửa sổ giải pháp và kích thước được truyền đến hàm là time_dimension.
Các hàm sau đây in giải pháp từ các tuyến và dữ liệu tích luỹ.
Python
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();
}
Hoàn thành chương trình
Dưới đây là toàn bộ các chương trình giải quyết vấn đề định tuyến xe với các khung thời gian.
Python
"""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;
}
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.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]
C#
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);
}
}