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

何鴻康

(重慶交通大學(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ā)展的黃金時期，這就給我們的城市配送、旅客運(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ā)了城市擁堵、配送成本高、配送時間長、城市污染等現(xiàn)象，成為城市配送、旅客運(yùn)輸業(yè)務(wù)發(fā)展的瓶頸。鑒于選址-路徑優(yōu)化問題的重大理論意義和實(shí)踐價值，有必要對國內(nèi)外現(xiàn)有的選址-路徑優(yōu)化問題的研究成果進(jìn)行歸納和分析。

一、LRP問題分類

(一)帶時間窗LRP問題

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

(二)模糊條件LRP問題

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

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

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

(四)帶容積約束LRP問題

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

(五)多車型LRP問題

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

(六)多級LRP問題

目前學(xué)者們主要對兩級LRP問題進(jìn)行研究。Rahmani[13]在研究兩級LRP問題時，同時考慮多產(chǎn)品、收發(fā)貨以及配送問題，建立帶有收發(fā)貨和交付兩級多產(chǎn)品LRP模型，采用混合整數(shù)線性規(guī)劃方法求得最優(yōu)方案。Grangier[14]在研究使用兩級車隊(duì)運(yùn)輸物品的LRP問題時，結(jié)合城市物流時間窗約束，并采用自適應(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ù)對評價權(quán)重進(jìn)行分析，以中心倉庫位置與集散系統(tǒng)到客戶路線為目標(biāo)建立模型，并采用模擬退火算法進(jìn)行求解，從而降低了整個網(wǎng)絡(luò)成本。

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

針對多節(jié)點(diǎn)問題，一般采用啟發(fā)式算法獲取多節(jié)點(diǎn)LRP問題的近似最優(yōu)解。Montoya[17]對多節(jié)點(diǎn)車輛路徑問題進(jìn)行綜述，并對時間窗、分割交付、異構(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安排問題，并首先采用禁忌搜索算法求得一個較好的設(shè)施位置，再利用蟻群算法獲得對應(yīng)的優(yōu)化運(yùn)輸路線。

二、研究方法

(一)精確算法

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

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

本文綜述的LRP問題啟發(fā)式算法主要包括：蟻群算法、遺傳算法、變領(lǐng)域搜索算法以及各種混合算法。在涉及啟發(fā)式算法研究文獻(xiàn)中，主要運(yùn)用模擬退火算法解決帶時間窗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)、模糊條件以及帶時間窗的LRP問題。對LRP優(yōu)化問題的求解主要采用了啟發(fā)式算法，同時精確算法也有所應(yīng)用。隨著人們對于城市道路交通擁堵問題的關(guān)注，本文認(rèn)為LRP優(yōu)化問題還將在以下兩個方面繼續(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ì)性與最低的碳排放來滿足客戶需求，同時使得物流企業(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í)時變化的，因此未來LRP優(yōu)化問題的實(shí)證研究將成為研究的熱點(diǎn)。

[1]羅耀波, 孫延明, 廖鵬. 帶退貨和軟時間窗的多倉庫選址-路徑問題研究[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)險的不確定需求應(yīng)急物流定位-路徑問題[J]. 上海交通大學(xué)學(xué)報, 2013, 47(6): 962-966.

[6]趙佳虹. 時變條件下應(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]李雙琳, 馬祖軍, 鄒坤. 危險品物流中的多目標(biāo)定位-路徑問題[J]. 運(yùn)籌與管理, 2014(3): 8-15.

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

[10]羅耀波. 基于模糊時間窗的同時送取貨選址路徑規(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é)報(自然科學(xué)版), 2006, 26(3): 80-83.

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