車(chē)輛路徑規(guī)劃問(wèn)題研究綜述

趙琨 王帥

摘 要：為了提高車(chē)輛路徑規(guī)劃能力，闡明路徑優(yōu)化問(wèn)題的發(fā)展趨勢(shì)。國(guó)內(nèi)外學(xué)者從理論以及實(shí)際應(yīng)用的角度對(duì)該問(wèn)題進(jìn)行研究。路徑優(yōu)化問(wèn)題的研究已經(jīng)發(fā)生了重大轉(zhuǎn)變。研究環(huán)境轉(zhuǎn)變?yōu)樾枨蟮牟淮_定、道路狀況的動(dòng)態(tài)變化;研究目標(biāo)轉(zhuǎn)變?yōu)檐?chē)輛總成本、能耗和污染物排放的權(quán)衡;研究客體轉(zhuǎn)變?yōu)槎嗄茉础⒍嘬?chē)型的車(chē)輛選擇;研究方法轉(zhuǎn)變?yōu)槎嗄Ｐ汀⒍嗨惴ā⒍鄬W(xué)科融合的綜合系統(tǒng)。

關(guān)鍵詞：路徑規(guī)劃;算法;仿真

中圖分類(lèi)號(hào)：TB 文獻(xiàn)標(biāo)識(shí)碼：Adoi：10.19311/j.cnki.1672-3198.2019.26.104

Vehicle Routing Problem，即車(chē)輛路徑規(guī)劃問(wèn)題，自1959年由Ramser和Dantzing提出，經(jīng)過(guò)60年來(lái)的研究與發(fā)展，研究的目標(biāo)、對(duì)象、限制條件等均有所變化，已經(jīng)從最初的簡(jiǎn)單車(chē)輛安排調(diào)度問(wèn)題轉(zhuǎn)變?yōu)閺?fù)雜的系統(tǒng)問(wèn)題。本文對(duì)近五年來(lái)具有代表性的路徑優(yōu)化文獻(xiàn)進(jìn)行分析、總結(jié)，從算法和模型的研究角度出發(fā)，揭示車(chē)輛路徑問(wèn)題優(yōu)化的發(fā)展方向，對(duì)日后該問(wèn)題的研究提出相應(yīng)地建議。

如今，路徑優(yōu)化算法除了傳統(tǒng)的遺傳算法、蟻群算法、模擬退火算法、禁忌搜索算法之外，而且演變出多學(xué)科融合的創(chuàng)新算法，如：模擬植物生長(zhǎng)算法、粒子群優(yōu)化算法、細(xì)菌覓食優(yōu)化算法等，主要應(yīng)用Matlab、Python等軟件來(lái)模擬算法結(jié)果，驗(yàn)證算法的有效性。

范厚明（2018）等提出一種半開(kāi)放式的多配送中心聯(lián)合配送模式，考慮到生鮮品運(yùn)輸?shù)臅r(shí)效性要求，設(shè)計(jì)了相應(yīng)的時(shí)間窗及懲罰成本，建立了車(chē)輛運(yùn)輸總成本、調(diào)度成本和時(shí)間懲罰成本最小的優(yōu)化模型，并設(shè)計(jì)了蟻群算法對(duì)其進(jìn)行求解。Nekooghadirli（2014）等針對(duì)不確定需求的LIRP問(wèn)題，以最小化總成本和最大化供應(yīng)時(shí)間為目標(biāo)，建立了多目標(biāo)優(yōu)化模型，并結(jié)合禁忌搜索和模擬退火算法求解算例。曹慶奎（2013）等針對(duì)港口集卡問(wèn)題，利用蟻群算法在解決組合優(yōu)化問(wèn)題方面的優(yōu)勢(shì)和遺傳算法的全局尋優(yōu)能力，設(shè)計(jì)了遺傳蟻群算法，建立了面向“作業(yè)面”的港口集卡路徑成本優(yōu)化模型。最后通過(guò)實(shí)例驗(yàn)證遺傳蟻群算法的可行性。程博（2013）]等針對(duì)大件公路運(yùn)輸路徑選擇優(yōu)化難題，以最小化運(yùn)輸成本為目標(biāo)，在考慮客戶服務(wù)和配送時(shí)限、懲罰超載車(chē)輛、車(chē)輛載重和容積限制的基礎(chǔ)上，針對(duì)大件公路運(yùn)輸路徑規(guī)劃問(wèn)題，改進(jìn)了遺傳模擬退火算法對(duì)此類(lèi)問(wèn)題進(jìn)行優(yōu)化。葛顯龍（2013）等針對(duì)跨區(qū)域多配送中心的動(dòng)態(tài)需求，提出了基于實(shí)際情況的配送車(chē)輛共享和聯(lián)合配送策略，建立了適合實(shí)際情況的車(chē)輛路徑優(yōu)化模型，并利用云模型理論對(duì)交叉概率和變異概率的設(shè)置模式進(jìn)行了改進(jìn)。并設(shè)計(jì)了云遺傳算法來(lái)求解模型。最后，通過(guò)實(shí)例對(duì)模型和算法進(jìn)行了驗(yàn)證和分析。

韓亞娟（2018）等引入對(duì)客戶容忍水平的考慮，構(gòu)造出一種折線型軟時(shí)間窗的車(chē)輛路徑問(wèn)題的通用數(shù)學(xué)模型，設(shè)計(jì)了一種具有一定通用性的超啟發(fā)式遺傳算法，在該算法中以遺傳算法作為上層搜索算法，以三種啟發(fā)式算法——CW 節(jié)約法、MJ 插入法和 Kilby 插入作為底層搜索規(guī)則，通過(guò)預(yù)排序、局部搜索和全局優(yōu)化來(lái)改進(jìn)算法。劉艷秋（2016）等基于倉(cāng)儲(chǔ)集貨運(yùn)輸與路徑可行性的回收車(chē)輛路徑特性，對(duì)傳統(tǒng)蟻群算法的編碼方式、概率選擇方式進(jìn)行改進(jìn)，提出一種逆選擇操作蟻群算法。最后通過(guò)算例證明模型與算法的有效性。侯玉梅（2015）等基于整車(chē)物流配送問(wèn)題，以總成本最小化為目標(biāo)，構(gòu)建了帶軟時(shí)間窗約束的整車(chē)物流路徑優(yōu)化模型，并設(shè)計(jì)了自適應(yīng)遺傳算法，用算例對(duì)其進(jìn)行了驗(yàn)證。葛顯龍（2013）等基于不同車(chē)型線路優(yōu)化的匹配問(wèn)題，根據(jù)綜合費(fèi)用的不同制定車(chē)型分配原則，建立多車(chē)型車(chē)輛調(diào)度問(wèn)題的數(shù)學(xué)模型，設(shè)計(jì)了一種高效的量子遺傳算法，并通過(guò)實(shí)例驗(yàn)證了該模型和算法的有效性。

楊翔（2018）等基于模糊可信性理論建立了模糊需求模型，利用隨機(jī)模擬算法進(jìn)行客戶需求預(yù)測(cè)，并設(shè)計(jì)了一種兩階段禁忌搜索算法進(jìn)行仿真，并通過(guò)實(shí)例驗(yàn)證了該模型和算法的有效性。實(shí)驗(yàn)表明，決策保守程度對(duì)配送總成本存在明顯影響，過(guò)于保守或過(guò)于冒險(xiǎn)均不能獲得較好的路徑安排方案。肖建華（2017）等將根據(jù)城市道路的限制因素，如區(qū)域和車(chē)輛類(lèi)型，引入了車(chē)輛路徑問(wèn)題。以碳排放和運(yùn)輸總成本最小為目標(biāo)，建立了基于城市道路約束的多能源多車(chē)型混合汽車(chē)路徑優(yōu)化模型。提出了一種變鄰域搜索算法來(lái)求解該模型，并通過(guò)實(shí)例和大規(guī)模基準(zhǔn)驗(yàn)證了該模型和算法的有效性。王茜（2016）等考慮了多車(chē)槽、多車(chē)型雙重屬性，在構(gòu)建HFFMCVRP的三下標(biāo)流數(shù)學(xué)模型基礎(chǔ)上，將在反應(yīng)機(jī)理與導(dǎo)引機(jī)理相結(jié)合的基礎(chǔ)上，提出了一種混合導(dǎo)引反應(yīng)禁忌搜索算法，予以求解。馬華偉（2016）等建立了多卡車(chē)、單掛車(chē)的甩掛運(yùn)輸路徑規(guī)劃模型，設(shè)計(jì)禁忌搜索算法改進(jìn)初始解，并通過(guò)實(shí)例驗(yàn)證算法的可行性和有效性。Nourinejad（2015）等針對(duì)單向車(chē)輛共享不平衡問(wèn)題，提出了車(chē)輛搬遷與員工聯(lián)合優(yōu)化模型，并利用禁忌搜索算法進(jìn)行計(jì)算。通過(guò)實(shí)驗(yàn)得出結(jié)論：車(chē)隊(duì)規(guī)模對(duì)需求的敏感性大于員工規(guī)模，員工規(guī)模與車(chē)輛數(shù)成反比，車(chē)輛搬遷時(shí)間與車(chē)輛成本成正比。李進(jìn)（2013）等建立了以低碳為目標(biāo)的多車(chē)型路徑規(guī)劃模型，利用多起點(diǎn)禁忌搜索算法進(jìn)行求解，并通過(guò)實(shí)例驗(yàn)證了算法的可行性，證明了多起點(diǎn)策略的有效性。

王偉（2018）等基于車(chē)輛速度限制，建立了危險(xiǎn)貨物運(yùn)輸網(wǎng)絡(luò)優(yōu)化的兩層規(guī)劃模型，設(shè)計(jì)了粒子群優(yōu)化算法來(lái)求解兩層規(guī)劃模型。最后，通過(guò)兩個(gè)實(shí)例對(duì)模型和算法進(jìn)行了驗(yàn)證。證明車(chē)輛限速是兼顧企業(yè)利益，同時(shí)可以有效降低危險(xiǎn)品運(yùn)輸總風(fēng)險(xiǎn)的有效途徑。周和平（2017）等建立了區(qū)間阻抗下的魯棒最短路模型，基于模型設(shè)計(jì)了分支定界算法，并對(duì)一個(gè)大型路網(wǎng)進(jìn)行了仿真測(cè)試。結(jié)果表明：相對(duì)于最短路徑法，該方法求解得到的最短路徑具有更強(qiáng)的魯棒性，且求解結(jié)果準(zhǔn)確高效。牟向偉（2016）等針對(duì)車(chē)貨匹配問(wèn)題建立模型，并設(shè)計(jì)改進(jìn)量子進(jìn)化算法對(duì)模型進(jìn)行求解，結(jié)果表明，改進(jìn)的量子進(jìn)化算法可以高效地搜索到高質(zhì)量的車(chē)貨匹配方案，為車(chē)主和貨主推薦較為合理的匹配信息。Adam（2015）等基于車(chē)輛容量限制對(duì)多商品運(yùn)輸問(wèn)題進(jìn)行研究，提出了連續(xù)松弛整數(shù)規(guī)劃模型，建立了列生成算法，經(jīng)過(guò)對(duì)比驗(yàn)證了所建模型和算法的有效性，為多貨種車(chē)輛路徑優(yōu)化提供新方向。譚立靜（2015）等提出了一種通過(guò)對(duì)自適應(yīng)細(xì)菌覓食優(yōu)化算法的學(xué)習(xí)，并將其應(yīng)用于帶時(shí)間窗的車(chē)輛路徑問(wèn)題。通過(guò)模擬實(shí)驗(yàn)，證明該算法具有收斂速度快、搜索精度高的特點(diǎn)。潘國(guó)強(qiáng)（2015）等采用微粒群算法解決多客戶、多供應(yīng)商、多產(chǎn)品的路徑選擇問(wèn)題，在建立復(fù)雜供應(yīng)鏈的復(fù)雜映射關(guān)系的基礎(chǔ)上，引入綜合運(yùn)輸概念，選擇運(yùn)輸方式，設(shè)計(jì)配送路徑。

模擬植物生長(zhǎng)算法是李彤在2005年所提出來(lái)的，其本質(zhì)思想就是迭代運(yùn)算。算法參數(shù)設(shè)計(jì)簡(jiǎn)單，且具有很強(qiáng)的適用性，尤其對(duì)網(wǎng)絡(luò)優(yōu)化有著十分理想的效果。曹慶奎（2015）等基于客戶需求的隨機(jī)性特點(diǎn)，考慮外包車(chē)輛和配送人員加班等限制因素，建立了機(jī)會(huì)約束規(guī)劃模型，并設(shè)計(jì)了模擬植物生長(zhǎng)算法求解模型，證明了算法可以高效地獲得最優(yōu)解。Guerrero（2013）等針對(duì)零售企業(yè)復(fù)雜的末端配送系統(tǒng)，設(shè)計(jì)了混合整數(shù)線性規(guī)劃模型，提出了一種精確式混合啟發(fā)算法，通過(guò)實(shí)驗(yàn)證明與分解方法相比，該算法具有較好的解決該問(wèn)題的能力。

車(chē)輛路徑規(guī)劃問(wèn)題算法逐漸細(xì)化，愈發(fā)貼近實(shí)際生活。在追求降本增利的總目標(biāo)時(shí)，充分考慮“顧客需求穩(wěn)定性”、“城市運(yùn)輸車(chē)輛限制”以及“顧客的容忍程度”等客觀因素，并且作為算法的立足點(diǎn)。這樣的算法在實(shí)際應(yīng)用時(shí)更容易給組織帶來(lái)利益。

關(guān)于路徑優(yōu)化問(wèn)題的研究已經(jīng)發(fā)生了重大的轉(zhuǎn)變。研究環(huán)境變化：由傳統(tǒng)的單一車(chē)輛的調(diào)度問(wèn)題，轉(zhuǎn)變?yōu)樾枨蟮牟淮_定性、道路狀況的動(dòng)態(tài)性的復(fù)雜環(huán)境;研究目標(biāo)變化：由單純追求成本最小化，轉(zhuǎn)變?yōu)闄?quán)衡車(chē)輛總成本、能耗和污染物排放等，考慮距離、運(yùn)量和車(chē)速對(duì)成本、能耗和污染物排放的影響;研究客體轉(zhuǎn)變?yōu)槎嗄茉础⒍嘬?chē)型的車(chē)輛選擇;研究方法變化：由早期的簡(jiǎn)單分析方法，轉(zhuǎn)變?yōu)槎嗄Ｐ汀⒍嗨惴ā⒍鄬W(xué)科融合的綜合系統(tǒng)研究。

參考文獻(xiàn)

[1]范厚明，楊翔，李陽(yáng).基于生鮮品多中心聯(lián)合配送的半開(kāi)放式車(chē)輛路徑問(wèn)題[J].計(jì)算機(jī)集成制造系統(tǒng)，2016，（01）.

[2]Nekooghadirli N，Tavakkoli-Moghddam R，Ghezavati V R，et al.Solving a new bi-objective location-routing-inventory problem in a distribution network by meta-heuristics[J].Computers & Industrial Engineering，2014，（76）：204-221.

[3]曹慶奎，趙斐.基于遺傳蟻群算法的港口集卡路徑優(yōu)化[J].系統(tǒng)工程理論與實(shí)踐，2013，（077）：1820-1828.

[4]程博，楊育，劉愛(ài)軍，等.基于遺傳模擬退火算法的大件公路運(yùn)輸路徑選擇優(yōu)化[J].計(jì)算機(jī)集成制造系統(tǒng)，2013，（04）：879-887.

[5]葛顯龍，王旭，鄧?yán)?基于聯(lián)合配送的開(kāi)放式動(dòng)態(tài)車(chē)輛路徑問(wèn)題及算法研究[J].管理工程學(xué)報(bào)，2013，（03）：60-68.

[6]韓亞娟，彭運(yùn)芳，魏航，等.超啟發(fā)式遺傳算法求解帶軟時(shí)間窗的車(chē)輛路徑問(wèn)題[J].計(jì)算機(jī)集成制造系統(tǒng)，2015，（01）.

[7]劉艷秋，徐世達(dá)，張穎，等.考慮路徑可行性與倉(cāng)儲(chǔ)集貨模式下的回收車(chē)輛路徑問(wèn)題研究[J].中國(guó)管理科學(xué)，2016，（12）：98-107.

[8]侯玉梅，賈震環(huán)，田歆，等.帶軟時(shí)間窗整車(chē)物流配送路徑優(yōu)化研究[J].系統(tǒng)工程學(xué)報(bào)，2015，（02）：240-250.

[9]葛顯龍，許茂增，王偉鑫.多車(chē)型車(chē)輛路徑問(wèn)題的量子遺傳算法研究[J].中國(guó)管理科學(xué)，2013，（01）：125-133.

[10]楊翔，范厚明，徐振林，等.模糊需求下多中心開(kāi)放式車(chē)輛路徑優(yōu)化[J].計(jì)算機(jī)集成制造系統(tǒng)，2017，（01）.

[11]肖建華，王超文，陳萍，等.基于城市道路限行的多能源多車(chē)型車(chē)輛路徑優(yōu)化[J].系統(tǒng)工程理論與實(shí)踐，2017，（05）：1339-1348.

[12]王茜，吉清凱，胡祥培.多車(chē)型多車(chē)槽VRP的混合導(dǎo)引反應(yīng)式禁忌搜索算法[J].管理工程學(xué)報(bào)，2016，（03）：179-187.

[13]馬華偉，范奉偉，胡笑旋.基于禁忌搜索算法的甩掛運(yùn)輸路徑規(guī)劃問(wèn)題研究[J].中國(guó)管理科學(xué)，2016，（S1）：194-198.

[14] Nourinejad M，Zhu S，Bahrami S，et al.Vehicle relocation and staff rebalancing in one-way carsharing system[J].Transportation Research Part E：Logistics and Transportation Review，2015，（81）：98-113.

[15]李進(jìn)，傅培華.具有固定車(chē)輛數(shù)的多車(chē)型低碳路徑問(wèn)題及算法[J].計(jì)算機(jī)集成制造系統(tǒng)，2013，（06）：1351-1362.

[16]王偉，張宏剛，丁黎黎，等.考慮車(chē)輛限速和風(fēng)險(xiǎn)公平性的危險(xiǎn)品運(yùn)輸網(wǎng)絡(luò)雙目標(biāo)優(yōu)化模型[J].系統(tǒng)工程，2018，36（07）：91-104.

[17]周和平，馮軒，彭巍.區(qū)間阻抗下的魯棒最短路算法[J].系統(tǒng)工程，2017，35（12）：121-125.

[18]牟向偉，陳燕，高書(shū)娟，等.基于改進(jìn)量子進(jìn)化算法的車(chē)貨供需匹配方法研究[J].中國(guó)管理科學(xué)，2016，（12）：166-176.

[19] Adam N L，Juan S.Stronger multi-commodity flow formulations of the capacitated vehicle routing problem[J].European Journal of Operational Research，2015，244（3）：730-738.

[20]譚立靜，王紅，牛奔.基于ACLBFO算法的車(chē)輛路徑規(guī)劃[J].系統(tǒng)工程，2015，33（04）：120-125.

[21]潘國(guó)強(qiáng)，胡俊逸，洪敏.面向綜合運(yùn)輸網(wǎng)絡(luò)的復(fù)雜供應(yīng)鏈問(wèn)題建模與耦合求解算法[J].計(jì)算機(jī)集成制造系統(tǒng)，2015，（11）：3041-3053.

[22]曹慶奎，劉新雨，任向陽(yáng).基于模擬植物生長(zhǎng)算法的車(chē)輛調(diào)度問(wèn)題[J].系統(tǒng)工程理論與實(shí)踐，2015，（06）：1449-1456.

[23] Guerrero W J，Prodhon C，Velasco N，et al.Hybird heuristic for inventory location-routing problem with deterministic demand[J].International Journal of Production Economics，2013，146（1）：359-370.