考慮供給商品價(jià)格的多車場(chǎng)車輛路徑問(wèn)題

魯建廈，洪歡蕾，陳青豐

(浙江工業(yè)大學(xué) 工業(yè)工程研究所，浙江 杭州 310014)

?

考慮供給商品價(jià)格的多車場(chǎng)車輛路徑問(wèn)題

魯建廈，洪歡蕾，陳青豐

(浙江工業(yè)大學(xué) 工業(yè)工程研究所，浙江 杭州 310014)

針對(duì)在煙草、石油和食品等生產(chǎn)配送行業(yè)，由于各地生產(chǎn)成本不同，導(dǎo)致商品由不同工廠所生產(chǎn)配送的補(bǔ)給價(jià)格存在差異，為了在車輛調(diào)度問(wèn)題中綜合考慮供給成本和運(yùn)輸成本，并使得總成本最小化，開(kāi)展了考慮商品供給價(jià)格的多車場(chǎng)車輛路徑問(wèn)題研究.建立了基于分布式生產(chǎn)銷售系統(tǒng)考慮商品供給價(jià)格的多點(diǎn)配送車輛路徑優(yōu)化模型；為了求解優(yōu)化模型，同時(shí)根據(jù)考慮供給價(jià)格的多車場(chǎng)車輛路徑問(wèn)題的性質(zhì)和特征，構(gòu)造出初始解，并結(jié)合8個(gè)鄰域結(jié)構(gòu)和局部搜索算法，設(shè)計(jì)了改進(jìn)變鄰域搜索算法；最后通過(guò)實(shí)例，驗(yàn)證了算法的有效性.

供給價(jià)格；多車場(chǎng)車輛路徑問(wèn)題；變鄰域搜索

多車場(chǎng)車輛路徑問(wèn)題一直是困擾學(xué)者的一類典型的NP難題，由于社會(huì)化物流需求不斷提高，物流成本占生產(chǎn)制造成本的比例一直居高不下，因此引起了國(guó)家、企業(yè)和學(xué)術(shù)界廣泛的關(guān)注.Dantzig等[1]在1959年最早把車輛路徑問(wèn)題(Vehicle routing problem ，VRP)作為“卡車調(diào)度問(wèn)題”進(jìn)行研究.

針對(duì)多車場(chǎng)車輛路徑問(wèn)題，Golden等[2]針對(duì)MDVRP提出了兩種解決方法，一是改進(jìn)后的節(jié)約里程法，二是“先分配，后路線”的兩階段方法.Cordeau等[3]研究了有時(shí)間窗約束的多車場(chǎng)路徑問(wèn)題(Multiple-depot vehicle routing problem with time window, MDVRPTW)，并提出了統(tǒng)一的禁忌搜索框架.Polacek等[4]使用了變鄰域搜索算法來(lái)求解MDVRPTW，在計(jì)算過(guò)程中，首先采用Cross-Exchange算子產(chǎn)生鄰域解，然后利用加強(qiáng)的3-Opt算子來(lái)執(zhí)行局域搜索.趙燕偉等[5]研究了多車型同時(shí)取送貨的多車場(chǎng)低碳路徑問(wèn)題，并采用了量子進(jìn)化算法進(jìn)行求解.魏云飛等[6]研究了非滿載車輛調(diào)度問(wèn)題，提出了免疫遺傳算法.陳曉瞇等[7]研究了需求不確定下的帶時(shí)間窗車輛調(diào)度問(wèn)題，并提出了一種混合禁忌搜索算法進(jìn)行求解.金盼等[8]研究了多目標(biāo)帶時(shí)間窗的多車場(chǎng)車輛路徑問(wèn)題，并提出了一種全局搜索的混合多目標(biāo)進(jìn)化算法.學(xué)者們研究這些問(wèn)題時(shí)，假設(shè)所有配送中心的補(bǔ)給價(jià)格都相同，但實(shí)際上，許多生產(chǎn)銷售配送行業(yè)普遍存在同樣的商品，各配送中心供應(yīng)商提供的價(jià)格不同.這樣供應(yīng)價(jià)格低的配送中心就應(yīng)該服務(wù)更多的客戶，這樣才可以使供給成本和運(yùn)輸成本之和在整體上達(dá)到最優(yōu)化.因此在車輛調(diào)度問(wèn)題中應(yīng)綜合考慮供給成本和運(yùn)輸成本，使得成本最小化，為此提出了考慮商品供給價(jià)格的多車場(chǎng)路徑問(wèn)題，即每個(gè)配送中心提供的商品價(jià)格允許存在差異，是另一種MDVRP理論擴(kuò)展范疇，更符合生產(chǎn)銷售實(shí)際需求.

1 考慮供給商品價(jià)格的車輛路徑問(wèn)題建模

1.1 考慮供給商品價(jià)格的車輛路徑問(wèn)題描述

G=(V，E)表示無(wú)向連通圖，其中V為無(wú)向連通圖中的所有節(jié)點(diǎn)集合(包括配送中心和客戶點(diǎn))，E為網(wǎng)絡(luò)中所有弧的集合.目標(biāo)是在滿足所有客戶點(diǎn)需求及每輛車的裝載量不超過(guò)其最大容量的條件下，使得商品的供給成本和運(yùn)輸路徑成本之和最小.

1.2 問(wèn)題模型建立

考慮商品供給價(jià)格的多車場(chǎng)車輛路徑模型為

(1)

約束條件分別為

(2)

(4)

(5)

(6)

(7)

(8)

h∈H,WK∈Kh,i∈V,j∈V,i≠j

(9)

(10)

(11)

其中：式(1)為目標(biāo)函數(shù)，由供給成本和配送成本兩部分組成；式(2)表示各配送中心使用車輛的數(shù)目低于配送中心所擁有的車輛數(shù)目；式(3)表示車輛從配送中心出發(fā)并返回原來(lái)的配送中心；式(4)表示每個(gè)客戶點(diǎn)只能被一輛車服務(wù)一次；式(5)確保同一車輛服務(wù)同一客戶兩次的情況不存在；式(6)表示車輛不能從一個(gè)配送中心到另一個(gè)配送中心；式(7)為車輛容量約束；式(8)表示車輛在車場(chǎng)時(shí)的時(shí)間點(diǎn)等于零；式(9)對(duì)于同一車輛服務(wù)的兩個(gè)用戶，到達(dá)后一用戶的時(shí)間要大于車輛到達(dá)前一用戶的時(shí)間點(diǎn)加上兩用戶之間的行駛時(shí)間，從而限制子路徑的出現(xiàn)，式(10)為車輛行駛時(shí)間約束；式(11)表示車輛到達(dá)用戶的時(shí)間點(diǎn)大于零.

2 改進(jìn)變鄰域搜索算法設(shè)計(jì)

由Mladenovic和Hansen(1997年)提出的變鄰域搜索算法(VNS)屬于啟發(fā)式算法，它是局部搜索算法的衍生，多用來(lái)求解組合優(yōu)化問(wèn)題.針對(duì)大規(guī)模的VRP問(wèn)題，VNS算法具有優(yōu)良的尋優(yōu)性能，一個(gè)有效的啟發(fā)式算法，在近幾年的文獻(xiàn)中，被廣泛的用于求解車輛路徑問(wèn)題.由于傳統(tǒng)的局部搜索算法在迭代的過(guò)程中，通常只會(huì)設(shè)計(jì)單個(gè)鄰域結(jié)構(gòu)生成鄰域解，再對(duì)鄰域解進(jìn)行局部搜索獲得最優(yōu)解.單個(gè)鄰域結(jié)構(gòu)的設(shè)計(jì)使得傳統(tǒng)的局部搜索算法很容易陷入局部最優(yōu)解，導(dǎo)致算法得到全局最優(yōu)的概率大大降低.所以將設(shè)計(jì)一個(gè)改進(jìn)的變鄰域搜索算法來(lái)解決考慮商品供給價(jià)格的多車場(chǎng)車輛路徑問(wèn)題.

2.1 算法框架設(shè)計(jì)

圖1為改進(jìn)變鄰域搜索算法的基本框架.算法的改進(jìn)之處主要包含以下4個(gè)方面：1)初始解的構(gòu)造階段，首先采用聚類法完成客戶點(diǎn)的分配，然后再用節(jié)約算法完成路徑的初始化；2) Shaking過(guò)程中，設(shè)計(jì)了8種不同的鄰域結(jié)構(gòu)，以擴(kuò)大搜索范圍，同時(shí)采用交換算子和插入算子；3)在Local Search過(guò)程中，采用2-Opt和Or-Opt兩種算子；4)引入模擬退火算法，用于在一定條件下接受部分較差解，減少算法陷入局部最優(yōu)的可能性.

圖1 改進(jìn)變鄰域算法框架圖Fig.1 Improved VNS flowchart

2.2 初始解的生成

初始解的生成方法為先聚集后路徑的方法.點(diǎn)的聚類過(guò)程采用的是類似三標(biāo)準(zhǔn)聚集算法[9]，由于需要同時(shí)考慮配送中心供給成本和車輛路徑之間的關(guān)系，把供給成本這一因素加入到聚類的構(gòu)造過(guò)程中，在計(jì)算平均距離和最近距離時(shí)，同時(shí)考慮供給成本項(xiàng).具體聚集流程如下：

Step 1 初始化Nu=N，其中集合Nu為所有沒(méi)有聚集的需求點(diǎn)集.

Step 2 重復(fù)一下步驟，直到Nu為空.

Step 3 以每個(gè)配送中心為中心，包含分配到各配送中心的客戶點(diǎn)構(gòu)成聚類，配送中心的數(shù)量即為聚類的數(shù)量.

Step 4 計(jì)算平均路徑成本和補(bǔ)給成本之和.計(jì)算每個(gè)客戶點(diǎn)Ni∈Nu與各個(gè)聚類之間的平均距離Lih，并用Cih=Lihβ+Diαh來(lái)表達(dá)客戶點(diǎn)Ni加入聚類h所增加的成本值.令Ci1為客戶點(diǎn)Ni加入到各個(gè)聚類后增加成本最少的聚類，Ci2為增加成本第二少的聚類，從Nu中選取滿足Ci2-Ci1≥0.1Ci2的客戶點(diǎn)組成集合Ns.如果Ns為空，則跳轉(zhuǎn)至Step 5；否則，從集合Ns中選擇Ci2-Ci1差值最大的客戶點(diǎn)Ni，并將Ni分配至增加成本最少的聚類中，Nu=Nu∕{Ni}，跳轉(zhuǎn)至Step 2.

Step 5 計(jì)算最近距離.對(duì)于余下的每個(gè)客戶點(diǎn)Ni∈Nu，如果聚類A的某個(gè)客戶點(diǎn)與Ni的距離最近，則將Ni分配至聚類A中，Nu=Nu∕{Ni}，跳轉(zhuǎn)至Step 2.

在點(diǎn)的聚類過(guò)程完成后，采用節(jié)約算法[9]對(duì)每個(gè)聚類進(jìn)行路徑的初始化.

2.3 鄰域結(jié)構(gòu)的設(shè)計(jì)

Polacek等[4]設(shè)計(jì)了由12個(gè)鄰域結(jié)構(gòu)組成的鄰域結(jié)構(gòu)集合，這個(gè)鄰域結(jié)構(gòu)集合針對(duì)的問(wèn)題也是多車場(chǎng)車輛路徑問(wèn)題，針對(duì)每個(gè)鄰域結(jié)構(gòu)都指定了相應(yīng)供應(yīng)點(diǎn)數(shù)和變化子路徑的最大長(zhǎng)度，但是其中并沒(méi)有指定Shaking過(guò)程中的操作算子，由于需要考慮商品供應(yīng)價(jià)格存在差異的特殊性，將對(duì)其設(shè)計(jì)的鄰域結(jié)構(gòu)做相應(yīng)修改，得到表1所示的鄰域結(jié)構(gòu).

表1 鄰域結(jié)構(gòu)集合1)

注：1)p為參與路徑交換的車場(chǎng)的數(shù)量值；Cr為分配給路徑r的客戶點(diǎn)數(shù).

該鄰域結(jié)構(gòu)包含了4個(gè)主要度量：1)變化子路徑所屬的供應(yīng)點(diǎn)p的數(shù)量，2)變化子路徑的數(shù)量，3)操作算子的選擇，4)變化子路徑的最大長(zhǎng)度.由于車輛路徑問(wèn)題中考慮了貨物的不同供給價(jià)格，顯然供給價(jià)格低的供應(yīng)點(diǎn)需要服務(wù)更多的客戶點(diǎn)，所以當(dāng)兩條變化路徑在兩個(gè)不同的供應(yīng)點(diǎn)，并且子路徑長(zhǎng)度不大于2時(shí)，采用插入算子，被選中的子路徑從供給價(jià)格高的路徑插入到供給價(jià)格低的路徑中去.

2.4 Shaking過(guò)程

Shaking過(guò)程的作用主要是通過(guò)先前已經(jīng)設(shè)計(jì)好的鄰域結(jié)構(gòu)，將當(dāng)前解經(jīng)過(guò)操作算子變換出一個(gè)新的解，來(lái)擴(kuò)展當(dāng)前解的搜索空間，以降低整個(gè)算法陷入局部最優(yōu)的可能性.Shaking過(guò)程并沒(méi)有改變當(dāng)前解的大部分特征，而這也就可以在一定程度上使算法的收斂速度加快.

插入算子包括原序插入和反轉(zhuǎn)插入，交換算子也可分為原序交換和反轉(zhuǎn)交換，分別如圖2，3所示，其中Depot代表配送中心.圖2所示插入算子的操作對(duì)象為屬于不同配送中心的兩條變換路徑；圖3所示交換算子的兩條變換路徑可以來(lái)自同一個(gè)配送中心，也可以來(lái)自不同的配送中心.Shaking過(guò)程中反轉(zhuǎn)算子的概率一般設(shè)置的較小，由于車輛行駛路徑都具有方向性，所以在子路徑的交換過(guò)程中都會(huì)盡可能保持子路徑的原有方向，以提高獲得可行解的概率.兩種反轉(zhuǎn)算子的概率都為picross，原序算子的概率為1-picross.picross的取值可以設(shè)定為1/K，其中K為所有配送中心擁有車輛的總數(shù).

圖2 插入算子操作示例Fig.2 Insert operator

圖3 交換算子操作示例Fig.3 Change operator

2.5 Local Search(局部搜索)過(guò)程

局部搜索過(guò)程的作用是對(duì)Shaking過(guò)程中所獲得的兩條新路徑進(jìn)行局部搜索操作，并分別求出兩條新路徑的最優(yōu)解，以獲得算法的局部最優(yōu)解.局部搜索過(guò)程最主要的部分是局部搜索算子的設(shè)計(jì)，好的局部搜索算子能使算法在一個(gè)合理的時(shí)間內(nèi)得到較理想的局部最優(yōu)解，也同時(shí)決定了整個(gè)變鄰域搜索算法的最終求解效率.

常用的局部搜索算子包括：2-Opt，Or-Opt，3-Opt和2-Opt*等，王征等[7]經(jīng)過(guò)大量實(shí)驗(yàn)顯示：3-Opt獲得的解要優(yōu)于2-Opt和Or-Opt，但其運(yùn)行時(shí)間往往過(guò)長(zhǎng)；Or-Opt則可以在較短的時(shí)間內(nèi)獲得求解質(zhì)量較好的解；2-Opt使得子路徑的方向發(fā)生改變，可以尋找反方向的較優(yōu)解.綜上所述，選擇2-Opt和Or-Opt算子，以達(dá)到能在合理時(shí)間內(nèi)獲得較優(yōu)解的目的.這兩個(gè)局部搜索算子的操作示例如圖4所示.每次局部搜索時(shí)都需要隨機(jī)的選擇一種算子，這里將Or-Opt算子被選中的概率設(shè)置為1/2，2-Opt算子被選中的概率則也為1/2.

圖4 單路徑局部?jī)?yōu)化算子操作示意圖Fig.4 Single-path local optimization operator

在Local Search過(guò)程中，除了要設(shè)計(jì)操作算子以外，還要設(shè)計(jì)算法的局部搜索策略.搜索策略有兩種主要的方式[9]：first-improvement和best-improvement.一般情況下，后者的搜索時(shí)間會(huì)比前者要短，但是前者的求解質(zhì)量會(huì)比較好.經(jīng)過(guò)前期測(cè)試，權(quán)衡算法求解時(shí)間和求解質(zhì)量之間的關(guān)系，這里采用best-improvement策略.

2.6 較差解接受原則和終止準(zhǔn)則

較差解接受原則的設(shè)計(jì)是為了提高算法對(duì)求解空間的一個(gè)擾動(dòng)程度，即在局部搜索過(guò)程結(jié)束后，可以以一定條件接受較差解，以改善算法過(guò)早陷入局部最優(yōu)的缺陷.這里將通過(guò)Chiang等[10]提出的模擬退火算法來(lái)設(shè)計(jì)變鄰域搜索算法的較差解接受原則，使得算法能在一定概率下接受較差解.模擬退火算法中需要設(shè)計(jì)溫度參數(shù)T和每個(gè)溫度下迭代的次數(shù)IT，設(shè)初始狀態(tài)T=T0，完成一個(gè)內(nèi)循環(huán)，則T每次減少T0(IT/Imax).

為了防止算法運(yùn)行時(shí)間過(guò)長(zhǎng)，將引用改編CHEN Qingfeng等[11]設(shè)計(jì)的終止準(zhǔn)則.終止準(zhǔn)則分為2個(gè)部分：首先，設(shè)計(jì)VNS算法的最大循環(huán)次數(shù)為1 000次；其次，如果計(jì)算機(jī)運(yùn)行時(shí)間超過(guò)1 800 s，則程序終止.

3 算法檢驗(yàn)

為了檢驗(yàn)改進(jìn)變鄰域搜索算法的有效性，需要設(shè)計(jì)拉格朗日松弛法求解出原問(wèn)題的一個(gè)下界；同時(shí)還需要設(shè)計(jì)具體的算例，并通過(guò)改進(jìn)變鄰域搜索算法求得的最優(yōu)解與下界的差值進(jìn)行比較分析，以此來(lái)評(píng)價(jià)所設(shè)計(jì)變鄰域搜索算法的有效性.所選算例是在Cordeau標(biāo)準(zhǔn)算例的基礎(chǔ)上，針對(duì)考慮商品供給價(jià)格的多車場(chǎng)車輛路徑問(wèn)題的特殊性作出相應(yīng)修改的計(jì)算算例.

3.1 拉格朗日松弛問(wèn)題

拉格朗日松弛法[12]是通過(guò)將約束規(guī)劃中造成問(wèn)題難解的約束吸收到目標(biāo)函數(shù)中，使得問(wèn)題變得容易求解的一種技術(shù).拉格朗日松弛法可吸收的約束包括3種類型：等式約束、不等式約束和混合型約束.

通過(guò)放松原問(wèn)題的“每個(gè)客戶點(diǎn)僅接受一輛車的一次配送”約束條件式(4～6)，利用拉格朗日松弛法法求得松弛問(wèn)題，建立松弛問(wèn)題模型，分解拉格朗日松弛問(wèn)題，建立子問(wèn)題，采用改進(jìn)的標(biāo)號(hào)法[12]來(lái)求解帶容量約束的子問(wèn)題，最后用次梯度法[13]解拉格朗日乘子問(wèn)題，并得到拉格朗日松弛問(wèn)題的下界.

3.2 算例驗(yàn)證

試驗(yàn)部分采用20個(gè)Cordeau標(biāo)準(zhǔn)算例的前六個(gè)算例進(jìn)行測(cè)試，這6個(gè)算例的Depot點(diǎn)數(shù)都為4.研究并沒(méi)有涉及超過(guò)4個(gè)Depot點(diǎn)的中大規(guī)模問(wèn)題，主要是因?yàn)樵诶窭嗜账沙趩?wèn)題中設(shè)計(jì)了回溯的過(guò)程，導(dǎo)致中大規(guī)模的算例很難在較短的時(shí)間范圍內(nèi)得到松弛問(wèn)題的下界.變鄰域搜索算法和拉格朗日松弛算法的代碼使用Matlab編寫(xiě)，算例代碼在個(gè)人計(jì)算機(jī)上運(yùn)行，運(yùn)行環(huán)境為Intel core i3 AMD2.10 GHz，2 GB RAM.

3.2.1 參數(shù)設(shè)置

在前期試驗(yàn)中，經(jīng)過(guò)對(duì)算例的多次試驗(yàn)，以確定算法中的各個(gè)參數(shù)，以便設(shè)計(jì)的變鄰域搜索算法在其他算例中能夠獲得較好的最優(yōu)值.變鄰搜索算法中部分重要參數(shù)值如下：算法總的迭代次數(shù)為1 000次；局部搜索次數(shù)為200次；評(píng)價(jià)函數(shù)中車輛超載的懲罰系數(shù)E值為200；抖動(dòng)過(guò)程中反轉(zhuǎn)算子的選擇概率picross設(shè)為0.2；局部搜索過(guò)程中的Or-Opt操作算子的選擇概率pOr-Opt設(shè)為0.5；4個(gè)Depot點(diǎn)的單位供給價(jià)格分別為7,8,9,10；車輛的最大容量180；車輛單位距離運(yùn)輸成本為6.

3.2.2 算例結(jié)果與分析

為了驗(yàn)證所設(shè)計(jì)的改進(jìn)變鄰域搜索算法對(duì)求解所提出問(wèn)題的有效性，需要對(duì)算例的求解結(jié)果與拉格朗日松弛算法的求解結(jié)果進(jìn)行比較，表2給出了拉格朗日松弛方法和變鄰域搜索算法針對(duì)Cordeau的6個(gè)算例得到的最優(yōu)解，以及它們所得結(jié)果之間的GAP值，其中GAP=(Z2-Z1)/Z2×100.從表2中可以清晰看出：變鄰域搜索算法得到的目標(biāo)值與拉格朗日松弛下界的差值比值最大時(shí)為4.21%，表示與最優(yōu)目標(biāo)值比較接近，因此所設(shè)計(jì)的變鄰域搜索算法在中小規(guī)模的問(wèn)題上可以獲得較好的值.

表2 拉格朗日松弛&變鄰域搜索計(jì)算結(jié)果對(duì)比

圖5 最優(yōu)路徑圖Fig.5 Optimal path diagram

圖5中的兩張圖都是算例01經(jīng)過(guò)設(shè)計(jì)的改進(jìn)變鄰域搜索算法獲得的最優(yōu)路徑圖，惟一不一樣的地方是圖5(a)中各Depot點(diǎn)的商品供給價(jià)格相同，而圖5(b)中各Depot點(diǎn)的商品供給價(jià)格不同.通過(guò)對(duì)比這兩張圖可以看出各個(gè)配送中心補(bǔ)給成本的差異給車輛路徑規(guī)劃所帶來(lái)的影響.相對(duì)于商品供給價(jià)格相同的圖5(a，b)中供給價(jià)格高的A-Depot點(diǎn)服務(wù)的客戶相對(duì)變少了，而供給價(jià)格低的D-Depot點(diǎn)則服務(wù)了更多的客戶點(diǎn).由此可以看出改進(jìn)的變鄰域搜索算法對(duì)考慮商品供給價(jià)格的多車場(chǎng)車輛路徑問(wèn)題的求解是有效的，并且更加符合實(shí)際的車輛運(yùn)輸問(wèn)題.

4 結(jié) 論

針對(duì)石油、煙草和食品等多點(diǎn)分布式生產(chǎn)銷售配送行業(yè)商品供給價(jià)格不同問(wèn)題，在車輛調(diào)度問(wèn)題中綜合考慮了供給成本和運(yùn)輸成本，使得成本最小化，提出了考慮商品供給價(jià)格的多車場(chǎng)路徑問(wèn)題(MDVRP)，研究目的是使貨物供給成本與配送成本的總和最小.建立了考慮商品補(bǔ)給價(jià)格的多車場(chǎng)車輛路徑問(wèn)題模型，該問(wèn)題模型更加符合實(shí)際；設(shè)計(jì)了改進(jìn)的變鄰域搜索算法，在算法的Shaking過(guò)程中，設(shè)計(jì)了8中鄰域結(jié)構(gòu)來(lái)擴(kuò)大解的搜索范圍，并且同時(shí)采用了插入操作算子和交換操作算了，減少了算法陷入局部最優(yōu)的可能性，在Local Search過(guò)程中采用了2-Opt算子和Or-Opt算子，較好的平衡了求解質(zhì)量和求解時(shí)間之間的關(guān)系；通過(guò)計(jì)算算例來(lái)驗(yàn)證變鄰域搜索算法求解的有效性.研究對(duì)于多點(diǎn)分布式生產(chǎn)銷售配送行業(yè)具有很好的應(yīng)用前景.

[1] DANTZIG G B，RAMSER J H. The truck dispatching problem[J]. Management science，1959，6(1)：80-91.

[2] GOLDEN B L，MAGNANTI T L，NGUYEN H Q. Implementing vehicle routing algorithms[J]. Networks，1977，7(2)：113-148.

[3] CORDEAU J F，LAPORTE G，MERCIER A. A unified tabu search heuristic for vehicle routing problems with time windows[J]. Journal of the operational research society，2001，52：928-936.

[4] POLACEK M，HARTL R F，DOERNER K，et al. A variable neighborhood search for the multi depot vehicle routing problem with time windows[J]. Journal of heuristics，2004，10(6)：613-627.

[5] 趙燕偉，李文，張景玲，等.多車型同時(shí)取送貨問(wèn)題的低碳路徑研究[J].浙江工業(yè)大學(xué)學(xué)報(bào)，2015，43(1)：18-23.

[6] 魏云飛，黃德才.求解非滿載車輛調(diào)度問(wèn)題的免疫遺傳算法[J].浙江工業(yè)大學(xué)學(xué)報(bào)，2005，33(5)：511-515.

[7] 陳曉瞇，孟志青，徐杰.基于混合禁忌搜索算法的動(dòng)態(tài)車輛路徑研究[J].浙江工業(yè)大學(xué)學(xué)報(bào)，2009，37(5)：580-585.

[8] 金盼.混合多目標(biāo)進(jìn)化算法在帶時(shí)間窗車輛路徑問(wèn)題中的應(yīng)用[D].杭州：浙江工業(yè)大學(xué)，2013.

[9] 王征，張俊，王旭坪.多車場(chǎng)帶時(shí)間窗車輛路徑問(wèn)題的變鄰域搜索算法[J].中國(guó)管理科學(xué)，2011(2)：99-109.

[10] CHIANG W C，RUSSELL R A. Simulated annealing metaheuristics for the vehicle routing problem with time windows[J]. Annals of operations research，1996，63(1)：3-27.

[11] CHEN Qingfeng，LI Kunpeng. Model and algorithm for an unpaired pickup and delivery vehicle routing problem with split loads[J]. Transportation research part E，2014，69(1)：218-235.

[12] 劉泳.基于拉格朗日松弛和分支定界算法的3PL運(yùn)輸調(diào)度問(wèn)題[D].武漢：華中科技大學(xué)，2011.

[13] 陶繼平.基于拉格朗日松弛法的調(diào)度算法研究[D].上海：上海交通大學(xué)，2014.

(責(zé)任編輯：劉 巖)

Model and algorithm for multiple-depot vehicle routing problem with different supply costs

LU Jiansha， HONG Huanlei， CHEN Qingfeng

(Institute of Industrial Engineering， Zhejiang University of Technology， Hangzhou 310014， China)

In some industries, like tobacco, oil and foodstuff, the supply costs can be different due to the different production costs. So in order to obtain an optimal total cost of delivery and supply, we address the multiple-depot vehicle routing problem (MDVRP) with different supply costs. A multiple-depot vehicle routing model is built considering different production costs; In order to solve the mathematical model, an initial solution based on the nature and characteristics of the problem is generated, and the modified variable neighborhood search algorithm (VNS) by combining eight neighborhoods and local improvement method is designed; Finally, an example was given to test the model and algorithm, and the results prove the method is effective.

supply costs; MDVRP; VNS

2016-03-05

浙江省自然科學(xué)基金資助項(xiàng)目((LY15G010009))

魯建廈(1963—)，男，浙江余姚人，教授，博士生導(dǎo)師，研究方向?yàn)榫嫔a(chǎn)、生產(chǎn)調(diào)度和制造業(yè)信息化，E-mail：ljs@zjut.edu.cn.

TP301

A

1006-4303(2016)05-0553-06