考慮路徑優化的共同配送站點選址研究

豆訓博+李莉

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

[關鍵詞]路徑優化；配送站點；選址

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

配送站點的選址問題（Common distribution site location）是指需求點委托相應的供應商統一在某個地區建立配送站點，集中來自不同供應商的貨物，然后向自己所輻射的范圍內進行集中配送。

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

1 問題描述與數學模型

考慮路徑優化的選址問題可描述為：從配送站點出發的車輛對轄區范圍內的需求點進行產品配送，結合相應約束要求（比如，車輛容量或者是時間窗約束條件）進行配送，配送結束后，車輛最終返回配送站點。然而，運輸路徑的長短在運費和配送效率方面至關重要。

1.1 共同配送站點CVRP問題選址模型

CVRP問題選址可描述為：從配送站點出發的車輛，結合車輛載重量約束，對輻射范圍內的需求點進行產品配送，配送結束后，車輛最終返回配送站點的過程。

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

1.2 共同配送站點CVRPTW問題選址模型

CVRPTW問題選址可描述為：從配送站點出發的車輛，結合車輛載重量和配送時間窗等雙重約束，對輻射范圍內的需求點進行產品配送，車輛在完成所有需求點服務后，最終返回配送站點的過程。

同樣，為了便于建立選址模型，相應的假設應滿足以下條件：①滿足每個需求點的配送要求，且由一輛配送車輛進行送貨作業；②車輛在完成所有需求點服務后，最后返回配送站點；③配送車輛的最大載重量應大于等于該配送路徑上各需求點的需求量之和；④各個需求點配送活動應在限制的時間窗范圍內完成。

2 應用實例與結果分析

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

以表1和表2的數據為基礎，根據CVRP問題選址模型編寫Lingo程序，以直銷點2作為備選站點為例，求得全局最優距離為20.45203km。同理，分別選取直銷點9、直銷點15得到全局最優解。其最終結果如表3所示。

從表3可知，依據CVRP問題選址模型，路徑長度20.45203（直銷點2）>20.39479（直銷點9）>20.31292（直銷點15）。因此，應當選擇直銷點15作為配送站點為烏魯木齊市社區蔬菜配送直銷點進行配送作業。

因此，根據CVRPTW問題選址模型編寫程序，以直銷點2作為備選站點為例，同樣可求得全局最優總距離為30.34672km。同理，分別選取直銷點9、直銷點15得到全局最優解。最終結果如表4所示。

從表4可知，依據CVRPTW問題選址模型，路徑長度30.34672（直銷點2）>28.56790（直銷點15）>27.91033（直銷點9），所以，應當選擇直銷點9作為配送站點，為烏魯木齊市社區蔬菜配送直銷點進行配送作業。

3 結 論

為了解決城市物流配送站點選址問題，本文從實際出發，構建了考慮容量、時間窗約束的選址模型，采用能夠快速求解線性問題的Lingo軟件進行求解。結合實例表明，Lingo軟件是一種快速有效求解配送站點選址的方法，能夠快速求得選址問題最優解。

參考文獻：

[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]謝金星，薛毅.優化建模與Lindo/Lingo軟件[M].北京：清華大學出版社，2005（7）.

[4]牛永亮，王金妹.物流配送車輛路線求解算法[J].交通運輸工程學報，2006，6（2）：83-87.

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