基于遺傳算法的固定費(fèi)用運(yùn)輸問(wèn)題研究

吳開信，牟瑞芳

（1.西南交通大學(xué) 交通運(yùn)輸學(xué)院，四川 成都 610031；2.華僑大學(xué) 廈門工學(xué)院，福建 廈門 361021）

運(yùn)輸問(wèn)題是線性規(guī)劃的重要分支，很多實(shí)際問(wèn)題可以轉(zhuǎn)化為運(yùn)輸模型來(lái)求解。簡(jiǎn)單的線性運(yùn)輸模型僅考慮兩組約束條件：即與源節(jié)點(diǎn)相關(guān)的m個(gè)約束條件和與目的節(jié)點(diǎn)相關(guān)的n個(gè)約束條件。固定費(fèi)用運(yùn)輸問(wèn)題(FCTP)是運(yùn)輸問(wèn)題的擴(kuò)展，它除了要考慮兩組約束條件以外，還要考慮每次運(yùn)輸時(shí)的固定成本和與運(yùn)量有關(guān)的可變成本，簡(jiǎn)單的線性運(yùn)輸問(wèn)題可以看作所有路徑的固定成本為零的FCTP問(wèn)題。簡(jiǎn)單線性運(yùn)輸問(wèn)題的解法通常是用表上作業(yè)法，對(duì)于源節(jié)點(diǎn)和目的節(jié)點(diǎn)較多的運(yùn)輸問(wèn)題，表上作業(yè)法計(jì)算量較大、效率低，而基于遺傳算法運(yùn)輸問(wèn)題的求解將更具有實(shí)效性。

由于FCTP問(wèn)題的目標(biāo)函數(shù)具有不連續(xù)性，所以比簡(jiǎn)單的線性運(yùn)輸問(wèn)題更難處理，Hirsch和Dantzig證明了其最優(yōu)解一般在問(wèn)題約束條件構(gòu)成的凸集的某個(gè)極值點(diǎn)上[1]。在早期的研究中，一些精確解法被運(yùn)用于求解FCTP問(wèn)題，如極點(diǎn)排列法和分支定界法等[2]。但這些算法沒有充分利用固定費(fèi)用運(yùn)輸問(wèn)題的網(wǎng)絡(luò)特征，只適合于解決規(guī)模較小的此類問(wèn)題。后來(lái)一些啟發(fā)式算法，如拉格朗日松弛法、模擬退火算法等被引入解決FCTP問(wèn)題，但在實(shí)際運(yùn)用中發(fā)現(xiàn)這些算法獲得的解質(zhì)量較差。本文根據(jù)FCTP問(wèn)題的最優(yōu)解是一個(gè)生成樹的網(wǎng)絡(luò)特性，結(jié)合遺傳算法設(shè)計(jì)出一種基于運(yùn)輸樹的遺傳算法，并給出實(shí)例得出運(yùn)用此方法可以快速提高獲得最優(yōu)解的幾率。

1 問(wèn)題的描述

對(duì)于FCTP問(wèn)題，可用以下數(shù)學(xué)模型表示：

式中：O和D分別表示m個(gè)源節(jié)點(diǎn)的集合和n個(gè)目的節(jié)點(diǎn)的集合；cij、fij和xij分別表示源節(jié)點(diǎn)i到目的節(jié)點(diǎn)j的單位可變成本、總的固定成本和運(yùn)輸數(shù)量；條件⑶和條件⑷分別表示產(chǎn)銷平衡條件下物資總的供應(yīng)量和總的需求量，如果是產(chǎn)銷不平衡運(yùn)輸問(wèn)題，可以通過(guò)增加一個(gè)虛擬產(chǎn)地或虛擬銷地轉(zhuǎn)化為產(chǎn)銷平衡的運(yùn)輸問(wèn)題；目標(biāo)函數(shù)表示求總運(yùn)輸成本最小的分配方案[3]。

運(yùn)輸問(wèn)題可用一個(gè)網(wǎng)絡(luò)二分圖來(lái)表示，因此可以嘗試運(yùn)用基于運(yùn)輸生成樹的遺傳算法來(lái)進(jìn)行求解。假設(shè)某運(yùn)輸問(wèn)題有m個(gè)源節(jié)點(diǎn)和n個(gè)目的節(jié)點(diǎn)，則FCTP問(wèn)題的運(yùn)輸網(wǎng)絡(luò)圖具有以下3個(gè)特點(diǎn)：①由于約束方程最多有m+n-1個(gè)獨(dú)立方程，即系數(shù)矩陣的秩小于等于m+n-1，因此共有m+n-1個(gè)基變量，每個(gè)變量對(duì)應(yīng)運(yùn)輸表中的1格；②基變量一定能構(gòu)成1棵運(yùn)輸樹，即在運(yùn)輸表中的每一行和每一列中至少存在1個(gè)基變量；③基變量不能構(gòu)成閉合回路。

2 基于運(yùn)輸樹的遺傳算法

2.1 編碼

設(shè)集合O表示m個(gè)源節(jié)點(diǎn)的集合，O={1,2,…,m}，集合D表示n個(gè)目的節(jié)點(diǎn)的集合，D={m+1,m+2,…,m+n}，則運(yùn)輸網(wǎng)絡(luò)圖中有m+n個(gè)節(jié)點(diǎn)和mn條邊。

運(yùn)輸問(wèn)題有特殊的數(shù)據(jù)結(jié)構(gòu)，由圖論知識(shí)可知，對(duì)于1個(gè)含m+n個(gè)節(jié)點(diǎn)的完備圖，可以表示(m+n)m+n-2棵標(biāo)號(hào)不同的樹，也就是說(shuō)，我們可以用m+n-2個(gè)數(shù)字的排列表示m+n個(gè)節(jié)點(diǎn)的樹，其中任何樹至少有2片葉子[4]。

在{1,2,…,m+n}共m+n個(gè)數(shù)字中隨機(jī)可重復(fù)地選取m+n-2個(gè)數(shù)字按順序排成1排，構(gòu)成1個(gè)初始染色體，染色體中的基因可以相同。運(yùn)輸樹和染色體之間的轉(zhuǎn)換關(guān)系按下列法則。

2.1.1 運(yùn)輸樹轉(zhuǎn)換成染色體

步驟1：令i是樹中最小的葉子節(jié)點(diǎn)，j為i的關(guān)聯(lián)節(jié)點(diǎn)，選擇j為染色體中最右邊的數(shù)字，再刪除節(jié)點(diǎn)i和邊(i,j)；

步驟2：重復(fù)上一步m+n-2次，直至剩下2個(gè)節(jié)點(diǎn)為止，此時(shí)染色體生成。

2.1.2 染色體轉(zhuǎn)換成運(yùn)輸樹

設(shè)P為一個(gè)染色體，S為{1,2,…,m+n}中沒有在P里出現(xiàn)的所有數(shù)字構(gòu)成的集合。設(shè)i是S中最小的數(shù)字，j是P中最左邊的數(shù)字，重復(fù)以下步驟，直至P中沒有數(shù)字為止。

步驟1：若i∈O和j∈D，則(i,j)構(gòu)成運(yùn)輸樹的1條邊，否則選擇j后面與i不在同一個(gè)集合中的元素k，交換 j 和 k 的位置，此時(shí)(i,k)構(gòu)成運(yùn)輸樹的1條邊。

步驟2：從S中去掉元素i，若P中仍含有與j相同的元素，則從P中直接去掉元素j即可；否則從P中直接去掉元素 j 后，在S中增加元素j。

步驟3：若P中沒有元素了，則S中剩下的最后兩個(gè)元素構(gòu)成運(yùn)輸樹的第m+n-1條邊。

步驟4：分配運(yùn)行量x?=

步驟5：更新產(chǎn)量ai=ai-xij和銷量bj=bj-xij。

步驟6：若沒有可行的運(yùn)量分配，則停止；否則，去掉運(yùn)量為0的邊，對(duì)產(chǎn)地r和銷地s增加邊(r,s)，且xij=ar=bs。

運(yùn)輸樹總可以按上面的法則轉(zhuǎn)換為染色體，反之不然，只有可行的染色體才能通過(guò)上面的法則轉(zhuǎn)換成運(yùn)輸樹。由于初始染色體是從{1，2，…，m+n}中隨機(jī)可重復(fù)地選取m+n-2個(gè)數(shù)字產(chǎn)生，未必是可行染色體，即初始染色體未必能生成1棵運(yùn)輸樹，在此必須根據(jù)運(yùn)輸樹特殊的數(shù)據(jù)結(jié)構(gòu)制定可行性準(zhǔn)則，對(duì)初始染色體進(jìn)行篩選。

由運(yùn)輸樹圖形可知，染色體中出現(xiàn)次數(shù)為t的基因(節(jié)點(diǎn))與其他節(jié)點(diǎn)有t+1個(gè)連接，由此對(duì)初始染色體可制定以下可行性準(zhǔn)則：，其中Lo和LD分別表示染色體中含集合O基因的連接數(shù)和含集合D基因的連接數(shù)，分別表示集合S中含集合O基因的個(gè)數(shù)和含集合D基因的個(gè)數(shù)。

可行性初始染色體可以編制計(jì)算機(jī)程序在java環(huán)境下執(zhí)行生成。

2.2 適應(yīng)函數(shù)

適應(yīng)度是1個(gè)群體中個(gè)體生存機(jī)會(huì)選擇的惟一確定性指標(biāo)，適應(yīng)度較高的個(gè)體遺傳到下一代的概率較大。適應(yīng)函數(shù)可表示為：

2.3 選擇策略

采用最優(yōu)方式實(shí)現(xiàn)選擇操作，即在父代種群中適應(yīng)度最大的染色體在子代中至少出現(xiàn)1次，然后按照輪盤賭選擇的方式進(jìn)行選擇操作，以保證優(yōu)良的染色體進(jìn)入到下一代。

2.4 單點(diǎn)交叉操作

在父代A和父代B中作如下交叉操作：隨機(jī)選擇1個(gè)交叉點(diǎn)r，把每個(gè)染色體分成2個(gè)子集，前面子集中的元素及順序不變，后面子集相互交換元素。

2.5 變異操作

可使用位移變異法，即在可行染色體中隨機(jī)選擇基因串，插入隨機(jī)選定的位置。由于變異操作只是產(chǎn)生基因位置的改變，所以變異后的染色體仍然滿足可行性準(zhǔn)則。

3 實(shí)驗(yàn)及其結(jié)果分析

某公司下設(shè)3個(gè)工廠生產(chǎn)某種產(chǎn)品，每日的產(chǎn)量分別是O1=7 t，O2=4 t，O3=9 t，該公司把生產(chǎn)的產(chǎn)品運(yùn)往4個(gè)銷售點(diǎn)，各個(gè)銷售點(diǎn)每日的銷量為D4=3 t，D5=6 t，D6=5 t，D7=6 t。已知從各個(gè)工廠運(yùn)往各個(gè)銷售點(diǎn)的單位可變成本和固定成本見表1，求總運(yùn)費(fèi)最少的運(yùn)輸方案。

表1 產(chǎn)量、銷量、單位可變成本和固定成本表

求解步驟：

（1）根據(jù)題意建立數(shù)學(xué)模型，確定適應(yīng)函數(shù)。

（2）按可行性規(guī)則，在java程序環(huán)境下在{1,2,…,7}中隨機(jī)可重復(fù)地選取5個(gè)數(shù)字生成初始可行性染色體，進(jìn)而組成初始種群，本文可選取種群規(guī)模為30。

如某一個(gè)初始染色體為{2,6,3,7,1}時(shí)，Lo=6，，即滿足可行性規(guī)則，對(duì)應(yīng)的運(yùn)輸樹見圖1，對(duì)應(yīng)的運(yùn)輸分配量見表2。

圖1 初始染色體{2,6,3,7,1}對(duì)應(yīng)的運(yùn)輸樹

表2 初始染色體{2,6,3,7,1}對(duì)應(yīng)的運(yùn)輸分配量

適應(yīng)度為：(4×3+95)+(3×10+76)+(3×1+51)+(1×2+65)+(6×4+89)+(3×5+89)=551。

（3）選擇操作。父代種群中適應(yīng)度最大的染色體在子代中至少出現(xiàn)1次，然后按照賭盤選擇的方式進(jìn)行選擇操作。

（4）交叉操作。選用單點(diǎn)位移交叉，交叉概率為Pc=1。

如某一個(gè)初始染色體為{1,5,2,6,3}時(shí)，Lo=6，，即滿足可行性規(guī)則

對(duì)應(yīng)的運(yùn)輸樹見圖2，對(duì)應(yīng)的運(yùn)輸分配量見表3。

圖2 初始染色體{1,5,2,6,3}對(duì)應(yīng)的運(yùn)輸樹

表3 初始染色體{1,5,2,6,3}對(duì)應(yīng)的運(yùn)輸分配量

符合可行性準(zhǔn)則的父代染色體通過(guò)交叉操作總可產(chǎn)生可行的子代，通過(guò)解碼得到相應(yīng)的運(yùn)輸樹。

例如：父代1＜2,6,3,|7,1＞和父代2＜1,5,2,|6,3＞通過(guò)交叉操作，得到子代1＜2,6,3,|6,3＞和子代2＜1,5,2,|7,1＞。

對(duì)于子代1＜2,6,3,|6,3＞，Lo=5，=1，LD=3，=3，滿足可行性準(zhǔn)則，子代1的解碼圖見圖3。

圖3 子代1的解碼圖

由于x26=0，x36=0，節(jié)點(diǎn)7還需求3個(gè)單位，而節(jié)點(diǎn)1還有2個(gè)單位沒有分配，節(jié)點(diǎn)2還有1個(gè)單位沒有分配，所以增加邊(1,7)和（2,7），x17=2，x27=1。對(duì)應(yīng)的運(yùn)輸樹如圖4表示。

圖4 子代1的運(yùn)輸樹

對(duì)于子代2＜1,5,2,|7,1＞，Lo=5，=1，LD=4，=2，即滿足可行性規(guī)則，子代2對(duì)應(yīng)的運(yùn)輸分配量見表4。

表4 子代2＜1,5,2,|7,1＞對(duì)應(yīng)的運(yùn)輸分配量

同理，由于x17=0，x25=0，節(jié)點(diǎn)7還需求2個(gè)單位，節(jié)點(diǎn)6還需求1個(gè)單位，而節(jié)點(diǎn)3還有3個(gè)單位沒有分配，所以增加邊(3,6)和（3,7），x36=1，x37=2。子代2的運(yùn)輸樹見圖5。

圖5 子代2的運(yùn)輸樹

（5）變異操作。使用位移變異規(guī)則，變異概率選取Pm=1/6。最大代數(shù)目取M=100。通過(guò)上述遺傳操作過(guò)程，可以得出該問(wèn)題的最優(yōu)染色體為{3,5,2,6,1}，解碼得：x16=6,x17=7,x25=0,x26=4,x34=3,x35=6,目標(biāo)函數(shù)值為508。

4 結(jié)論

遺傳算法是模擬自然選擇和生物進(jìn)化遺傳過(guò)程而提出并發(fā)展起來(lái)的搜素算法，此法能以較大概率尋求到問(wèn)題的最優(yōu)解，因而受到不同領(lǐng)域研究人員的重視[5]。本文針對(duì)固定費(fèi)用運(yùn)輸問(wèn)題的特點(diǎn)提出基于運(yùn)輸樹的遺傳算法，給出了能表示基解的染色體編碼方法，制定了染色體有效性判斷規(guī)則，并通過(guò)計(jì)算機(jī)程序生成有效初始種群，利用選擇、交配、變異規(guī)則最終得出滿意解。最后運(yùn)用實(shí)例對(duì)算法的有效性進(jìn)行了驗(yàn)證。

[1] Murty KG. Solving the fixed charge problem by ranking the extreme points[J]. Operations Research，1968，16：268-279.

[2] Palekar US, Karwan MK, Zionts S. A branch-and-bound method for the fixed charge transportation problem[J].Management Science，1990，36(9)：1092-1105.

[3] 郭耀煌. 運(yùn)籌學(xué)[M]. 成都：西南交通大學(xué)出版社，2000.

[4] 玄光男，程潤(rùn)偉. 遺傳算法與工程優(yōu)化[M]. 北京：清華大學(xué)出版社，2005.

[5] 刑文訓(xùn)，謝金星. 現(xiàn)代優(yōu)化計(jì)算方法[M]. 北京：清華大學(xué)出版社，1999.