目標是最小化在時間窗口內為所有客戶提供所需的服務時間和等待時間之和。

前面我們講了普通VRP和CVRP問題，這裡的VRPTW問題相信你也明白，只需要添加時間窗口約束介面。

from ortools.constraint_solver import pywrapcp
from ortools.constraint_solver import routing_enums_pb2

# 創建數據集
def create_data_model():
data = {}
# 不同客戶節點之間的距離
_distances =
[
[0, 548, 776, 696, 582, 274, 502, 194, 308, 194, 536, 502, 388, 354, 468, 776, 662],
[548, 0, 684, 308, 194, 502, 730, 354, 696, 742, 1084, 594, 480, 674, 1016, 868, 1210],
[776, 684, 0, 992, 878, 502, 274, 810, 468, 742, 400, 1278, 1164, 1130, 788, 1552, 754],
[696, 308, 992, 0, 114, 650, 878, 502, 844, 890, 1232, 514, 628, 822, 1164, 560, 1358],
[582, 194, 878, 114, 0, 536, 764, 388, 730, 776, 1118, 400, 514, 708, 1050, 674, 1244],
[274, 502, 502, 650, 536, 0, 228, 308, 194, 240, 582, 776, 662, 628, 514, 1050, 708],
[502, 730, 274, 878, 764, 228, 0, 536, 194, 468, 354, 1004, 890, 856, 514, 1278, 480],
[194, 354, 810, 502, 388, 308, 536, 0, 342, 388, 730, 468, 354, 320, 662, 742, 856],
[308, 696, 468, 844, 730, 194, 194, 342, 0, 274, 388, 810, 696, 662, 320, 1084, 514],
[194, 742, 742, 890, 776, 240, 468, 388, 274, 0, 342, 536, 422, 388, 274, 810, 468],
[536, 1084, 400, 1232, 1118, 582, 354, 730, 388, 342, 0, 878, 764, 730, 388, 1152, 354],
[502, 594, 1278, 514, 400, 776, 1004, 468, 810, 536, 878, 0, 114, 308, 650, 274, 844],
[388, 480, 1164, 628, 514, 662, 890, 354, 696, 422, 764, 114, 0, 194, 536, 388, 730],
[354, 674, 1130, 822, 708, 628, 856, 320, 662, 388, 730, 308, 194, 0, 342, 422, 536],
[468, 1016, 788, 1164, 1050, 514, 514, 662, 320, 274, 388, 650, 536, 342, 0, 764, 194],
[776, 868, 1552, 560, 674, 1050, 1278, 742, 1084, 810, 1152, 274, 388, 422, 764, 0, 798],
[662, 1210, 754, 1358, 1244, 708, 480, 856, 514, 468, 354, 844, 730, 536, 194, 798, 0]
]

# 每個客戶的需求量，0 表示改節點是倉庫，倉庫是沒有需求
demands = [0, 1, 1, 2, 1, 2, 4, 8, 8, 1, 2, 1, 2, 4, 4, 8, 8]

# 每個節點的時間窗口約束
time_windows =
[(0, 0),
(75, 85),
(75, 85),
(60, 70),
(45, 55),
(0, 8),
(50, 60),
(0, 10),
(10, 20),
(0, 10),
(75, 85),
(85, 95),
(5, 15),
(15, 25),
(10, 20),
(45, 55),
(30, 40)]

# 距離矩陣
data["distances"] = _distances
# 網路節點數量
data["num_locations"] = len(_distances)
# 車輛數量
data["num_vehicles"] = 4
# 倉庫索引，我們假設所有的車輛都從同一地點出發，也就是車場。
# 或者，你可以允許車輛在任何位置啟動和結束。
data["depot"] = 0
# 需求
data["demands"] = demands
# 時間窗
data["time_windows"] = time_windows
# 假設每個客戶的服務時間的5分鐘
data["time_per_demand_unit"] = 5
# 車輛平均行駛速度
data["vehicle_speed"] = 83.33
return data

#######################
# Problem Constraints #
#######################
def create_distance_callback(data):
"""Creates callback to return distance between points."""
distances = data["distances"]

def distance_callback(from_node, to_node):
"""Returns the manhattan distance between the two nodes"""
return distances[from_node][to_node]

return distance_callback

# 時間窗口約束的回調函數
def create_time_callback(data):
"""Creates callback to get total times between locations."""

def service_time(node):
"""Gets the service time for the specified location."""
return data["demands"][node] * data["time_per_demand_unit"]

def travel_time(from_node, to_node):
"""Gets the travel times between two locations."""
travel_time = data["distances"][from_node][to_node] / data["vehicle_speed"]
return travel_time

def time_callback(from_node, to_node):
"""Returns the total time between the two nodes"""
serv_time = service_time(from_node)
trav_time = travel_time(from_node, to_node)
return serv_time + trav_time

return time_callback

# 和容量約束的維度約束類似，這裡需要添加時間窗口的約束，也是用 routing.AddDimension 函數
def add_time_window_constraints(routing, data, time_callback):
"""Add time window constraints."""
time = "Time"
horizon = 120
routing.AddDimension(
time_callback,
horizon, # allow waiting time
horizon, # maximum time per vehicle
False, # Dont force start cumul to zero. This doesnt have any effect in this example,
# since the depot has a start window of (0, 0).
time)

time_dimension = routing.GetDimensionOrDie(time)
for location_node, location_time_window in enumerate(data["time_windows"]):
index = routing.NodeToIndex(location_node)
time_dimension.CumulVar(index).SetRange(location_time_window[0], location_time_window[1])

# 列印結果
def print_solution(data, routing, assignment):
"""Prints assignment on console"""
# Inspect solution.
time_dimension = routing.GetDimensionOrDie(Time)
total_dist = 0
time_matrix = 0

for vehicle_id in range(data["num_vehicles"]):
index = routing.Start(vehicle_id)
plan_output = Route for vehicle {0}:
.format(vehicle_id)
route_dist = 0
while not routing.IsEnd(index):
node_index = routing.IndexToNode(index)
next_node_index = routing.IndexToNode(
assignment.Value(routing.NextVar(index)))
route_dist += routing.GetArcCostForVehicle(node_index, next_node_index, vehicle_id)
time_var = time_dimension.CumulVar(index)
time_min = assignment.Min(time_var)
time_max = assignment.Max(time_var)
plan_output += {0} Time({1},{2}) ->.format(node_index, time_min, time_max)
index = assignment.Value(routing.NextVar(index))

node_index = routing.IndexToNode(index)
time_var = time_dimension.CumulVar(index)
route_time = assignment.Value(time_var)
time_min = assignment.Min(time_var)
time_max = assignment.Max(time_var)
total_dist += route_dist
time_matrix += route_time
plan_output += {0} Time({1},{2})
.format(node_index, time_min, time_max)
plan_output += Distance of the route: {0} m
.format(route_dist)
plan_output += Time of the route: {0} min
.format(route_time)
print(plan_output)
print(Total Distance of all routes: {0} m.format(total_dist))
print(Total Time of all routes: {0} min.format(time_matrix))

# 主函數
def main():

# 創建數據集
data = create_data_model()

# 創建VRP路由模型
routing = pywrapcp.RoutingModel(data["num_locations"], data["num_vehicles"], data["depot"])

# Define weight of each edge
# 提供距離回調，以便解決程序可以計算位置之間的距離。
distance_callback = create_distance_callback(data)
routing.SetArcCostEvaluatorOfAllVehicles(distance_callback)

# Add Time Window constraint
# 添加時間窗口約束
time_callback = create_time_callback(data)
add_time_window_constraints(routing, data, time_callback)

# Setting first solution heuristic (cheapest addition).
# 必須指定啟發式方法來找到第一個解決方案
search_parameters = pywrapcp.RoutingModel.DefaultSearchParameters()
search_parameters.first_solution_strategy = (
routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)

# Solve the problem.
# 求解問題
assignment = routing.SolveWithParameters(search_parameters)
if assignment:
printer = print_solution(data, routing, assignment)

if __name__ == __main__:
main()

# 結果
Route for vehicle 0:
0 Time(0,0) -> 12 Time(5,13) -> 13 Time(17,25) -> 15 Time(45,52) -> 11 Time(88,95) -> 0 Time(99,120)
Distance of the route: 1780 m
Time of the route: 99 min

Route for vehicle 1:
0 Time(0,3) -> 5 Time(3,6) -> 8 Time(15,18) -> 6 Time(57,60) -> 2 Time(80,85) -> 0 Time(94,120)
Distance of the route: 1712 m
Time of the route: 94 min

Route for vehicle 2:
0 Time(0,8) -> 7 Time(2,10) -> 4 Time(46,55) -> 3 Time(60,70) -> 1 Time(75,85) -> 0 Time(86,120)
Distance of the route: 1552 m
Time of the route: 86 min

Route for vehicle 3:
0 Time(0,8) -> 9 Time(2,10) -> 14 Time(10,18) -> 16 Time(32,40) -> 10 Time(76,85) -> 0 Time(92,120)
Distance of the route: 1552 m
Time of the route: 92 min

Total Distance of all routes: 6596 m
Total Time of all routes: 371 min

注意add_time_window_constraints函數中的routing.AddDimension調用，在容量約束問題中我們調用了routing.AddDimensionWithVehicleCapacity，相應的，在時間約束問題中，也要在相應的維度上做約束。

為了創建時間維度，我們需要計算如下:

• 服務時間：在每個地點交付或提供服務所需的時間，這裡我們假設服務時間與該位置的需求成正比。
• 地點之間行駛時間：我們假設所有的車輛以相同的速度行駛，所以行駛時間就是地點之間的距離除以速度。
• 地點間總時間：即起始位置的服務時間加上到下一個位置的旅行時間。

這三個時間分別對應時間回調函數中的：service_time(node),travel_time(from_node, to_node),time_callback(from_node, to_node).

然後我們看如何添加時間窗口的維度約束。和容量約束的維度約束類似，這裡需要添加時間窗口的約束，也是用 routing.AddDimension 函數，看下面的代碼片段：

routing.AddDimension(
time_callback,
horizon, # allow waiting time
horizon, # maximum time per vehicle
False, # Dont force start cumul to zero. This doesnt have any effect in this example,
# since the depot has a start window of (0, 0).
time)

AddDimension方法的參數如下：

• time_evaluator ：返回服務時間加上到下一個位置的旅行時間。
• horizon ：每輛車行駛路線累計時間的上限，這將為所有位置設置一個全局時間窗口[0,horizon]，要在每個位置設置單獨的時間窗口，需要在時間的累積變數上設置範圍。
• 第四個參數和CVRP問題一個意思，由於該值為False，所以在每輛車的路線開始時，時間的累積變數沒有設置為零。
• time ：維度的名稱，可用於訪問其中存儲的數據或變數。

2. 參考

• allow-vehicles-to-start-and-end-any-location
• google_ortools_guide

大家看完記得關注點贊.

master蘇.

推薦閱讀：