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

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

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

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

中圖分類號：TP311 ? ? 文獻標識碼：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）

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

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

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

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

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

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

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

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

2.2 ? 要求較高的準時性

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

2.3 ? 配送范圍的限制

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

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

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

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

5 ? 結論（Conclusion）

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

參考文獻（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].中國管理科學，2011，9（2）：99-109.

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

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

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

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

作者簡介：

郭 ?琪（1998-），男，本科生.研究領域：化學工程與工藝.

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

郭鵬祥（1999-），男，本科生.研究領域：化學工程與工藝.

張 ?碩（1999-），男，本科生.研究領域：化學工程與工藝.

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