化工儀器網(wǎng)
技術(shù)文章
開學(xué)季 | 第壹課《車輛路徑問題與算法》
閱讀：1891 發(fā)布時間：2020-4-10請問膜拜技術(shù)大牛除了獻(xiàn)上膝蓋還有什么更好的方式,？答：可以把大家的膝蓋一起獻(xiàn)上,，又或者好好學(xué)習(xí)天天向上，利用碎片化時間多為自己充電,，一起參與技術(shù)的交流與探討,。——四月，我們迎來了藍(lán)芯科技的開學(xué)季,，我們將在此分享機(jī)器人相關(guān)技術(shù)知識,。今天是開學(xué)第壹課《車輛路徑問題與算法》，歡迎大家留言一起探討,。
一 ,、車輛路徑問題
在介紹 （Vehicle Routing Problem,VRP）問題前，先介紹它的一個特例,，旅行商問題（Traveling Salesman Problem, TSP）：有一個旅行商人,，要拜訪n個城市，每個城市只能訪問一次,，后返回到原來出發(fā)的城市,。該商人要選擇一條路徑，路徑的選擇目標(biāo)是旅程短,。
圖1 TSP問題
車輛路徑問題（Vehicle Routing Problem,VRP）早是由Dantzig和Ramser于1959年*提出,，它是指一定數(shù)量有一定數(shù)量（n個）的客戶,，各自有不同數(shù)量的貨物需求（qi），配送中心或車場（depot）向客戶提供貨物,，由一個車隊(duì)（m輛車）負(fù)責(zé)分送貨物,，組織適當(dāng)?shù)男熊嚶肪€，目標(biāo)是使得客戶的需求得到滿足,，并能在一定的約束下（例如車輛存在載荷上限Q,、里程長度上限L），達(dá)到總旅行成本小,、耗費(fèi)時間少等目的[1, 2],。
圖 2 VRP問題
在理解了車輛路徑問題后，接下來介紹幾個常用的路徑搜索算法,。
二,、路徑搜索算法
在路徑搜索算法中，常用的算法用Dijkstra算法和 A*算法,。這里不對算法原理進(jìn)行詳細(xì)介紹,，僅簡單給出相應(yīng)的使用示例,。給出一個網(wǎng)格圖,，如圖3所示。在該網(wǎng)格圖中,，僅橫,、縱向相鄰網(wǎng)格可以通過，其中黑色背景網(wǎng)格不可通過,。在網(wǎng)各圖中,，每移動一格會增加一個單位成本。現(xiàn)給定一個起點(diǎn)（46）和終點(diǎn)（49）,，通過Dijkstra算法和A*算法分別求解短路徑,。
圖 3網(wǎng)格圖示例
2.1 Dijkstra算法
該算法的思想是從起點(diǎn)開始，每次新擴(kuò)展一個距離短的點(diǎn),，并更新從起點(diǎn)到該點(diǎn)的距離與路線,。直到拓展到終點(diǎn)，并且往其他方向拓展點(diǎn)的距離不比該點(diǎn)的距離更近時停止,。對圖 3 的求解過程如圖4所示,。終的路線是
。
圖 4 Dijkstra算法拓展過程
2.2 A*算法在Dijkstra中,，當(dāng)前拓展到的點(diǎn)的距離為從起點(diǎn)到當(dāng)前點(diǎn)的實(shí)際短距離,。而A* 算法與 Dijkstra相比增加了一個啟發(fā)項(xiàng)，即在計(jì)算當(dāng)前點(diǎn)的路線距離時,，使用從起點(diǎn)到當(dāng)前點(diǎn)的實(shí)際短距離加上從當(dāng)前拓展的點(diǎn)到終點(diǎn)的估計(jì)距離,。因此,，在實(shí)際距離相同時，估計(jì)距離近的點(diǎn)優(yōu)先繼續(xù)拓展,。使用A*算法對圖3 的求解結(jié)果如圖5 所示,。終的路線是
圖 5 A*算法拓展過程示例
2.3 多訪問點(diǎn)的路徑搜索算法
前面提到的Dijkstra和 A*算法主要是針對兩個點(diǎn)（起點(diǎn)、終點(diǎn)）尋找一條短路徑,，但是對于多訪問點(diǎn)找短路的問題,，比如在文初提到的TSP問題，就不適用了,。我們開發(fā)了一個快速求解的算法,。
我們首先使用 Dijkstra算法找出所有兩點(diǎn)之間的短路并存儲相應(yīng)的路線信息。然后針對多訪問點(diǎn)尋短路問題,，分兩個階段進(jìn)行搜索,。
第壹階段：基于動態(tài)規(guī)劃（DP）求解 TSP的框架，控制初始搜索步長快速得出初始解,。
第二階段：對第壹階段得到的初始解使用變鄰域搜索（VND）進(jìn)行優(yōu)化,。
假設(shè)我們有1個出發(fā)點(diǎn)（編號為
）和6個訪問點(diǎn)（編號為
），車輛從
出發(fā),，需要完成對所有訪問點(diǎn)的訪問,。如果終讓車輛停留在后一個訪問點(diǎn)的訪問點(diǎn)，這就是一個開環(huán)的路徑,，如果要求車輛必須返回出發(fā)地,，則是閉環(huán)的路徑。這里假設(shè)為開環(huán)路徑,，即認(rèn)為路徑結(jié)束的標(biāo)志是完成所有任務(wù)中所有訪問點(diǎn)的配貨,。
因?yàn)橐还灿?個點(diǎn)（1個出發(fā)點(diǎn)加6個訪問點(diǎn)），所以搜索劃分為6個step,，方向?yàn)閺挠抑磷螅◤慕K點(diǎn)至起點(diǎn)）,，如圖6所示。
圖 6基于 DP框架的step示例
計(jì)算過程為,，以后一列的點(diǎn)為終點(diǎn),，搜索第壹個弧（arc）,，即step(1)的路徑,，然后再增加一個 arc，即在step(1)的基礎(chǔ)上搜索step(2)的路徑,，以此類推,。假設(shè)以為終點(diǎn)進(jìn)行搜索，搜索中的部分過程如圖7所示,。終搜索完step(6) 時會搜索出完整的路線,。需要注意的一點(diǎn)是,，一旦發(fā)現(xiàn)某條路線不是可行解時（比如一個訪問點(diǎn)在路線中多次出現(xiàn)），后面可以不再基于此結(jié)果進(jìn)行搜索,。
圖7基于 DP框架的部分搜索過程示例
我們這里控制了初始搜索步長len,，意為從step(1) 到step(len) 搜索出的路徑是按照 DP的方式搜索到的當(dāng)前精確合適的路線，而從step(len+1)開始,，只記錄該step下的n條路徑中合適的結(jié)果,。因此，當(dāng)len的值越大,，終搜索的結(jié)果越接近精確合適解,，但是相應(yīng)的求解時間也會越長。假設(shè)通過該階段終搜索出的合適結(jié)果為
,，接下來將基于此結(jié)果執(zhí)行變鄰域搜索操作,。由于是規(guī)定的出發(fā)點(diǎn)需要保持在輸出路徑的首先位置，因此我們對序列{2,6,1,5,4,3}進(jìn)行鄰域搜索,。VND的框架如圖8 所示,。
圖 8 VND算法框架
在鄰域搜索中，常用的變換策略有Reinsert,、Exchange和Reverse,，如圖9所示。
圖 9 三種常見的鄰域變換策略
使用VND不斷地對序列變換得到新的序列,，并求新序列的路徑成本,。需要注意的是,，求路徑成本時要將出發(fā)點(diǎn)考慮在內(nèi),，即將出發(fā)點(diǎn)
添加到序列前，求該完整路徑的旅行成本,。經(jīng)過VND過程的處理,，輸出的路線即作為終規(guī)劃的路線，例如一個可能的終輸出路徑果是
,，需要注意的是,，這里的節(jié)點(diǎn)相當(dāng)于是“關(guān)鍵節(jié)點(diǎn)”，即只包含的出發(fā)點(diǎn)和需要進(jìn)行配貨操作的訪問點(diǎn),。而相鄰“關(guān)鍵節(jié)點(diǎn)”之間的路線,，則是根據(jù)前述的 Dijkstra計(jì)算的兩點(diǎn)之間的路線進(jìn)行行駛。今天的介紹就到這里,，希望小伙伴們能對路徑規(guī)劃問題和算法有所了解和收獲,！
本文為杭州藍(lán)芯科技有限公司原創(chuàng)文章，轉(zhuǎn)載請注明出處