考慮實時路況下的商砼配送路徑優(yōu)化研究

郭琪 韋金銀 郭鵬祥 張碩 史彬

摘 ?要：本文從商砼配送特點出發(fā)，考慮到商砼配送屬于兩點之間的配送過程，以及配送過程要求較高的準(zhǔn)時性，使用百度地圖API獲取行駛時間矩陣，在考慮實時路況的情況下，以時間最短為目標(biāo)建立商砼配送路徑優(yōu)化模型，采用Dijkstra算法求解，求解的實例表明，優(yōu)化出來的配送路徑，可以有效地躲避擁擠路段從而降低配送時間，提高配送效率。

關(guān)鍵詞：商砼配送;路徑優(yōu)化;實時路況;百度地圖API

中圖分類號：TP311 ? ? 文獻(xiàn)標(biāo)識碼：A

Abstract：Given the characteristics of commercial concrete distribution，considering that the distribution of commercial concrete belongs to the distribution process between two points，as well as the high punctuality required by the delivery process，Baidu map API is used to obtain the travel time matrix.In consideration of the real-time road conditions and the goal of the shortest time，the distribution route optimization model is established，and the Dijkstra algorithm is used to solve the problem.The example of the solution shows that the optimized distribution route can effectively avoid the crowded roads，thus reducing the delivery time and improving the distribution efficiency.

Keywords：commercial concrete distribution;routing optimization;real-time road conditions;Baidu Map API

1 ? 引言（Introduction）

近幾年隨著我國城市化進(jìn)程的不斷推進(jìn)，混凝土作為城市建筑的原料迅速增值，與此同時隨著建筑行業(yè)的發(fā)展，以及商品混凝土政策的出臺，混凝土行業(yè)迎來了發(fā)展的黃金時期，各種混凝土企業(yè)如雨后春筍般涌現(xiàn)，行業(yè)競爭日益加劇。目前整個混凝土行業(yè)缺乏科學(xué)的物流調(diào)度，還沒有將互聯(lián)網(wǎng)時代所帶來的信息優(yōu)勢運用于配送過程中，導(dǎo)致信息流通不暢，供求雙方不能及時掌握重要信息，例如砼車配送途中面臨交通堵塞時新路線的規(guī)劃。同時，道路交通的復(fù)雜化和多變化也是影響配送效率的關(guān)鍵因素。因此，車輛路徑優(yōu)化成為商砼配送的核心環(huán)節(jié)。

對于車輛路徑優(yōu)化國內(nèi)外早已展開相關(guān)的研究。車輛路徑優(yōu)化問題（Vehicle Routing Problem，VRP）是由1959年國外的Dantzig和Ramser[1]最先提出的，為的是提高資源的利用率和配送效率。2012年，Glaydston[2]運用大鄰域搜索算法（Large Neighborhood Search）求解VI沖問題，Taranrilis應(yīng)用空間決策支持系統(tǒng)來解決車輛路徑問題。2011年，王征等學(xué)者研究了帶時間窗的車輛路徑優(yōu)化問題，提出了改進(jìn)的變鄰域搜索算法（VNS），該算法首先通過聚類分析把客戶群指派分類，然后在對每個客戶群采用VNS算法進(jìn)行車輛路徑優(yōu)化，通過標(biāo)準(zhǔn)算例驗證了算法的有效性[3];李金夫和庹先國（2016）等人研究了約束為成本最低、車輛利用率高等條件的整車物流的車輛路線優(yōu)化問題，設(shè)計了貪心算法和遺傳算法的混和算法求其模型最優(yōu)解，并進(jìn)行了仿真[4]。

基于商砼配送路徑優(yōu)化的研究大體為，2011年，武寧學(xué)者詳細(xì)分析了混凝土配送現(xiàn)狀、混凝土配送車輛調(diào)度研究現(xiàn)狀，以及存在的問題，構(gòu)建了以配送站為中心的混凝土生產(chǎn)廠配送車輛調(diào)度模型，應(yīng)用模擬退火—粒子群算法優(yōu)化求解，不僅保證了施工質(zhì)量和進(jìn)度，還極大提高混凝土生產(chǎn)企業(yè)的利潤，實現(xiàn)了雙贏[5]。2012年浙江大學(xué)的宋梟對車聯(lián)網(wǎng)技術(shù)系統(tǒng)進(jìn)行擴展，設(shè)計和實現(xiàn)了系統(tǒng)中的數(shù)據(jù)轉(zhuǎn)發(fā)模塊，構(gòu)建模型并運用禁忌搜索算法使得工地等待混凝土原料的時間和配送車輛排隊等待時間最短，從而大大提高了配送效率[6]。

本文在現(xiàn)有的商砼配送路徑優(yōu)化的研究基礎(chǔ)上，結(jié)合商砼運輸特點，使用百度地圖API獲取行駛時間矩陣，在考慮實時路況的情況下，以時間最短為目標(biāo)建立砼配送路徑優(yōu)化模型，采用Dijkstra算法求解。

2 ?問題分析與模型建立（Analyzing problems and? ? ? building models）

面對城市日益增長的商砼需求，以及復(fù)雜的道路交通環(huán)境，商砼配送逐漸成為企業(yè)運營中重要的一環(huán)，成為企業(yè)利潤的重要來源。商砼配送具有三大特點。

2.1 ? 配送專業(yè)化程度高

商品混凝土與其他產(chǎn)品配送不同，其配送過程需要配置專有的商砼攪拌車，且商砼配送是企業(yè)與施工單位之間兩個點之間的配送，卸料的過程中還需要泵車等其他專用工具。

2.2 ? 要求較高的準(zhǔn)時性

由于商砼是一種暫時性的過渡產(chǎn)品，如果不能在規(guī)定的時間內(nèi)完成配送，商砼便失原有價值成為廢棄物，因此商砼對準(zhǔn)時性有較高的要求，所以配送時間越短越好。

2.3 ? 配送范圍的限制

由于商品混凝土具有較高的準(zhǔn)時性要求，所以商砼配送的范圍有一定的限制，配送距離不能太遠(yuǎn)。

通過比較以上結(jié)果，我們發(fā)現(xiàn)在一天內(nèi)不同時間段進(jìn)行實驗，行駛時間矩陣表中的數(shù)據(jù)是不一樣的，這是因為百度地圖API是基于實時路況計算得出的，不同時間段，路況狀態(tài)不同，所以得到的數(shù)據(jù)結(jié)果也不同，通過Dijkstra算法所得出的路徑也是不一樣的，所用的時間也不一樣。

不同時間段內(nèi)優(yōu)化出來的路徑各不相同，我們可以從交通狀況的角度分析，8：00時處于早高峰階段，道路交通狀況差，交通處于擁堵狀態(tài)，為了躲避擁擠路段，車輛會選擇走路徑較長但是相對時間最短的路徑，12：00時處于中午時段，此時道路交通狀況良好，此時選擇走路徑較短的路線，在車速一定的情況下時間最短，所以路徑優(yōu)化時得到的路徑所需時間較8：00時短。

基于以上分析，以時間最短為優(yōu)化目標(biāo)建立數(shù)學(xué)模型，通過Dijkstra算法計算所得出的路徑具有滿足商砼配送要求較高的準(zhǔn)時性的特點，且能較好地應(yīng)用于實際商砼配送過程中。

5 ? 結(jié)論（Conclusion）

本文在對商砼配送路徑優(yōu)化問題的基礎(chǔ)上，通過引入百度地圖API，得到基于實時路況的選擇的節(jié)點的行駛時間矩陣，我們以時間最短為目標(biāo)建立商砼配送路徑優(yōu)化模型，采用Dijkstra算法求解，求解的實例表明，優(yōu)化出來的配送路徑，可以有效的降低配送時間，提高配送效率，減少企業(yè)的運輸成本。

參考文獻(xiàn)（References）

[1] Danting G.B，Ramser J.H.The Truck Dispatching problem[J].Management Science，1959（6）：80-91.

[2] Glaydston Mattos Ribera，Gilbert Laborite.An adaptive large neighborhood search heuristic for the cumulmive capacitated vehicle routing probem[J].Original Research Article Computers&Operations Research，2012，39（3）：728-735.

[3] 王征，張俊，王旭坪.多車場帶時間窗車輛路徑問題的變鄰域搜索算法[J].中國管理科學(xué)，2011，9（2）：99-109.

[4] 李金夫，庹先國，劉勇，等.關(guān)于整車物流運輸車輛路徑優(yōu)化設(shè)計的研究[J].計算機仿真，2016，3（4）：184-188.

[5] 武寧.基于SA-PSO的預(yù)拌混凝土配送車輛調(diào)度優(yōu)化研究[D].河北工程大學(xué)，2011.

[6] 宋梟.基于車聯(lián)網(wǎng)的混凝土車輛監(jiān)控與調(diào)度系統(tǒng)[D].浙江大學(xué)，2012.

[7] 百度地圖開發(fā)平臺.Direction API產(chǎn)品介紹[EB/OL].https：//lbsyun.baidu.com/index.php？title=webapi/direction-api-v2，2019-01-25.

作者簡介：

郭 ?琪（1998-），男，本科生.研究領(lǐng)域：化學(xué)工程與工藝.

韋金銀（1993-），男，碩士生.研究領(lǐng)域：過程系統(tǒng)工程.

郭鵬祥（1999-），男，本科生.研究領(lǐng)域：化學(xué)工程與工藝.

張 ?碩（1999-），男，本科生.研究領(lǐng)域：化學(xué)工程與工藝.

史 ?彬（1982-），男，博士，副教授.研究領(lǐng)域：過程系統(tǒng)工程.本文通訊作者.