ortools系列:容量約束VRP問題
容量約束的車輛路徑問題是一個對車輛能力有附加約束的車輛路徑問題。在CVRP中,每個位置都有一個需求,例如重量或體積,對應於在那裡取走或交付的項目。每次一輛車訪問一個地點,它所承載的總數量會根據該地點的需求增加(取貨)或減少(送貨)。此外,每輛車在任何時候都有最大的承載能力。
CVRP可以用一個圖來表示,該圖具有分配給邊緣的距離和分配給節點的需求。
如下圖所示,在每個位置都有一個與要取的物品相對應的需求。此外,每輛車的最大容量為15。這個問題和VRP中是差不多的,只不過增加了車輛容量約束限制條件而已。
既然如此,那麼代碼差不多是一樣的,只不過需要額外處理車輛容量問題。
# 導入模塊 from ortools.constraint_solver import pywrapcp from ortools.constraint_solver import routing_enums_pb2
# 創建數據集 def create_data_model(): data = {} # Array of distances between locations. _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, 4, 2, 4, 8, 8, 1, 2, 1, 2, 4, 4, 8, 8] # 有4輛車,每輛車的最大裝載容量 capacities = [15, 15, 15, 15] # 各個節點之間的距離矩陣 data["distances"] = _distances # 節點數量 data["num_locations"] = len(_distances) # 車輛數量 data["num_vehicles"] = 4 # 倉庫索引,我們假設所有的車輛都從同一地點出發,也就是車場。 # 或者,你可以允許車輛在任何位置啟動和結束。 data["depot"] = 0 data["demands"] = demands data["vehicle_capacities"] = capacities return data
# 回調函數,用於計算兩個節點間的距離 # 和前面的VRP問題一樣的理解 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_demand_callback(data): """Creates callback to get demands at each location."""
def demand_callback(from_node, to_node): return data["demands"][from_node]
return demand_callback
# 容量約束限制 def add_capacity_constraints(routing, data, demand_callback): """Adds capacity constraint""" capacity = "Capacity" routing.AddDimensionWithVehicleCapacity( demand_callback, 0, # null capacity slack data["vehicle_capacities"], # vehicle maximum capacities True, # 從累積到零,意思應該和「裝了這麼多剩餘空間還能裝多少」差不多吧 capacity)
# 列印每輛車的路線(訪問的位置),以及路線的距離。 # 請注意,這些距離包括從倉庫到路線中第一個位置的距離以及從最後一個位置返回到倉庫的距離。 # IndexToNode, NextVar 函數和前面的tsp問題是相同的意思 def print_solution(data, routing, assignment): """Print routes on console.""" total_dist = 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 route_load = 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) route_load += data["demands"][node_index] plan_output += {0} Load({1}) -> .format(node_index, route_load) index = assignment.Value(routing.NextVar(index))
node_index = routing.IndexToNode(index) total_dist += route_dist plan_output += {0} Load({1}) .format(node_index, route_load) plan_output += Distance of the route: {0}m .format(route_dist) plan_output += Load of the route: {0} .format(route_load) print(plan_output) print(Total Distance of all routes: {0}m.format(total_dist))
# 主函數 def main():
# 創建數據集 data = create_data_model()
# 初始化路由模型 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 Capacity constraint # 添加容量約束條件 demand_callback = create_demand_callback(data) add_capacity_constraints(routing, data, demand_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: print_solution(data, routing, assignment)
if __name__ == __main__: main()
# 結果 Route for vehicle 0: 0 Load(0) -> 1 Load(1) -> 4 Load(5) -> 3 Load(7) -> 15 Load(15) -> 0 Load(15) Distance of the route: 2192m Load of the route: 15
Route for vehicle 1: 0 Load(0) -> 14 Load(4) -> 16 Load(12) -> 10 Load(14) -> 2 Load(15) -> 0 Load(15) Distance of the route: 2192m Load of the route: 15
Route for vehicle 2: 0 Load(0) -> 7 Load(8) -> 13 Load(12) -> 12 Load(14) -> 11 Load(15) -> 0 Load(15) Distance of the route: 1324m Load of the route: 15
Route for vehicle 3: 0 Load(0) -> 9 Load(1) -> 8 Load(9) -> 6 Load(13) -> 5 Load(15) -> 0 Load(15) Distance of the route: 1164m Load of the route: 15
Total Distance of all routes: 6872m
在這個例子中,所有車輛容量都是相同的,因此可以使用routing.AddDimensionWithVehicleCapacity方法,該方法為所有車輛數量取一個上界。但是該方法也可以處理不同車輛具有不同容量,這種情況更加普遍。
routing.AddDimensionWithVehicleCapacity
大家看完記得關注點贊.
master蘇.
推薦閱讀: