考慮路徑優(yōu)化的共同配送站點(diǎn)選址研究

豆訓(xùn)博+李莉

[摘 要]為了降低物流配送距離，提高城市物流的配送效率，文章提出以配送路線最小化為目標(biāo)，分別建立考慮配送車(chē)輛容量和時(shí)間窗約束下的兩種物流配送路徑優(yōu)化模型。并采用Lingo軟件快速求解線性規(guī)劃問(wèn)題的優(yōu)勢(shì)，引用實(shí)例分析，最終求得不同模型下的配送選址最優(yōu)解。

[關(guān)鍵詞]路徑優(yōu)化；配送站點(diǎn)；選址

[DOI]10.13939/j.cnki.zgsc.2017.15.216

配送站點(diǎn)的選址問(wèn)題（Common distribution site location）是指需求點(diǎn)委托相應(yīng)的供應(yīng)商統(tǒng)一在某個(gè)地區(qū)建立配送站點(diǎn)，集中來(lái)自不同供應(yīng)商的貨物，然后向自己所輻射的范圍內(nèi)進(jìn)行集中配送。

考慮路徑優(yōu)化的配送站點(diǎn)選址是指多輛配送車(chē)輛從共同配送站點(diǎn)出發(fā)，按照一定的路徑配送給各個(gè)需求點(diǎn)，每個(gè)需求點(diǎn)只能被訪問(wèn)一次。目前在Lingo語(yǔ)言求解選址方面，Massimo Paolucci（2011）在Vehicle Routing Problem 中建立了相應(yīng)的配送路徑時(shí)間窗求解模型（VRPTW）；王林等（2008）在一般要求下建立混合整數(shù)規(guī)劃選址模型來(lái)確定配送站點(diǎn)選址最佳方案；丁曉東等（2009）建立0～1混合整數(shù)規(guī)劃模型求解選址問(wèn)題；徐麗蕊（2013）在求解路徑優(yōu)化模型中討論了考慮容量約束配送路徑優(yōu)化問(wèn)題。本文主要討論：一是考慮車(chē)輛載重量約束；二是進(jìn)行載重量和時(shí)間窗雙重約束條件，建立數(shù)學(xué)模型，然后基于Lingo軟件進(jìn)行配送站點(diǎn)的選址進(jìn)行求解，得出最優(yōu)的路徑長(zhǎng)度。

1 問(wèn)題描述與數(shù)學(xué)模型

考慮路徑優(yōu)化的選址問(wèn)題可描述為：從配送站點(diǎn)出發(fā)的車(chē)輛對(duì)轄區(qū)范圍內(nèi)的需求點(diǎn)進(jìn)行產(chǎn)品配送，結(jié)合相應(yīng)約束要求（比如，車(chē)輛容量或者是時(shí)間窗約束條件）進(jìn)行配送，配送結(jié)束后，車(chē)輛最終返回配送站點(diǎn)。然而，運(yùn)輸路徑的長(zhǎng)短在運(yùn)費(fèi)和配送效率方面至關(guān)重要。

1.1 共同配送站點(diǎn)CVRP問(wèn)題選址模型

CVRP問(wèn)題選址可描述為：從配送站點(diǎn)出發(fā)的車(chē)輛，結(jié)合車(chē)輛載重量約束，對(duì)輻射范圍內(nèi)的需求點(diǎn)進(jìn)行產(chǎn)品配送，配送結(jié)束后，車(chē)輛最終返回配送站點(diǎn)的過(guò)程。

為了便于建立選址模型，相應(yīng)的假設(shè)滿足以下條件：①滿足每個(gè)需求點(diǎn)的配送要求，且由一輛配送車(chē)輛進(jìn)行送貨作業(yè)；②車(chē)輛在完成所有需求點(diǎn)服務(wù)后，最后返回配送站點(diǎn)；③配送車(chē)輛的最大載重量應(yīng)大于等于該配送路徑上各需求點(diǎn)的需求量之和。

1.2 共同配送站點(diǎn)CVRPTW問(wèn)題選址模型

CVRPTW問(wèn)題選址可描述為：從配送站點(diǎn)出發(fā)的車(chē)輛，結(jié)合車(chē)輛載重量和配送時(shí)間窗等雙重約束，對(duì)輻射范圍內(nèi)的需求點(diǎn)進(jìn)行產(chǎn)品配送，車(chē)輛在完成所有需求點(diǎn)服務(wù)后，最終返回配送站點(diǎn)的過(guò)程。

同樣，為了便于建立選址模型，相應(yīng)的假設(shè)應(yīng)滿足以下條件：①滿足每個(gè)需求點(diǎn)的配送要求，且由一輛配送車(chē)輛進(jìn)行送貨作業(yè)；②車(chē)輛在完成所有需求點(diǎn)服務(wù)后，最后返回配送站點(diǎn)；③配送車(chē)輛的最大載重量應(yīng)大于等于該配送路徑上各需求點(diǎn)的需求量之和；④各個(gè)需求點(diǎn)配送活動(dòng)應(yīng)在限制的時(shí)間窗范圍內(nèi)完成。

2 應(yīng)用實(shí)例與結(jié)果分析

本文以烏魯木齊市社區(qū)蔬菜配送直銷(xiāo)點(diǎn)作為需求點(diǎn)進(jìn)行分析，假設(shè)社區(qū)有16個(gè)社區(qū)配送直銷(xiāo)點(diǎn)，需要建立一個(gè)配送站點(diǎn)，根據(jù)實(shí)地考察和專(zhuān)家意見(jiàn)，從中選出了3個(gè)地點(diǎn)，分別為直銷(xiāo)點(diǎn)2、直銷(xiāo)點(diǎn)9和直銷(xiāo)點(diǎn)15作為備選配送站點(diǎn)，結(jié)合本文兩種模型選出最優(yōu)的一個(gè)備選配送站點(diǎn)作為其他社區(qū)直銷(xiāo)點(diǎn)的配送站點(diǎn)，該配送站點(diǎn)將擁有2噸的貨車(chē)10輛進(jìn)行配送作業(yè)活動(dòng)，運(yùn)行速度30km/h，允許的最大運(yùn)行時(shí)間為2h，允許的最大運(yùn)行距離為30km，其中ai表示為直銷(xiāo)點(diǎn)i的允許最早時(shí)間，bi表示直銷(xiāo)點(diǎn)i的最晚時(shí)間，[JB（[]ai，bi[JB）]]為需求點(diǎn)i所要求服務(wù)的時(shí)間范圍，各個(gè)需求點(diǎn)坐標(biāo)及需求量如表1所示；各個(gè)社區(qū)蔬菜直銷(xiāo)點(diǎn)的服務(wù)時(shí)間范圍如表2所示。

以表1和表2的數(shù)據(jù)為基礎(chǔ)，根據(jù)CVRP問(wèn)題選址模型編寫(xiě)Lingo程序，以直銷(xiāo)點(diǎn)2作為備選站點(diǎn)為例，求得全局最優(yōu)距離為20.45203km。同理，分別選取直銷(xiāo)點(diǎn)9、直銷(xiāo)點(diǎn)15得到全局最優(yōu)解。其最終結(jié)果如表3所示。

從表3可知，依據(jù)CVRP問(wèn)題選址模型，路徑長(zhǎng)度20.45203（直銷(xiāo)點(diǎn)2）>20.39479（直銷(xiāo)點(diǎn)9）>20.31292（直銷(xiāo)點(diǎn)15）。因此，應(yīng)當(dāng)選擇直銷(xiāo)點(diǎn)15作為配送站點(diǎn)為烏魯木齊市社區(qū)蔬菜配送直銷(xiāo)點(diǎn)進(jìn)行配送作業(yè)。

因此，根據(jù)CVRPTW問(wèn)題選址模型編寫(xiě)程序，以直銷(xiāo)點(diǎn)2作為備選站點(diǎn)為例，同樣可求得全局最優(yōu)總距離為30.34672km。同理，分別選取直銷(xiāo)點(diǎn)9、直銷(xiāo)點(diǎn)15得到全局最優(yōu)解。最終結(jié)果如表4所示。

從表4可知，依據(jù)CVRPTW問(wèn)題選址模型，路徑長(zhǎng)度30.34672（直銷(xiāo)點(diǎn)2）>28.56790（直銷(xiāo)點(diǎn)15）>27.91033（直銷(xiāo)點(diǎn)9），所以，應(yīng)當(dāng)選擇直銷(xiāo)點(diǎn)9作為配送站點(diǎn)，為烏魯木齊市社區(qū)蔬菜配送直銷(xiāo)點(diǎn)進(jìn)行配送作業(yè)。

3 結(jié) 論

為了解決城市物流配送站點(diǎn)選址問(wèn)題，本文從實(shí)際出發(fā)，構(gòu)建了考慮容量、時(shí)間窗約束的選址模型，采用能夠快速求解線性問(wèn)題的Lingo軟件進(jìn)行求解。結(jié)合實(shí)例表明，Lingo軟件是一種快速有效求解配送站點(diǎn)選址的方法，能夠快速求得選址問(wèn)題最優(yōu)解。

參考文獻(xiàn)：

[1]Angela L.Rademeyer.The Assignment Routing Problem with Nominated Delivery Days（ARPNDD）：Definition and Solution Heuristics [C].University of Illinois Press，2008，pp.1-120.

[2] Swagath Janakiraman.Truck Routing Problem in Distribution of Gasoline to Gas Stations[C].University of The Pennsylvania State，2010，pp.1-94.

[3]謝金星，薛毅.優(yōu)化建模與Lindo/Lingo軟件[M].北京：清華大學(xué)出版社，2005（7）.

[4]牛永亮，王金妹.物流配送車(chē)輛路線求解算法[J].交通運(yùn)輸工程學(xué)報(bào)，2006，6（2）：83-87.

[5]徐麗蕊.基于LINGO的城市物流配送路徑優(yōu)化[J].電子設(shè)計(jì)工程，2013，21（22）：52-54.