范厚明， 徐振林， 李 陽， 楊 翔

(大連海事大學 交通運輸工程學院，遼寧 大連 116026)

0 引言

開放式多中心需求可拆分車輛路徑問題(Open Multi-Depot Split Delivery VRP，OMDSDVRP)允許車輛從任意配送中心出發(fā)，完成配送任務后就近返回配送中心，同一個客戶允許被多輛車進行訪問。

Gulczynski等[1]首次提出多中心需求可拆分車輛路徑問題(Multi-Depot Split Delivery VRP，MDSDVRP)問題，利用文獻[2]的方法建立數(shù)學模型，然后采用文獻[3]中的巡回算法優(yōu)化路徑。Soeanu等[4]設計了啟發(fā)式算法對MDSDVRP問題進行求解。Ray等[5]的研究與文獻[1]不同的是，在文獻[5]中同一客戶既可以由不同配送中心也可以由同一配送中心的不同車輛進行配送。Wang等[6]研究了MDSDVRP問題，設計三階段啟發(fā)式算法進行求解。

綜上，以上參考文獻還有以下幾點未考慮：

(1)多配送中心車輛路徑問題，先將客戶進行分組，然后進行路徑規(guī)劃，易導致客戶劃分不合理，配送中心資源不能合理利用等情況。

(2)需求可拆分的車輛路徑問題，不應限制每次訪問客戶的車輛來源，即來自不同配送中心的車輛也可對同一客戶進行多次訪問。

(3)多中心車輛路徑問題，不應限制車輛完成配送任務后返回的配送中心，就近返回既能降低配送成本，又能實現(xiàn)資源共享。

(4)載重對于油耗的影響至關重要，忽略載重的變化，不能切實反映實際能源消耗。此外，針對需求可拆分的車輛路徑問題，應考慮理貨成本對總成本的影響。

結合以上未考慮的因素，對開放式多中心需求可拆分車輛路徑問題(OMDSDVRP)展開研究。

1 OMDSDVRP的提出

圖1(a)為傳統(tǒng)VRP問題示意圖，當車輛載重不足，則返回配送中心進行補貨；圖1(b)為需求可拆分VRP問題示意圖，當車輛載重不足，可先服務客戶的部分需求，剩余需求由下一輛車進行服務；圖1(c)為MDSDVRP問題的示意圖，允許來自不同配送中心的車輛對同一客戶進行服務，車輛服務完成后，返回原配送中心；圖1(d)為本文研究的OMDSDVRP問題示意圖，允許來自不同配送中心的車輛對同一客戶進行服務，車輛服務完成后，返回就近的配送中心。

2 問題描述及模型建立

2.1 問題描述

假設配送網(wǎng)絡有完備的有向圖：配送網(wǎng)絡中所有節(jié)點集合V=D∪C∪0={0,1,…,m,m+1,…,m+n}，其中D={1,2,…,m}代表配送中心集合，C={m+1,m+2,…,m+n}代表客戶集合，K={1,2,…,k,…|K|}代表配送車輛集合。0為虛擬配送中心，其與其他配送中心的距離為0。E={(i,j)|i,j∈V}代表配送網(wǎng)絡中所有邊的集合。di代表客戶i點的配貨需求量，Q代表配送車輛的額定裝載量，dij代表兩點之間的直線距離，ω代表道路迂回系數(shù)。tj代表客戶j被配送車輛訪問的次數(shù)，sjk代表配送車輛k配送給客戶j的貨物數(shù)量。Ci代表配送中心的日均建設成本，Ck代表配送車輛的固定成本，Ci代表配送車輛服務一次客戶的理貨成本。xijk表示配送車輛k是否從點i到點j。yij表示服務客戶j的車輛是否來自配送中心i。

2.2 油耗成本分析

油耗成本受配送車輛服務客戶的方向影響較大，其主要原因是配送裝載量的變化。圖2展示了配送方向對油耗的影響。

(1)

由于配送車輛油耗率受路況的影響，則油耗率可用式(2)表示。

(2)

φij代表節(jié)點i到節(jié)點j的道路狀況系數(shù)，φij=1，表示道路通暢；φij>1，表示道路擁堵。

綜上，配送車輛的油耗成本為:

Cijk=c·rijk·dij

(3)

其中c為油價。

2.3 模型建立

綜上分析，本文建立的模型如下:

(4)

(18)

式(4)以配送中心日均建設成本、車輛固定成本、理貨成本和油耗成本之和最小為目標；式(5)表示每個客戶最少被配送車輛訪問一次，最多被配送車輛訪問兩次；式(6)表示對于任一個客戶，最少有來自一個配送中心的車輛對其進行服務；式(7)表示進入該點的車輛數(shù)量等于離開該點的車輛數(shù)量；式(8)表示每條配送路徑的起止點都是虛擬中心0；式(9)表示從配送中心派出的車輛數(shù)限制；式(10)表示車輛的載重限制；式(11)表示兩個配送中心之間沒有路徑連接；式(12)表示每輛車最多從一個配送中心出發(fā)，且只有一條服務路徑；式(13)為子回路消除約束；式(14)表示有路徑連接客戶與配送車輛出發(fā)時的配送中心；式(15)表示任一配送中心都能滿足客戶的配貨需求；式(16)表示車輛對客戶的配貨量應大于0；式(17)、(18)定義決策變量取值。

2.4 最優(yōu)解理論

Dror等給出關于SDVRP的最優(yōu)解定理，結合文獻[3]中的定理，給出以下定理及證明。

定理若客戶點之間的距離符合三角形不等式規(guī)則，則任意兩條配送路徑最多有一個拆分點。

證明如圖3(a)所示，d1和d2為客戶點C1、C2的配貨量，配送路徑Ra和Rb對C1、C2的配貨量是d1a、d1b、d2a、d2b。

圖3(b)中將Ra路徑上的d2b轉至Rb，同時將Rb上的配貨量d2b轉至Ra。圖3(c)為各路徑的配送方案，可以看出C1由Ra和Rb共同服務，C2只由Ra服務。

3 混沌遺傳模擬退火算法

本文設計混沌遺傳模擬退火算法對OMDSDVRP問題進行求解。

在初始解生成過程中引入混沌系統(tǒng)，以增加解的多樣性、遍歷性，式(19)為Logistic映射方程:

xn+1=rxn(1-xn),n=1,2,…

(19)

其中r∈(3.57,4]，xi∈[0,1]。

本文采用整數(shù)編碼方式，算法流程見3.1節(jié)。

3.1 算法具體描述

步驟1參數(shù)設置。

步驟2路徑編碼。包括全路徑編碼和子路徑編碼。

步驟3初始化種群。

步驟3.1用式(19)生成Logistic映射初值。

步驟3.2產(chǎn)生初始種群。

步驟4令gen=1，把初始種群視為當代種群。

步驟5取第一條染色體生成配送方案。

步驟6計算各子路徑上車輛訪問的第一個和最后一個客戶到各配送中心的距離，根據(jù)就近原則返回配送中心。

步驟7計算該染色體的總行駛距離。

步驟8重復執(zhí)行步驟5～7，得到每條染色體的總行駛距離。

步驟9若當代最優(yōu)染色體的總行駛距離小于歷史最優(yōu)總行駛距離，則接受該染色體；否則，拒絕。

步驟10解的擾動。本文采用三種變鄰域操作，并設計自適應進化壓力和鄰域半徑搜索策略提高搜索效率：

(2)引入鄰域半徑搜索策略，提高求解效率，具體流程見3.2節(jié)。

步驟11更新解。采用Metropolis準則接受較差的解。

步驟12重復步驟4～11，直到gen>MAXGEN。

3.2 解的擾動策略

(1)0-1 Exchange。隨機選擇2個客戶，把第二個客戶插入到第一個客戶的前面。

(2)1-1 Exchange。隨機選擇2個客戶并互相交換位置。

(3)2-opt。隨機先選擇2個作用弧，交換每個作用弧上其中一個客戶的位置。

(4)鄰域半徑搜索策略[7]。

步驟1設置range為客戶o的鄰域搜索半徑，其中range=3～8；

步驟2計算dij；

步驟3range個與客戶i最近的客戶被挑選出，組成搜索范圍。

4 算例驗證及結果分析

本文設置參數(shù)pop_size=200～1000，MAXGEN=50～1000，r=4。

實驗1取文獻[8,9]中的算例進行求解，表1給出了求解結果，就總行駛距離而言，本文算法比文獻[8]改進了7.09%，比文獻[9]改進了1.23%。實驗結果表明本文使用網(wǎng)絡化聯(lián)合配送方式，具有較好的求解效果。

表1 實驗1結果分析

采用文獻[8]中的算例，用本文設計的算法與其他幾種啟發(fā)式算法進行比較，實驗結果如表2所示。實驗結果表明：本文設計的算法具有較強的求解性能、穩(wěn)定性較好。

表2 實驗1結果對比

實驗2對文獻[10]中客戶規(guī)模為30～50的算例進行求解，與文獻[10]的對比結果如表3所示。實驗結果表明：本文設計的混沌遺傳模擬退火算法能找到9個算例的已知最優(yōu)解，文獻[10]中的兩種算法均未找到已知最優(yōu)解。本文設計的混沌遺傳模擬退火算法的平均偏差為0.67%，均小于其他兩種算法，再次證明算法的穩(wěn)定性。

表3 實驗2結果對比

實驗3對MDVRP標準算例進行測試，與文獻[11]的對比結果如表4所示。實驗結果表明：本文設計的混沌遺傳模擬退火算法的平均偏差為0.26%，小于GRASP/VND，證明了本文算法的穩(wěn)定性。

表4 實驗3結果對比

算例p01、p02最優(yōu)行駛路徑以及最短路徑變化趨勢如圖4所示，其中1～4代表配送中心，5～54代表客戶。

實驗4用文獻[8,9]中算例文獻[10]和本文設計的算法進行分析，對比結果如表5所示。實驗結果表明：文獻[10]設計的算法與本文算法的求解質量相差不多，但本文算法的自適應進化壓力和鄰域半徑搜索策略提高了求解效率。

表5 實驗4不同算法求解結果統(tǒng)計表

表6展示了以下四種算法的求解結果。圖5為收斂迭代圖。

表6 四種算法運行結果比較

實驗5對文獻[12]中算例SQ1進行修改，修改如下：Q=10t，客戶需求量也相應修改，u1=0.15L/km,u2=0.4L/km,c=6,ω=1.2,Ci=20,Ck=5,Ct=2.5,φij∈[1,1.25]。

表7展示了本文算法對以下三種模式的求解結果。實驗結果表明：OMDSDVRP模式的總配送成本最低，MDVRP模式的總配送成本最高。OMDSDVRP模式實現(xiàn)了車輛資源和客戶資源的整合，再次驗證了本文模型的有效性。

表7 實驗5結果對比

5 結論

本文針對OMDSDVRP進行了研究，主要結論如下：

(1)OMDSDVRP模型充分利用各配送中心的資源，實現(xiàn)了資源共享。

(2)混沌遺傳模擬退火算法引入混沌系統(tǒng)增加初始解的多樣性，自適應進化壓力和鄰域半徑搜索策略提高求解效率。

(3)通過對多組不同規(guī)模不同類型的算例進行求解，驗證了本文算法具有較強的搜索性能。