基于遺傳算法的醫(yī)藥配送路徑規(guī)劃

摘要:在物流配送業(yè)務(wù)中，存在許多優(yōu)化決策的問題，該文只討論物流配送路線規(guī)劃問題。該文主要以醫(yī)藥物流配送為研究對(duì)象，將現(xiàn)實(shí)的地理網(wǎng)絡(luò)抽象為便于計(jì)算機(jī)實(shí)現(xiàn)的抽象的點(diǎn)線網(wǎng)絡(luò)。論文中選擇了基于遺傳算法作為該網(wǎng)絡(luò)模型的分析算法的基礎(chǔ)，并對(duì)配送線路進(jìn)行了規(guī)劃。

關(guān)鍵詞:醫(yī)藥物流遺傳算法路徑規(guī)劃旅行商問題

中圖分類號(hào):TP301文獻(xiàn)標(biāo)識(shí)碼:A文章編號(hào):1009-3044(2010)11-2717-02

醫(yī)藥物流是指醫(yī)藥器械從醫(yī)藥配送中心分發(fā)、配送到各個(gè)醫(yī)院和醫(yī)療中心的過程，甚至包括通過醫(yī)院到達(dá)消費(fèi)者(患者)手中的過程，其中所產(chǎn)生的物流成本是醫(yī)藥器械成本的重要組成部分。降低醫(yī)藥運(yùn)輸成本是減少患者醫(yī)療負(fù)擔(dān)的重要途徑之一。而藥物配送實(shí)際上就是旅行商問題[1]。遺傳算法作為一種求解問題的高效并行全局搜索方法，成為目前解決NP完全問題的較為有效的方法之一。

1 旅行商問題與遺傳算法

1.1 旅行商問題原理

旅行商問題(Traveling Saleman Problem，TSP)是VRP[2]的特例，已證明TSP問題是NP難題。旅行商問題(TSP)又譯為旅行推銷員問題、貨郎擔(dān)問題，簡(jiǎn)稱為TSP問題。TSP問題可描述為:給定一組n個(gè)城市和它們兩兩之間的直達(dá)距離，尋找一條閉合的旅程，使得每個(gè)城市剛好經(jīng)過一次而且總的旅行路徑最短。TSP問題的描述很簡(jiǎn)單，簡(jiǎn)言之就是尋找一條最短的遍歷n個(gè)城市的路徑，或者說搜索整數(shù)子集X={1，2，…，n}(X中的元素表示對(duì)n個(gè)城市的編號(hào))的一個(gè)排列π(X)={v1，v2，…，vn}，使取最小值。式中的d(vi，vi+1)表示城市vi到城市vi+1的距離。

1.2 遺傳算法基本原理與描述

1.2.1 算法原理

遺傳算法是一種借鑒生物界自然選擇和自然遺傳機(jī)制的隨機(jī)搜索算法，由美國J.Holland教授提出，其主要內(nèi)容是種群搜索策略和種群中個(gè)體之間的信息交換，搜索不依賴于梯度信息。該算法是一種全局搜索算法，尤其適用于傳統(tǒng)搜索算法難于解決的復(fù)雜和非線性問題。

1.2.2 算法描述

該算法包括以下6個(gè)基本要素:

1) 編碼:遺傳算法不能直接處理解空間的數(shù)據(jù)，必須通過編碼將它們表示成基因型串?dāng)?shù)據(jù)。常對(duì)參數(shù)采用二進(jìn)制編碼，編碼當(dāng)作一條染色體，編碼前應(yīng)先量化[3]。

2) 生成初始種群:初始種群的個(gè)體通過隨機(jī)方法產(chǎn)生，且對(duì)應(yīng)研究問題的一個(gè)解。

3) 評(píng)估適應(yīng)度:遺傳算法在搜索過程中用適應(yīng)度來評(píng)估個(gè)體的優(yōu)劣，并把它作為遺傳操作的依據(jù)。適應(yīng)度函數(shù)常取非負(fù)數(shù)，且適應(yīng)度增大的方向與目標(biāo)函數(shù)的優(yōu)化方向一致。

4) 選擇:根據(jù)適者生存的選擇原理，從當(dāng)前種群中選擇生命力強(qiáng)的個(gè)體(即適應(yīng)度高的個(gè)體)，產(chǎn)生新的種群。適應(yīng)度越高的個(gè)體，被選擇的機(jī)會(huì)就越大，但并不意味著適應(yīng)度高的個(gè)體一定會(huì)被選擇[4]。

5) 交叉:將選擇出的個(gè)體存入配對(duì)庫，用隨機(jī)的方法進(jìn)行配對(duì)，以產(chǎn)生新一代的個(gè)體。

6) 變異:在交叉過程中可能丟失一些重要的遺傳信息(特定位置的0或1)1必須引入適度的變異，即按一定的概率改變?nèi)旧w基因位。

2 優(yōu)化路徑遺傳算法的構(gòu)造

針對(duì)優(yōu)化物流配送路徑的特點(diǎn)，本文構(gòu)造了求解該問題的遺傳算法。

2.1 初始種群的生成與編碼方法的選定

隨機(jī)生成規(guī)模為N的初始種群。采用巡回旅行路線所經(jīng)過的各個(gè)城市的順序排，列來表示各個(gè)個(gè)體的編碼串，這是TSP問題最自然的一種個(gè)體編碼方式。例如對(duì)于一個(gè)10個(gè)城市的TSP:2-5-3-4-7-1-6-8-9(可簡(jiǎn)單表示為[253471698])，表示從城市2出發(fā)依次經(jīng)過城市5，3，4，7，1，6，8，9，然后返回城市2的一條路徑。這種編碼方式滿足TSP問題的約束條件，保證了每個(gè)城市經(jīng)過且只經(jīng)過一次，在任何一個(gè)城市子集中不形成回路[5]。

2.2 適應(yīng)度評(píng)估

對(duì)于某條染色體，設(shè)其對(duì)應(yīng)的配送路徑方案的不可行路徑數(shù)為Ni(Ni=0表示該個(gè)體對(duì)應(yīng)一個(gè)可行解)，其目標(biāo)函數(shù)7值為Td，則該個(gè)體的適應(yīng)度可用下式表示:，式中α為對(duì)每條不可行路徑的懲罰權(quán)重，可根據(jù)目標(biāo)函數(shù)的取值范圍取一個(gè)相對(duì)較大的正數(shù)(α值太小則會(huì)影響適應(yīng)度的比較)。

2.3 遺傳操作

2.4.1 選擇操作

選擇將使適應(yīng)度較大個(gè)體有較大的存在機(jī)會(huì)，而適應(yīng)度較小的個(gè)體繼續(xù)存在的機(jī)會(huì)也較小。簡(jiǎn)單遺傳算法采用賭輪選擇機(jī)制，令Σfi表示群體的適應(yīng)度值之總和，fi表示種群中第i個(gè)染色體的適應(yīng)度值，它產(chǎn)生后代的能力正好為其適應(yīng)度值所占份額fi/Σfi。作為其被選中的概率Psi。這方法既可保證最優(yōu)個(gè)體生存至下一代，又能保證適應(yīng)度較大的個(gè)體以較大的機(jī)會(huì)進(jìn)入下一代。

2.4.2 雜交操作

采用順序編碼法后，若用簡(jiǎn)單的一點(diǎn)雜交或多點(diǎn)雜交，必然會(huì)導(dǎo)致未能完全遍歷所有城市的非法路徑。如城市9的TSP問題的兩個(gè)父路徑為:1 2 3 4 |5 6 7 8 9; 9 8 7 6 |5 4 3 2 1，若采取一點(diǎn)雜交，雜交點(diǎn)隨機(jī)選為4，則雜交產(chǎn)生的兩個(gè)后代為:9 8 7 6 |5 6 7 8 9;1 2 3 4 |5 4 3 2 1，顯然，這兩個(gè)子路徑均未能遍歷所有9個(gè)城市都違反了TSP問題的約束條件，為解決這一問題，既要進(jìn)行雜交操作，又要滿足約束條件，就必須對(duì)雜交操作進(jìn)行修正[6]。關(guān)于路徑表示的常用的幾種修正的雜交操作方法為:

1) 部分映射雜交(PMX， partially-mapped cross-over)。

在PMX操作中，先隨機(jī)地在父體中選取兩雜交點(diǎn)，并交換相應(yīng)段。再根據(jù)段內(nèi)的城市確定部分映射。在每父體中先填入無沖突的城市，而對(duì)有沖突的城市分別執(zhí)行這些部分映射直到填入無沖突，則獲得雜交后的兩后代。例如，兩父體A1、A2為('|'標(biāo)記截?cái)帱c(diǎn)) A1=(2 6 4 |7 3 5 8 |9 1)， A2=(4 5 2 |1 8 7 6 |9 3)。則由交換段確定的部分映射為:7-1，3-8，5-7，8-6，先交換相應(yīng)的段得B1=(### |1 8 7 6|##)，B2=(### |7 3 5 8 |##)。此處'#'表示城市待定。再從各自的父體中填入無沖突的城市得B1=(2#4 |1 8 7 6 |9#)，B2=(4#2 |7 3 5 8 |9#)。個(gè)體B1第一個(gè)'# '處原處為6，映射到8后仍有沖突，再將8映到3填入。第二個(gè)'#'處原處為1，映射到7后仍有沖突，再將7映到5填入。類似地求得B2。于是兩后代為B1=(2 3 4 |1 8 7 6 |9 5)， B2=(4 1 2 |7 3 5 8 |9 6)。這樣，子代仍是遍歷的，但每個(gè)子代的次序部分地由其父代確定。

2) 次序雜交(OX， order crossover)。

次序雜交的操作與部分映射雜交的操作非常類似。也是首先隨機(jī)地在父體中選擇兩雜交點(diǎn)，再交換雜交段，其它位置根據(jù)保持父體中城市的相對(duì)次序來確定。例如，設(shè)兩父體及雜交點(diǎn)仍為前述的A1和A2， A1=(2 6 4 |7 3 5 8 |9 1)， A2=(4 5 2 |1 8 7 6 |9 3)。交換雜交段于是仍有B1=(### |1 8 7 6 |##)，B2=(### |7 3 5 8 |##)。從B1的第二個(gè)雜交點(diǎn)開始，將路徑依原次序排列，即: 9-1-2-6-4-7-3-5-8去除雜交段中的城市，得子路徑9-2-4-3-5。依次順序從第二個(gè)雜點(diǎn)開始填入得B1=(4 3 5 |1 8 7 6 |9 2)，類似地有B2=(2 1 6 |7 3 5 8 |9 4)，雖然， PMX法與OX法非常類似，但它們處理相似特性的手段卻不同。PMX法趨向于所期望的絕對(duì)城市位置。本算法采用此方法交雜交。

3) 循環(huán)雜交(CX， cycle crossover)

循環(huán)雜交將另一父體作為參照以對(duì)當(dāng)前父體中的城市進(jìn)行重組。先與另一父體實(shí)現(xiàn)一個(gè)循環(huán)鏈，并將對(duì)應(yīng)的城市填入相應(yīng)的位置。循環(huán)組成后，再將另一父體的城市填入相同的位置。例如，仍考慮前兩個(gè)父體路徑A1=(2 6 4 7 3 5 8 9 1)， A2=(4 5 2 1 8 7 6 9 3)。先從A1中取第1個(gè)城市作為B1的起始點(diǎn)，于是B1=(2########)，由于后代中第一個(gè)城市都必須從父體相同位置的城市中選取，于是根據(jù)循環(huán)原則，2對(duì)應(yīng)于A2中的城市4，而在A1中位于第3位，所以應(yīng)有B1=(2#4######)，又A1中城市4對(duì)應(yīng)于A2中的2，于是組成了一個(gè)環(huán)。再將A2中剩余的城市填入對(duì)應(yīng)的相同位置得到B1=(2 5 4 1 8 7 6 9 3)，類似地可得到B2=(4 6 2 7 3 5 8 9 1)，由此可見，循環(huán)雜交保持其父體串中城市所處的絕對(duì)位置。

3 算法實(shí)現(xiàn)和結(jié)果

下面對(duì)某市一醫(yī)藥公司的銷售點(diǎn)的物流配送路徑規(guī)劃用遺傳算法進(jìn)行優(yōu)化。該公司有56處銷售點(diǎn)，通過路徑規(guī)劃希望找出最優(yōu)路徑以節(jié)省運(yùn)輸成本。

3.1 運(yùn)行參數(shù)設(shè)計(jì)

本實(shí)驗(yàn)采用n城市的遍歷順序編碼法，適應(yīng)度函數(shù)取總長(zhǎng)度Td的倒數(shù)(無懲罰函數(shù))。選擇機(jī)制是保留M個(gè)較優(yōu)個(gè)體，在每一代運(yùn)算中，個(gè)體被選中的概率與其在群體中的相對(duì)適應(yīng)度成正比。雜交操作采用OX(次序雜交)法。為使算法盡快地收斂，在經(jīng)過雜交變異操作后，增加了局部?jī)?yōu)化過程，提高個(gè)體對(duì)環(huán)境的適應(yīng)。群體規(guī)模取56，交叉概率和變異概率分別取0.9和0.01， 最大迭代數(shù)2000。

3.2 實(shí)驗(yàn)結(jié)果

運(yùn)行環(huán)境:操作系統(tǒng)Microsoft Windows XP;仿真軟件:MierosoftVisualC++6.0。

在實(shí)驗(yàn)計(jì)算中采用以上設(shè)定參數(shù)對(duì)該公司配送路徑問題求解，所得到的優(yōu)配送化路徑最優(yōu)長(zhǎng)度為862，用時(shí)126秒，迭代次數(shù)1528。得到的路徑線路如圖1所示。

4 結(jié)論

在此也可以看到，運(yùn)用遺傳算法解決實(shí)際問題，算法是使用參數(shù)的編碼集，而不是參數(shù)本身，參數(shù)的選擇十分方便;遺傳算法與其他計(jì)算機(jī)算法不同，相比之下，它比較具有隨機(jī)性而不是穩(wěn)定性，遺傳算法是在點(diǎn)群中，而不是在一個(gè)單點(diǎn)尋優(yōu)。因此利用遺傳算法解決實(shí)際問題需要選取大量數(shù)據(jù)，通過多次實(shí)驗(yàn)的數(shù)據(jù)分析不斷改進(jìn)算法和設(shè)置參數(shù)來求得更優(yōu)的結(jié)果。用遺傳算法求解組合優(yōu)化問題具有巨大的優(yōu)越性[7]。非常有助于物流企業(yè)根據(jù)自己的實(shí)際情況科學(xué)、有效地制定物流決策，降低風(fēng)險(xiǎn)，降低成本，提高經(jīng)濟(jì)效益和自身的競(jìng)爭(zhēng)力。

參考文獻(xiàn):

[1] 田貴超，黎明.旅行商問題(TSP)的幾種求解方法[J].計(jì)算機(jī)仿真，2006，23(8):153-157.

[2] Holland J H.Adaptation in natural and artificial systems[M].Ann Arbor，Ml:The University Michigan Press，1975.

[3] 余有明，劉玉樹.遺傳算法的編碼理論與應(yīng)用[J].計(jì)算機(jī)工程與應(yīng)用，2006，42(3):86-89.

[4] 陳國良，王煦法，莊鎮(zhèn)泉，等.遺傳算法及其應(yīng)用[M].北京:人民郵電出版社，1996.

[5] 唐坤.車輛路徑問題中的遺傳算法設(shè)計(jì)[J].東北大學(xué)學(xué)報(bào):自然科學(xué)版，2002，28(1):66-70.

[6] 郎茂.物流配送車輛調(diào)度問題的模型和算法研究[M].北京:北方交通大學(xué)，2002.

[7] 李敏強(qiáng)，寇紀(jì)淞.遺傳算法的基本理論與應(yīng)用[M].北京:科學(xué)出版社，2003.