B2C電子商務中帶退貨的多配送站點車輛路徑優化問題研究

馮芳媛，張麗華，李阿慧（沈陽師范大學，遼寧 沈陽110034）

0 引 言

由于B2C 電子商務市場的發展在社會消費品零售總額中的比重逐年增加，使得電子商務企業之間的競爭越來越大，企業為贏取更大的效益必須不斷完善其物流配送體系。然而近幾年來隨著電子商務的發展以及消費者維權意識的增強，使得產品退回事件趨于增多，這就要求在發展正向物流配送的同時考慮逆向物流配送，以減少因退貨帶來的損失，為此本文討論了一個B2C電子商務下帶退貨的多配送站點車輛路徑優化問題。

針對B2C電子商務下的車輛路徑優化問題的研究成果較少[1-3]，而且都是研究不帶退貨的情形，而對帶退貨車輛路徑優化問題，多數學者只研究了單配送中心的情形[4-8]，少數學者研究了多配送中心的情形[9-11]，但這些研究中未考慮車輛的啟動費用，而且有的文獻還要求送貨優先于退貨，本文在加入車輛啟動費用的同時改進車輛的車載限制約束，極小化車輛使用數目和總的運輸費用，建立了更符合實際情況的帶退貨的多配送站點車輛路徑優化問題的模型并給出用一次禁忌搜索算法直接求解的方法。

1 問題描述

一個B2C電子商務企業在一個小區域內建有m個配送站點負責完成為n顧客配送的任務。當有客戶訂貨（或退貨）時，要求根據客戶的地理位置及需求（或退貨）量，在配送站點中進行選擇并確定實際配送路線，完成配送訂貨和取回退貨任務，使得總費用（包括車輛行駛費用和車輛一次啟動費用）最小。

當m=1并限定配送站點的車輛數為1、各個客戶只有需求時，上述問題就是旅行商問題，因此旅行商問題是本文所討論問題的子問題。因旅行商問題是NP－hard的，所以本文的問題也是NP－hard的。

2 數學建模

假設每個配送站點的可用車輛數一定、車型一樣，且每輛車僅隸屬于一個配送站點；每輛車從各自所屬的配送站點出發，完成配送和取貨任務后裝載回收的退貨返回其所屬配送站點；每個客戶僅能由一個配送站點的一輛車服務；每個配送站點無存儲量限制。

用1,2,…,m表示配送站點編號，令D=｛1,2 , …,m｝；m+1,…,m+n表示客戶編號（其中既包括訂貨的客戶也包括退貨的客戶，還有可能一個客戶既有退貨又有訂貨），令C=｛m+1,…,m+n｝；dij、cij分別表示i與j之間的距離和i與j之間單位距離的運輸費用，（i,j∈D∪C，且當i=j時dij=0,cij=0）；qj、pj分別表示客戶j（j∈C）的需求量與退貨量；Ki、Ai、mi、ni分別表示配送站點i（i∈D）的車輛集合、可用車輛數、要配送的貨物總量、收到的顧客的退貨總量，且當i,j∈D,i≠j時Ki∩Kj=?；K表示所有車輛的集合；R、B分別表示每輛車的車載限制和一次性啟動費用；Qjk、Pjk（k∈ K）當j∈D時分別表示車輛k在其所屬的配送站點j的載貨量和車輛k從其所屬的配送站點j出發或返回所屬的配送站點時回收的退貨總量，當j∈C時分別表示車輛k到達顧客j處裝載的還未配送的貨物總量（不包括j處的需求量）與車輛k從其所屬的配送站點出發到達顧客j處回收的退貨總量（包括j處的退貨量）；設決策變量為：

那么當ωi=0且k∈Ki時，有Qjk=0，Pjk=0,?j∈D∪C；當ωi=1時，如果yjk=0,也有Qjk=0，Pjk=0,?j∈D∪C。于是本文的問題可用下列的0－1整數規劃模型描述：

上式（1）表示車輛行駛費用和車輛一次性啟動費用之和，其中車輛一次性啟動費用按車輛使用數量計算；（2）每個客戶只能由一輛車服務且僅能服務一次；（3）保證如果客戶由一輛車服務則該車恰好訪問此客戶一次；（4）車輛不在配送站點之間行駛；（5）每個客戶屬于且僅屬于一個配送站點；（6）每個客戶由它所屬的配送站點的一輛車進行服務；（7）配送站點的總供應量小于等于其客戶的需求量；（8）配送站點回收的退貨總量等于其客戶的所有退貨之和；（9）每個配送站點的可用車輛數限制；（10）～（12）配送過程中的車載限制；（13）保證每輛車從各自的配送站點出發，完成任務后返回原配送站點；（14）若配送站點沒有選用則無客戶由此配送站點服務。

3 模型求解

由于本文討論的問題是NP-hard的，所以下面給出一個禁忌搜索算法來對其進行求解。

3.1 禁忌搜索算法中求初始可行解的方法

因為禁忌搜索算法對初始解具有很大的依賴性，即最終解的質量以及收斂速度都與初始解有很大的關系，所以在本文給出的禁忌搜索算法中首先調用下面的算法1來產生一個較好的初始可行解。

算法 1：

第一步：修改文獻[12]的算法對配送站點和顧客按著下列方法進行分組：

（1）針對每一個配送站點計算其可接收的貨物總量=其可用車輛數×車載。

（3）取一適當的δ（0≤δ≤1），比較r（i）與δ的大小，若r（i）＜δ就稱點i為非臨界點，否則稱點i為臨界點。

（4）對非臨界點的分派如下：①將所有非臨界點客戶按r（i）從小到大進行排列；②將各個配送站點總的配送量和總的回收量都賦值為空；③按著①的順序對每一非臨界點客戶執行下列操作：a將各個配送站點按與該非臨界點客戶的距離由小到大順序排列；b按a的順序尋找第一個滿足下列條件的配送站點：這個配送站點原來總的配送量+要分派的這個非臨界點客戶的需求量不超過它所擁有的車數×R，并且它原來的總回收量+要分派的這個非臨界點客戶的退貨量不超過它所擁有的車數×R，將該非臨界點客戶分配給它，更新這個配送站點總的配送量=原來總的配送量+要分派的這個非臨界點客戶的需求量，總的回收量=它原來的總回收量+要分派的這個非臨界點客戶的退貨量。

（5）對臨界點的分派如下：將所有臨界點顧客按需求量與退貨量的和從大到小排列，若同時存在幾個客戶的需求量與退貨量之和相等，則按r（i）從小到大的順序將這些客戶進行排列，之后按此順序依次對它們執行對非臨界點分派的③中的a與b操作。

注：對非臨界點而言，最近距離與次近距離相差較大，所以對其分派主要考慮的是距離，而對臨界點而言，最近距離與次近距離相差較小，所以對其分派主要考慮的是運量。

由此可得到一種分派，每個被選的配送站點都有一組要服務的顧客且能夠滿足其服務的顧客要求。

第二步：將文獻[12]的C-W節約算法進行修改來實現對每個配送站點和其服務的顧客進行路徑優化，其過程如下：

（1）計算節約值s（i,j）=di0+d0j－dij，令M=｛s（i,j）＞0|i,j∈C∪D,i≠j｝。

（2）在M內按s（i,j）從大到小的順序排列。

（3）若M=?，終止，否則對M中第一項s（i,j）考察對應的（i,j），若滿足下述條件之一就轉（4），否則轉（7）：

①點i與點j均不在已構成的線路上；

②點i或點j在已構成的線路上，但不是線路的內點（即不與車場相連）；

③點i與點j位于已構成的不同線路上，均不是內點，且一個是起點，一個是終點。

（4）計算點i與點j連接后線路上的總需求量Qi與總退貨量Pi，若Qi≤R且Pi≤R，（R為車載）轉（5），否則轉（7）。

（5）從起始點（配送站點）開始依次計算車輛到達線路上每一個客戶點時的裝載量（裝載量的計算方法為：起點的裝載量為整個線路上所有客戶的配送量之和，而線路上各個客戶處的裝載量為線路上該客戶緊前點的裝載量-該客戶的配送量+該客戶的退貨量），若滿足車載限制則轉（6），否則轉（7）。

（6）連接點i和點j。

（7）令M=M－s（i,j），轉（3）。

3.2 禁忌搜索算法中解的表示方法

本文參考文獻[13]給出求解帶退貨的多配送站點車輛路徑優化問題一種新的解的表示方法，下面舉例對該方法進行說明：假設有3個配送站點，6個顧客的問題，若其解為x=（14711282359363），則表示：配送站點1：可用車輛數為2輛，第一輛車的行駛路線為1-4-7-1；第二輛車行駛路線為1-1即未使用；配送站點2：可用車輛數為1輛，行駛路線為2-8-2；配送站點3：可用車輛數為2輛，第一輛車的行駛路線為3-5-9-3；第二輛車行駛路線為3-6-3。由此種解的表示方法既可以表示出每輛車的行駛路線又可以表示出每個配送中心擁有的可用車輛數目，所以是一種有效的表示方法。

3.3 禁忌搜索算法中的鄰域結構

本文針對多配送中心車輛調度問題的特點對頂點重新指派法[14]進行改進，按此方法實施鄰域操作可以實現線路的調整與合并。改進后的頂點重新指派方法步驟為：隨機從解中選取兩個節點，按如下情況進行操作：若所選的兩個節點均為配送中心，則不進行節點間的重新指派；若所選的兩個節點均為客戶，則將第二個節點從其線路中取出并插入到所選的第一個節點的位置之前；若所選的第一個節點為客戶，第二個節點為配送中心，那么如果第二個節點的緊前點為異于該配送中心的其它配送中心，則不進行節點間的重新指派；否則，將第一個節點從其線路中取出并插入到所選的第二個節點的位置之前；若所選的第一個節點為配送中心，第二個節點為客戶，此時需分情況討論：（1）若第一個節點為總線路的起點，則不進行節點間的重新指派；（2）若第一個節點的緊前點為異于該配送中心的其它配送中心，則不進行節點間的重新指派；否則，將第二個節點從其線路中取出并插入到所選的第一個節點的位置之前。

3.4 禁忌搜索算法中解的評價

本文所研究的模型因為車輛行駛具有啟動費用，而一般認為啟動費用是一個非常大的數，多用一輛車所增加的啟動費用要遠遠大于其總行駛路程縮短而帶來的節省，因此將極小化車輛使用數目作為第一目標，極小化車輛行駛費用作為第二目標[14]。為了充分對解空間進行搜索，接受導致不可行解的鄰域變換，當違反了車輛裝載能力限制時，其不可行性的程度可以引進一個懲罰值將該約束條件包含到目標函數中去進行度量，為此設p為懲罰因子，在本文中令，用E（x）表示對給定的解x的不可行程度實施懲罰的量，其計算方式如下：若x中共有ux條線路不可行，則，設x對應的目標函數值為fx，那么解x的評價值等于p×E（x）+fx。

3.5 禁忌搜索算法中禁忌對象、禁忌長度、候選集合以及終止準則的確定

本文將每次迭代得到的局部最好解（評價值最小）localbestjie（不一定可行）作為禁忌對象放入禁忌表中；取禁忌長度為一個常數l，其值根據問題的規模來確定；將從當前解的鄰域中隨機選擇N個鄰居作為候選集合；采用迭代指定步數T的終止準則。

禁忌搜索算法：

步驟1：初始化：為dij（i,j∈D∪C）、qj,pj（j∈C）、K、T、l、N、p賦值，調用上面的算法1求得一個初始可行解x0，初始化禁忌表H←｛x0｝，令迭代步數t←0；用localbestjiezhi記錄localbestjie的評價值，用Sbest與Ebest分別記錄次優可行解和其目標函數值，并令Sbest←x0，Ebest←x0的評價值；M是所有解的評價值的一個上界，令，x記錄每次迭代時用于實施鄰域操作的解，并令x←x。0

步驟2：當t＜T時重復下列操作，否則轉步驟3：

（1）localbestjie←?，localbestjiezhi←M；n←1。

（2）當n＜N時重復下列操作，否則轉（3）：

①對x用頂點重新指派法實施鄰域操作，得到x的一個鄰居x'；

②對x'執行下列操作：若x'?H，求x'的評價值，若x'的評價值小于localbestjiezhi，令localbestjie←x'，localbestjiezhi←x'的評價值，n←n+1轉①，否則令n←n+1轉①；若x'∈H，令n←n+1轉①。

（3）若 localbestjiezhi≥Ebest轉（4），否則令 Sbest←localbestjie；Ebest←localbestjiezhi轉（4）。

（4）如果禁忌長度＜l將localbestjie放在禁忌表的末尾，令x←localbestjie，t←t+1轉步驟2，否則將禁忌表的第一個元素解禁，之后將localbestjie放在禁忌表的末尾，令x←localbestjie，t←t+1轉步驟2。

步驟 3：輸出Sbest和 Ebest。

4 計算實例

假設某一B2C電子商務企業在某一區域內建有3個配送站點，其中第一個配送站點擁有2輛車，第二個配送站點擁有3輛車，第三個配送站點擁有2輛車，每輛車的車型都一樣載重都為10噸，某一時刻有17個需要服務的顧客，客戶的需求量或退貨量以及點對之間的距離分別如下面的表1和表2所示。要求在配送站點中合理選擇車輛并安排行駛路線使總費用最小。

表1 各客戶點的需求量和退貨量

用禁忌搜索算法進行求解，其中迭代步數取400，每次迭代共搜索當前解的40個鄰居，禁忌長度取5，車輛一次啟動費用為300，在本例中設單位距離的運輸費用cij=1,i,j∈｛1,2 , …,20｝。

應用算法1得到初始可行解及其目標函數值分別為：

用禁忌搜索算法求得的可行解及其目標函數值分別為：

由此例可以看出，禁忌搜索算法對初始可行解的改進效果是比較明顯。

5 結 論

本文對帶退貨的多配送站點車輛路徑優化問題進行了描述，為求解該問題提出了一種新的解的表示方法和鄰域變換，從而構造了直接求解帶退貨的多配送站點車輛路徑優化問題的禁忌搜索算法，該算法具有良好的尋優性能，所設計的解的表示方法直觀且操作簡便，易于理解。此外為了更符合B2C電子商務的經營特點可加入時間窗約束，我們將下一步對其進行研究。

表2 各點對之間的距離

[1]李維健.B2C電子商務模式下物流配送路徑優化問題研究[D].北京：北京交通大學（碩士學位論文），2006.

[2]許志生.B2C網上超市與敏捷配送相結合的新零售模式研究[D].鎮江：江蘇大學（碩士學位論文），2010.

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

[4]隆穎.用遺傳算法求解帶同樣取貨的車輛路徑問題[J].遼寧師專學報：自然科學版，2005,7(3):86-88.

[5]郭伏，隆穎.帶時窗同時取貨的車輛路徑問題的算法[J].東北大學學報，2006,27(5):575-578.

[6]胡天軍，程文科.帶回程取貨的逆向物流車輛路徑建模及蟻群算法[J].交通運輸系統工程與信息，2010,10(3):110-114.

[7]Zhang H.G.,WU Y.X..Study on the model and improved immune algorithm for vehicle routing problem with backhauls[C]//International Conference on Computing,Control and Industrial Engineering,2010:371-374.

[8]Shu C.L.,Chich H.C..A heuristic method for the vehicle routing problem with backhauls and inventory[J].Journal of Intelligent Manufacturing,2009,20:29-42.

[9]Fan J.H.,Wang X.F.,Chen Q.S..A heuristic algorithm for multiple depots vehicle routing problem with backhauls[C]//Fourth International Conference on Fuzzy Systems and Knowledge Discovery,2007.

[10]Ren C.Y.,Wang X.B..Study on improved hybrid genetic algorithm for multi-depot vehicle routing problem with backhauls[C]//International Conference on Artificial Intelligence and Computational Intelligence,2009:347-350.

[11]Ren C.Y.,Wang X.B..Study on hybrid genetic algorithm for multi-type vehicles and multi-depot vehicle routing problem with backhauls[C]//Second International Conference on Intelligent Computation Technology and Automation,2009:197-200.

[12]李軍，郭耀煌.物流配送車輛優化調度理論與方法[M].北京：中國物資出版社，2001.

[13]郎茂祥，胡思繼.車輛路徑問題的禁忌搜索算法研究[J].管理工程學報，2004,18(1):81-84.

[14]符卓.帶裝載能力約束的開放式車輛路徑問題及其禁忌搜索算法研究[J].系統工程理論與實踐，2004(3):123-128.