基于時(shí)間窗的城市醫(yī)藥品動(dòng)態(tài)配送路徑優(yōu)化模型與算法＊*

鄭國華，周小強(qiáng)，張力敏

(1.中南大學(xué)交通運(yùn)輸工程學(xué)院，湖南 長沙 410075;2.湖南三一工業(yè)職業(yè)技術(shù)學(xué)院，湖南 長沙 410129)

1 問題的提出

在城市醫(yī)藥品配送網(wǎng)絡(luò)體系中，由于區(qū)域內(nèi)醫(yī)藥供應(yīng)鏈終端客戶需求信息的不確定性，導(dǎo)致醫(yī)藥物流配送中心的配送路徑動(dòng)態(tài)變化。如何在客戶需求的服務(wù)時(shí)間內(nèi)，提供及時(shí)準(zhǔn)確且成本最小化的配送服務(wù)，需要對(duì)城市醫(yī)藥品動(dòng)態(tài)配送路徑進(jìn)行優(yōu)化。

城市醫(yī)藥品動(dòng)態(tài)配送路徑優(yōu)化問題少見專門研究，相關(guān)研究成果主要集中在一般性的動(dòng)態(tài)車輛路徑問題上［1］。Dror等［2］集中研究了動(dòng)態(tài)隨機(jī)車輛運(yùn)輸?shù)男枨蠼７椒?，并將模型?yīng)用于郵政速遞、產(chǎn)品配送和生產(chǎn)調(diào)度等眾多領(lǐng)域;Hanshar等［3］研究了當(dāng)客戶的需求不確定或交通信息發(fā)生變化時(shí)，如何在滿足相關(guān)約束的條件下為車輛尋求最合理的規(guī)劃路徑;李兵等［4］通過引入虛擬任務(wù)點(diǎn)的方法將其轉(zhuǎn)化為一個(gè)靜態(tài)的車輛路徑問題，并采用節(jié)約算法求解;劉士新等［5］設(shè)計(jì)了在動(dòng)態(tài)環(huán)境下進(jìn)行車輛路徑優(yōu)化的導(dǎo)向局域搜索算法;Alan等［6－9］也從不同的角度對(duì)動(dòng)態(tài)車輛路徑優(yōu)化問題進(jìn)行了相關(guān)研究。但上述文獻(xiàn)研究極少考慮到時(shí)間窗因素，本文主要以客戶服務(wù)時(shí)間窗為約束，以降低藥品配送費(fèi)用及提高服務(wù)準(zhǔn)時(shí)性為目標(biāo)，建立配送路徑初始與動(dòng)態(tài)優(yōu)化模型，并設(shè)計(jì)了遺傳算法［10］，對(duì)城市醫(yī)藥品動(dòng)態(tài)配送路徑優(yōu)化問題進(jìn)行相關(guān)研究。

2 問題分析及變量定義

醫(yī)藥品作為一種特殊的商品，不僅品類繁多、分類復(fù)雜，而且儲(chǔ)運(yùn)條件要求高、時(shí)效性強(qiáng)。針對(duì)醫(yī)藥品的獨(dú)特性，在對(duì)城市醫(yī)藥品配送網(wǎng)絡(luò)的路徑優(yōu)化建模時(shí)，摒棄了按零售端店面劃分配送節(jié)點(diǎn)的傳統(tǒng)做法，而是采用按零售端需求的醫(yī)藥品種來劃分配送節(jié)點(diǎn)，以有效解決醫(yī)藥品配送時(shí)，由于品類多、分類雜而造成的分揀難度大的問題，亦可有效地滿足醫(yī)藥品配送中客戶多批次、小批量的配送服務(wù)需求。

為發(fā)揮規(guī)模經(jīng)濟(jì)性和技術(shù)經(jīng)濟(jì)性，假設(shè)某一城市區(qū)域內(nèi)確定由一家醫(yī)藥配送中心對(duì)城市醫(yī)藥客戶進(jìn)行配送，且該醫(yī)藥配送中心總能滿足醫(yī)藥客戶的需求，其服務(wù)水平主要體現(xiàn)為在客戶規(guī)定的時(shí)間窗范圍內(nèi)，最大化服務(wù)客戶的數(shù)量和最小化配送服務(wù)的費(fèi)用，其中藥品配送費(fèi)用主要考慮配送當(dāng)中的運(yùn)輸費(fèi)用。

首先，根據(jù)客戶的初始訂單進(jìn)行配送路徑的初始優(yōu)化，配送車輛從醫(yī)藥配送中心出發(fā)將藥品送到各客戶點(diǎn)，然后返回醫(yī)藥配送中心，假定每個(gè)客戶點(diǎn)的位置、需求量與服務(wù)時(shí)間已知，每輛車的載重量一定，要求合理安排配送路徑，盡可能地降低配送費(fèi)用及提高服務(wù)準(zhǔn)時(shí)性。

其次，在初始配送路徑優(yōu)化的基礎(chǔ)上結(jié)合動(dòng)態(tài)需求信息進(jìn)行城市醫(yī)藥品動(dòng)態(tài)配送路徑的優(yōu)化。所謂動(dòng)態(tài)需求信息主要有包括4種情形:①原客戶需求量減少;②原客戶取消訂貨;③原客戶需求量增加;④新客戶訂貨。

上述情形下的動(dòng)態(tài)配送路徑優(yōu)化問題主要考慮以下狀態(tài):

(1)若動(dòng)態(tài)需求信息只出現(xiàn)情形①或②，對(duì)于取消訂貨的原客戶直接跳過到下一客戶，初始配送路徑不變。

(2)若動(dòng)態(tài)需求信息出現(xiàn)情形③或④，則需建立相關(guān)模型進(jìn)行配送路徑的動(dòng)態(tài)優(yōu)化，此時(shí)，由于有些配送車輛已經(jīng)駛離醫(yī)藥配送中心并且服務(wù)了部分客戶，車輛的剩余載重量發(fā)生了改變，為此本文特引入虛擬配送中心的概念。若該時(shí)刻配送車輛位于某服務(wù)的客戶點(diǎn)處，則將該客戶點(diǎn)設(shè)為虛擬配送中心，否則將下一服務(wù)客戶點(diǎn)設(shè)為虛擬配送中心，此時(shí)，將該時(shí)刻未服務(wù)的客戶(虛擬配送中心除外)都作為新客戶處理。因此配送路徑動(dòng)態(tài)優(yōu)化問題可表述為:在客戶需求信息實(shí)時(shí)更新的情況下，配送車輛從醫(yī)藥配送中心以及虛擬配送中心出發(fā)對(duì)新客戶進(jìn)行配送服務(wù)，然后返回醫(yī)藥配送中心，每輛車的載重量一定，要求合理優(yōu)化配送路徑以盡可能地降低配送費(fèi)用及提高服務(wù)準(zhǔn)時(shí)性。

為方便敘述起見，定義變量如下:

S'表示原配送中心;W表示配送車輛的載重量，且載重量相同;集合L={1，2，…，l}表示初始訂貨客戶集合;gi(i∈L)表示每個(gè)客戶的需求量;Tj表示到達(dá)客戶j的時(shí)間;tij表示客戶i到客戶j行駛所用的時(shí)間;t'i表示服務(wù)客戶i所需要的服務(wù)時(shí)間;LTj表示客戶j要求的最遲到貨時(shí)間;Pj表示藥品不能按照客戶j要求的時(shí)間段準(zhǔn)時(shí)送達(dá)所產(chǎn)生的懲罰費(fèi)用(貨物提前到達(dá)不懲罰);集合L'={1，2，…，l'}表示新客戶集合;g'i(i∈L')表示新客戶的需求量;集合K={1，2，…，k}表示虛擬配送中心集合;W'k(k∈K)表示虛擬配送中心的剩余車載量;集合D={1，2，…，d}表示原配送中心可使用的車輛;Rik表示配送中心i的第k輛配送車的運(yùn)行路徑;Nik表示該路徑上的客戶數(shù)量;Nik=0表示未使用該車輛表示某客戶在 Rik中的順序號(hào)為j;Cij=t×α×S表示兩點(diǎn)間的運(yùn)輸費(fèi)用;α表示現(xiàn)實(shí)情況道路狀況的修正系數(shù)，當(dāng)?shù)缆窢顩r擁擠時(shí)α＞1，當(dāng)?shù)缆窢顩r好時(shí)0＜α≤1;S表示兩地的道路實(shí)際長度;t表示單位距離運(yùn)輸費(fèi)用;β表示懲罰系數(shù)。

定義決策變量如下:

3 基于時(shí)間窗的城市醫(yī)藥品動(dòng)態(tài)配送路徑優(yōu)化模型

3.1 基于時(shí)間窗的配送路徑初始優(yōu)化模型

以降低藥品配送費(fèi)用及提高服務(wù)準(zhǔn)時(shí)性為目標(biāo)，以客戶服務(wù)時(shí)間窗、車載量為約束，建立配送路徑初始優(yōu)化模型如下:

目標(biāo)函數(shù)(3－1)使得總的藥品配送費(fèi)用以及超出客戶服務(wù)時(shí)間窗所產(chǎn)生的懲罰費(fèi)用之和達(dá)到最小;約束條件(3－2)為每輛車所服務(wù)的客戶的需求量小于車輛的載重量;約束條件(3－3)為每個(gè)客戶有且只有一輛配送車進(jìn)行配送服務(wù);式(3－4)提供了懲罰函數(shù)中Tj的數(shù)學(xué)表達(dá)式;約束條件(3－5)表示保證行車路徑上時(shí)間的順序性。懲罰函數(shù)(3－6)為藥品不能按照客戶要求的時(shí)間段準(zhǔn)時(shí)運(yùn)到客戶手中所產(chǎn)生的懲罰費(fèi)用(貨物提前到達(dá)不懲罰)。

3.2 基于時(shí)間窗的配送路徑動(dòng)態(tài)優(yōu)化模型

以降低藥品配送費(fèi)用及提高服務(wù)準(zhǔn)時(shí)性為目標(biāo)，以客戶服務(wù)時(shí)間窗、車載量為約束，建立配送路徑動(dòng)態(tài)優(yōu)化模型如下:

目標(biāo)函數(shù)(3－7)使得總的藥品配送費(fèi)用以及超出客戶服務(wù)時(shí)間窗所產(chǎn)生的懲罰費(fèi)用之和達(dá)到最小;約束條件(3－8)限制從原配送中心出發(fā)所服務(wù)的客戶的需求量不超過其車載量;約束條件(3－9)限制從虛擬配送中心出發(fā)的車所服務(wù)的客戶的需求量不超過其剩余車載量;約束條件(3－10)、(3－11)、(3－12)限制每個(gè)客戶點(diǎn)有且只有一個(gè)配送中心的一輛車提供服務(wù);式(3－13)提供了懲罰函數(shù)中Tj的數(shù)學(xué)表達(dá)式;懲罰函數(shù)(3－14)為藥品不能按照客戶要求的時(shí)間段準(zhǔn)時(shí)運(yùn)到客戶手中所產(chǎn)生的懲罰費(fèi)用(貨物提前到達(dá)不懲罰)。

4 遺傳算法設(shè)計(jì)

城市醫(yī)藥品動(dòng)態(tài)配送路徑優(yōu)化問題是一個(gè)典型的NP(Nondeterministic Polynomial)難問題，如采用傳統(tǒng)方法對(duì)其進(jìn)行求解，不但工作量大，花費(fèi)時(shí)間長，而且通用性差，因此本文采用遺傳算法(Genetic Algorithm，GA)求解。

4.1 染色體編碼

采用符號(hào)來進(jìn)行編碼且基于貪婪構(gòu)造法的方式進(jìn)行譯碼，譯碼時(shí)只須按序盡最大可能地將基因位表示的客戶點(diǎn)插入到路線中，當(dāng)一個(gè)點(diǎn)違背時(shí)間窗或載重約束時(shí)，就開辟一條新路徑并將這個(gè)點(diǎn)插入該路徑。如編碼為acdbfeghij，經(jīng)過譯碼表示的路線為:路徑1:0－a－c－d－0;路徑2:0－b－f－e－g－0;路徑3:0－h(huán)－i－j－0，其中0表示配送中心。

4.2 交叉概率、變異概率的自適應(yīng)機(jī)制

在遺傳算法中，對(duì)其收斂性起決定作用的是交叉和變異算子。在遺傳算法中交叉概率一般取一個(gè)較大的數(shù)，變異概率一般取一個(gè)較小的數(shù)。為了避免發(fā)散和陷入局部最優(yōu)點(diǎn)以及加快優(yōu)化進(jìn)程，本文提出新的自適應(yīng)機(jī)制，通過個(gè)體適應(yīng)度值間的比較，動(dòng)態(tài)地調(diào)整pc和pm，對(duì)適應(yīng)度值高的個(gè)體降低pm和pc，對(duì)適應(yīng)度值低的個(gè)體提高pm和pc。

式中:fmax為種群中最大適應(yīng)值;fmin為種群中最小適應(yīng)值;f'為交叉?zhèn)€體的適應(yīng)值;為種群的平均適應(yīng)值;f為變異個(gè)體的適應(yīng)值;pcmax為交叉概率的最大值;pcmin為交叉概率的最小值;pmmax為變異概率的最大值;pmmin為變異概率的最小值。

4.3 交叉、變異算子

交叉算子進(jìn)行內(nèi)部交叉，其操作方法如下:首先隨機(jī)地在染色體串中選擇一個(gè)交配區(qū)域，如父串交配區(qū)域選定為，然后將A的交配區(qū)域進(jìn)行反轉(zhuǎn)得到

變異算子采用隨機(jī)交換染色體兩點(diǎn)的基因值。

5 算例分析

設(shè)某醫(yī)藥配送中心為城市30位醫(yī)藥銷售終端客戶提供醫(yī)藥配送服務(wù)，配送中心在提供服務(wù)時(shí)，主要按零售客戶需求的醫(yī)藥品種劃分配送節(jié)點(diǎn)，其中18個(gè)客戶對(duì)于品種A下了初始訂單(考慮到其他醫(yī)藥品種的配送問題與品種A的配送問題一致，本文只針對(duì)醫(yī)藥品種A進(jìn)行算例分析)，醫(yī)藥配送中心與各客戶點(diǎn)間的實(shí)際距離、各客戶的初始需求量以及客戶的服務(wù)時(shí)間窗等初始數(shù)據(jù)不詳細(xì)列出。

另設(shè)醫(yī)藥配送中心到各客戶點(diǎn)的路況修正系數(shù)α =1.1，各客戶點(diǎn)間的路況修正系數(shù) α =1.2，單位距離運(yùn)輸費(fèi)用t=2，其中α和t可以根據(jù)實(shí)際情況進(jìn)行動(dòng)態(tài)調(diào)整，懲罰系數(shù)β=0.5，每個(gè)客戶點(diǎn)需要的服務(wù)時(shí)間t'=3，汽車的載重量相同且w=10。

首先根據(jù)客戶的初始訂貨信息及配送路徑初始優(yōu)化模型，利用遺傳算法求解得到城市醫(yī)藥品初始配送優(yōu)化路徑，遺傳算法參數(shù)設(shè)置:種群個(gè)體數(shù)為30，迭代次數(shù)為300，pcmax=0.8，pcmin=0.6，pmmax=0.1，pmmin=0.005?？紤]到通用啟發(fā)式算法求取最優(yōu)解的質(zhì)量可能與初始解有關(guān)，而遺傳算法又是從問題解的串集開始搜索，因此在上述算法的實(shí)現(xiàn)中，記錄10次運(yùn)算中得到的最優(yōu)解目標(biāo)值與初始解集平均目標(biāo)值進(jìn)行比較以此對(duì)前面所提出的優(yōu)化模型和算法進(jìn)行檢驗(yàn)，結(jié)果如表1所示?？芍顑?yōu)解的目標(biāo)值相對(duì)初始解集的平均目標(biāo)值，其配送費(fèi)用節(jié)省56.5% ～64.1%，由此可以證明配送路徑初始優(yōu)化模型及遺傳算法的有效性，且算法可以迅速收斂到最優(yōu)解，收斂曲線如圖1所示。

表1 對(duì)應(yīng)的初始解集平均目標(biāo)值和最優(yōu)解目標(biāo)值Table 1 The average target of initial solution set and corresponding optimal target

圖1 初始配送路徑優(yōu)化收斂曲線圖Fig.1 The convergence graph of initial distribution path optimization

將表1中最優(yōu)解目標(biāo)值最小的路徑作為初始配送優(yōu)化路徑(見表2)。

表2 初始配送優(yōu)化路徑表Table 2 Initial distribution optimization path table

假設(shè)在時(shí)刻40更新客戶動(dòng)態(tài)需求信息，原客戶6，17需求量分別增加 1，1，客戶 25，23需求量分別減少2，1，此時(shí)又有5個(gè)新客戶提出服務(wù)請(qǐng)求，其需求量及服務(wù)時(shí)間窗分別為32(2，［50，55］)，33(1，［52，58］)，34(2，［60，65］)，35(2，［65，70］)，36(2，［55，65］)，新客戶到原配送中心與虛擬配送中心的距離等信息，這里不詳細(xì)列出，此時(shí)需要進(jìn)行配送路徑的動(dòng)態(tài)實(shí)時(shí)優(yōu)化。

由初始優(yōu)化配送路徑信息可知，此時(shí)醫(yī)藥配送中心已發(fā)出4輛車，車輛1已經(jīng)回到醫(yī)藥配送中心;車輛2服務(wù)完客戶10，正在前往客戶20的途中，因此客戶20設(shè)為虛擬配送中心，剩余車載量為5;車輛3服務(wù)完客戶17，在前往客戶25的途中，因此客戶25設(shè)為虛擬配送中心，剩余車載量為3;車輛4服務(wù)完客戶23，在前往客戶19的途中，因此客戶19設(shè)為虛擬配送中心，剩余車載量為3;此時(shí)原配送中心依然服務(wù)，新客戶數(shù)量總共為9個(gè)。

根據(jù)配送路徑動(dòng)態(tài)優(yōu)化模型，利用遺傳算法求解。遺傳算法參數(shù)設(shè)置:種群個(gè)體數(shù)為30，迭代次數(shù)為300，pcmax=0.8，pcmin=0.6，pmmax=0.15，pmmin=0.005。同樣考慮到通用啟發(fā)式算法求取的最優(yōu)解的質(zhì)量可能與初始解有關(guān)，而遺傳算法又是從問題解的串集開始搜索，因此在算法的實(shí)現(xiàn)中，記錄10次運(yùn)算中得到的最優(yōu)解目標(biāo)值與初始解集平均目標(biāo)值進(jìn)行比較以此對(duì)配送路徑動(dòng)態(tài)優(yōu)化模型和算法進(jìn)行檢驗(yàn)，結(jié)果如表3所示。從表3可知，最優(yōu)解的目標(biāo)值非常接近，且相對(duì)初始解集平均目標(biāo)值，最優(yōu)解的目標(biāo)值即配送總費(fèi)用節(jié)省39.26% ～42.33%(由于此時(shí)問題的規(guī)模較小，因此配送費(fèi)用節(jié)省較低)，算法能夠迅速收斂到最優(yōu)解，并且算例的計(jì)算時(shí)間為55 s，因此可以滿足調(diào)度的實(shí)時(shí)性要求，動(dòng)態(tài)配送優(yōu)化路徑如表4所示，算法的收斂曲線如圖2所示。

表3 對(duì)應(yīng)的初始解集平均目標(biāo)值和最優(yōu)解目標(biāo)值Table 3 The average target of initial solution set and corresponding optimal target

表4 動(dòng)態(tài)配送優(yōu)化路徑表Table 4 Dynamic distribution path table

圖2 動(dòng)態(tài)配送路徑優(yōu)化收斂曲線圖Fig.2 The convergence graph of dynamic distribution path optimization

6 結(jié)論

(1)考慮客戶服務(wù)時(shí)間的要求，利用本文建立的配送路徑初始優(yōu)化模型、動(dòng)態(tài)優(yōu)化模型以及設(shè)計(jì)的遺傳算法可以有效地優(yōu)化配送路徑，較大程度地節(jié)省配送費(fèi)用，提高配送服務(wù)水平，并且滿足城市醫(yī)藥品動(dòng)態(tài)配送路徑優(yōu)化問題的實(shí)時(shí)性要求。

(2)本文所提出的優(yōu)化模型和算法是解決城市醫(yī)藥品動(dòng)態(tài)配送網(wǎng)絡(luò)路徑優(yōu)化設(shè)計(jì)問題的一種有效方法，也可為其他需要考慮服務(wù)水平的物流配送網(wǎng)絡(luò)路徑優(yōu)化設(shè)計(jì)提供較理想的決策支持。

［1］Psaraftis H N.Dynamic vehicle routing:status and prospects［J］.Annals of Operations Research，1995，61(1):143－164.

［2］Dror M，Powell W.Stochastic and dynamic models in transportation preface［J］.Operations Research ，1993，41(1):11－14.

［3］Hanshar F T，Ombuki－Berman B M.Dynamic vehicle routing using genetic algorithms［J］.Applied Intelli －gence，2007，27(1):89 －99.

［4］李 兵，鄭四發(fā)，曹劍東，等.求解客戶需求動(dòng)態(tài)變化的車輛路徑規(guī)劃方法［J］.交通運(yùn)輸工程學(xué)報(bào)，2007，7(1):106－110.LI Bing，ZHENG Si-fa，CAO Jian-dong，et al.Method of solving vehicle routing problem with customers’dynamic requests［J］.Journal of Traffic and Transportation Engineering，2007，7(1):106 －110.

［5］劉士新，馮海蘭.動(dòng)態(tài)車輛路徑問題的優(yōu)化方法［J］.東北大學(xué)學(xué)報(bào):自然科學(xué)版，2008，29(4):484－487.LIU Shi-xin，F(xiàn)ENG Hai-lan.Optimization approach to solving dynamic vehicle routing problems［J］.Journal of Northeastern University:Natural Science，2008，29(4):484－487.

［6］Alan S.Specification for a dynamic vehicle routing and scheduling system［J］.International Journal of Transportation Management，2002，1(1):29 －40.

［7］熊 浩，胡列格.多車型動(dòng)態(tài)車輛調(diào)度及其遺傳算法［J］.系統(tǒng)工程，2009，27(10):21－24.XIONG Hao，HU Lie-ge.Dynamic vehicle routing problem with multiple vehicle type and its genetic algorithm［J］.Systems Engineering，2009，27(10):21 －24.

［8］吳兆福，董文永.求解動(dòng)態(tài)車輛路徑問題的演化蟻群算法［J］.武漢大學(xué)學(xué)報(bào):理學(xué)版，2007，53(5):571－575.WU Zhao-fu，DONG Wen-yong.A mixed evolutionary ant algorithm for the dynamic vechicle routing problem［J］.J.Wuhan Univ:Nat.Sci.Ed.，2007，53(5):571 －575.

［9］吳 升，陳 楠.基于位置服務(wù)的動(dòng)態(tài)車輛路徑問題研究［J］.福州大學(xué)學(xué)報(bào):自然科學(xué)版，2007，35(6):953－956.WU Sheng，CHEN Nan.Study on dynamic vehicle routing problem based on location － based services［J］.Journal of Fuzhou University:Natural Science，2007，35(6):953－956.

［10］周 明，孫樹棟.遺傳算法原理及應(yīng)用［M］.北京:國防工業(yè)出版社，1999.ZHOU Ming，SUN Shu-dong.Genetic algorithms:theory and applications［M］.Bei Jing:National Defence Industry Press，1999.

［11］張得志，李雙艷.不確定環(huán)境下協(xié)同運(yùn)輸優(yōu)化模型及其算法［J］.鐵道科學(xué)與工程學(xué)報(bào)，2010，7(4):116－120.ZHANG De-zhi，LI Shang-yan.An optimization model for coordination transportation and its solution algorithm under uncertain environment［J］.Jouranl of Railway Scinence and Engineering，2010，7(4):116 －120.