OR-Tools VRP 問(wèn)題從入門(mén)到升天(一) TSP問(wèn)題

Ortools的VRP求解器簡(jiǎn)介

谷歌的Ortools整合了許多對(duì)運(yùn)籌優(yōu)化問(wèn)題的求解器，其中最好用的部分就是VRP求解器。

在ortools中，VRP求解器是建立在constraint programming求解器之上的，因此除了一些經(jīng)典的VRP問(wèn)題約束，例如最大負(fù)載，時(shí)間窗以外，還可以通過(guò)約束規(guī)劃求解器，靈活地添加一系列高度定制化的約束，例如要求某輛車(chē)經(jīng)過(guò)某個(gè)節(jié)點(diǎn)，要求一個(gè)節(jié)點(diǎn)被多臺(tái)車(chē)訪問(wèn)等。

在ortools中求解VRP問(wèn)題時(shí)，最常用的有兩類(lèi)變量，我們可以從抽象層面了解一下其含義：

路徑變量(Path variable)：
- next(i) - 代表節(jié)點(diǎn) i 在路徑中的后繼節(jié)點(diǎn)的下標(biāo)。用IndexToNode()可以從下表獲取節(jié)點(diǎn)變量。
- vehicle(i) - 表示節(jié)點(diǎn) i 所屬于的車(chē)輛路徑編號(hào)，即第 i 個(gè)節(jié)點(diǎn)由哪輛車(chē)來(lái)服務(wù)。
- active(i) - 布爾變量，如果節(jié)點(diǎn) i 被訪問(wèn)，那么值為T(mén)rue，否則為False。
- 下面的幾組關(guān)系是等價(jià)的：active(i) == 0 <==> next(i) == i <==> vehicle(i) == -1，next(i) == j ==> vehicle(j) == vehicle(i)
維度變量(Dimension variable) - 用于標(biāo)記經(jīng)過(guò)路徑時(shí)累加的值，例如車(chē)輛的負(fù)載、消耗時(shí)間、行駛距離等。常用的有兩類(lèi)：
- cumul(i, d) - 代表車(chē)輛到達(dá)節(jié)點(diǎn) i 時(shí)維度 d 的值
- transit(i, d) - 代表車(chē)輛經(jīng)過(guò)節(jié)點(diǎn) i 時(shí)，需要在維度 d 上累加的值
- 這兩者的關(guān)系為： next(i)==j ==> cumul(j,d)=cumul(i,d)+transit(i,d)

因此，從抽象層面上來(lái)講，每臺(tái)車(chē)從depot出發(fā)，不斷進(jìn)行next(i)操作，最終回到depot，即可求得該車(chē)輛的路徑。每次next(i)操作的同時(shí)，我們也通過(guò)transit(i,d)不斷累加我們關(guān)注的值，例如車(chē)輛的總行駛距離、消耗時(shí)間等。這就是ortools對(duì)VRP問(wèn)題的抽象概括。

數(shù)據(jù)

這里我們使用的測(cè)試數(shù)據(jù)來(lái)自TSPlib中的gr120，其中包含120個(gè)節(jié)點(diǎn)。

數(shù)據(jù)的讀入使用python中的tsplib95包來(lái)完成，節(jié)省自己編寫(xiě)數(shù)據(jù)讀入部分的時(shí)間。

所有節(jié)點(diǎn)的可視化如下：

gr120.tsp_nodes.png

整體代碼

我們先看一下整體的代碼，了解調(diào)用ortools求解VRP的基本框架，然后再在后面去對(duì)各個(gè)重要的類(lèi)進(jìn)行詳細(xì)分析：

## 包的導(dǎo)入
from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp
import tsplib95
import matplotlib.pyplot as plt
%matplotlib inline
 
## 設(shè)定數(shù)據(jù)目錄并讀入數(shù)據(jù)
fname: str = "gr120.tsp"
input_fpath: str = r"data/" + fname
data = tsplib95.load(input_fpath).as_name_dict()

## 建立模型
# 創(chuàng)建routing index manager
n_vehicle = 1 # 車(chē)輛數(shù)，在TSP問(wèn)題中為1
depot_index = 0 # 車(chē)庫(kù)，設(shè)置為0號(hào)節(jié)點(diǎn)
manager = pywrapcp.RoutingIndexManager(data['dimension'], n_vehicle, depot_index)
# 創(chuàng)建一個(gè)Routing model
routing = pywrapcp.RoutingModel(manager)
# 創(chuàng)建一個(gè)distance call back，這里使用歐幾里得距離
def distance_callback(from_index: int, to_index: int):
    from_node = manager.IndexToNode(from_index)
    to_node = manager.IndexToNode(to_index)
    # +1是因?yàn)樽x入數(shù)據(jù)時(shí)節(jié)點(diǎn)下標(biāo)從1開(kāi)始
    from_coor = data['display_data'][from_node+1]
    to_coor = data['display_data'][to_node+1]
    return (to_coor[0] - from_coor[0])**2 + (to_coor[1] - from_coor[1])**2
 # 因?yàn)槲覀冃枰谲?chē)輛經(jīng)過(guò)節(jié)點(diǎn)i是為其在距離維度d上累加一定的值，所以這里我們使用transitCallBack; 之后我們會(huì)看到在設(shè)置時(shí)間窗口時(shí)，會(huì)用到cumul類(lèi)的維度變量
transit_callback_index = routing.RegisterTransitCallback(distance_callback)
# 給每條邊設(shè)置cost
routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)
# 設(shè)置求解的啟發(fā)式算法
search_parameters = pywrapcp.DefaultRoutingSearchParameters()
search_parameters.first_solution_strategy = (routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)
# 求解
solution = routing.SolveWithParameters(search_parameters)

## 輸出結(jié)果：
if solution:
    print("路徑總長(zhǎng)度: {} miles".format(solution.ObjectiveValue()))
    index = routing.Start(0) # routing.Start(0)代表獲取0號(hào)車(chē)輛的起點(diǎn)
    path: str = "旅行商的路徑：\n"
    visiting_sequence: list = []
    while not routing.IsEnd(index):
        visiting_sequence.append(manager.IndexToNode(index)+1)
        path += " {} ->".format(manager.IndexToNode(index)+1)
        previous_index = index
        index = solution.Value(routing.NextVar(index))
    visiting_sequence.append(manager.IndexToNode(index)+1)
    path += " {}\n".format(manager.IndexToNode(index)+1)
    print(path)
else:
    print("沒(méi)有得到可行解")

得到結(jié)果：

路徑總長(zhǎng)度: 28422 miles
旅行商的路徑：
 1 -> 76 -> 59 -> 15 -> 30 -> 29 -> 120 -> 32 -> 92 -> 28 -> 45 -> 78 -> 86 -> 94 -> 81 -> 22 -> 66 -> 31 -> 117 -> 85 -> 18 -> 19 -> 25 -> 108 -> 43 -> 79 -> 52 -> 33 -> 100 -> 58 -> 91 -> 68 -> 65 -> 69 -> 113 -> 107 -> 20 -> 46 -> 50 -> 98 -> 17 -> 118 -> 13 -> 49 -> 42 -> 41 -> 56 -> 44 -> 75 -> 14 -> 87 -> 74 -> 105 -> 40 -> 72 -> 7 -> 38 -> 4 -> 119 -> 103 -> 9 -> 23 -> 51 -> 11 -> 115 -> 21 -> 93 -> 2 -> 82 -> 3 -> 80 -> 27 -> 53 -> 64 -> 109 -> 88 -> 97 -> 12 -> 95 -> 77 -> 5 -> 63 -> 73 -> 57 -> 39 -> 83 -> 67 -> 37 -> 62 -> 99 -> 10 -> 35 -> 104 -> 106 -> 114 -> 101 -> 102 -> 48 -> 110 -> 112 -> 36 -> 84 -> 6 -> 89 -> 55 -> 47 -> 71 -> 26 -> 34 -> 116 -> 70 -> 8 -> 54 -> 90 -> 96 -> 111 -> 24 -> 60 -> 16 -> 61 -> 1

我們還可以對(duì)路徑進(jìn)行可視化：

plt.figure(figsize=(8, 6))
# 畫(huà)出depot
depot_coor = data['display_data'][depot_index + 1]
plt.plot(depot_coor[0], depot_coor[1], 'r*', markersize=11)
# 路徑可視化
for i, j in zip(visiting_sequence, visiting_sequence[1:]):
 start_coor = data['display_data'][i]
 end_coor = data['display_data'][j]
 plt.arrow(start_coor[0], start_coor[1], end_coor[0] - start_coor[0], end_coor[1] - start_coor[1])
plt.xlabel("X coordinate", fontsize = 14)
plt.ylabel("Y coordinate", fontsize = 14)
plt.title("TSP path for {}".format(fname), fontsize = 16)

結(jié)果如下圖（紅色星星代表depot）：

Path_for_gr120.tsp.png

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

OR-Tools VRP 問(wèn)題從入門(mén)到升天(一) TSP問(wèn)題