定位坐標

[(456, 320), # location 0
(228, 0), # location 1
(912, 0), # location 2
(0, 80), # location 3
(114, 80), # location 4
(570, 160), # location 5
(798, 160), # location 6
(342, 240), # location 7
(684, 240), # location 8
(570, 400), # location 9
(912, 400), # location 10
(114, 480), # location 11
(228, 480), # location 12
(342, 560), # location 13
(684, 560), # location 14
(0, 640), # location 15
(798, 640)] # location 16

在這裡我們根據上面的坐標算出不同位置之間的距離，距離函數使用曼哈頓距離:|x1 - x2| + |y1 - y2|.

好，基本問題都解釋清楚了，我們還是直接看代碼吧：

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

# 定義這個VRP問題的數據，使用字典結構存儲
def create_data_model():
"""Creates the data for the example."""
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]
]
data["distances"] = _distances
data["num_locations"] = len(_distances) # 有幾個節點
data["num_vehicles"] = 4 # 有幾輛車
data["depot"] = 0 # 倉庫索引，我們假設所有的車輛都從同一地點出發，也就是車場。
# 或者，你可以允許車輛在任何位置啟動和結束。
return data

# 計算距離的回調函數，和之前的routing問題一樣的
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 add_distance_dimension(routing, distance_callback):
"""Add Global Span constraint"""
distance = Distance
maximum_distance = 3000 # 每輛車能形式的最大距離
routing.AddDimension(
distance_callback,
0, # null slack
maximum_distance,
True, # 從累積到零，意思應該和「走了這麼久還剩多少汽油」差不多吧
distance)
distance_dimension = routing.GetDimensionOrDie(distance)
# Try to minimize the max distance among vehicles.
# 盡量減少車輛之間的最大距離。
distance_dimension.SetGlobalSpanCostCoefficient(100)

# 列印每輛車的路線(訪問的位置)，以及路線的距離。
# 請注意，這些距離包括從倉庫到路線中第一個位置的距離以及從最後一個位置返回到倉庫的距離。
# IndexToNode, NextVar 函數和前面的tsp問題是相同的意思
def print_solution(data, routing, assignment):
"""Print routes on console."""
total_distance = 0
for vehicle_id in range(data["num_vehicles"]):
index = routing.Start(vehicle_id)
plan_output = Route for vehicle {}:
.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)
plan_output += {0} ->.format(node_index)
index = assignment.Value(routing.NextVar(index))
plan_output += {}
.format(routing.IndexToNode(index))
plan_output += Distance of route: {}m
.format(route_dist)
print(plan_output)
total_distance += route_dist
print(Total distance of all routes: {}m.format(total_distance))

# 主函數
def main():
# 創建數據集
data = create_data_model()

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

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

# 添加距離維度
add_distance_dimension(routing, distance_callback)

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

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

if __name__ == __main__:
main()

# 結果
Route for vehicle 0:
0 -> 8 -> 6 -> 2 -> 5 -> 0
Distance of route: 1552m

Route for vehicle 1:
0 -> 7 -> 1 -> 4 -> 3 -> 0
Distance of route: 1552m

Route for vehicle 2:
0 -> 9 -> 10 -> 16 -> 14 -> 0
Distance of route: 1552m

Route for vehicle 3:
0 -> 12 -> 11 -> 15 -> 13 -> 0
Distance of route: 1552m

Total distance of all routes: 6208m

注意函數添加距離維度(Add a distance dimension)，

要解決這個VRP，需要創建一個距離維度，它計算每輛車沿其路線行駛的累計距離。然後，將成本設置為每條路線總距離的最大值。關於距離信息可以參考vrp_dimension_details.

若要添加距離維度，請使用求解器的AddDimension方法。下面的代碼為距離創建一個維度，並設置累計距離成本。

def add_distance_dimension(routing, distance_callback):
"""Add Global Span constraint"""
distance = Distance
maximum_distance = 3000 # 每輛車能形式的最大距離
routing.AddDimension(
distance_callback,
0, # null slack
maximum_distance,
True, # 從累積到零，意思應該和「走了這麼久還剩多少汽油」差不多吧
distance)
distance_dimension = routing.GetDimensionOrDie(distance)
# Try to minimize the max distance among vehicles.
# 盡量減少車輛之間的最大距離。
distance_dimension.SetGlobalSpanCostCoefficient(100)

下面是求解的結果：

看起來也不難呢，但是我想說的是，如果有1000個節點會怎樣？歡迎大家討論討論。

參考

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

大家看完記得關注點贊.

master蘇.

推薦閱讀：