ortools解决tsp_ortools系列：路由问题1
ortools系列：路由問題1
1. 路由問題
運籌學(xué)中最有趣的領(lǐng)域之一是路由，其目標(biāo)是找到通過復(fù)雜網(wǎng)絡(luò)傳輸物品的有效路徑。網(wǎng)絡(luò)通常用如下圖所示的圖來表示。
每個節(jié)點表示一個位置，路由是通過一組節(jié)點的路徑。大多數(shù)實際的路由問題都涉及到為車輛(汽車、火車、飛機等等)尋找有效的路徑，因此它們通常被稱為車輛路由問題。
路由問題可以分為兩種主要類型：節(jié)點路由問題和弧線路由問題，這取決于目標(biāo)是以訪問節(jié)點(位置)還是弧線(連接它們的邊)的形式表示的。我們將給出每個例子。
首先，這里有一個弧線路由問題，如果你看過谷歌地圖街景，你可能想知道谷歌是如何在全世界數(shù)百萬個地址獲得街道級別的圖像的。答案很簡單:谷歌的一個團(tuán)隊駕駛著一隊裝備有自動拍攝每個地址照片的攝像頭的車隊，持續(xù)行駛在世界各地的道路上。谷歌的問題是為每輛在指定區(qū)域內(nèi)穿越每條街道的車輛構(gòu)造最短的路線。如果你用一個圖來表示這個問題，其中弧線代表街道，而節(jié)點是街道的交叉點，那么弧線路由問題就是找出穿過圖中每個弧線的最短路徑。谷歌每天使用ortools中提供的技術(shù)來解決這個問題。
節(jié)點路由問題的一個例子是車輛路由。假設(shè)一個公司需要使用車隊將包裹運送到不同的地點。在這個問題的圖中，節(jié)點表示位置，弧線表示它們之間的路由。每條弧線都有一個重量，對應(yīng)于該路線的運行成本。問題:在圖中找到一組路徑(對應(yīng)于每輛車的送貨路線)，其中包含每個目的地，同時最小化總成本。這與弧路由問題不同，因為路徑不必遍歷每個弧，只需包含每個節(jié)點。
OR-Tools包括一個專門的路由庫來解決許多類型的節(jié)點路由問題：Traveling Salesman Problems (TSP)，旅行商問題，這個問題非常著名，也是編程中一個基本問題，在編程領(lǐng)域通常用動態(tài)規(guī)劃解決，現(xiàn)在很多用智能算法比如遺傳算法等求解。當(dāng)然如果你把它看成是一個運籌學(xué)的路由問題，就用運籌學(xué)的思路解決。
Vehicle Routing Problems (VRP), 這個問題類似收快遞或送快遞，比如說，有100個快遞需要送到100個客戶手中，但是一輛車只能送30個快遞，需要怎么安排成本最小或最快的問題。
Capacitated Vehicle Routing Problems (CVRP),有約束的VRP問題，比如每輛車都有載重限制等。
Vehicle Routing Problems with Time Windows (VRPTW), 時間限制，車輛必須在一定時間內(nèi)開始或完成任務(wù)。
Vehicle Routing Problems with Resource Constraints, 倉庫可能有車輛限制，或車輛需要補充燃料。
Vehicle Routing Problems with Pickup and Delivery (VRPPD),車輛在交付客戶前必須先取貨。
我們看到，這些都是同一類問題，但是有不同的約束條件，比如車輛載重限制，時間限制，或者倉庫限制等，針對不同的場景分別建模，效果會好得多，ortools也是這樣做的。
注意：需要說明的是，還有其他的解決方案，如Concorde，致力于解決非常大的tsp優(yōu)化，這已經(jīng)超過了ortools的能力范圍。然而，ortools提供了一個更好的平臺來解決包含純TSP之外的約束的更一般的路由問題。
2. TSP問題1
旅行商問題是計算機科學(xué)中最著名的問題之一。在下面的內(nèi)容中，我們講解如何解決TSP問題。
在推銷員挨家挨戶兜售真空吸塵器和百科全書的年代，他們不得不計劃自己的路線，從一家到另一家，從一個城市到另一個城市。路線越短越好。查找訪問一組地點的最短路徑是一個指數(shù)難度的問題:查找20個城市的最短路徑的難度是查找10個城市的兩倍多。
對所有可能的路徑進(jìn)行徹底的搜索將確保找到最短的路徑，但是對于除小的位置集之外的所有路徑，這在計算上都是棘手的。對于較大的問題，需要使用優(yōu)化技術(shù)來智能搜索解空間，找到近似最優(yōu)解。
在數(shù)學(xué)上，旅行商問題可以表示為一個圖，其中的位置是節(jié)點，而邊(或弧)表示節(jié)點之間的直接路由。每條邊的權(quán)值是節(jié)點之間的距離。目標(biāo)是找到權(quán)值之和最短的路徑。下面，我們看到一個簡單的四節(jié)點圖，以及訪問每個節(jié)點的最短周期:
OR-Tools除了為經(jīng)典的旅行商問題尋找解決方案外，還提供了針對更一般類型的tsp的方法，包括:傳統(tǒng)的TSP是對稱的:不對稱成本問題從A點到B點的距離等于從A點B點的距離不過,航運物品的成本從A點到B點的成本可能不等于把A點B點或工具也可以處理成本不對稱的問題。
Prize-collecting TSP:從訪問節(jié)點中獲益。
帶有時間窗口的TSP。
我們來看這么一個例子，在美國的13個城市，不同城市之間的距離已經(jīng)知道，現(xiàn)在需要找到一條路徑，每個城市只訪問一次，需要訪問所有城市，該怎么走，才能使這條路徑最短呢？
OK，讓我們來擼代碼：
from ortools.constraint_solver import pywrapcp
from ortools.constraint_solver import routing_enums_pb2
# 距離的回調(diào)函數(shù)，用于計算兩個節(jié)點之間的距離
# 在后面的例子中我們也會看到類似的回調(diào)函數(shù)，只是計算節(jié)點間距離方法不一樣而已
def create_distance_callback(dist_matrix):
# Create a callback to calculate distances between cities.
def distance_callback(from_node, to_node):
return int(dist_matrix[from_node][to_node])
return distance_callback
def main():
# 一共13個城市，以及城市之間的距離
city_names = ["New York", "Los Angeles", "Chicago", "Minneapolis",
"Denver", "Dallas", "Seattle", "Boston", "San Francisco",
"St. Louis", "Houston", "Phoenix", "Salt Lake City"]
# Distance matrix
dist_matrix = [
[0, 2451, 713, 1018, 1631, 1374, 2408, 213, 2571, 875, 1420, 2145, 1972], # New York
[2451, 0, 1745, 1524, 831, 1240, 959, 2596, 403, 1589, 1374, 357, 579], # Los Angeles
[713, 1745, 0, 355, 920, 803, 1737, 851, 1858, 262, 940, 1453, 1260], # Chicago
[1018, 1524, 355, 0, 700, 862, 1395, 1123, 1584, 466, 1056, 1280, 987], # Minneapolis
[1631, 831, 920, 700, 0, 663, 1021, 1769, 949, 796, 879, 586, 371], # Denver
[1374, 1240, 803, 862, 663, 0, 1681, 1551, 1765, 547, 225, 887, 999], # Dallas
[2408, 959, 1737, 1395, 1021, 1681, 0, 2493, 678, 1724, 1891, 1114, 701], # Seattle
[213, 2596, 851, 1123, 1769, 1551, 2493, 0, 2699, 1038, 1605, 2300, 2099], # Boston
[2571, 403, 1858, 1584, 949, 1765, 678, 2699, 0, 1744, 1645, 653, 600], # San Francisco
[875, 1589, 262, 466, 796, 547, 1724, 1038, 1744, 0, 679, 1272, 1162], # St. Louis
[1420, 1374, 940, 1056, 879, 225, 1891, 1605, 1645, 679, 0, 1017, 1200], # Houston
[2145, 357, 1453, 1280, 586, 887, 1114, 2300, 653, 1272, 1017, 0, 504], # Phoenix
[1972, 579, 1260, 987, 371, 999, 701, 2099, 600, 1162, 1200, 504, 0]] # Salt Lake City
# 定義TSP問題的參數(shù)
tsp_size = len(city_names) # 網(wǎng)絡(luò)中節(jié)點的數(shù)量
num_routes = 1 # 定義路由數(shù)，TSP為1
depot = 0 # 路由的開始和結(jié)束節(jié)點，0表示從New York出發(fā)，最后要回到New York
# 創(chuàng)建路由模型，需要指定路由的參數(shù)
routing = pywrapcp.RoutingModel(tsp_size, num_routes, depot)
search_parameters = pywrapcp.RoutingModel.DefaultSearchParameters()
# 創(chuàng)建距離回調(diào)函數(shù)，用于計算兩個節(jié)點之間的距離
dist_callback = create_distance_callback(dist_matrix)
routing.SetArcCostEvaluatorOfAllVehicles(dist_callback)
# Solve the problem.
# 求解并打印結(jié)果
assignment = routing.SolveWithParameters(search_parameters)
if assignment:
# 最小距離
print("Total distance: " + str(assignment.ObjectiveValue()) + " miles\n")
# 規(guī)劃路徑結(jié)果
# Only one route here; otherwise iterate from 0 to routing.vehicles() - 1
route_number = 0
index = routing.Start(route_number) # Index of the variable for the starting node.
route = ''
while not routing.IsEnd(index):
# Convert variable indices to node indices in the displayed route.
# IndexToNode 求當(dāng)前節(jié)點的對應(yīng)的編號
# NextVar 當(dāng)前節(jié)點的下一個節(jié)點，當(dāng)然還要再外層套上assignment.Value
route += str(city_names[routing.IndexToNode(index)]) + ' -> '
index = assignment.Value(routing.NextVar(index))
route += str(city_names[routing.IndexToNode(index)])
print("Route:\n\n" + route)
else:
print('No solution found.')
if __name__ == '__main__':
main()
# 結(jié)果
Total distance: 7293 miles
Route:
New York -> Boston -> Chicago -> Minneapolis -> Denver
-> Salt Lake City -> Seattle -> San Francisco
-> Los Angeles -> Phoenix -> Houston -> Dallas
-> St. Louis -> New York
注意，因為路由解決程序使用整數(shù)進(jìn)行所有計算，所以距離回調(diào)需要將距離回調(diào)返回的值轉(zhuǎn)換為整數(shù)。在上面的例子中，轉(zhuǎn)換由Python int()函數(shù)完成。雖然在這種情況下不需要進(jìn)行轉(zhuǎn)換，因為所有的距離都是整數(shù)，但是建議始終將回調(diào)的返回值轉(zhuǎn)換為整數(shù)。
3. TSP問題2-鉆線路
這個例子是用自動鉆孔機在電路板上鉆孔，問題是為了鉆完所有需要的孔，找到鉆板的最短路徑。該示例取自TSP問題庫TSPLIB。
見下圖，和TSP是一個問題，只是看起來更復(fù)雜而已，不過距離函數(shù)計算不同，在前面的問題中，距離直接給出來了，而這里需要自己計算歐拉距離。
下面是python代碼，就不注釋了。
import math
from ortools.constraint_solver import pywrapcp
from ortools.constraint_solver import routing_enums_pb2
def euclid_distance(x1, y1, x2, y2):
# 歐式距離計算
dist = math.sqrt((x1 - x2) ** 2 + (y1 - y2) ** 2)
return dist
def create_distance_matrix(locations):
# Create the distance matrix.
size = len(locations)
dist_matrix = {}
for from_node in range(size):
dist_matrix[from_node] = {}
for to_node in range(size):
x1 = locations[from_node][0]
y1 = locations[from_node][1]
x2 = locations[to_node][0]
y2 = locations[to_node][1]
dist_matrix[from_node][to_node] = euclid_distance(x1, y1, x2, y2)
return dist_matrix
def create_distance_callback(dist_matrix):
# Create the distance callback.
def distance_callback(from_node, to_node):
return int(dist_matrix[from_node][to_node])
return distance_callback
def main():
# Create the data.
locations = create_data_array()
dist_matrix = create_distance_matrix(locations)
dist_callback = create_distance_callback(dist_matrix)
tsp_size = len(locations)
num_routes = 1
depot = 0
# Create routing model.
if tsp_size > 0:
routing = pywrapcp.RoutingModel(tsp_size, num_routes, depot)
search_parameters = pywrapcp.RoutingModel.DefaultSearchParameters()
routing.SetArcCostEvaluatorOfAllVehicles(dist_callback)
# Solve the problem.
assignment = routing.SolveWithParameters(search_parameters)
if assignment:
# Solution cost.
print("Total distance: " + str(assignment.ObjectiveValue()) + "\n")
# Inspect solution.
# Only one route here; otherwise iterate from 0 to routing.vehicles() - 1.
route_number = 0
node = routing.Start(route_number)
start_node = node
route = ''
while not routing.IsEnd(node):
route += str(node) + ' -> '
node = assignment.Value(routing.NextVar(node))
route += '0'
print("Route:\n\n" + route)
else:
print('No solution found.')
else:
print('Specify an instance greater than 0.')
def create_data_array():
locations = [[288, 149], [288, 129], [270, 133], [256, 141], [256, 157], [246, 157], [236, 169],
[228, 169], [228, 161], [220, 169], [212, 169], [204, 169], [196, 169], [188, 169], [196, 161],
[188, 145], [172, 145], [164, 145], [156, 145], [148, 145], [140, 145], [148, 169], [164, 169],
[172, 169], [156, 169], [140, 169], [132, 169], [124, 169], [116, 161], [104, 153], [104, 161],
[104, 169], [90, 165], [80, 157], [64, 157], [64, 165], [56, 169], [56, 161], [56, 153], [56, 145],
[56, 137], [56, 129], [56, 121], [40, 121], [40, 129], [40, 137], [40, 145], [40, 153], [40, 161],
[40, 169], [32, 169], [32, 161], [32, 153], [32, 145], [32, 137], [32, 129], [32, 121], [32, 113],
[40, 113], [56, 113], [56, 105], [48, 99], [40, 99], [32, 97], [32, 89], [24, 89], [16, 97],
[16, 109], [8, 109], [8, 97], [8, 89], [8, 81], [8, 73], [8, 65], [8, 57], [16, 57], [8, 49],
[8, 41], [24, 45], [32, 41], [32, 49], [32, 57], [32, 65], [32, 73], [32, 81], [40, 83], [40, 73],
[40, 63], [40, 51], [44, 43], [44, 35], [44, 27], [32, 25], [24, 25], [16, 25], [16, 17], [24, 17],
[32, 17], [44, 11], [56, 9], [56, 17], [56, 25], [56, 33], [56, 41], [64, 41], [72, 41], [72, 49],
[56, 49], [48, 51], [56, 57], [56, 65], [48, 63], [48, 73], [56, 73], [56, 81], [48, 83], [56, 89],
[56, 97], [104, 97], [104, 105], [104, 113], [104, 121], [104, 129], [104, 137], [104, 145],
[116, 145], [124, 145], [132, 145], [132, 137], [140, 137], [148, 137], [156, 137], [164, 137],
[172, 125], [172, 117], [172, 109], [172, 101], [172, 93], [172, 85], [180, 85], [180, 77],
[180, 69], [180, 61], [180, 53], [172, 53], [172, 61], [172, 69], [172, 77], [164, 81], [148, 85],
[124, 85], [124, 93], [124, 109], [124, 125], [124, 117], [124, 101], [104, 89], [104, 81],
[104, 73], [104, 65], [104, 49], [104, 41], [104, 33], [104, 25], [104, 17], [92, 9], [80, 9],
[72, 9], [64, 21], [72, 25], [80, 25], [80, 25], [80, 41], [88, 49], [104, 57], [124, 69],
[124, 77], [132, 81], [140, 65], [132, 61], [124, 61], [124, 53], [124, 45], [124, 37], [124, 29],
[132, 21], [124, 21], [120, 9], [128, 9], [136, 9], [148, 9], [162, 9], [156, 25], [172, 21],
[180, 21], [180, 29], [172, 29], [172, 37], [172, 45], [180, 45], [180, 37], [188, 41], [196, 49],
[204, 57], [212, 65], [220, 73], [228, 69], [228, 77], [236, 77], [236, 69], [236, 61], [228, 61],
[228, 53], [236, 53], [236, 45], [228, 45], [228, 37], [236, 37], [236, 29], [228, 29], [228, 21],
[236, 21], [252, 21], [260, 29], [260, 37], [260, 45], [260, 53], [260, 61], [260, 69], [260, 77],
[276, 77], [276, 69], [276, 61], [276, 53], [284, 53], [284, 61], [284, 69], [284, 77], [284, 85],
[284, 93], [284, 101], [288, 109], [280, 109], [276, 101], [276, 93], [276, 85], [268, 97],
[260, 109], [252, 101], [260, 93], [260, 85], [236, 85], [228, 85], [228, 93], [236, 93],
[236, 101], [228, 101], [228, 109], [228, 117], [228, 125], [220, 125], [212, 117], [204, 109],
[196, 101], [188, 93], [180, 93], [180, 101], [180, 109], [180, 117], [180, 125], [196, 145],
[204, 145], [212, 145], [220, 145], [228, 145], [236, 145], [246, 141], [252, 125], [260, 129],
[280, 133]]
return locations
if __name__ == '__main__':
main()
# 結(jié)果
Total distance: 2790
Route:
0 -> 1 -> 279 -> 2 -> 278 -> 277 -> 248 -> 247 -> 243 -> 242 -> 241
-> 240 -> 239 -> 238 -> 245 -> 244 -> 246 -> 249 -> 250 -> 229 -> 228
……
-> 276 -> 3 -> 4 -> 0
那么長的代碼不用細(xì)看，看幾個關(guān)鍵點就好了。上面兩個例子只是練手，其實沒多大用處，接下來將的VRP問題就用處就比較直接了，當(dāng)然，現(xiàn)實業(yè)務(wù)可不這么簡單，總是有各種各樣的狀況要考慮，不管是簡化模型也好，增加各種約束也好，開開心心干活是不存在的。
敬請期待。
4. 參考
大家看完記得關(guān)注點贊.
master蘇.
總結(jié)
以上是生活随笔為你收集整理的ortools解决tsp_ortools系列：路由问题1的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
