基于混合算法的雙向物流路徑優化問題的研究

劉艷秋　楊勇

【摘 要】本文針對雙向物流的特點，重點分析研究了車輛配送的策略。為了更好地協調車輛進行路徑選擇和運輸成本間的關系，以及更好地考慮綜合因素及實際情況進行節點間的選擇，針對雙向物流路徑問題的研究方法，建立了優化路徑的極小化數學模型。最后針對路徑優化方法及研究狀況，采用了聚類分析及蟻群算法，并經仿真驗證，結果合理有效。

【關鍵詞】物流配送；雙向物流；物流路徑優化；蟻群算法；減法聚類

Two-way Logistics Path Optimization Problems Based on Clustering Analysis Research

LIU Yan-qiu YANG Yong

（Shenyang University of Technology， Shenyang Liaoning 110000， China）

【Abstract】According to the characteristics of two-way logistics， this paper focus on analysis and research the vehicles distribution. In order to better coordinate the vehicle path selection and the relationship between transport costs， and better conditions for considering comprehensive factors and the choice between nodes， study of two-way logistics path problem method， established the mathematical model of optimal path minimization. Finally based on path optimization method and the research situation， adopted the cluster analysis and the ant colony algorithm， and it has been verified by the simulation， the results reasonable and effective.

【Key words】Logistics distribution； Two-way logistics； Logistics path optimization； Ant colony algorithm； Subtraction clustering

0 引言

物流配送在物流管理中占有重要地位，它是指按照客戶的訂貨需求，在配送中心進行分貨、配貨，并調度車輛及時為客戶配送貨物[1]。車輛路徑問題（vehicle routing problem，VRP）是車輛配送研究中最核心的問題，一直是組合優化領域的熱點和前沿問題[2]，而雙向物流路徑優化問題（vehicle routing problem with simultaneous delivery and pickup，VRPSDP）是VRP問題中的一個典型，它是指同時帶送貨取貨的物流車輛路徑優化問題，既考慮了客戶需要的貨物從配送中心送到各個客戶，又需要把客戶需要回送的貨物運回到配送中心，要求取貨送貨同時進行，因此比單向物流問題還要復雜，也是一種NP-hard難題，所以求解復雜度較高，計算量較大。本文在前人研究的基礎上通過聚類分析方法和蟻群算法對雙向物流路徑優化問題進行了求解。

1 雙向物流配送的數學模型

1.1 問題描述

雙向物流路徑優化問題可以這樣描述：

已知有C個客戶點，給定每個客戶的坐標點和需求量，貨車從配送中心出發，將貨物送到各個客戶，并同時把客戶供應的貨物帶回到配送中心。車輛應在條件允許下進行服務，當完成任務或者不存在能滿足約束條件的情況下，返回配送中心，直到所有的客戶的送取貨任務完成，整個流程結束。物流路徑優化要求在滿足約束的條件下，合理安排貨車的配送路線，使得運輸成本最小。由于運輸成本很大程度上是由貨車的路徑長度決定的，因此本文求解VRPSDP問題的目標函數的最優解就是要求路徑最短。

1.2 數學模型的建立

1.2.1 參數說明

1.2.2 數學模型

根據上面對VRPSDP問題的描述和已設定的數學參數，加之針對該問題所需要考慮的約束條件，對此問題進行了建模，將服務完所有客戶點后所有車輛的行駛總路程定義為目標函

2 VRPSDP模型的求解

本文中求解模型的方法，首先是通過FCM聚類，把需要提供服務的城市進行分類，然后再用蟻群算法在滿足約束的情況下對每個分類進行求解最優路徑，具體做法如圖1所示。

圖1 求解流程圖

3 實例仿真

為了檢驗上述雙向物流路徑優化方法的有效性，本文采用實例數據對其進行性能分析。設車輛從配送中心出發，為各個客戶提供服務，配送中心坐標位置是（0km，0km），車輛在滿足約束的情況下向 30 個客戶配送貨物。

首先經matlab仿真得到的30個城市的聚類圖如圖2所示。

圖2 經FCM聚類的城市坐標圖

然后經過蟻群算法對每個聚類進行路徑優化，得到的車輛配送路徑圖如圖3所示。

圖3 車輛配送路線圖

4 結論

本文針對雙向物流的特點，首先給出了問題的相關描述，然后通過抽象建模，給出了帶路程和負載量約束的雙向物流路徑優化模型。根據給出的VRPSDP問題模型，用基于FCM聚類和蟻群算法的混合算法對模型進行求解。最后通過仿真實驗，證明了本文混合算法求解雙向物流路徑優化問題的的正確性和有效性。

【參考文獻】

[1]楊燕霞，伍岳慶，姚宇，等.帶時間窗車輛調度問題的啟發式算法研究與應用[J].計算機應用，2013，33（S1）：59-61.

[2]談曉勇，劉秋菊.應急配送車輛調度優化研究綜述與展望[J].8.計算機應用研究，2012，29（9）：3212-3215，3220.

[3]Knoke D， Burt R S. Applied network analysis[M]. Newbury Park：Sage， 1983：195-222.

[責任編輯：楊玉潔]