王芳婷 蔡延光 湯雅連 黃 剛

（廣東工業(yè)大學(xué) 自動化學(xué)院，廣州 510006）

關(guān)聯(lián)運輸調(diào)度問題的模糊機會約束規(guī)劃模型

王芳婷 蔡延光 湯雅連 黃 剛

（廣東工業(yè)大學(xué) 自動化學(xué)院，廣州 510006）

提出了針對多車場多車型的關(guān)聯(lián)運輸調(diào)度問題（Multiple-depot and Heterogeneous-vehicle Incident Vehicle Routing Problem）的模糊機會約束規(guī)劃模型，將問題模型中各個客戶的需求量及各供貨點庫存看成是模糊參數(shù)，討論了如何處理模糊目標(biāo)函數(shù)，并討論了改進的遺傳算法和免疫克隆選擇算法，比較其優(yōu)劣。實驗證明，對于求解該模型，免疫克隆選擇算法能夠快速收斂于全局最優(yōu)解，優(yōu)于改進的遺傳算法，能有效地解決關(guān)聯(lián)運輸調(diào)度問題。

關(guān)聯(lián)運輸調(diào)度問題；模糊機會約束規(guī)劃；遺傳算法；免疫克隆選擇算法

多車場多車型IVRP屬于復(fù)雜的運輸問題，是運輸問題的擴展，也屬于MP-hard問題。針對多車場VRP問題，不少學(xué)者［1-3］已經(jīng)做了很多研究，并取得了很好的成果。但是對于IVRP的探討甚少，文獻［4］中探討了用改進的遺傳算法求解IVRP。一般是若干個客戶有一定的貨物需求且貨物之間存在某種關(guān)聯(lián)性，車輛從供貨點將貨物送到各個客戶，然后返回車場。在滿足所有客戶要求的前提下，使配送成本最低。

機會約束規(guī)劃主要是指約束條件中含有隨機參數(shù)，機會表示約束條件成立的概率，該思想是由Charnes和Cooper提出的。Liu和Iwamura在模糊環(huán)境下，將機會理解成約束條件成立的可能性，提出了模糊機會約束規(guī)劃［5］。在實際生活中，客戶的需求一般很難確定，具有不確定性的特點，會隨著季節(jié)、天氣、交通、經(jīng)濟環(huán)境、社會環(huán)境等的變化而變化。Laporte、郭強［6］等學(xué)者提出將車輛行駛時間通過經(jīng)驗統(tǒng)計得出其規(guī)律并用隨機變量表示，在這樣缺乏統(tǒng)計數(shù)據(jù)的情況下得到隨機變量分布函數(shù)是相當(dāng)困難的。

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

1.1 問題描述

帶貨物關(guān)聯(lián)約束的多車場多車型關(guān)聯(lián)物流運輸調(diào)度問題可以簡單描述為，假設(shè)給定車場信息以及客戶信息（位置和貨物需求量等），貨物之間存在某種關(guān)聯(lián)性，不同類型車輛信息（載重約束、里程約束和容量約束等），要求合理安排車輛和運輸路線，在滿足所有客戶需求的前提下，使配送成本最低。

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

模糊機會約束規(guī)劃模型的建模思想是允許所做的決策在某種程度上不滿足約束條件，但是模糊約束條件成立的可能性（必要性或者可信性）不小于決策者預(yù)先給定的置信水平。

建立模糊機會約束規(guī)劃:

Step4運算Step4至Step5，直到b-a＞0.000 1返回。

對目標(biāo)函數(shù)約束，尋找給定的決策向量~gi使上面不等式成立的最小的或。

2 算法設(shè)計

克隆選擇是生物免疫系統(tǒng)理論的重要學(xué)說，通過從不同角度模擬生物學(xué)抗體克隆選擇機理，L.M. DeCastro等人相繼提出了不同的克隆選擇算法［7］。其中，僅采用克隆選擇算子的算法稱為免疫克隆選擇算法（Immune Clonal Selection Algorithm，ICSA）。它模擬自然免疫系統(tǒng)功能的一種新的智能方法［8］，并利用相應(yīng)的算子保證了該算法能快速地收斂到全局最優(yōu)解，并兼顧了全局和局部搜索，加上克隆算子的作用，有效增加了種群的多樣性，并以變異作為主要的基因操作。

2.1 編碼

采用文獻［9］中的自然數(shù)編碼，用0表示車場，1，2，…l表示客戶。每條子路徑始于車場，也必須回到車場。例如，對于一個有1個車場3輛車的VRP，抗體01230450670表示如下車輛配送路徑安排:路徑1:0-1-2-3-0；路徑2:0-4-5-0；路徑2:0-6-7-0。

2.2 產(chǎn)生初始群體

初始化規(guī)模為N的抗體種群Ab，采用自然數(shù)編碼。

2.3 計算親和力

計算初始種群親和力，并按照親和力由大到小降序排列，得到Ab=｛Ab1，Ab2，…，AbN｝，且aff（Abi）＞aff（Abi+1），i=1，2，…，N-1。aff（）為親和力函數(shù)，aff（Abi）為第i個抗體對于抗原的親和力。fi表示目標(biāo)函數(shù)，r0i為供應(yīng)點車場到客戶i的路況系數(shù)，M0i為路徑。

2.4 克隆選擇算子

定義克隆規(guī)模函數(shù)

Nc為克隆后的抗體群規(guī)模；β為克隆系數(shù)，用來控制克隆的規(guī)模；round為取整函數(shù)。由于抗體是按照親和力大小降序排列的，由上式知，抗體群中第i個抗體將會克隆出round（）個相同的抗體，即抗體的親和力越高，克隆的規(guī)模越大，從而使高親和力抗體中的優(yōu)秀基因能夠更好地保存和發(fā)展。記Ab克隆后產(chǎn)生的抗體群為Abc。

2.5 重組和變異

1）抗體交換算子:單個抗體按照一定的交換概率Pc，隨機選取抗體中的兩個點，交換這兩個點的基因，形成新的抗體。

2）抗體逆轉(zhuǎn)算子:單個抗體按照一定的逆轉(zhuǎn)概率Pi，隨機選取抗體中的兩個點，從第一個點開始將這兩個點之間的基因段首尾倒轉(zhuǎn)過來形成新的抗體。

3）抗體移位算子:單個抗體按照一定的移位概率Ps，隨機選取抗體中的兩個點，將兩個點之間基因段中的基因循環(huán)向左移位，再將該基因段的末位基因移到段的首位形成新的抗體。

4）抗體變異算子:單個抗體按照一定的突變概率Pm，隨機選取抗體中的一個或多個點，將這些點的基因抽出后插入原抗體隨機的某個位置，形成新抗體。

2.6 免疫克隆選擇算法流程

如圖1所示。

圖1 免疫克隆選擇算法流程

3 仿真分析

某公司有5個供貨點，每個供貨點配有1個車場，每個車場有不同類型的車輛，車場信息表如表1，客戶信息表如表2。每輛車的最大配送里程為120 km。

表1 車場位置信息表

本文中的實驗是在Intel（R）CoreTMi3 CPU2.53GHz、內(nèi)存為2.0G、安裝系統(tǒng)為win7的PC機上采用Microsoft Visual C++6.0和Matlab7.1編程實現(xiàn)。

表2 客戶位置信息表

圖2 各供貨點及客戶的坐標(biāo)位置

表3 各供貨點配送車輛的配送數(shù)據(jù)

表4 兩種算法計算結(jié)果比較

戶所需貨物之間的關(guān)聯(lián)系數(shù)由Matlab隨機產(chǎn)生。改進遺傳算法中參數(shù)設(shè)置:種群規(guī)模為30，最大迭代次數(shù)Gen=100，pcmax=0.1，pcmin=0.005，變異概率0.05，尺度收縮參數(shù)為α=1，β=10，γ=0.5，δ=0.5。免疫克隆選擇算法中參數(shù)設(shè)置:最大迭代次數(shù)Gen=100，編碼長度l=9，抗體群規(guī)模N= 11，Nr=30，Ns=2，克隆系數(shù)β=0.9。令Pc，Pi，Ps為0.9，Pm為0.7。

運行程序30次得到該算法求解本算例的最優(yōu)結(jié)果如表3，ICSA求解得到的配送示意圖如圖3所示。免疫克隆選擇算法的一次收斂過程如圖4所示。該算例的最優(yōu)解為:0-23-17-25-10-28-34-14 -26-0；0-13-29-11-24-8-15-7-0；0-6-1-2-27-3-5-21-30-12-0；0-9-4-22 -31-18-14-0；0-16-20-19-32-33-35-0。最優(yōu)配送距離為412.77千米，平均配送里程為428.95千米。

4 結(jié)語

針對關(guān)聯(lián)運輸調(diào)度問題中客戶需求與供應(yīng)點庫存不確定的特點，提出了模糊機會約束模型，這樣更接近于實際情況，是求解此類不確定性需求問題的一種有效途徑。并用免疫克隆選擇算法對其求解，并與改進的遺傳算法求解此類問題相比較，仿真結(jié)果表明免疫克隆選擇算法的收斂速度更快，甚至在第5代就能找到最優(yōu)解，找到最優(yōu)解的平均代數(shù)為15代，且求解質(zhì)量也明顯優(yōu)于改進的遺傳算法。

圖3 最優(yōu)配送網(wǎng)絡(luò)圖

圖4 免疫克隆選擇算法的一次收斂過程

［1］ Lijun Pan，Z.Fu.A Clone Selection Algorithm for the Open Vehicle Routing Problem［C］//2009 Third International Conference on Genetic and Evolutionary Computing，Guilin，china:wgec，2009:786-790.

［2］ Jacek Dabrowski.Clonal Selection Algorithm for Vehicle Routing［C］//Proceeding of the2008 1stInternational Conference on Information Technology.Poland，83-86.

［3］ 李敏，郭強，劉紅麗.多車場多配送中心的物流配送問題研究［J］.計算機工程與應(yīng)用，2007，43（8）:202-204.

［4］ 湯雅連，蔡延光，趙學(xué)才.關(guān)聯(lián)物流運輸調(diào)度問題的改進遺傳算法［J］.微型機與應(yīng)用，2012，31（17）:69-71.

［5］ 丁曉東，吳讓泉，邵世煌.含有模糊和隨機參數(shù)的混合機會約束規(guī)劃模型［J］.控制與決策，2002，17（5）:587-591.

［6］ 郭強，謝秉磊.隨機旅行時間車輛路徑問題的模型及其算法［J］.系統(tǒng)工程學(xué)報，2003，18（3）:244-247.

［7］ 秦子玄，陳霞，唐小鵬，梁時木，漆楊，于中華.基于免疫克隆選擇算法的固定費用運輸問題優(yōu)化［J］.計算機應(yīng)用研究，2009，26（7）: 2530-2534.

［8］ 張向榮，焦李成.基于免疫克隆選擇算法的特征選擇［J］.復(fù)旦學(xué)報:自然科學(xué)版，2004，43（5）:926-929.

［9］ 章兢，周泉.基于免疫克隆算法的物流配送車輛路徑優(yōu)化研究［J］.湖南大學(xué)學(xué)報:自然科學(xué)版，2004，31（5）:54-60.

Fuzzy Chance Constrained Programming Model forIncident Vehicle Routing Problem

WANG Fang.ting CA IYan.guang TANG Ya.lian HUANG Gang
（School of Automation，Guangdong University of Technology，Guangzhou 510006，China）

This paper introduces the fuzzy chance constrained programming model formultiple-depot and heterogeneousvehicle Incident Vehicle Routing Problem（IVRP，in which customers'demands for products and stocks of supply point are treated as fuzzy parameters，discussing how to deal with the fuzzy object function，improving and comparing genetic algorithm and Immune Clone Selection Algorithm（ICSA）.The experiment result shows that ICSA could converge to global optimal solution rapidly and overcome the slow convergence speed of the improved genetic algorithm so as to solve the IVRP effectively and efficiently.

IVRP；fuzzy chance constrained programming；genetic algorithm；immune clone selection algorithm

TP301

A

1009-0312（2014）01-0030-06

2013-03-25

王芳婷（1990—），女，廣東湛江，碩士研究生，主要從事物流優(yōu)化和智能交通方向研究。