ปัญหาการกำหนดเส้นทางรถหลายอย่างเกี่ยวข้องกับการนัดเวลาเข้าพบลูกค้าที่ให้บริการเฉพาะช่วงเวลาที่ต้องการเท่านั้น
ปัญหาเหล่านี้เรียกว่าปัญหาการกำหนดเส้นทางยานพาหนะที่มีกรอบเวลา (VRPTW)
ตัวอย่าง VRPTW
ในหน้านี้ เราจะแนะนำตัวอย่างที่แสดงให้เห็นวิธีแก้ไข VRPTW เนื่องจากปัญหาเกี่ยวข้องกับกรอบเวลา ข้อมูลจึงประกอบด้วยเมทริกซ์เวลา ซึ่งมีเวลาที่ใช้ในการเดินทางระหว่างสถานที่ (แทนที่จะเป็นเมทริกซ์ระยะทางเหมือนในตัวอย่างก่อนหน้า)
แผนภาพด้านล่างแสดงสถานที่ท่องเที่ยวเป็นสีน้ำเงินและสถานีรถไฟสีดำ กรอบเวลาจะแสดงอยู่เหนือสถานที่แต่ละแห่ง ดูพิกัดของตำแหน่งในส่วน VRP สำหรับรายละเอียดเพิ่มเติมเกี่ยวกับการระบุตำแหน่ง
โดยมีเป้าหมายเพื่อย่นระยะเวลาการเดินทางรวมของยานพาหนะ
การแก้ตัวอย่าง VRPTW ด้วยเครื่องมือ OR-
ส่วนต่อไปนี้อธิบายวิธีแก้ตัวอย่าง VRPTW ด้วย OR-เครื่องมือ
สร้างข้อมูล
ฟังก์ชันต่อไปนี้จะสร้างข้อมูลสำหรับปัญหา
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
โดยประกอบด้วยข้อมูลต่อไปนี้
-
data['time_matrix']: อาร์เรย์ของเวลาในการเดินทางระหว่างสถานที่ โปรดทราบว่าจำนวนนี้จะแตกต่างจากตัวอย่างก่อนหน้านี้ซึ่งใช้เมทริกซ์ระยะทาง หากยานพาหนะทุกคันวิ่งด้วยความเร็วเท่ากัน คุณจะได้คำตอบเดียวกันเมื่อใช้เมทริกซ์ระยะทางหรือเมทริกซ์เวลา เนื่องจากระยะการเดินทางเป็นค่าคงที่ของเวลาที่ใช้ในการเดินทาง -
data['time_windows']: อาร์เรย์ของกรอบเวลาสำหรับสถานที่ ซึ่งอาจหมายถึงเวลาที่ขอเข้าชม ยานพาหนะต้องไปที่สถานที่ภายในกรอบเวลาที่กำหนด -
data['num_vehicles']: จำนวนยานพาหนะในกลุ่ม -
data['depot']: ดัชนีของ 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: ดัชนีของ Depot
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;
}
โดยประกอบด้วยข้อมูลต่อไปนี้
-
timeMatrix: อาร์เรย์ของเวลาในการเดินทางระหว่างสถานที่ โปรดทราบว่าจำนวนนี้จะแตกต่างจากตัวอย่างก่อนหน้านี้ซึ่งใช้เมทริกซ์ระยะทาง หากยานพาหนะทุกคันวิ่งด้วยความเร็วเท่ากัน คุณจะได้คำตอบเดียวกันเมื่อใช้เมทริกซ์ระยะทางหรือเมทริกซ์เวลา เนื่องจากระยะการเดินทางเป็นค่าคงที่ของเวลาที่ใช้ในการเดินทาง -
timeWindows: อาร์เรย์ของกรอบเวลาสำหรับสถานที่ ซึ่งอาจหมายถึงเวลาที่ขอเข้าชม ยานพาหนะต้องไปที่สถานที่ภายในกรอบเวลาที่กำหนด -
vehicleNumber: จำนวนยานพาหนะในกลุ่ม -
depot: ดัชนีของ Depot
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;
};
โดยประกอบด้วยข้อมูลต่อไปนี้
-
TimeMatrix: อาร์เรย์ของเวลาในการเดินทางระหว่างสถานที่ โปรดทราบว่าจำนวนนี้จะแตกต่างจากตัวอย่างก่อนหน้านี้ซึ่งใช้เมทริกซ์ระยะทาง หากยานพาหนะทุกคันวิ่งด้วยความเร็วเท่ากัน คุณจะได้คำตอบเดียวกันเมื่อใช้เมทริกซ์ระยะทางหรือเมทริกซ์เวลา เนื่องจากระยะการเดินทางเป็นค่าคงที่ของเวลาที่ใช้ในการเดินทาง -
TimeWindows: อาร์เรย์ของกรอบเวลาสำหรับสถานที่ ซึ่งอาจหมายถึงเวลาที่ขอเข้าชม ยานพาหนะต้องไปที่สถานที่ภายในกรอบเวลาที่กำหนด -
VehicleNumber: จำนวนยานพาหนะในกลุ่ม -
Depot: ดัชนีของ Depot
การติดต่อกลับตามเวลา
ฟังก์ชันต่อไปนี้จะสร้างโค้ดเรียกกลับและส่งผ่านไปยังเครื่องมือแก้โจทย์ นอกจากนี้ยังกำหนดค่าใช้จ่ายของเส้นโค้ง (Arc) ซึ่งกำหนดค่าใช้จ่ายในการเดินทางเป็นเวลาที่ใช้ในการเดินทางระหว่างสถานที่ต่างๆ
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);
เพิ่มข้อจํากัดของกรอบเวลา
โค้ดต่อไปนี้จะเพิ่มข้อจํากัดของกรอบเวลาสําหรับสถานที่ทั้งหมด
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)));
}
โค้ดจะสร้างมิติข้อมูลสำหรับเวลาเดินทางของยานพาหนะ ซึ่งคล้ายกับมิติข้อมูลสำหรับระยะทางในการเดินทางหรือความต้องการในตัวอย่างก่อนหน้านี้ มิติข้อมูลจะติดตามปริมาณที่สะสมในเส้นทางของยานพาหนะ ในรหัสด้านบน time_dimension.CumulVar(index) คือระยะเวลาเดินทางสะสมเมื่อยานพาหนะมาถึงสถานที่โดยมี index ที่ระบุ
ระบบจะสร้างมิติข้อมูลโดยใช้เมธอด AddDimension ซึ่งมีอาร์กิวเมนต์ต่อไปนี้
- ดัชนีสำหรับการติดต่อกลับเวลาเดินทาง:
transit_callback_index - ขอบเขตบนของ Slack (เวลารอที่สถานที่):
30แม้ว่าในตัวอย่าง CVRP จะกำหนดค่านี้เป็น 0 แต่ VRPTW จะต้องรอเป็น 0 เนื่องจากข้อจำกัดด้านกรอบเวลา - ขีดจำกัดบนของเวลารวมในเส้นทางของยานพาหนะแต่ละคัน:
30 - ตัวแปรบูลีนที่ระบุว่ามีการตั้งค่าตัวแปรสะสมเป็น 0 ที่จุดเริ่มต้นของเส้นทางของยานพาหนะแต่ละคันหรือไม่
- ชื่อของมิติข้อมูล
ต่อไปคือเส้น
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]);
}
กำหนดให้รถต้องไปยังสถานที่ในช่วงกรอบเวลาของสถานที่
ตั้งค่าพารามิเตอร์การค้นหา
โค้ดต่อไปนี้จะกำหนดพารามิเตอร์การค้นหาเริ่มต้นและวิธีการแบบฮิวริสติกสำหรับการค้นหาโซลูชันแรก
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;
เพิ่มเครื่องพิมพ์โซลูชัน
ฟังก์ชันที่แสดงเฉลยจะปรากฏด้านล่าง
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);
}
โซลูชันจะแสดงเส้นทางของยานพาหนะและหน้าต่างโซลูชันในแต่ละสถานที่ตามที่อธิบายไว้ในส่วนถัดไป
หน้าต่างโซลูชัน
กรอบเวลาโซลูชันในสถานที่หนึ่งๆ คือช่วงเวลาที่ยานพาหนะต้องเดินทางมาถึงเพื่อให้เป็นไปตามกำหนด กรอบเวลาการแก้ปัญหาจะรวมอยู่ในสถานที่นั้นๆ และมักจะน้อยกว่ากรอบเวลาที่จํากัดในสถานที่นั้น
ในฟังก์ชันโซลูชันเครื่องพิมพ์ด้านบน หน้าต่างโซลูชันจะแสดงผลโดย (assignment.Min(time_var), assignment.Max(time_var) โดยที่ time_var = time_dimension.CumulVar(index) คือเวลาที่ใช้ในการเดินทางสะสมของยานพาหนะ ณ ตำแหน่งนั้น
หากค่าต่ำสุดและสูงสุดของ time_var เท่ากัน หน้าต่างคำตอบจะเป็นช่วงเวลาเดียว ซึ่งหมายความว่ารถต้องออกจากตำแหน่งทันทีที่มาถึง ในทางกลับกัน หากต่ำสุดน้อยกว่าค่าสูงสุด รถสามารถรอก่อนออกเดินทาง
หัวข้อการเรียกใช้โปรแกรมจะอธิบายถึงหน้าต่างโซลูชันสำหรับตัวอย่างนี้
แก้โจทย์
ฟังก์ชันหลักของตัวอย่างนี้คล้ายกับฟังก์ชันในตัวอย่าง 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);
การใช้งานโปรแกรม
เมื่อเรียกใช้โปรแกรม โปรแกรมจะแสดงเอาต์พุตต่อไปนี้
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, 3) ที่ให้ไว้ในข้อมูลปัญหา กรอบเวลาของโซลูชันจะเริ่มต้นที่เวลา 2 เพราะต้องใช้เวลา 2 หน่วย (รายการ 0, 9 ของเมทริกซ์เวลา) ในการเดินทางจาก Depot ไปยังตำแหน่งที่ 9
ทำไมรถถึงออกจากตำแหน่ง 9 ได้ทุกเมื่อระหว่างตี 2 ถึง 3 เนื่องจากระยะเวลาเดินทางจากตำแหน่ง 9 ไปยังตำแหน่ง 14 คือ 3 หากรถออกเมื่อใดก็ได้ก่อนวันที่ 3 ก็จะไปถึงสถานที่ 14 ก่อนเวลา 6 ซึ่งเป็นเวลาเร็วเกินไป ดังนั้นรถจะต้องรอที่ใดที่หนึ่ง เช่น คนขับอาจตัดสินใจรอที่ตำแหน่ง 9 จนถึงเวลา 3 โดยไม่ทำให้เส้นทางล่าช้า
คุณอาจสังเกตเห็นว่าหน้าต่างโซลูชันบางบาน (เช่น ตำแหน่งที่ 9 และ 14) มีเวลาเริ่มต้นและเวลาสิ้นสุดแตกต่างกัน แต่บางช่วง (เช่น บนเส้นทางที่ 2 และ 3) มีเวลาเริ่มต้นและเวลาสิ้นสุดเหมือนกัน ในกรณีเดิม รถยนต์สามารถรอจนกระทั่งถึงช่วงท้ายหน้าต่างก่อนออกเดินทาง และในกรณีหลังรถต้องออกเดินทางทันทีที่มาถึง
บันทึกหน้าต่างโซลูชันลงในรายการหรืออาร์เรย์
ส่วน TSP จะแสดงวิธีบันทึกเส้นทางในคำตอบไปยังรายการหรืออาร์เรย์ สำหรับ VRPTW คุณจะบันทึกกรอบเวลาโซลูชันได้ด้วย ฟังก์ชันด้านล่างนี้จะบันทึกหน้าต่างโซลูชันไปยังรายการ (Python) หรืออาร์เรย์ (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;
}
ฟังก์ชันนี้จะบันทึกค่าต่ำสุดและสูงสุดของข้อมูลสะสมสำหรับมิติข้อมูลต่างๆ (ไม่ใช่แค่เวลา)
ในตัวอย่างปัจจุบัน ค่าเหล่านี้คือขอบเขตล่างและบนของหน้าต่างโซลูชัน และมิติข้อมูลที่ส่งไปยังฟังก์ชันคือ time_dimension
ฟังก์ชันต่อไปนี้จะพิมพ์คำตอบจากเส้นทางและข้อมูลสะสม
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();
}
เข้าร่วมโปรแกรม
โปรแกรมทั้งหมดสำหรับปัญหาการกำหนดเส้นทางรถโดยมีกรอบเวลาแสดงมีดังนี้
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);
}
}