ortools系列：VRP中的一些常見問題
ortools系列：VRP中的一些常見問題
1. 搜索限制
對於節點很多的車輛路徑問題需要很長時間才能解決。對於此類問題，最好設置搜索限制，即在指定的時間長度或返回的結果數量之後終止搜索。當解決程序達到極限時，可以將最新的解決方案保存到文件中。如果以後您想找到更好的解決方案，可以使用保存的結果作為初始點重新啟動搜索。
要設置搜索的時間限制，請在調用解決程序之前添加以下搜索參數：
search_parameters.time_limit_ms = 30000
這將在30000毫秒(或30秒)後停止搜索。有關有時間限制的完整示例，請參見Changing-the-search-strategy。
要設置返回的解決方案數量的限制，請添加以下內容：
search_parameters.solution_limit = 100
2. 將結果存儲在數組中
有時可能會發現將VRP的結果存儲在數組中非常方便。例如，可能希望使用不同的參數執行多個搜索，然後比較保存的結果。
def get_routes_array(assignment, num_vehicles, routing):
# Get the routes for an assignent and return as a list of lists.
routes = []
for route_nbr in range(num_vehicles):
node = routing.Start(route_nbr)
route = []
while not routing.IsEnd(node):
index = routing.NodeToIndex(node)
route.append(index)
node = assignment.Value(routing.NextVar(node))
routes.append(route)
return routes
當然，你也可以將此函數添加到VRP的Python程序中，並按如下方式調用它:
assignment = routing.SolveWithParameters(search_parameters)
routes = get_routes_array(assignment, num_routes, routing)
將搜索結果存儲在數組中的另一個原因是，可以將數組保存到文件中，然後從保存的文件中恢復。
3. 設置搜索的初始路徑
要創建初始路由，請執行以下步驟：
- 建立路由模型並聲明求解器。
- 定義包含初始路由的數組。(在下面的例子中，數組是在程序中顯式定義的，但是如果之前已將解決方案保存到文件中，則可以從文件中創建數組。)
- 使用
ReadAssignmentFromRoutes方法創建初始賦值。
下面是示例代碼
initial_routes = [[8, 16, 14, 13, 12, 11], [3, 4, 9, 10], [15, 1], [7, 5, 2, 6]]
routing = pywrapcp.RoutingModel(num_locations, num_vehicles, depot)
dist_callback = create_dist_callback(dist_matrix)
add_distance_dimension(routing, dist_callback)
routing.SetArcCostEvaluatorOfAllVehicles(dist_callback)
initial_assignment = routing.ReadAssignmentFromRoutes(initial_routes, True)
4. 設置路由的開始和結束位置
到目前為止，我們假設所有的車輛都在一個地點開始和結束，即倉庫。其實還可以為問題中的每個車輛設置可能不同的開始和結束位置。為此，將包含起始位置和結束位置索引的兩個向量作為輸入傳遞給主函數中的RoutingModel方法。下面是一些示例代碼，用於解決四種車輛的問題:
start_locations = [8, 3, 15, 7]
end_locations = [11, 10, 1, 6]
routing = pywrapcp.RoutingModel(num_locations,
num_vehicles,
start_locations,
end_locations)
5. 允許任意開始和結束位置
在其他版本的車輛路徑問題中，車輛可以在任意位置開始和結束。以這種方式設置問題，只需修改距離回調，使從倉庫到任何其他位置的距離為0。這就把車場變成了一個虛擬的位置，它的位置對最優路線沒有影響。
locations =
[(4, 4), # depot
(2, 0), (8, 0), # row 0
(0, 1), (1, 1),
(5, 2), (7, 2),
(3, 3), (6, 3),
(5, 5), (8, 5),
(1, 6), (2, 6),
(3, 7), (6, 7),
(0, 8), (7, 8)]
num_locations = len(locations)
dist_matrix = {}
for from_node in range(num_locations):
dist_matrix[from_node] = {}
for to_node in range(num_locations):
if from_node == depot or to_node == depot:
# Define the distance from the depot to any node to be 0.
# 這裡將到距離設置為0
self.matrix[from_node][to_node] = 0
else:
dist_matrix[from_node][to_node] = (
manhattan_distance(locations[from_node], locations[to_node]))
6. 關於VRPLite
安利一個軟體：VRPLite：為交通運輸規劃服務的車輛路徑問題解決方案，有時間研究一下其原理，道理都是差不多的。
7. 參考
- google_ortools_guide
大家看完記得關注點贊.
master蘇.
推薦閱讀：