考慮不可行路徑的逆向物流回收路徑問題*

劉艷秋， 吳　蒙， 徐世達

(沈陽工業大學 理學院， 沈陽 110870)

?

考慮不可行路徑的逆向物流回收路徑問題*

劉艷秋， 吳蒙， 徐世達

(沈陽工業大學 理學院， 沈陽 110870)

針對車輛回收路徑問題的研究較少考慮部分節點可被多次訪問的情況，以及現實生活中無法保證可行的直線路徑均存在的問題，建立了以逆向物流網絡最低總運輸成本為優化目標的數學模型.通過FLOYD算法將問題轉化為傳統車輛路徑問題模型，通過改進的蟻群算法進行求解，確定回收設施的數量和位置，并得到最優回收車輛路徑.通過算例驗證了模型和算法的有效性，對解決逆向物流路徑問題具有一定的實際意義.

逆向物流； 回收路徑； 不可行路徑； 物流節點； 回收中心； 數學模型； FLOYD算法； 改進的蟻群算法

逆向物流回收路徑問題(Vehicle routing problem in reverse logistics，VRPRL)是車輛路徑問題(Vehicle routing problem，VRP)在逆向物流環境下的擴展問題研究.VRPRL是通過設計逆向物流網絡并合理調配回收車輛以滿足各個客戶需求點的廢棄物回收需求.傳統的逆向物流網絡模型中假設任意兩個物流節點之間均存在可行的直線路徑并且每個節點僅可被訪問一次，而在現實生活中，無法保證可行的直線最短路徑均存在.

高舉紅等[1]針對危險廢棄物的回收路徑問題，綜合考慮回收成本與風險因素進行了研究；蔣忠中等[2]研究了考慮不可行路徑的B2C電子商務物流的配送路徑優化問題；梁春艷等[3]針對含有隨機參數的廢舊家電逆向物流路徑規劃問題，建立了面向對象的仿真模型；Tolga等[4]考慮了碳排放約束下的車輛路徑問題；Kim等[5]研究了電子產品的車輛回收路徑問題；Tang等[6]運用禁忌搜索算法和局部優化算法，求解了多節點情況下的最大行程約束車輛路徑問題；李華俊[7]分析了逆向物流系統優化中回收中轉站的選址、庫存控制策略和收集車輛的路徑選擇三者之間的內在聯系；任志剛[8]提出逆向物流網絡選址運輸問題求解首先要規劃出回收站與回收中心之間最短路徑，然后才可進行優化；劉艷秋等[9]提出了帶能力約束的多級物流配送網絡，并應用模擬退火算法思想進行求解.

1　問題描述與模型建立

自建物流情況下，車輛調度要求從回收中心發出的車輛完成回收任務后最終返回該回收中心.傳統車輛路徑問題模型所研究的物流網絡模型假設網絡中各個物流節點之間均存在可行的直線路徑，并且每個物流節點只能被訪問一次.而實際情況中，由于地理環境、運載條件等外界因素的限制，無法保證物流網絡中物流節點間可行路徑均存在.為了保證物流網絡中所有客戶的回收需求均能得到滿足，回收車輛完成部分節點的回收任務后，沿著回收路徑返回到某一個已訪問節點，之后行駛向其他節點進行回收任務，則部分物流節點會出現被多次訪問的情況.

根據實際情況中物流節點會出現多次被訪問的情況，本文增加了對路徑可行性與物流節點可被多次訪問的情況建立數學模型.通過FLOYD算法[10]將問題轉化為傳統VRP模型，并通過改進的蟻群算法[11]進行求解.

設G={V，E}為一個由處理中心、回收站組成的不完全無向圖，式中，V=S∪R，S為回收中心節點集合，R為回收站節點集合，E為兩類物流節點間可行路徑集合.模型可表示為

(1)

(?p∈S，k∈Kp)

(2)

(3)

(4)

(5)

(6)

(7)

ωi≥yij(?i∈S，j∈R)

(8)

xijk=0，1(?i，j∈V，k∈K)

(9)

yij=0，1(?i∈S，j∈R)

(10)

zjk=0，1(?j∈R，k∈K)

(11)

ωi=0，1(?i∈S)

(12)

式中：K為回收車輛集合；Kp為回收中心p的車輛集合；Np為回收中心p的車輛總數；Vp為回收中心的最大處理能力，即回收中心的容量；Mk為車輛k的調用費用；Fi為回收中心i的建設費用；cij、dij為路徑(i，j)之間的單位運輸費用和最短路程距離；qj為回收點j的廢棄物總量；Q為車輛的最大載重量.

模型中的決策變量為

模型的目標函數第一部分是車輛的運輸費用，第二部分是車輛的調用費用，第三部分是回收中心的建設費用；式(2)表示回收中心發出的車輛最終必須返回該回收中心；式(3)表示若j由k負責回收，則k至少訪問j一次；式(4)表示每個待回收站僅由一輛車輛負責回收；式(5)表示每個回收中心車輛調用數限制；式(6)表示回收車輛的裝載量不超過容量；式(7)表示回收中心可以處理所有調出車輛所回收的廢棄物；式(8)確保回收中心用于回收任務時，該回收中心已經建立；式(9)～(12)為變量約束.

2　基于FLOYD算法的改進蟻群算法

傳統蟻群算法無法對VRPRL中不可行路徑與節點被多次訪問情況進行表達和求解，因此，本文運用FLOYD算法思想對距離矩陣與信息素更新策略進行修改，并增加指針矩陣，將問題轉化為傳統VRP問題進行求解.

傳統VRP問題研究的是一類完全圖，任意兩個物流節點間存在可行的直線路徑，在蟻群算法中體現為距離矩陣D中的元素可以直接表達出任意兩個物流節點的最短距離.而本文研究的是一類如圖1所示的不完全網絡圖，圖1所對應的距離矩陣D表示為

圖1　網絡結構圖Fig.1　Network structure diagram

對于圖中沒有可行直線路徑的兩個物流節點，采用FLOYD算法求得最短路徑與路徑長度.FLOYD算法用于求解網絡中任意兩個點的最短距離，并可通過指針矩陣同步記錄最短路徑.通過該算法，問題轉化為傳統VRP問題，更新后的距離矩陣D′表示物流網絡中任意兩個節點的可行最短距離，指針矩陣P表示達到最短距離時的路徑走向，其表達式分別為

3　仿真結果與比較分析

為了驗證本文所提出數學模型與改進蟻群算法的有效性，運用改進前后的兩種模型算法分別對VRP問題進行求解分析.隨機產生3個處理中心，17個回收站，70個需求點的逆向物流回收網絡.17個回收站將需求點部分廢棄物回收后，3個回收中心的最大回收量以及各個回收站的待回收廢棄物量如表1、2所示.

表1　回收中心最大回收量Tab.1　Maximum recycling amount in recycling center

表2　回收站待回收量Tab.2　Recycling amount to be recycled in recycling stations

設回收中心可用車輛數Np=3，車輛最大載重Q=20 t，車輛調用費用Mk=500元，各條路徑單位運輸費用cij=7元，回收中心的運作費用均為5 000元，逆向物流回收網絡如圖2所示.

圖2　逆向物流回收網絡結構圖Fig.2　Structure diagram of reverse logistics recovery network

改進的蟻群算法使用Matlab語言實現，運行環境為AMD Athlon(tm) 5200+2.70 GHz處理器，內存2 GB的Windows平臺，通過大量的實驗確定改進蟻群算法參數設置為α=1，β=5，γ=2，ρ=0.25，η=0.3，求得改進前后兩種數學模型回收路徑及運作費用如表3、4所示.

表3　改進后回收路徑及運作費用Tab.2　Recovery path and operating expenses with improvement

表4　改進前回收路徑及費用Tab.4　Recovery path and operating expenses without improvement

通過表3與表4可直接得到逆向物流回收網絡中的各個回收車輛的回收路徑以及回收中心建設情況，計算結果給出了節點間存在不可行路徑時回收車輛的最短行駛路徑.本文所提出的數學模型中部分節點需要被多次訪問，被多次訪問的物流節點在第一次被訪問時完成回收服務，實際逆向物流回收網絡運作圖如圖3所示.對于傳統VRP模型，當出現不可行路徑時，放棄替代路徑而搜索最短的可行路徑進行回收任務，網絡運作圖如圖4所示.

圖3　實際物流網絡運作圖Fig.3　Actual logistics network operation diagram

由圖3可以看出，為了滿足所有回收站的回收需求，需要建立0、2兩座回收中心，并發出3輛回收車輛；為了應對不可行路徑產生的問題，出現部分非回收中心物流節點被多次訪問的情況，如節點3與5.由圖4可以看出，傳統VRP問題不考慮物流節點可被多次訪問情況，為了滿足所有客戶回收需求，則需要額外調用回收車輛去完成回收任務.特別對于節點9、10，兩個節點僅與物流節點3相連，若節點3不可被二次訪問，則節點9，10的回收需求無法滿足.

圖4　傳統VRP網絡運作圖Fig.4　Traditional VRP network operation diagram

通過上述計算結果分析可知，對于逆向物流回收路徑問題的研究，考慮不可行路徑與節點可被多次訪問情況所建立的數學模型更加符合實際情況，具有很強的實際應用價值，很大程度節約了回收過程中的運輸費用與回收車輛調用費用.

4　結　論

本文提出一種改進的蟻群算法求解一類不完全網絡圖下的VRP問題，當存在不可行路徑時需要對部分節點進行二次訪問來進行替代路徑的搜索，因此，路徑求解問題更為復雜.為了提高問題的求解效率，本文在傳統蟻群算法基礎上增加了距離矩陣更新操作.在實際應用中，可以將客戶需求、回收站容量、物流網絡可靠性等多方面因素加入模型進行討論，使得逆向物流回收路徑問題的研究能夠更加貼近實際要求.

[1]高舉紅，趙天一.危險廢棄物回收路徑的優化分析 [J].中國安全科學學報，2013，23(11)：67-71.

(GAO Ju-hong，ZHAO Tian-yi.Analysis of routing optimization for hazardous waste recycling path [J].China Safety Science Journal，2013，23(11)：67-71.)

[2]蔣忠中，汪定偉.B2C電子商務中物流配送路徑優化的模型與算法 [J].信息與控制，2005，34(2)：482-485.

(JIANG Zhong-zhong，WANG Ding-wei.Model and algorithm for logistics distribution routing of B2C E-commerce [J].Information and Control，2005，34(2)：482-485.)

[3]梁春艷，石宇強，張敏，等.基于 eM-Plant 的廢舊家電逆向物流路徑規劃的仿真研究 [J].物流工程與管理，2014，36(3)：43-45.

(LIANG Chun-yan，SHI Yu-qiang，ZHANG Min，et al.Simulation of discarded appliances reverse logistics route planning based on eM-Plant [J].Logistics Engineering and Management，2014，36(3)：43-45.)

[4]Tolga B，Gilbert L.The pollution-routing problem [J].Transportation Research，2011，16(10)：1232-1250.

[5]Kim H，Yang J，Lee K D.Vehicle routing in reverse logistics for recycling end-of-life consumer electronic goods in South Korea [J].Transportation Research，2009，14(5)：291-299.

[6]Tang L，Galvao M.A tabu search algorithm for the vehicle routing problem with simultaneous pick-up and delivery service [J].Computer & Operation Research，2011，33：595-611.

(LI Hua-jun.Location-roution-inventor problem in optimization of reverse logistic system [D].Chengdu：Southwest Jiaotong University，2006.)

[8]任志剛.逆向物流網絡選址優化策略研究 [M].北京：中國社會科學出版社，2011.

(REN Zhi-gang.Optimization strategy for facility location problem of reverse logistics center [M].Beijing：China Social Science Press，2011.)

[9]劉艷秋，焦妮，李佳.基于確定網絡的多級物流網絡優化設計 [J].沈陽工業大學學報，2015，37(1)：64-68.

(LIU Yan-qiu，JIAO Ni，LI Jia.Optimization design of multi level logistics network based on determined network [J].Journal of Shenyang University of Technology，2015，37(1)：64-68.)

[10]張德全，吳果林.最短路徑問題的Floyd算法優化 [J].許昌學院學報，2009，28(2)：10-13.

(ZHANG De-quan，WU Guo-lin.Optimization of Floyd algorithm for shortest path problem [J].Journal of Xuchang University，2009，28(2)：10-13.)

[11]黃摯雄，張登科.蟻群算法及其改進形式綜述 [J].計算技術與自動化，2006，25(3)：35-38.

(HUANG Zhi-xiong，ZHANG Deng-ke.Ant colony algorithm and summary of its improved algorithms [J].Computing Technology and Automation，2006，25(3)：35-38.)

(責任編輯：景勇英文審校：尹淑英)

Reverse logistics recovery path problem with considering unfeasible path

LIU Yan-qiu, WU Meng, XU Shi-da

(School of Science, Shenyang University of Technology, Shenyang 110870, China)

Aiming at the situation that the multiple accesses of some nodes have been seldom considered in the study on the problem of vehicle recovery path and in order to solve the problem that the feasible linear paths can not be entirely guaranteed in real life, a mathematical model with taking the minimum total transportation cost of reverse logistics network as the optimization objective was established. The problem is transformed into the traditional vehicle path problem model through the FLOYD algorithm, and is solved with the improved ant colony algorithm, the number and location of recycling facilities are determined, and the optimum vehicle recovery path is obtained. Furthermore, the validity of both model and algorithm is verified with a numerical example, which has certain practical significance for solving the problem of reverse logistics path.

reverse logistics; recovery path; unfeasible path; logistics node; recycling center; mathematical model; FLOYD algorithm; improved ant colony algorithm

2015-09-21.

遼寧省科學技術計劃基金資助項目(2013216015)； 沈陽市科學技術計劃基金資助項目(F13-051-2-00，F14-231-1-24).

劉艷秋(1963-)男，吉林四平人，教授，博士生導師，主要從事復雜系統可靠性建模與優化等方面的研究.

信息科學與工程

10.7688/j.issn.1000-1646.2016.04.10

TP 15

A

1000-1646(2016)04-0416-05

*本文已于2016-03-02 16∶47在中國知網優先數字出版. 網絡出版地址： http：∥www.cnki.net/kcms/detail/21.1189.T.20160302.1647.042.html