摘要:物流配送中常用的Dijkstra、Floyd、A*等最短路徑算法只能計(jì)算兩點(diǎn)之間的最短路徑，沒(méi)有帶約束條件和回程規(guī)劃。多車多點(diǎn)路徑規(guī)劃算法利用神經(jīng)網(wǎng)絡(luò)對(duì)收送貨地點(diǎn)進(jìn)行分區(qū)，用百度地圖API計(jì)算各點(diǎn)之間的最短路徑，通過(guò)繞行遍歷思想計(jì)算繞行貢獻(xiàn)值，利用貪婪思想在車輛限載重、限路程的情況下組合回程，從而形成最優(yōu)路徑方案。該算法已用在物流企業(yè)的多車多點(diǎn)路徑規(guī)劃云平臺(tái)上，大大提高了物流配送效率。
關(guān)鍵詞:多車多點(diǎn);最短路徑;繞行貢獻(xiàn)值;規(guī)劃算法;物流配送
0引言
在物流配送活動(dòng)中，物流配送路徑的最優(yōu)化問(wèn)題，是物流配送系統(tǒng)優(yōu)化中關(guān)鍵的一環(huán)。隨著配送路網(wǎng)的日趨復(fù)雜，配送成本日益增大[1]，在物流配送中規(guī)劃合理的配送路線，避免迂回運(yùn)輸與重復(fù)運(yùn)輸，有利于節(jié)省配送費(fèi)用，降低物流成本，提高物流配送的效率和經(jīng)濟(jì)效益。物流配送問(wèn)題是典型的組合尋優(yōu)問(wèn)題[2]，常用的路徑最優(yōu)算法有Dijkstra[3]、Floyd、A*等算法[4]。Dijkstra算法是經(jīng)典的廣度優(yōu)先算法，該算法的主要特點(diǎn)是以起始點(diǎn)為中心搜索所有與其連接的點(diǎn)，從中心向外層延展，直到延展到終點(diǎn)為止，因此能夠有效解決單源最短路徑問(wèn)題[5]。
Floyd算法是經(jīng)典的深度優(yōu)先算法，該算法利用動(dòng)態(tài)規(guī)劃思想，尋找給定的加權(quán)圖中多源點(diǎn)之間最短路徑，因此能夠有效解決任意兩點(diǎn)之間最短距離[6]。A*算法是基于啟發(fā)式的最短路徑算法，是一種靜態(tài)路網(wǎng)中求解最短路徑最有效的直接搜索方法，通過(guò)計(jì)算函數(shù)的慢相對(duì)最優(yōu)解來(lái)篩選出發(fā)點(diǎn)周圍的后繼點(diǎn)[7]。這些算法都是求兩頂點(diǎn)之間的最短路徑，并且沒(méi)有帶約束條件，也沒(méi)有規(guī)劃回程。現(xiàn)實(shí)物流配送中，可能有不同的收送貨地點(diǎn)、不同的收送貨重量，車輛也有限重、限程、限時(shí)等多條件的限制，如何合理安排車輛，使得車輛在限制負(fù)載、限制行程的情況下遍歷所有客戶，并且規(guī)劃回程的路徑方案最優(yōu)，本文提出了多車多點(diǎn)路徑規(guī)劃算法。
1多車多點(diǎn)路徑規(guī)劃算法思想
1.1繞行遍歷思想
多車多點(diǎn)路徑規(guī)劃算法主要是對(duì)多車輛在限制負(fù)載、限制行程的情況下遍歷所有客戶，而且還能規(guī)劃回程的最短路徑方案，其核心是繞行遍歷思想。假設(shè)由S點(diǎn)為起始點(diǎn)，現(xiàn)在要去A、B兩個(gè)地點(diǎn)去收送貨，兩地間的距離單位為km，求要規(guī)劃回程的最短路徑。從起始點(diǎn)出發(fā)，要遍歷所有點(diǎn)，并且返回起始點(diǎn)，路徑的走法有四種：①?gòu)V播方式：S→A→S→B→S，即從S點(diǎn)出發(fā)到A，返回S，再?gòu)腟點(diǎn)到B，返回S。②往返方式：S→A→B→A→S，由S點(diǎn)出發(fā)，經(jīng)過(guò)所有點(diǎn)A、B，再沿路返回。③往返方式：S→B→A→B→S，由S點(diǎn)出發(fā)，經(jīng)過(guò)所有點(diǎn)B、A，再沿路返回。
④繞行遍歷方式：S→A→B→S，環(huán)繞一周，遍歷所有點(diǎn)，回到起始點(diǎn)。表1求出了每種走法的距離及繞行貢獻(xiàn)值。根據(jù)三角形兩邊之和大于第三邊，可知第四種走法(繞行遍歷方式)是最短路徑，是最佳走法。假設(shè)把前三種走法與第四種走法的距離差稱為繞行貢獻(xiàn)值，繞行貢獻(xiàn)值越大，越值得繞行，這是本算法的一個(gè)核心思想。此外，還要根據(jù)S點(diǎn)的夾角K來(lái)判斷采用廣播方式、往返方式還是繞行遍歷方式。當(dāng)S點(diǎn)的夾角K為銳角，才采用繞行遍歷，鈍角則不繞行。
1.2貪婪思想
本算法中，先要計(jì)算出最短距離矩陣SM、繞行貢獻(xiàn)值矩陣RX。RX值根據(jù)篩選公式篩選出來(lái)后形成隊(duì)列，并按降序存放到JXDL隊(duì)列中，再逐條路徑從JXDL堆棧中出棧，進(jìn)入累加堆棧，累加路程值及重量值，一旦路程累加值超過(guò)限程值、重量累加值超過(guò)限重值就出棧，剔除剛進(jìn)棧的路徑，在網(wǎng)絡(luò)圖上按照貪婪思想連接已經(jīng)出棧的路徑，形成一條回程路徑。
1.3靠近原則
在組成回程時(shí)，根據(jù)收送貨點(diǎn)是否靠近來(lái)組合回路，把相對(duì)較遠(yuǎn)的路徑推后處理。是否靠近采用模糊神經(jīng)網(wǎng)絡(luò)來(lái)處理，假設(shè)E點(diǎn)與組成的回程成銳角時(shí)，可以把該地點(diǎn)加入回程，如果是鈍角，則考慮和后面的回程組成回路。
2多車多點(diǎn)路徑規(guī)劃算法的實(shí)現(xiàn)
2.1多車多點(diǎn)路徑規(guī)劃算法的實(shí)現(xiàn)流程
多車多點(diǎn)路徑規(guī)劃算法具體的實(shí)現(xiàn)流程如下：(1)先從數(shù)據(jù)庫(kù)中讀取各個(gè)收送貨地點(diǎn)的經(jīng)緯度、客戶收送的貨物重量以及車輛載重、車輛最大行程信息。(2)利用模糊神經(jīng)網(wǎng)絡(luò)根據(jù)收貨點(diǎn)與送貨點(diǎn)的遠(yuǎn)近進(jìn)行分區(qū)。(3)利用百度地圖API計(jì)算出各個(gè)地點(diǎn)的最短路徑，再算出所有路徑的繞行貢獻(xiàn)值。(4)對(duì)繞行貢獻(xiàn)值篩選后形成降序路徑隊(duì)列，再出隊(duì)，路徑進(jìn)入累加堆棧，入棧的時(shí)候，累加重量值及路程值;一旦路程累加值超過(guò)路程值和重量值就出棧，并剔除剛進(jìn)棧的路徑。
(5)利用貪婪思想根據(jù)路徑是否靠近，對(duì)路徑作連接處理形成回路。(6)把規(guī)劃好后的結(jié)果存儲(chǔ)到數(shù)據(jù)庫(kù)中，并且用百度地圖API顯示出來(lái)。
2.2多車多點(diǎn)路徑規(guī)劃算法的實(shí)現(xiàn)
以物流貨車收貨為例，假設(shè)現(xiàn)有A至J的10個(gè)收貨地點(diǎn)是在同一組，每個(gè)地點(diǎn)的貨物重量(kg)為網(wǎng)絡(luò)圖上的結(jié)點(diǎn)值，L為起始點(diǎn)S到每個(gè)節(jié)點(diǎn)的矩離，D為節(jié)點(diǎn)間的距離。現(xiàn)有兩種貨車，分別是載重30kg與50kg，且貨車一次行駛路程為40公里以內(nèi)。每組成一個(gè)回程，則對(duì)第二類客戶點(diǎn)與現(xiàn)有的回程作是否靠近的判斷，如果靠近的話，則用插入路徑方法，插入經(jīng)過(guò)此客戶點(diǎn)的路徑。重復(fù)此操作，直到所有結(jié)點(diǎn)訪問(wèn)完畢。這樣根據(jù)繞行思想和貪婪思想，逐步組合好了規(guī)劃路徑，最后通過(guò)百度地圖API把這些路徑顯示在地圖上。
3結(jié)語(yǔ)
本算法是針對(duì)多輛車到多個(gè)地點(diǎn)的最短路徑問(wèn)題，在算法中利用神經(jīng)網(wǎng)絡(luò)對(duì)地點(diǎn)按遠(yuǎn)近進(jìn)行分區(qū)，利用百度地圖API計(jì)算出各個(gè)地點(diǎn)的最短路徑，根據(jù)繞行遍歷思想算出所有路徑的繞行貢獻(xiàn)值，再用貪婪思想把路徑組合起來(lái)，最后把規(guī)劃好后的結(jié)果存儲(chǔ)到數(shù)據(jù)庫(kù)中，并且用百度地圖API顯示出來(lái)，使得在物流配送中能夠滿足車輛不超重、不超程并規(guī)劃回程的路徑最短。該算法已用在物流企業(yè)的多車多點(diǎn)智能路徑規(guī)劃云平臺(tái)，也可以廣泛應(yīng)用在物流企業(yè)、公交路線規(guī)劃、旅游規(guī)劃、無(wú)人駕駛等各個(gè)行業(yè)。
參考文獻(xiàn)
[1]鈕亮,張寶友.基于云計(jì)算求解城市物流配送最短路徑研究[J].科技通報(bào),2015(5):184-188.
[2]李晶,閆軍.基于Dijkstra算法和Floyd算法的物流運(yùn)輸最短路徑研究[J].科技信息,2012(2):575-576.
[3]王華.基于Dijkstra算法的物流配送最短路徑算法研[J].計(jì)算機(jī)與數(shù)字工程,2011(3):48-50.
[4]高小芳.物流配送最優(yōu)路徑規(guī)劃[D].福建:華僑大學(xué),2016.
物流方向論文范文：連鎖餐企如何“玩轉(zhuǎn)”物流配送
配送中心的良好發(fā)展離不開(kāi)物流人才，具有物流管理理論和實(shí)踐能力，并對(duì)市場(chǎng)有了解的專業(yè)人才是廣大連鎖餐企的需求目標(biāo)。對(duì)于連鎖餐飲企業(yè)來(lái)說(shuō)，原料價(jià)格一般相差不大，物流配送的成本才是各企業(yè)研究的焦點(diǎn)。從麥當(dāng)勞、肯德基的成功經(jīng)驗(yàn)來(lái)看，連鎖經(jīng)營(yíng)模式之所以能夠高效運(yùn)行，原因在于這些企業(yè)具有匹配自身的物流配送模式，可以輕易實(shí)現(xiàn)多品種、小批量、高頻次的食材運(yùn)輸，大大降低企業(yè)的運(yùn)營(yíng)成本，更迅速的占領(lǐng)市場(chǎng)。
相關(guān)閱讀
