何鴻康

(重慶交通大學(xué)管理學(xué)院 重慶 400074)

選址-路徑優(yōu)化問題研究綜述

何鴻康

(重慶交通大學(xué)管理學(xué)院 重慶 400074)

設(shè)施節(jié)點(diǎn)選址以及城市配送引發(fā)的城市交通擁堵、配送成本高等問題制約著交通運(yùn)輸相關(guān)行業(yè)的發(fā)展，運(yùn)用選址-路徑優(yōu)化模型分析城市道路交通運(yùn)輸問題，是解決城市擁堵的重要途徑。本文綜述了2011～2016年國內(nèi)外有關(guān)選址-路徑優(yōu)化(Location Routing Problem)的文獻(xiàn)，并按問題類別與求解模型分類，最后提出了未來選址-路徑問題研究方向。

交通運(yùn)輸；選址-路徑優(yōu)化；文獻(xiàn)綜述；分析方法

引言

我國目前正處于交通運(yùn)輸行業(yè)發(fā)展的黃金時(shí)期，這就給我們的城市配送、旅客運(yùn)輸?shù)葮I(yè)務(wù)帶來了巨大的市場機(jī)遇。城市配送、旅客運(yùn)輸?shù)葮I(yè)務(wù)的發(fā)展離不開設(shè)施選址與路徑優(yōu)化的支持與支撐，而現(xiàn)階段設(shè)施選址與車輛調(diào)度不合理、車輛配送線路不經(jīng)濟(jì)等問題，制約了城市配送、旅客運(yùn)輸業(yè)務(wù)的發(fā)展，引發(fā)了城市擁堵、配送成本高、配送時(shí)間長、城市污染等現(xiàn)象，成為城市配送、旅客運(yùn)輸業(yè)務(wù)發(fā)展的瓶頸。鑒于選址-路徑優(yōu)化問題的重大理論意義和實(shí)踐價(jià)值，有必要對國內(nèi)外現(xiàn)有的選址-路徑優(yōu)化問題的研究成果進(jìn)行歸納和分析。

一、LRP問題分類

(一)帶時(shí)間窗LRP問題

對于帶時(shí)間窗的LRP問題的研究主要結(jié)合多節(jié)點(diǎn)、需求與旅行時(shí)間不確定性等方面。羅耀波[1]通過建立帶退貨和軟時(shí)間窗的多倉庫LRP數(shù)學(xué)模型，解決集成物流網(wǎng)絡(luò)問題。Wang[2]則采用自適應(yīng)變領(lǐng)域搜索與強(qiáng)化禁忌搜索算法，解決帶時(shí)間窗的電動汽車充電站選址問題與車輛路徑優(yōu)化問題。針對客戶需求與旅行時(shí)間的不確定性，Zarandi[3]建立帶時(shí)間窗的位置-路徑模糊約束規(guī)劃模型，并采用模擬退化算法求解。

(二)模糊條件LRP問題

目前關(guān)于模糊條件下LRP問題的研究，研究重點(diǎn)在于客戶需求不確定性、旅行時(shí)間不確定性兩方面。針對同時(shí)具有模糊需求和模糊時(shí)間等多約束條件問題，張曉楠[4]建立變動補(bǔ)償?shù)臋C(jī)會約束預(yù)優(yōu)化模型，同時(shí)引入時(shí)間懲罰成本修正，得到實(shí)時(shí)調(diào)整變動幅度小且整體最優(yōu)的預(yù)優(yōu)化方案。針對應(yīng)急物資配送需求和運(yùn)輸時(shí)間的不確定性，孫華麗[5]構(gòu)造基于隨機(jī)機(jī)會約束規(guī)劃的多目標(biāo)應(yīng)急物流定位-路徑模型，并引入處罰函數(shù)處理約束條件，最后通過算例驗(yàn)證模型的可行性。

(三)多目標(biāo)LRP問題

在多目標(biāo)LRP問題研究方面，主要從時(shí)間和費(fèi)用最小化、總的環(huán)境影響、客戶需求最大化以及最小處理量等目標(biāo)著手進(jìn)行優(yōu)化。趙佳虹[6]考慮時(shí)變條件下應(yīng)急物資類別多樣性以及物流中心最小處理量要求，以時(shí)間和費(fèi)用最小化為目標(biāo)，建立混合整數(shù)線性規(guī)劃模型，優(yōu)化方案費(fèi)用和時(shí)間消耗。針對同一問題，陳剛[7]則運(yùn)用帶精英策略的快速非支配排序遺傳算法求解該問題，并與變權(quán)目標(biāo)遺傳算法對比，證明該方法能夠得到更高質(zhì)量的帕累托最優(yōu)解。李雙琳[8]在研究?；愤\(yùn)輸問題時(shí)，構(gòu)造?；范嗉壟渌椭行摹⒍嗄繕?biāo)LRP優(yōu)化模型，設(shè)計(jì)遺傳算法得到最優(yōu)解，有效控制風(fēng)險(xiǎn)。

(四)帶容積約束LRP問題

容積約束作為LRP問題的一種約束條件，多與不確定性條件、多節(jié)點(diǎn)問題等相結(jié)合進(jìn)行研究。針對客戶彈性預(yù)約服務(wù)時(shí)間問題，羅耀波[9]以容量約束為基礎(chǔ)，總成本最小和客戶滿意度最高為原則，采用兩階段模擬退火算法求解基于模糊時(shí)間窗的有容量限制的雙目標(biāo)LRP徑優(yōu)化問題，同時(shí)，為了解決同時(shí)送取貨問題，結(jié)合客戶需求多樣性與時(shí)間不確定性，建立基于模糊時(shí)間窗的同時(shí)送取貨的多車型、多倉庫選址路徑模型，并采用改進(jìn)兩階段自適應(yīng)遺傳算法進(jìn)行求解[10]。

(五)多車型LRP問題

目前單獨(dú)研究多車型LRP問題的文獻(xiàn)較少，多與多級配送與車輛容量限制問題相結(jié)合研究。石兆[11]首先采用改進(jìn)聚類分析方法確定配送中心、服務(wù)群位置，然后采用遺傳算法很好地解決了包含不同車型、車輛容量、時(shí)間窗等約束的配送選址-多車型運(yùn)輸路徑優(yōu)化問題。趙崤含[12]在研究污水處理廠選址-配送問題時(shí)，充分考慮車輛容量以及設(shè)施容量等約束，在此基礎(chǔ)上構(gòu)建多設(shè)施多車型的有容量限制的LRP模型，采用遺傳算法求解得到優(yōu)化的設(shè)施選址與路徑。

(六)多級LRP問題

目前學(xué)者們主要對兩級LRP問題進(jìn)行研究。Rahmani[13]在研究兩級LRP問題時(shí)，同時(shí)考慮多產(chǎn)品、收發(fā)貨以及配送問題，建立帶有收發(fā)貨和交付兩級多產(chǎn)品LRP模型，采用混合整數(shù)線性規(guī)劃方法求得最優(yōu)方案。Grangier[14]在研究使用兩級車隊(duì)運(yùn)輸物品的LRP問題時(shí)，結(jié)合城市物流時(shí)間窗約束，并采用自適應(yīng)大鄰域搜索求解。基于應(yīng)急物資配送依托多級應(yīng)急物流中心的特點(diǎn)，楊恩緣[15]考慮應(yīng)急物流中心容量限制，運(yùn)用混合整數(shù)規(guī)劃模型求解，實(shí)現(xiàn)最小運(yùn)輸成本的選址-路徑優(yōu)化。針對制造商、零售商以及客戶組成的三級網(wǎng)絡(luò)定位-路線問題，Torfi[16]首先采用梯形模糊數(shù)對評價(jià)權(quán)重進(jìn)行分析，以中心倉庫位置與集散系統(tǒng)到客戶路線為目標(biāo)建立模型，并采用模擬退火算法進(jìn)行求解，從而降低了整個(gè)網(wǎng)絡(luò)成本。

(七)多節(jié)點(diǎn)LRP問題

針對多節(jié)點(diǎn)問題，一般采用啟發(fā)式算法獲取多節(jié)點(diǎn)LRP問題的近似最優(yōu)解。Montoya[17]對多節(jié)點(diǎn)車輛路徑問題進(jìn)行綜述，并對時(shí)間窗、分割交付、異構(gòu)車隊(duì)、定期交付等問題進(jìn)行研究?；诙喙?jié)點(diǎn)多旅行商問題與LRP問題的聯(lián)系，Benavent[18]采用分支和切割算法研究多方面誘導(dǎo)的不均衡性，證明該方法同樣適用于選址-路徑問題?；诙鄠}庫配送中倉庫選擇與共享商品交付問題，Ray[19]建立多段拆分車輛路徑模型，并采用啟發(fā)式算法求解在同一目標(biāo)函數(shù)下允許建立的符合客戶要求的倉庫位置與車路徑。胡大偉[20]建立單設(shè)施LRP問題模型，利用空間填充曲線構(gòu)造初始解，并采用動態(tài)規(guī)劃方法確定最優(yōu)車輛配置。萬鳳嬌[21]考慮單獨(dú)研究物流設(shè)施選址和車輛運(yùn)輸路線安排問題的局限性，提出了多倉庫LRP安排問題，并首先采用禁忌搜索算法求得一個(gè)較好的設(shè)施位置，再利用蟻群算法獲得對應(yīng)的優(yōu)化運(yùn)輸路線。

二、研究方法

(一)精確算法

在選址-路徑優(yōu)化涉及精確算法研究中，主要運(yùn)用混合整數(shù)規(guī)劃方法來解決多目標(biāo)時(shí)變LRP問題[6]、多級LRP問題[13][15]。在上述研究中，對于多節(jié)點(diǎn)多旅行商LRP問題也采用分支定界[18]方法求解，此外，胡大偉等[20]采用了動態(tài)規(guī)劃方法。

(二)啟發(fā)式算法

本文綜述的LRP問題啟發(fā)式算法主要包括：蟻群算法、遺傳算法、變領(lǐng)域搜索算法以及各種混合算法。在涉及啟發(fā)式算法研究文獻(xiàn)中，主要運(yùn)用模擬退火算法解決帶時(shí)間窗LRP問題[3]、三級網(wǎng)絡(luò)LRP問題[16]、帶容積約束LRP問題[9]。對于?；范嗉?多目標(biāo)運(yùn)輸問題[8]、帶容積約束LRP問題[10]、多車型LRP問題[11][12]采用遺傳算法進(jìn)行求解。除此以外Wang等[2]、萬鳳嬌[21]采用了禁忌搜索算法，羅耀波[1]采用了混合遺傳算法，Grangier等[14]采用了自適應(yīng)搜索算法。

三、 結(jié)論與發(fā)展趨勢

通過對以上LRP問題研究文獻(xiàn)的分析，學(xué)者們對LRP優(yōu)化問題重點(diǎn)關(guān)注多節(jié)點(diǎn)、多目標(biāo)、模糊條件以及帶時(shí)間窗的LRP問題。對LRP優(yōu)化問題的求解主要采用了啟發(fā)式算法，同時(shí)精確算法也有所應(yīng)用。隨著人們對于城市道路交通擁堵問題的關(guān)注，本文認(rèn)為LRP優(yōu)化問題還將在以下兩個(gè)方面繼續(xù)深入探討研究：

(一)可持續(xù)的配送LRP優(yōu)化

隨著經(jīng)濟(jì)的不斷發(fā)展，城市不斷擴(kuò)張，汽車保有量逐年升高，從而引發(fā)了嚴(yán)重的交通擁堵問題以及環(huán)境問題。為了適應(yīng)交通大環(huán)境的要求，后續(xù)對于LRP問題的研究應(yīng)該考慮在交通限行條件下，如何以最高的燃油經(jīng)濟(jì)性與最低的碳排放來滿足客戶需求，同時(shí)使得物流企業(yè)自身利益最大化，從而建立可持續(xù)的配送路徑優(yōu)化效果。

(二)動態(tài)LRP優(yōu)化

隨著選址-路徑優(yōu)化理論研究的進(jìn)一步深入，已經(jīng)逐步建立了LRP問題研究基本框架，然而，目前對于LRP優(yōu)化問題的研究主要集中于算法的創(chuàng)新以及約束條件增加，缺少實(shí)際數(shù)據(jù)作為支撐。在現(xiàn)實(shí)情況下，客戶需求、車輛調(diào)度等條件都是實(shí)時(shí)變化的，因此未來LRP優(yōu)化問題的實(shí)證研究將成為研究的熱點(diǎn)。

[1]羅耀波, 孫延明, 廖鵬. 帶退貨和軟時(shí)間窗的多倉庫選址-路徑問題研究[J]. 運(yùn)籌與管理, 2014, 2014(5): 78-85.

[2]Wang L Y, Song Y B. Multiple Charging Station Location-Routing Problem with Time Window of Electric Vehicle[J]. Journal Of Engineering Science & Technology Review, 2015, 8(5): 190-201.

[3]Fazel Zarandi M H, Hemmati A, Davari S, et al. Capacitated location-routing problem with time windows under uncertainty[J]. Knowledge-Based Systems, 2013, 37(2): 480-489.

[4]張曉楠, 范厚明, 李劍鋒. 變動補(bǔ)償?shù)亩嗄：x址-路徑機(jī)會約束模型及算法[J]. 系統(tǒng)工程理論與實(shí)踐, 2016(2): 442-453.

[5]孫華麗, 周戰(zhàn)杰, 薛耀鋒. 考慮路徑風(fēng)險(xiǎn)的不確定需求應(yīng)急物流定位-路徑問題[J]. 上海交通大學(xué)學(xué)報(bào), 2013, 47(6): 962-966.

[6]趙佳虹. 時(shí)變條件下應(yīng)急物流多目標(biāo)LRP研究[J]. 公路交通科技, 2012, 29(4): 137-142+148.

[7]陳剛, 付江月. 基于NSGAII的應(yīng)急物流多目標(biāo)LRP研究[J]. 軟科學(xué), 2016(4): 135-139.

[8]李雙琳, 馬祖軍, 鄒坤. 危險(xiǎn)品物流中的多目標(biāo)定位-路徑問題[J]. 運(yùn)籌與管理, 2014(3): 8-15.

[9]羅耀波, 孫延明. 基于模糊時(shí)間窗的帶容積約束選址路徑問題[J]. 系統(tǒng)工程, 2014(1): 19-25.

[10]羅耀波. 基于模糊時(shí)間窗的同時(shí)送取貨選址路徑規(guī)劃模型研究[D].華南理工大學(xué), 2014.

[11]石兆, 符卓. 配送選址-多車型運(yùn)輸路徑優(yōu)化問題及求解算法[J]. 計(jì)算機(jī)科學(xué), 2015, 42(5): 245-250.

[12]趙崤含, 李冰毅, 石詠, 郭海湘, 周欣然, 潘雯雯. 基于遺傳算法的污水處理廠選址-配送問題集成研究[J]. 物流技術(shù), 2015, 34(11): 136-141.

[13]Rahmani Y, Cherifkhettaf W R, Oulamara The two-echelon multi-products location-routing problem with pick-up and delivery: formulation and heuristic approaches[J]. International Journal Of Production Research, 2015, 54(4): 999-1019.

[14]Grangier P, Gendreau M, Lehuédé F, et al. An adaptive large neighborhood search for the two-echelon multiple-trip vehicle routing problem with satellite synchronization[J]. European Journal of Operational Research, 2014, 254(1): 80-91.

[15]楊恩緣, 李進(jìn), 嚴(yán)翌嫻, 黃文耀. 震后多品種應(yīng)急物資多級配送中的選址-路徑模型[J]. 災(zāi)害學(xué), 2016, 2016(2): 200-205.

[16]Torfi F, Farahani RZ, Mahdavi I. Fuzzy MCDM for weight of object’s phrase in location routing problem[J]. Applied Mathematical Modeling, 2015, 40(1): 526-541.

[17]Montoya-Torres J R, Franco J L, Isaza S N, et al. A literature review on the vehicle routing problem with multiple depots[J]. Computers & Industrial Engineering, 2015, 79: 115-129.

[18]Benavent E, Martinez A. Multi-depot Multiple TSP: a polyhedral study and computational results[J]. Annals Of Operations Research, 2013, 207(207): 7-25.

[19]Ray S, Soeanu A, Berger J, Debbabi M. The multi-depot split-delivery vehicle routing problem: Model and solution algorithm[J]. Knowledge-Based Systems, 2014, 71: 238-265.

[20]胡大偉, 胡勇, 朱志強(qiáng). 基于空間填充曲線和動態(tài)規(guī)劃解的定位路線問題[J]. 長安大學(xué)學(xué)報(bào)(自然科學(xué)版), 2006, 26(3): 80-83.

[21]萬鳳嬌. 多倉庫定位-運(yùn)輸路線安排問題的模型和算法研究[J]. 江漢大學(xué)學(xué)報(bào)(自然科學(xué)版), 2012, 40(3): 26-32.