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

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

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

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

中圖分類號(hào)：TP311 ? ? 文獻(xiàn)標(biāo)識(shí)碼：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）

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

對(duì)于車輛路徑優(yōu)化國(guó)內(nèi)外早已展開相關(guān)的研究。車輛路徑優(yōu)化問題（Vehicle Routing Problem，VRP）是由1959年國(guó)外的Dantzig和Ramser[1]最先提出的，為的是提高資源的利用率和配送效率。2012年，Glaydston[2]運(yùn)用大鄰域搜索算法（Large Neighborhood Search）求解VI沖問題，Taranrilis應(yīng)用空間決策支持系統(tǒng)來解決車輛路徑問題。2011年，王征等學(xué)者研究了帶時(shí)間窗的車輛路徑優(yōu)化問題，提出了改進(jìn)的變鄰域搜索算法（VNS），該算法首先通過聚類分析把客戶群指派分類，然后在對(duì)每個(gè)客戶群采用VNS算法進(jìn)行車輛路徑優(yōu)化，通過標(biāo)準(zhǔn)算例驗(yàn)證了算法的有效性[3];李金夫和庹先國(guó)（2016）等人研究了約束為成本最低、車輛利用率高等條件的整車物流的車輛路線優(yōu)化問題，設(shè)計(jì)了貪心算法和遺傳算法的混和算法求其模型最優(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è)的利潤(rùn)，實(shí)現(xiàn)了雙贏[5]。2012年浙江大學(xué)的宋梟對(duì)車聯(lián)網(wǎng)技術(shù)系統(tǒng)進(jìn)行擴(kuò)展，設(shè)計(jì)和實(shí)現(xiàn)了系統(tǒng)中的數(shù)據(jù)轉(zhuǎn)發(fā)模塊，構(gòu)建模型并運(yùn)用禁忌搜索算法使得工地等待混凝土原料的時(shí)間和配送車輛排隊(duì)等待時(shí)間最短，從而大大提高了配送效率[6]。

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

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

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

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

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

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

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

2.3 ? 配送范圍的限制

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

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

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

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

5 ? 結(jié)論（Conclusion）

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

參考文獻(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] 王征，張俊，王旭坪.多車場(chǎng)帶時(shí)間窗車輛路徑問題的變鄰域搜索算法[J].中國(guó)管理科學(xué)，2011，9（2）：99-109.

[4] 李金夫，庹先國(guó)，劉勇，等.關(guān)于整車物流運(yùn)輸車輛路徑優(yōu)化設(shè)計(jì)的研究[J].計(jì)算機(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ā)平臺(tái).Direction API產(chǎn)品介紹[EB/OL].https：//lbsyun.baidu.com/index.php？title=webapi/direction-api-v2，2019-01-25.

作者簡(jiǎn)介：

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

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

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

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

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