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

王芳婷 蔡延光 湯雅連 黃 剛

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

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

王芳婷 蔡延光 湯雅連 黃 剛

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

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

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

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

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

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

1.1 問(wèn)題描述

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

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

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

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

Step4運(yùn)算Step4至Step5，直到b-a＞0.000 1返回。

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

2 算法設(shè)計(jì)

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

2.1 編碼

采用文獻(xiàn)［9］中的自然數(shù)編碼，用0表示車場(chǎng)，1，2，…l表示客戶。每條子路徑始于車場(chǎng)，也必須回到車場(chǎng)。例如，對(duì)于一個(gè)有1個(gè)車場(chǎng)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 計(jì)算親和力

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

2.4 克隆選擇算子

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

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

2.5 重組和變異

1）抗體交換算子:單個(gè)抗體按照一定的交換概率Pc，隨機(jī)選取抗體中的兩個(gè)點(diǎn)，交換這兩個(gè)點(diǎn)的基因，形成新的抗體。

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

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

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

2.6 免疫克隆選擇算法流程

如圖1所示。

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

3 仿真分析

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

表1 車場(chǎng)位置信息表

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

表2 客戶位置信息表

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

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

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

戶所需貨物之間的關(guān)聯(lián)系數(shù)由Matlab隨機(jī)產(chǎn)生。改進(jì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，編碼長(zhǎng)度l=9，抗體群規(guī)模N= 11，Nr=30，Ns=2，克隆系數(shù)β=0.9。令Pc，Pi，Ps為0.9，Pm為0.7。

運(yùn)行程序30次得到該算法求解本算例的最優(yōu)結(jié)果如表3，ICSA求解得到的配送示意圖如圖3所示。免疫克隆選擇算法的一次收斂過(guò)程如圖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é)語(yǔ)

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

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

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

［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］ 李敏，郭強(qiáng)，劉紅麗.多車場(chǎng)多配送中心的物流配送問(wèn)題研究［J］.計(jì)算機(jī)工程與應(yīng)用，2007，43（8）:202-204.

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

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

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

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

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

［9］ 章兢，周泉.基于免疫克隆算法的物流配送車輛路徑優(yōu)化研究［J］.湖南大學(xué)學(xué)報(bào):自然科學(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)化和智能交通方向研究。