請(qǐng)問(wèn)膜拜技術(shù)大牛除了獻(xiàn)上膝蓋還有什么更好的方式？答：可以把大家的膝蓋一起獻(xiàn)上，又或者好好學(xué)習(xí)天天向上，利用碎片化時(shí)間多為自己充電，一起參與技術(shù)的交流與探討。——四月，我們迎來(lái)了藍(lán)芯科技的開(kāi)學(xué)季，我們將在此分享機(jī)器人相關(guān)技術(shù)知識(shí)。今天是開(kāi)學(xué)第一課《車(chē)輛路徑問(wèn)題與算法》，歡迎大家留言一起探討。  
 

一 、車(chē)輛路徑問(wèn)題
在介紹 （Vehicle Routing Problem,VRP）問(wèn)題前，先介紹它的一個(gè)特例，旅行商問(wèn)題（Traveling Salesman Problem, TSP）：有一個(gè)旅行商人，要拜訪n個(gè)城市，每個(gè)城市只能訪問(wèn)一次，zui后返回到原來(lái)出發(fā)的城市。該商人要選擇一條路徑，路徑的選擇目標(biāo)是旅程zui短。
 

 

圖1 TSP問(wèn)題
 

車(chē)輛路徑問(wèn)題（Vehicle Routing Problem,VRP）zui早是由Dantzig和Ramser于1959年*提出，它是指一定數(shù)量有一定數(shù)量（n個(gè)）的客戶(hù)，各自有不同數(shù)量的貨物需求（qi），配送中心或車(chē)場(chǎng)（depot）向客戶(hù)提供貨物，由一個(gè)車(chē)隊(duì)（m輛車(chē)）負(fù)責(zé)分送貨物，組織適當(dāng)?shù)男熊?chē)路線，目標(biāo)是使得客戶(hù)的需求得到滿(mǎn)足，并能在一定的約束下（例如車(chē)輛存在載荷上限Q、里程長(zhǎng)度上限L），達(dá)到總旅行成本zui小、耗費(fèi)時(shí)間zui少等目的[1, 2]。

 

圖 2 VRP問(wèn)題

在理解了車(chē)輛路徑問(wèn)題后，接下來(lái)介紹幾個(gè)常用的路徑搜索算法。

 

二、路徑搜索算法

在路徑搜索算法中，常用的算法用Dijkstra算法和 A*算法。這里不對(duì)算法原理進(jìn)行詳細(xì)介紹，僅簡(jiǎn)單給出相應(yīng)的使用示例。給出一個(gè)網(wǎng)格圖，如圖3所示。在該網(wǎng)格圖中，僅橫、縱向相鄰網(wǎng)格可以通過(guò)，其中黑色背景網(wǎng)格不可通過(guò)。在網(wǎng)各圖中，每移動(dòng)一格會(huì)增加一個(gè)單位成本?，F(xiàn)給定一個(gè)起點(diǎn)（46）和終點(diǎn)（49），通過(guò)Dijkstra算法和A*算法分別求解zui短路徑。

圖 3網(wǎng)格圖示例

 

2.1 Dijkstra算法
該算法的思想是從起點(diǎn)開(kāi)始，每次新擴(kuò)展一個(gè)距離zui短的點(diǎn)，并更新從起點(diǎn)到該點(diǎn)的距離與路線。直到拓展到終點(diǎn)，并且往其他方向拓展點(diǎn)的距離不比該點(diǎn)的距離更近時(shí)停止。對(duì)圖 3 的求解過(guò)程如圖4所示。zui終的路線是。

 

圖 4 Dijkstra算法拓展過(guò)程

 

2.2 A*算法在Dijkstra中，當(dāng)前拓展到的點(diǎn)的距離為從起點(diǎn)到當(dāng)前點(diǎn)的實(shí)際zui短距離。而A* 算法與 Dijkstra相比增加了一個(gè)啟發(fā)項(xiàng)，即在計(jì)算當(dāng)前點(diǎn)的路線距離時(shí)，使用從起點(diǎn)到當(dāng)前點(diǎn)的實(shí)際zui短距離加上從當(dāng)前拓展的點(diǎn)到終點(diǎn)的估計(jì)距離。因此，在實(shí)際距離相同時(shí)，估計(jì)距離近的點(diǎn)優(yōu)先繼續(xù)拓展。使用A*算法對(duì)圖3 的求解結(jié)果如圖5 所示。zui終的路線是

 

圖 5 A*算法拓展過(guò)程示例
 

2.3 多訪問(wèn)點(diǎn)的路徑搜索算法
前面提到的Dijkstra和 A*算法主要是針對(duì)兩個(gè)點(diǎn)（起點(diǎn)、終點(diǎn)）尋找一條zui短路徑，但是對(duì)于多訪問(wèn)點(diǎn)找zui短路的問(wèn)題，比如在文初提到的TSP問(wèn)題，就不適用了。我們開(kāi)發(fā)了一個(gè)快速求解的算法。

我們首先使用 Dijkstra算法找出所有兩點(diǎn)之間的zui短路并存儲(chǔ)相應(yīng)的路線信息。然后針對(duì)多訪問(wèn)點(diǎn)尋zui短路問(wèn)題，分兩個(gè)階段進(jìn)行搜索。
第一階段：基于動(dòng)態(tài)規(guī)劃（DP）求解 TSP的框架，控制初始搜索步長(zhǎng)快速得出初始解。
第二階段：對(duì)第一階段得到的初始解使用變鄰域搜索（VND）進(jìn)行優(yōu)化。


假設(shè)我們有1個(gè)出發(fā)點(diǎn)（編號(hào)為）和6個(gè)訪問(wèn)點(diǎn)（編號(hào)為），車(chē)輛從出發(fā)，需要完成對(duì)所有訪問(wèn)點(diǎn)的訪問(wèn)。如果zui終讓車(chē)輛停留在zui后一個(gè)訪問(wèn)點(diǎn)的訪問(wèn)點(diǎn)，這就是一個(gè)開(kāi)環(huán)的路徑，如果要求車(chē)輛必須返回出發(fā)地，則是閉環(huán)的路徑。這里假設(shè)為開(kāi)環(huán)路徑，即認(rèn)為路徑結(jié)束的標(biāo)志是完成所有任務(wù)中所有訪問(wèn)點(diǎn)的配貨。

 

因?yàn)橐还灿?個(gè)點(diǎn)（1個(gè)出發(fā)點(diǎn)加6個(gè)訪問(wèn)點(diǎn)），所以搜索劃分為6個(gè)step，方向?yàn)閺挠抑磷螅◤慕K點(diǎn)至起點(diǎn)），如圖6所示。

 

圖 6基于 DP框架的step示例

 

計(jì)算過(guò)程為，以zui后一列的點(diǎn)為終點(diǎn)，搜索第一個(gè)?。╝rc），即step(1)的路徑，然后再增加一個(gè) arc，即在step(1)的基礎(chǔ)上搜索step(2)的路徑，以此類(lèi)推。假設(shè)以為終點(diǎn)進(jìn)行搜索，搜索中的部分過(guò)程如圖7所示。zui終搜索完step(6) 時(shí)會(huì)搜索出完整的路線。需要注意的一點(diǎn)是，一旦發(fā)現(xiàn)某條路線不是可行解時(shí)（比如一個(gè)訪問(wèn)點(diǎn)在路線中多次出現(xiàn)），后面可以不再基于此結(jié)果進(jìn)行搜索。

 

圖7基于 DP框架的部分搜索過(guò)程示例

 

我們這里控制了初始搜索步長(zhǎng)len，意為從step(1) 到step(len) 搜索出的路徑是按照 DP的方式搜索到的當(dāng)前精確zui合適的路線，而從step(len+1)開(kāi)始，只記錄該step下的n條路徑中zui合適的結(jié)果。因此，當(dāng)len的值越大，zui終搜索的結(jié)果越接近精確zui合適解，但是相應(yīng)的求解時(shí)間也會(huì)越長(zhǎng)。假設(shè)通過(guò)該階段zui終搜索出的zui合適結(jié)果為，接下來(lái)將基于此結(jié)果執(zhí)行變鄰域搜索操作。由于是規(guī)定的出發(fā)點(diǎn)需要保持在輸出路徑的首先位置，因此我們對(duì)序列{2,6,1,5,4,3}進(jìn)行鄰域搜索。VND的框架如圖8 所示。

 

圖 8  VND算法框架

 

在鄰域搜索中，常用的變換策略有Reinsert、Exchange和Reverse，如圖9所示。

圖 9 三種常見(jiàn)的鄰域變換策略

 

使用VND不斷地對(duì)序列變換得到新的序列，并求新序列的路徑成本。需要注意的是，求路徑成本時(shí)要將出發(fā)點(diǎn)考慮在內(nèi)，即將出發(fā)點(diǎn)添加到序列前，求該完整路徑的旅行成本。經(jīng)過(guò)VND過(guò)程的處理，輸出的路線即作為zui終規(guī)劃的路線，例如一個(gè)可能的zui終輸出路徑果是，需要注意的是，這里的節(jié)點(diǎn)相當(dāng)于是“關(guān)鍵節(jié)點(diǎn)”，即只包含的出發(fā)點(diǎn)和需要進(jìn)行配貨操作的訪問(wèn)點(diǎn)。而相鄰“關(guān)鍵節(jié)點(diǎn)”之間的路線，則是根據(jù)前述的 Dijkstra計(jì)算的兩點(diǎn)之間的路線進(jìn)行行駛。今天的介紹就到這里，希望小伙伴們能對(duì)路徑規(guī)劃問(wèn)題和算法有所了解和收獲！

本文為杭州藍(lán)芯科技有限公司原創(chuàng)文章，轉(zhuǎn)載請(qǐng)注明出處