賀政綱,鄒　曄，楊　曉

(1.西南交通大學　交通運輸與物流學院，四川　成都　610031;

2.宜賓職業(yè)技術學院　五糧液技術學院，四川　宜賓　644003)

?

報廢汽車物流網(wǎng)絡選址-路徑問題建模與求解算法研究

賀政綱1,鄒曄1，楊曉2

(1.西南交通大學交通運輸與物流學院，四川成都610031;

2.宜賓職業(yè)技術學院五糧液技術學院，四川宜賓644003)

摘要：為提高報廢汽車的回收利用率，實現(xiàn)其經(jīng)濟價值和資源環(huán)境價值，重點考慮報廢汽車大而重的特點，放寬越級回收的條件約束，以此為基礎構建報廢汽車回收物流網(wǎng)絡選址-路徑優(yōu)化模型，旨在解決拆解中心選址問題、中轉場選址問題、拆解中心和中轉場的建設數(shù)目以及車輛路徑問題。然后采用遺傳算法和禁忌搜索算法相結合的方法對模型進行算法設計，最后以成都市為例對模型進行了分析和驗證，得到了廢舊汽車回收物流網(wǎng)絡選址-選線布局。

關鍵詞：運輸經(jīng)濟；選址-路徑優(yōu)化；組合算法；報廢汽車；回收物流網(wǎng)絡

0引言

報廢汽車資源化具有巨大的經(jīng)濟價值和資源環(huán)境價值。在報廢汽車回收物流網(wǎng)絡中，其結構如圖1所示,拆解中心和中轉場的兩級選址-路徑?jīng)Q策將對整個網(wǎng)絡的運作效率與效益有重大影響，進而影響報廢汽車的回收利用率。

圖1　報廢汽車回收物流網(wǎng)絡結構Fig.1　Structure of ELVs recycling logistics network

趙佳虹等構建了一個危險廢物回收物流系統(tǒng)選址-路徑問題的多目標改進模型。該模型特別考慮了廢物類型與運輸車輛的多樣性，廢物與運輸車輛的相容性，并采用暴露人口噸數(shù)表示風險，以最小化最大風險區(qū)域代表風險公平性優(yōu)化目標。同時，該模型主要確定了回收中心的位置，回收中心配備的運輸車輛類型，以及各類危險廢物的車輛運輸路徑[1]。聞軼對LRP問題進行了多目標優(yōu)化，以最短時間、客戶需求和最小成本為目標建立了多目標隨機優(yōu)化模型，隨機性在于論文考慮了客戶需求的不確定性、車輛行駛時間的不確定性、以及車輛載重約束等影響因素[2]。張長星對選址-路徑問題的算法進行了研究分析，設計了改進遺傳算法求解LRP問題[3]。曾慶成等建立了物流配送系統(tǒng)網(wǎng)絡優(yōu)化的雙層規(guī)劃模型。配送中心的選址問題為模型上層，車輛路徑優(yōu)化問題為模型下層。先由上層選址模型給出初始配送中心選址方案，在此基礎上再由一下層VRP模型獲得最優(yōu)車輛路徑，然后計算上層選址模型中的供應商到已選配送中心的運輸成本，構成系統(tǒng)模型目標函數(shù)，通過對目標函數(shù)的優(yōu)化過程再對上層選址模型方案進行調整[4]。張潛對LRP問題中的選址配給、路徑優(yōu)化、選址-路徑優(yōu)化3類問題的具體優(yōu)化算法進行了分析和比較，并提出采用兩階段啟發(fā)式算法來求解LRP問題[5]。

1模型構建

1.1模型描述

報廢汽車回收物流網(wǎng)絡選址-路徑問題主要包括：(1)拆解中心選址問題。拆解中心的選址盡可能滿足：遠離居民區(qū)、學校等民用建筑；盡可能靠近中轉量大的中轉場。(2)中轉場選址問題。中轉場的選址盡可能滿足：回收點到相應的中轉站距離最短；報廢汽車數(shù)量多的回收點盡可能靠近中轉站。(3)拆解中心和中轉場的建設數(shù)目。在模型構建中考慮拆解中心和中轉站本身的建設費用。(4)車輛路徑問題。車輛路徑包括收集車輛及運輸車輛的路徑問題，需解決收集車輛在每一個周期內的運行路線。

報廢汽車回收物流系統(tǒng)可看作由集合G=(V,E)表示的一個網(wǎng)絡圖。V為節(jié)點位置，V={o|o=1,2,…,p,p+1,p+2,…,p+n,p+n+1,p+n+2,…,p+n+m}； 節(jié)點H={h|h=1,2,…,p}為拆解中心候選點的位置；J={j|j=1,2,…,n}為中轉場候選點的位置；I={i|i=1,2,…,m}為m個回收點的位置。

報廢汽車回收物流系統(tǒng)中，共配備兩種車型，一種是從回收站點將收集到的廢舊汽車運往中轉場的收集車輛；另一種是從中轉場大批量運送廢舊汽車到拆解中心的運輸車輛。

報廢汽車回收物流網(wǎng)絡中選址-路徑問題屬于兩級設施選址、多車型回收并包含車輛載重約束、設施容量約束、無時間窗的LRP問題。選址-路徑優(yōu)化模型構建的目標是使得整個系統(tǒng)的固定投資和周期內的運行成本之和最小，即拆解中心和中轉場的建設成本、收集車輛的收集成本及運輸車輛的運輸成本之和最小。

1.2模型假設

模型的前提假設：(1)拆解中心和中轉場候選點的數(shù)目、位置及建設費用已知；(2)回收點數(shù)目、位置及日回收量已知；(3)每個回收點的報廢汽車僅由一輛收集車輛進行收集，車輛運載量不得超過其最大載重，且同類型的車輛最大載重相同；(4)假定車輛在每條路徑上行駛的最長時間為1 d；(5)每條路徑上回收點的報廢汽車收集量小于或等于收集車輛的額定載重；(6)每輛收集車輛的始發(fā)點和終點為同一中轉場或拆解中心，且只負責一次收集活動；(7)拆解中心具有中轉場的全部功能，即拆解中心是一個特殊的中轉場，故拆解中心可越級收集報廢汽車；(8)車輛收集和運輸成本與運輸距離和運量成正比；(9)道路狀況穩(wěn)定，不考慮交通堵塞問題或車輛本身故障情況，車輛恒速穩(wěn)定運行；(10)拆解中心建成后的使用年限為M年，中轉場建成后的使用年限為N年。

1.3模型建立

故模型構建如下：

(1)

s.t.

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

(13)

(14)

(15)

(16)

上述式(1)表示總目標函數(shù)，即中轉場和拆解中心建設及運行成本、各節(jié)點間運輸成本之和最小；式(2)表示每個回收點僅由一輛收集車輛負責收集；式(3)表示路徑連續(xù)性約束，即到達任何節(jié)點的車輛必須離開該節(jié)點；式(4)表示收集車輛最大載重約束；式(5)表示每輛收集車輛在每條收集路徑上只經(jīng)過一個拆解中心或中轉場，并保證拆解中心或中轉場的每一輛收集車輛都能投入運行；式(6)表示拆解中心一旦為某個回收點服務，該拆解中心一定建設；式(7)表示中轉場一旦為某個回收點服務，該中轉場一定建設；式(8)表示中轉場容量約束；式(9)表示拆解中心容量約束；式(10)表示每個中轉場只能被運輸車輛訪問一次；式(11)表示從回收點運往中轉場的報廢汽車和回收點運往拆解中心的報廢汽車的總和等于回收點的回收量；式(12)～式(16)為決策變量0-1取值約束。

2算法設計

針對遺傳算法和禁忌搜索算法各自的搜索不足，文章將構造遺傳算法和禁忌搜索的組合算法。采用兩階段算法進行求解：第一階段進行中轉場選址,按照實際問題結合已構建的數(shù)學模型初始化問題，設計遺傳算法算子以及禁忌搜索算法的參數(shù)。其次設定遺傳算法和禁忌搜索算法之間的結合條件，規(guī)定結合點。執(zhí)行遺傳搜索，在遺傳搜索的過程中判定是否滿足禁忌搜索的條件，若滿足，則進行禁忌搜索，否則繼續(xù)進行遺傳搜索，最終輸出最優(yōu)解。第二階段在中轉場已選的基礎上進行拆解中心選址。

2.1算法設計要素

(1)編碼

選址-路徑問題的解包括四部分內容：選址、分派、車輛分配、路徑選擇， 文章擬采用非定長實數(shù)編碼方式。①對候選拆解中心、候選中轉場、回收站點、車輛進行編號，利用編號進行編碼；②根據(jù)解的特點構建染色體，染色體的長度各不相等，但所有染色體均由3個子串構成。其中子串3表示各回收點的排列順序；子串1和子串3一一對應表示為各回收點服務的車輛編號；子串2表示的是子串1中車輛歸屬的中轉場的編號。具體編碼過程參照以下實例：現(xiàn)已知收集車輛4輛，編號1，2，3，4；回收點10個，編號4，5，…，14；3個中轉場，編號1，2，3；拆解中心2個，編號為4，5。具體編碼如下：

其中子串1中1，2，3，4車輛都有，表示沒有多余車輛，每輛車都得到合理利用。另外子串1中基因位1，6，7均為1，一一對應的子串3中回收點10，9，13，表示由車輛1按照10-9-13的順序回收。同理，車輛2按12-8-14的順序進行回收，車輛3按6-7-11的順序回收，車輛4單獨對回收點5進行回收。子串2按照3-1-4-2的順序排列，表示車輛1，2，4分別歸屬于中轉場和拆解中心3，1，2，車輛3歸屬于拆解中心4。

(2)初始化種群

設種群規(guī)模為num，隨機產(chǎn)生初始種群，方法如下：隨機產(chǎn)生一條染色體，判斷是否滿足車輛容量和中轉場容量的限制。若滿足，即為可行解，否則另外產(chǎn)生一條染色體，直到產(chǎn)生num條可行染色體為止。其具體的生成步驟如下：①設置種群規(guī)模為m。②從待選拆解中心和中轉場中隨機選擇3個作為已選物流節(jié)點。③對已選的3個物流節(jié)點進行分派，分別計算ru，riu(ru表示拆解中心或中轉場與其他拆解中心或中轉場之間的最短距離的一半，riu表示客戶點與拆解中心或中轉場之間的距離)。④判定是否riu≤ru，若是，則將客戶點i分配給拆解中心或中轉場u；否則，將客戶點i分配給距離最近的拆解中心或中轉場。⑤已選拆解中心或中轉場u從分派的回收點中隨機選擇產(chǎn)生一條新路徑，判定該路線的運載量超限與否，若不超限，繼續(xù)隨機選擇客戶點插入路線，累加路線的總回收量；否則，進行調整。⑥所有回收站點均加入路線中，并且均滿足車容量和場站容量限制，得到一個初始解。

(3)適應度函數(shù)

(4)選擇操作

(5)交叉和變異操作

①選擇交叉操作的概率Pc，并生產(chǎn)偽隨機數(shù)rk[rk∈(0,1)，k=1,2,…，n]，若rk

(6)禁忌搜索操作

①設定遺傳算法迭代過程中，每隔N代對種群中所有染色體執(zhí)行禁忌搜索算法(設迭代步數(shù)為IN，每次迭代共搜索當前解的NS個鄰近解，禁忌長度為TL)，之后繼續(xù)執(zhí)行遺傳算法。②在遺傳算法計算過程中若當前最優(yōu)解連續(xù)保持L代不變，也對其執(zhí)行禁忌搜索算法(設迭代步數(shù)為IN′，每次迭代共搜索當前解的NS′個鄰近解，禁忌長度為TL′)，之后繼續(xù)執(zhí)行遺傳搜索。③當前最優(yōu)解已連續(xù)保持2×L代不變，則對其再次執(zhí)行禁忌搜索算法，之后繼續(xù)執(zhí)行遺傳算法。④當前最優(yōu)解已連續(xù)保持3×L代不變，則終止遺傳/禁忌混合算法。

2.2算法求解步驟

Step 1：初始化問題。

Step 2：設置遺傳算法的種群規(guī)模num和最大迭代次數(shù)maxgen，交叉概率Pc，變異概率Pm和禁忌搜索算法的參數(shù)N,L。

Step 3：生成種群規(guī)模為num的初始種群；設遺傳算法的當前進化代數(shù)gen=0。

Step 4：計算初始種群中每個個體的目標函數(shù)值和適應度函數(shù)值。

Step 5：將初始種群的最優(yōu)目標函數(shù)值best作為當前最優(yōu)目標函數(shù)值bestnew，記錄當前最優(yōu)解連續(xù)保持代數(shù)β=0。

Step 6：若β=3L，轉Step 16；否則，轉Step 7。

Step 7：若β

Step 8：若β%L≠0，轉Step 9。否則，對當前最優(yōu)解執(zhí)行禁忌搜索算法，將當前種群的最優(yōu)目標函數(shù)值best和bestnew進行比較，若best

Step 9：若gen%N=0，對當前種群中所有染色體執(zhí)行禁忌搜索算法，轉Step 10；否則，直接轉Step10。

Step 10：采用輪盤賭選擇和精英保留策略相結合的選擇策略選擇染色體。

Step 11：采用替代策略使用種群中最優(yōu)的染色體替代種群中適應能力較差的個體。

Step 12：按照交叉概率Pc，兩兩配對執(zhí)行交叉操作。

Step 13：按照變異概率Pm，在種群中選擇進行變異的個體執(zhí)行變異操作。

Step 14：令gen=gen+1，計算當前種群中每個個體的目標函數(shù)值和適應度函數(shù)值。將當前種群的最優(yōu)目標函數(shù)值best和bestnew進行比較，若best

Step 15：若gen>maxgen，轉Step 16；否則，轉Step 6。

Step 16：算法結束，輸出結果。

以上算法步驟中禁忌搜索算法的具體步驟如下：

Step 1：在遺傳搜索過程生產(chǎn)的最優(yōu)解中產(chǎn)生初始解。

Step 2 ：令禁忌表為空，制定禁忌長度L及迭代次數(shù)StopL。

Step 3：令初始解為當前解和bestnew。

Step 4：若p

Step 5：設計鄰域產(chǎn)生策略。

Step 6：產(chǎn)生當前解的25個鄰域解。

Step 7：將這25個鄰域解進行從小到大的排序。

Step 8：選出其中前面10個鄰域解作為候選解。

Step 9：若best

Step 10：若該解的禁忌對象的禁忌長度≠0，排名第一的候選解被刪除，排名第二的候選解成為排名第一，轉Step 13；若否更新當前解；更新禁忌表，當前解對應的禁忌對象的禁忌長度為n,禁忌表中其他對象分別減1。

Step 11：p=p+1轉step 4。

3算例分析

3.1數(shù)據(jù)假設

經(jīng)調研可知，成都市某報廢汽車回收拆解公司正面臨選址-路徑?jīng)Q策。該公司有20家報廢汽車回收點，6家中轉場候選點，3家拆解中心候選點，其位置如圖2所示。

注：實心圓圈表示拆解中心候選點；“米”形表示中轉場候選點；空心圓圈表示回收點。圖2　回收站點、中轉場和拆解中心的位置圖Fig.2　Locations of recycling sites, transit depots and disassembly centers

假定在收集報廢汽車過程中，單位運費一致，且假設所有路段的運輸條件均相同，即報廢汽車運價函數(shù)相同。利用網(wǎng)絡Google地圖測距，得到回收點與候選中轉場及拆解中心之間的距離(lz表示回收點到中轉場的距離；lc表示回收點到拆解中心的距離)如表1所示，各中轉場候選點至拆解中心候選點距離如表2所示。

從回收點到中轉場、回收站點到拆解中心以及回收點到拆解中心均采用整車運輸，根據(jù)對2006年以來的公路貨物運輸價格指數(shù)的分析，結合汽車的平均質量，從回收點到中轉場和拆解中心每輛車每千米的運價為0.000 3元/(kg·km),即0.3元/(t·km)，中轉場到處理中心單位車輛單位里程的運價為0.000 35元/(kg·km)，即0.35元/(t·km)。

表1　X公司回收點相關數(shù)據(jù)表

表2　X公司中轉場與拆解中心間距離(單位：km)

X公司中轉場是基于已有站點的改造擴建，中轉場1，2，3，4，5，6的固定建設成本分別為9，10，7，13，12，10。資源整合背景下成立的X公司，其拆解中心采用兩條機械拆解線，其專業(yè)化和機械化程度較高，拆解中心1，2，3的建設成本分別為500，600，1 000。中轉場和拆解中心的建設投資回收期均為15 a。各中轉場最大回收能力與最小回收能力、拆解中心最大處理能力與最小處理能力的值如表3和表4所示。

表3　X公司各中轉場廢舊汽車的最大與最小

表4　X公司各拆解中心廢舊汽車的最大與最小

此外，收集車輛的最大車容量為4輛，運輸車輛的最大車容量為12輛。

3.2模型求解

參數(shù)設置如下：

(1)遺傳算法初始種群規(guī)模num=80；最大迭代次數(shù)maxgen=500；交叉概率Pc=0.3；變異概率Pm=0.1。

(2)禁忌搜索算法禁忌長度L=10；最大迭代次數(shù)stopL=90。

(3)規(guī)定遺傳搜索過程中gen%N=0(其中N=200)，執(zhí)行禁忌搜索。

采用仿真計算，使用MATLAB7.9編程實現(xiàn)。最終報廢汽車回收網(wǎng)絡選址-路徑如圖3所示，搜索過程中平均迭代次數(shù)變化趨勢如圖4所示，搜索過程中最優(yōu)解迭代次數(shù)的變化趨勢如圖5所示。

圖4　平均迭代次數(shù)變化趨勢圖Fig.4　Changing trend of average iteration number

圖5　最優(yōu)解迭代次數(shù)變化趨勢Fig.5　Changing trend of iteration number of optimal solution

故搜索最終得到的最優(yōu)解如表5～表7所示。

表5　拆解中心選址結果

表6　中轉場選址結果

表7　車輛最優(yōu)運輸線路

4結論

我國即將進入報廢汽車數(shù)量激增的時期，高效率、高效益的回收物流體系是報廢汽車回收利用的重要基礎，而報廢汽車回收物流節(jié)點的布局及回收線路的安排在整個回收物流體系構建中又起著舉足輕重的作用。本文構建了報廢汽車回收物流網(wǎng)絡選址-路徑優(yōu)化模型，針對該模型設計了遺傳搜索和禁忌搜索組合算法，并以成都某公司為例，采用matlab7.9編程，對模型進行了實例驗證。該研究以期能為企業(yè)進行報廢汽車回收網(wǎng)絡設施選址及車輛路徑安排提供決策依據(jù)，從而實現(xiàn)企業(yè)資源利用效率的最大化，并提高報廢汽車的回收利用率。文章在各回收點回收量已知的基礎上構建模型，將來可以將回收量的不確定性納入研究范疇，還可進行回收質量、回收時間等的不確定性研究。

參考文獻：

References:

[1]趙佳虹,彭艷梅.危險廢物回收物流的選址-路徑多目標模型[J].交通運輸工程與信息學報,2011,9(2):25-29.

ZHAO Jia-hong, PENG Yan-mei. A New Multi-objective Model for the Combined Location-routing Problem in Hazardous Waste Recycling Logistics[J]. Journal of Transportation Engineering and Information, 2011,9(2):25-29.

[2]聞軼. 隨機物流選址和車輛徑路問題綜合優(yōu)化的研究[D].北京:北京交通大學,2006.

WEN Yi. Research on Optimization of Stochastic Location-routing Problem [D].Beijing: Beijing Jiaotong University, 2006.

[3]張長星,黨延忠.定位-運輸路線安排問題的遺傳算法研究[J].計算機工程與應用,2004,8(3):65-67.

ZHANG Chang-xing, DANG Yan-zhong. A Novel Genetic Algorithm for Location-routing Problem [J]. Computer Engineering and Applications, 2004,8(3):65-67.

[4]曾慶成,楊忠振,蔣永雷.配送中心選址與車輛路徑一體優(yōu)化模型與算法[J].武漢理工大學學報:交通科學與工程版,2009,33(2):267-270.

ZENG Qing-cheng, YANG Zhong-zhen, JIANG Yong-lei. Optimization Model and Algorithm of Coordinated Distribution Center Location and Vehicle Routing[J]. Journal of Wuhan University of Technology: Transportation Science & Engineering Edition,2009,33(2):267-270.

[5]張潛,高立群,胡祥培.集成化物流中的定位-運輸路線安排問題(LRP)優(yōu)化算法評述[J].東北大學學報:自然科學版,2003,24(l):31-34.

ZHANG Qian, GAO Li-qun, HU Xiang-pei. Review on Optimal Algorithms of Location-routing Problem (LRP) in Integrated Logistics [J]. Journal of Northeastern University: Natural Science Edition,2003,24(1):31-34.

[6]汪壽陽,趙秋紅,夏國平.集成物流管理系統(tǒng)中的定位-運輸路線安排問題的研究[J].管理科學學報,2000,3(2):69-75.

WANG Shou-yang, ZHAO Qiu-hong, XIA Guo-ping. Research on Combined Location-routing Problems in Integrated Logistics Systems[J]. Journal of Management Sciences in China,2000,3(2):69-75.

[7]孫穎蓀.汽車回收處理中心的一種選址模型[D].合肥:中國科技大學,2009.

SUN Ying-sun. A Location Model for Automobile’s Recovery Treatment Center[D]. Hefei:University of Science and Technology of China,2009.

[8]劉鶴，解棍.基于循環(huán)經(jīng)濟理論的汽車逆向物流分析[J].物流技術,2009,28(1):42-43,59.

LIU He, XIE Gun. Analysis on the Automobile Reverse Logistics Based on Circular Economy Theory [J].Logistics Technology,2009,28(1):42-43,59.

[9]李曉玲.報廢汽車逆向物流網(wǎng)絡構建[D].北京:北京交通大學,2011.

LI Xiao-ling. Construction of Reverse Logistics Network of End-of-life Automobile[D]. Beijing: Beijing Jiaotong University,2011.

[10]CHAN Y, CARTER W B, BURNES M D. A Multiple-depot, Multiple-vehicle, Location Routing Problem with Stochastically Processed Demands[J]. Computers & Operations Research, 2001, 28(8): 803-826.

[11]王勇,張永,毛海軍,等.基于改進蟻群算法的多物流中轉站選址規(guī)劃[J].公路交通科技,2011,28(8):140-146.

WANG Yong, ZHANG Yong, MAO Hai-jun, et al. Multi-logistics Transfer Stations Allocation Based on Improved Ant Colony Optimization Algorithm[J]. Journal of Highway and Transportation Research and Development,2011,28(8):140-146.

[12]稅文兵,葉懷珍,張詩波.考慮庫存成本的配送中心動態(tài)選址模型及算法[J].公路交通科技,2010,27(4):149-154.

Research of Modeling and Algorithm for ELV Logistics Network Location-routing Problem

HE Zheng-gang1, ZOU Ye1, YANG Xiao2

(1.School of Transportation & Logistics, Southwest Jiaotong University, Chengdu Sichuan 610031, China;2. Wuliangye Technology Institute, Yibin Vocational and Technical College, Yibin Sichuan 6444003, China)

Abstract：In order to improve the recycling rate of ELVs and realize the economic value and environmental resource value, taking the big and heavy features of ELVs into consideration, relaxing the constraints of grade-skip recycling, an optimization model for ELV recycling logistics network location-routing problem is built to solve the problems of location and quantity of transit depot and disassembly center as well as vehicle routing. Then, a corresponding algorithm based on genetic algorithm and tabu search algorithm is designed. At last, the model is analysed and verified through a numerical example of Chengdu, and the location-routing for ELVs logistics recycling network is finished.

Key words：transport economics; location-routing optimization; combinational algorithm; end-of-life vehicle (ELV); recycling logistics network

文獻標識碼：A

文章編號：1002-0268(2016)03-0138-08

中圖分類號：U113;F540

doi:10.3969/j.issn.1002-0268.2016.03.023

作者簡介：賀政綱(1977-)，男，湖南安化人，博士，副教授.(wlxyhzg@163.com)

基金項目：國家社會科學基金項目(13CGL127)；四川省軟科學計劃項目(2013ZR0041)；四川省哲學社會科學研究規(guī)劃項目(SC12W022)；中央高?；究蒲袠I(yè)務費專項資金項目(2682014CX101)。

收稿日期：2015-03-19