基于混合算法的雙向物流路徑優(yōu)化問題的研究

劉艷秋　楊勇

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

【關(guān)鍵詞】物流配送；雙向物流；物流路徑優(yōu)化；蟻群算法；減法聚類

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 引言

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

1 雙向物流配送的數(shù)學(xué)模型

1.1 問題描述

雙向物流路徑優(yōu)化問題可以這樣描述：

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

1.2 數(shù)學(xué)模型的建立

1.2.1 參數(shù)說明

1.2.2 數(shù)學(xué)模型

根據(jù)上面對(duì)VRPSDP問題的描述和已設(shè)定的數(shù)學(xué)參數(shù)，加之針對(duì)該問題所需要考慮的約束條件，對(duì)此問題進(jìn)行了建模，將服務(wù)完所有客戶點(diǎn)后所有車輛的行駛總路程定義為目標(biāo)函

2 VRPSDP模型的求解

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

圖1 求解流程圖

3 實(shí)例仿真

為了檢驗(yàn)上述雙向物流路徑優(yōu)化方法的有效性，本文采用實(shí)例數(shù)據(jù)對(duì)其進(jìn)行性能分析。設(shè)車輛從配送中心出發(fā)，為各個(gè)客戶提供服務(wù)，配送中心坐標(biāo)位置是（0km，0km），車輛在滿足約束的情況下向 30 個(gè)客戶配送貨物。

首先經(jīng)matlab仿真得到的30個(gè)城市的聚類圖如圖2所示。

圖2 經(jīng)FCM聚類的城市坐標(biāo)圖

然后經(jīng)過蟻群算法對(duì)每個(gè)聚類進(jìn)行路徑優(yōu)化，得到的車輛配送路徑圖如圖3所示。

圖3 車輛配送路線圖

4 結(jié)論

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

【參考文獻(xiàn)】

[1]楊燕霞，伍岳慶，姚宇，等.帶時(shí)間窗車輛調(diào)度問題的啟發(fā)式算法研究與應(yīng)用[J].計(jì)算機(jī)應(yīng)用，2013，33（S1）：59-61.

[2]談曉勇，劉秋菊.應(yīng)急配送車輛調(diào)度優(yōu)化研究綜述與展望[J].8.計(jì)算機(jī)應(yīng)用研究，2012，29（9）：3212-3215，3220.

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

[責(zé)任編輯：楊玉潔]