帶退貨的周期車輛路徑問題的C—W節(jié)約算法

竇冰潔 張麗華 趙麗娜 孫蕊

摘 要：文章用MATLAB代碼給出了一個改進的C-W節(jié)約算法來求解帶退貨的周期車輛路徑問題，目標是最小化周期內(nèi)總的行駛費用和總的啟動費用之和，并舉例對算法進行了說明。

關(guān)鍵詞：運籌學(xué)；周期車輛路徑問題；C-W節(jié)約算法

中圖分類號：U116.2 文獻標識碼：A

Abstract： In this paper， an improved C-W saving algorithm is given by MATLAB codes to solve the periodic vehicle routing problem with backhauls， aiming to minimize the sum of the total travel expenses and the total startup cost over the planning horizon， an example is gives to illustrate the algorithm.

Key words： operations research； periodic vehicle routing problem； C-W saving algorithm

0 引 言

周期車輛路徑問題（Period Vehicle Routing Problem， PVRP）是車輛路徑問題（Vehicle Routing Problem， VRP）的一個重要的分支，最早由Beltrami和Bodin[1]于1974年提出，是VRP在時間上的擴展，而由于企業(yè)很多計劃都是按一定的周期來制定的，所以PVRP有著很強的實用價值，因此到目前為止國內(nèi)外對其進行的研究已有很多成果：Ann和Jill[2]對國外從1974到2012年這方面的文獻以及2013年的部分文獻進行了詳細綜述，之后又有10多篇文獻[3-13]對PVRP進行了研究。國內(nèi)學(xué)者在VRP領(lǐng)域進行了大量的研究，但目前對PVRP方面的研究還比較少：姜貴山[14]設(shè)計了改進的引導(dǎo)鄰域搜索算法、蔡婉君等[15]給出了改進的蟻群算法來求解PVRP。以上這些文獻可分為兩種類型：（1）只送貨的PVRP問題；（2）帶取送貨（pickup and delivering）的PVRP。其中只有文獻[10]和[16]是研究類型（2）的，然而近年來，保障商品質(zhì)量、上架及時和退貨服務(wù)成為電商及大型連鎖超市應(yīng)對激烈的市場競爭的關(guān)鍵所在，而在這一過程中物流配送是核心環(huán)節(jié)，因此受到了高度的關(guān)注。另外，不同種類貨物的銷售多受地域影響，以及消費者維權(quán)意識的增強，使得超市間貨物調(diào)換和產(chǎn)品退回事件趨于普遍，這就要求發(fā)展逆向物流配送系統(tǒng)，因此，本文研究了一個帶退貨的PVRP，該問題隸屬于類型（2）中帶同時取送貨的PVRP，而且要求每個客戶在其被服務(wù)的各個時間段里取貨和送貨任務(wù)都由一輛車來完成，這與文獻[10]和[16]研究的問題都有所不同。

1 問題描述及數(shù)學(xué)模型

1.1 問題描述

在一個區(qū)域內(nèi)有一個配送站點（車場），m個顧客，一個周期中有T個時間段，顧客ll=1，2，…，m在周期內(nèi)要求的服務(wù)次數(shù)（以下簡稱頻率）為f0

當各個顧客的退貨量都是零時上述問題就是傳統(tǒng)的PVRP，因此傳統(tǒng)的PVRP是本文所討論問題時的子問題。因PVRP是NP-hard的，所以本文的問題也是NP-hard的。

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

令N為顧客點集合，N=1，2，3，…，m，0表示車場；A為弧的集合，a為連接客戶點i和j的弧；d和c分別表示i與j之間距離和單位距離的運輸費用（當i=j時，d=0， c=0）；K表示所有車輛集合；Q和C分別表示每輛車的車載限制和一次性啟動費用；在周期為T個時間段計劃中，f表示客戶i要求的頻率，分別表示客戶i在第t個時間段t∈T的需求量與退貨量。模型中決策變量為：w表示第t天弧a上的車載量。

式（1）的第一項為總的行駛費用，第二項為總的啟動費用；式（2）保證對每一個客戶點總訪問次數(shù)等于其要求頻率；式（3）表示被一輛車依次服務(wù)的兩個客戶點必須被安排在同一個時間段；式（4）為流平衡約束：在第tt=1，…，T個時間段進入某點的車輛數(shù)等于從此點出去的車輛數(shù)；式（5）表示分配到每一個時間段的所有客戶點在該時間段都被訪問到；式（6）為子回路消去約束；式（7）表示一輛車在一個時間段內(nèi)最多只被用一次；式（8）至式（10）表示車輛在行駛過程中的車容量約束；式（11）至式（13）定義變量的取值范圍。

2 問題求解

姜貴山[20]設(shè)計改進的引導(dǎo)鄰域搜索算法中，提出應(yīng)用C-W節(jié)約算法構(gòu)建PVRP的初始可行解。本文對此算法做出進一步改進，得到解決本問題的改進C-W 節(jié)約算法，下面用Matlab代碼給出該算法。

function [solution， Customers_just_information]=Modified_CW_SAT，m，f，M，p，q，Q本函數(shù)Modified_CW_SA為求解帶退貨的周期車輛路徑問題的修改C-W節(jié)約算法。

T，m，Q： 分別存儲周期長度、客戶數(shù)量、車輛容量；f： 是一個1×m矩陣，存儲所有客戶的頻率；M： 是一個m×m矩陣， 存儲所有客戶間的節(jié)約值；p，q： 都是T×m矩陣， 分別存儲每個時間段所有客戶的需求量和退貨量；solution：是一個T行m+1列的元胞數(shù)組，各行第一個元素存儲該行對應(yīng)時間段路徑總數(shù)，其余元素分別存儲該行對應(yīng)時間段里的各條路徑； Customers_just_information： 是一個m行2列的元胞數(shù)組， 其第i行第1個元素Customers_just_informationi，1存儲一個1×T矩陣，該矩陣的第j個元素Customers_just_informationi，1j=0或1，前者和后者分別表示第i個客戶在第j個時間段沒有被服務(wù)和已經(jīng)被服務(wù)，Customers_just_information的第i行第2個元素Customers_just_informationi，2存儲一個T×3 矩陣，該矩陣的第t行第1-3個元素Customers_just_informationi，2t，s，s=1，2，3依次存儲第i個客戶在第t個時間段所在的路徑（在第k條路徑上就存k）、在該路徑上的位置（是該路徑上第u個客戶點就存u）、該路徑的長度。

Customers_just_information=cellm，2； solution=cellT，m+1；

for k=1：m

Customers_just_informationk，1=zeros1，T； Customers_just_informationk，2=zerosT，3；

end

for v=1：T

solutionv，1= 0；

end

temp_M=M：； hs，wz=sorttemp_M， 1，'descend'； temp=findM～=0，1；

while～isempty（temp）

for s=1：m^2

x，y=ind2subsizeM，wzs； wzs對應(yīng)的客戶點x，y；nx，ny：客戶點x，y當前已被服務(wù)的次數(shù)。

nx=sum（Customers_just_informationx，1（：））； ny=sum（Customers_just_informationy，1（：））；

if nx==fx&& ny==fy

Mx，y=0； temp_M=M（：）； hs，wz=sorttemp_M， 1，'descend'； temp=findM～=0，1； break

end

if nx==fx&& ny

left_ny=fy-ny； 客戶點y的剩余被服務(wù)次數(shù)

[newCustomers_just_information， newsolution]=Joint_point_to_endpoint （Customers_just_information， solution， x， y， left_ny， p， q， Q）； 調(diào)用函數(shù)Joint_point_to_endpoint來處理x為端點而y未被服務(wù)的那些時間段函數(shù)Joint_point_to_endpoint先在所有的時間段里尋找未完成路徑中以客戶點x為端點且在該時間段里客戶點y未被服務(wù)的時間段，之后判別在這些時間段里將客戶點y安排在客戶點x之前或之后是否可行且客戶點y被安排的次數(shù)不超過其剩余被服務(wù)次數(shù)left_ny， 如果滿足這些條件就更新Customers_just_information和solution，并將最終的更新結(jié)果分別賦值給newCustomers_just_information與newsolution返回。

Customers_just_information=newCustomers_just_information； solution=newsolution；

Mx，y=0； temp_M=M：；

hs，wz=sorttemp_M， 1，'descend'； temp=findM～=0，1； break

end

if nx

left_nx=fx-nx； 客戶點x的剩余被服務(wù)次數(shù)

[newCustomers_just_information， newsolution]=Joint_point_to_endpoint（Customers_just_information， solution， y， x， left_ nx， p， q， Q）； 調(diào)用函數(shù)Joint_point_to_endpoint來處理y為端點而x未被服務(wù)的那些時間段

Customers_just_information=newCustomers_just_information； solution=newsolution；

Mx，y=0； temp_M=M：； hs，wz=sorttemp_M， 1，'descend'； temp=findM～=0，1； break

end

if nx

left_ny=fy-ny； 客戶點y的剩余被服務(wù)次數(shù)

[newCustomers_just_information， newsolution]=Joint_point_to_endpoint（Customers_just_information， solution， x， y， left_ny， p， q， Q）； 調(diào)用函數(shù)Joint_point_to_endpoint來處理x為端點而y未被服務(wù)的那些時間段

Customers_just_information=newCustomers_just_information； solution=newsolution；

left_nx=fx-nx； 客戶點y的剩余被服務(wù)次數(shù)

[newCustomers_just_information， newsolution]=Joint_point_to_endpoint （Customers_just_information， solution， y， x， left_nx， p， q， Q）； 調(diào)用函數(shù)Joint_point_to_endpoint來處理y為端點而x未被服務(wù)的那些時間段

Customers_just_information=newCustomers_just_information； solution=newsolution；

ny=sum（Customers_just_informationy，1：）； nx=sum（Customers_just_informationx，1：）；

if nx

[newCustomers_just_information， newsolution]=Creat_two_points_path （solution， f， Customers_just_information， nx， ny， x， y， p， q， Q）； 生成新路徑：：車場→x→y→車場

函數(shù)Creat_two_points_path （solution， f， Customers_just_information， nx， ny， x， y， p， q， Q）首先尋找x，y都未被服務(wù)的時間段，如果這樣的時間段存在，就計算x，y剩余被服務(wù)次數(shù)left_nx，left_ny將最小者記為Min_Left_Delivery_Times，接著判斷路徑：車場→x→y→車場在x，y都未被服務(wù)的時間段中是否可行，如果可行，就在這些時間段中個數(shù)不超過Min_Left_Delivery_Times的時間段里生成新路徑：車場→x→y→車場，更新Customers_just_information和solution，并將最終的更新結(jié)果分別賦值給newCustomers_just_information與newsolution返回。

solution=newsolution； Customers_just_information=newCustomers_just_information；

ny=sum （Customers_just_informationy，1：）； nx=sum （Customers_just_informationx，1：）；

if nx

[newCustomers_just_information， newsolution]=Creat_two_points_path （solution， f， Customers_just_information， ny， nx， y， x， p， q， Q）； 生成新路徑：車場→y→x→車場

solution=newsolution； Customers_just_information=newCustomers_just_information；

end

end

Mx，y=0； temp_M=saving_values：； hs，wz=sort （temp_M， 1， 'descend'）； temp=findM～=0，1； break

end

end

end 此時所有客戶點間的節(jié)約值都變成了0

for h=1：m 處理未達到其頻率的客戶

nh=sum（Customers_just_informationh，1）； 客戶點h已經(jīng)被服務(wù)的次數(shù)nh

if nh

tem=find （Customers_just_informationh，1==0）； 找到客戶點h未被服務(wù)的所有時間段將它們存儲在tem里

for h1=1： fh-nh 在客戶點h未被服務(wù)的時間段里挑出其剩余頻率fh-nh個時間段，單獨派車對其進行服務(wù)

Customers_just_informationh，1temh1=1； solutiontemh1，1=solutiontemh1，1+1；

solutiontemh1， solutiontemh1，1+1=h；

end

end

end

3 例 子

在-500，500×-500，500的區(qū)域內(nèi)隨機產(chǎn)生21個點，第1個點為車場，其余的點為客戶（如圖1所示）。設(shè)一個周期為7個時間段，隨機產(chǎn)生每一客戶在周期內(nèi)要求的服務(wù)次數(shù)（簡稱為頻率）見表1，表2為每個客戶在各個時間段的需求量和退貨量。

根據(jù)本文所給出的改進的C-W節(jié)約算法，得到周期內(nèi)每個時間段的路徑及路徑數(shù)見表3。表3中第k行第s列（如果不空）k=2-8，s=2-8給出第k-1個時間段的第s-1條路徑，如第4行第5列為15，3，10，就表示第4個時間段第5條路徑為：車場→客戶點15→客戶點3→客戶點10→車場。

此例子中：①總的啟動費用為：（3+4+5+7+3+3+5）×10=300；

②總的行駛費用為：5.0773e+004；

③總費用為：300+（5.0773e+004）=5.1073e+004。

4 結(jié) 論

本文對帶退貨的單車場周期車輛路徑問題進行了描述，無論對于大型連鎖超市還是供貨商而言，此問題都有實際意義和商業(yè)價值。用MATLAB代碼給出了求解該問題的C-W節(jié)約算法，通過例子表明所設(shè)計的算法操作簡便，易于理解。

參考文獻：

[1] Beltrami E J， Bodin L D. Networks and vehicle routing for municipal waste collection[J]. Networks， 1974，4（1）：65-94.

[2] Ann M C， Jill H W. Forty years of periodic vehicle routing[J]. Networks， 2014，63（1）：2-15.

[3] Alper Hamzadayi， Seyda Topaloglu， Simge Yelkenci Kose. Nested simulated annealing approach to periodic routing problem of a retail distribution system[J]. Computers & Operations Research， 2013，40：2893-2905.

[4] Theodore A， Ioannis M. Efficient techniques for the multi-period vehicle routing problem with time windows within a branch and price framework[J]. Annals of Operations Research， 2013，206：1-22.

[5] Alireza R-V， Teodor GC， Michel G， et al. A path relinking algorithm for a multi-depot periodic vehicle routing problem[J]. Heuristics， 2013，19：497-524.

[6] Mohammad Mirabi. A hybrid electromagnetism algorithm for multi-depot periodic vehicle routing problem[J]. Int J Adv Manuf Technol， 2014，71：509-518.

[7] Phuong Khanh Nguyen， Teodor Gabriel Crainic， Michel Toulouse. A hybrid generational genetic algorithm for the periodic vehicle routing problem with time windows[J]. J Heuristics， 2014，20：383-416.

[8] V. Cacchiani， V. C. Hemmelmayr， F. Tricoire. A set-covering based heuristic algorithm for the periodic vehicle routing problem[J]. Discrete Applied Mathematics， 2014，163：53-64.

[9] Julien Michallet， Christian Prins， Lionel Amodeo， et al. Multi-start iterated local search for the periodic vehicle routing problem with time windows and time spread constraints on services[J]. Computers & Operations Research， 2014，41：196-207.

[10] Suyanto C， Herman M. A model for periodic vehicle routing problem with delivery and pick-up considering maximum distance[J]. International Journal of Science and Advanced Technology， 2014，4（8）：1-9.

[11] Narges Norouzi， Mohsen Sadegh-Amalnick， Mehdi Alinaghiyan. Evaluating of the particle swarm optimization in a periodic vehicle routing problem[J]. Measurement， 2015，62：162-169.

[12] Mohammad M. A novel hybrid genetic algorithm for the multidepot periodic vehicle routing problem[J]. Artificial Intelligence for Engineering Design， 2015，29：45-54.

[13] Alireza Rahimi-Vahed， Teodor Gabriel Crainic， Michel Gendreau， et al. Fleet-sizing for multi-depot and periodic vehicle routing problems using a modular heuristic algorithm[J]. Computers & Operations Research， 2015，53：9-23.

[14] 姜貴山. 周期性車輛路徑問題的引導(dǎo)式鄰域搜索算法設(shè)計及應(yīng)用[D]. 上海：上海交通大學(xué)（碩士學(xué)位論文），2010.

[15] 蔡婉君，王晨宇，等. 改進蟻群算法優(yōu)化周期性車輛路徑問題[J]. 運籌與管理，2014，23（5）：70-77.

[16] Peter F， Karen S， Michal T. The period vehicle routing problem with service choice[J]. Transportation Science， 2006，40（4）：439-454.