李 晶，邵 倩

（大連海事大學(xué) 交通運(yùn)輸工程學(xué)院，遼寧 大連 116026）

1 引言

隨著經(jīng)濟(jì)的發(fā)展以及對(duì)物流服務(wù)要求的提高，醫(yī)藥物流業(yè)面臨利潤(rùn)空間小、時(shí)效性差、經(jīng)營(yíng)成本高、難以形成集約化發(fā)展等諸多問(wèn)題，現(xiàn)階段我國(guó)醫(yī)藥物流仍然有待提高以滿足人們的要求[1-2]。通常醫(yī)藥物流運(yùn)輸批量小、頻率高，對(duì)于一些特殊醫(yī)療物資還需要低溫特殊運(yùn)輸，例如疫苗、針劑等。甚至在極其特殊的情況下，比如新型冠狀病毒疫情影響下，醫(yī)療物資更加需要保證在特定時(shí)間段的供應(yīng)。車(chē)輛配送路徑優(yōu)化作為醫(yī)藥物流的重要問(wèn)題之一，直接影響到物流企業(yè)的物流成本、時(shí)效性以及客戶對(duì)物流企業(yè)的滿意度、依賴性，對(duì)提高服務(wù)水平具有很高的現(xiàn)實(shí)效益。同時(shí)，由于全球能源消耗嚴(yán)重、氣候變暖形勢(shì)的加劇，對(duì)可以減少能源消耗的低碳物流的要求日益迫切，并且低碳物流的運(yùn)營(yíng)模式可以有效降低成本。醫(yī)藥物流車(chē)輛配送路徑問(wèn)題可以表達(dá)為帶時(shí)間窗的車(chē)輛路徑問(wèn)題（Vehicle Routing Problems with Time Windows，VRPTW），數(shù)學(xué)上描述為一個(gè)NP（Nondeterministic Polynomial，非確定多項(xiàng)式）問(wèn)題，這類(lèi)問(wèn)題很難求得最優(yōu)解[3]。針對(duì)不同的時(shí)間窗約束條件，結(jié)合車(chē)輛路徑模型和客戶滿意度，啟發(fā)式算法[4]、禁忌搜索算法[5]、自適應(yīng)遺傳算法[6]以及蟻群算法[7]等算法被成功用于求解VRPTW 問(wèn)題，并解決一些實(shí)際的物流車(chē)輛路徑優(yōu)化問(wèn)題。針對(duì)多模糊時(shí)間窗醫(yī)藥物流車(chē)輛路徑優(yōu)化問(wèn)題，可以使用改進(jìn)遺傳算法和粒子群算法[8]求解。

2 數(shù)學(xué)模型構(gòu)建

2.1 問(wèn)題描述

使醫(yī)藥物流配送車(chē)輛從醫(yī)藥物流企業(yè)倉(cāng)庫(kù)站點(diǎn)出發(fā)服務(wù)醫(yī)院、診所或者個(gè)人，完成用戶需求后仍返回倉(cāng)庫(kù)站點(diǎn)。這里多模糊時(shí)間窗表達(dá)的含義是當(dāng)客戶有多個(gè)不確定的時(shí)間段允許物流企業(yè)進(jìn)行醫(yī)療物資配送，每個(gè)時(shí)間段當(dāng)中有一個(gè)最令客戶滿意的時(shí)間段即客戶期望被服務(wù)的時(shí)間段，送達(dá)時(shí)間越靠近這個(gè)時(shí)間段，客戶越滿意，若送達(dá)時(shí)間在這個(gè)時(shí)間段內(nèi)客戶滿意度最高，越遠(yuǎn)離這個(gè)時(shí)間段滿意度越低，但送達(dá)時(shí)間不能超出客戶給定的時(shí)間范圍即客戶可以容忍的服務(wù)時(shí)間段，否則滿意度為零。該多模糊時(shí)間窗車(chē)輛路徑問(wèn)題可以描述為：一個(gè)配送中心，共有m輛配送車(chē)輛對(duì)n個(gè)客戶進(jìn)行配送服務(wù)，客戶i有Wi個(gè)不重合的模糊時(shí)間窗。已知客戶的位置坐標(biāo)、客戶需要的服務(wù)時(shí)間，車(chē)輛從配送中心出發(fā)，分別在用戶的時(shí)間窗內(nèi)對(duì)客戶進(jìn)行配送服務(wù)，然后返回配送中心。通過(guò)優(yōu)化路徑，在滿足客戶時(shí)間窗的情況下，降低運(yùn)輸成本，減少碳排放，提高客戶的滿意度。

根據(jù)上述問(wèn)題設(shè)定各個(gè)符號(hào)的意義，見(jiàn)表1。

表1 模型符號(hào)及解釋

本文采用梯級(jí)模糊時(shí)間窗，因此客戶滿意度定義為函數(shù)μi(ti)。

2.2 模型構(gòu)建

考慮碳排放因素的多模糊時(shí)間窗的車(chē)輛路徑問(wèn)題優(yōu)化模型可表達(dá)為：

式（2）為最小總成本數(shù)學(xué)模型，包括車(chē)輛固定使用成本、燃油消耗成本、二氧化碳排放的環(huán)境成本；式（3）為最大客戶平均滿意度。其中：

2.3 約束條件

約束條件可表達(dá)為：

式（6）保證每個(gè)客戶的滿意度不低于σ，σ是依據(jù)經(jīng)驗(yàn)給出；式（7）保證每個(gè)客戶都只被一輛車(chē)服務(wù)，服務(wù)每個(gè)客戶的車(chē)輛流量平衡；式（8）表示對(duì)每個(gè)客戶的時(shí)間窗按時(shí)間順序排序；式（9）和式（10）表示客戶在時(shí)間窗內(nèi)被服務(wù)；式（11）表示每個(gè)客戶都有一個(gè)時(shí)間窗被服務(wù)；式（12）表示每輛車(chē)的配送總重量不可以超出額定載重量。

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

3.1 構(gòu)造染色體

在此模型中使用自然數(shù)編碼。使用一組矢量表示染色體。染色體元素為自然序號(hào)，代表不同的客戶和配送中心，在染色體中自然序號(hào)的順序代表了車(chē)輛訪問(wèn)的順序。在本文模型中有一個(gè)配送中心，因此使用0代表配送中心，n代表不同的客戶。

例如，總共有3輛車(chē)為10個(gè)客戶進(jìn)行配送，假設(shè)在種群中其中一條染色體為：[0，7，3，4，10，8，0，2，1，5，0，6，9，0]。染色體表示車(chē)輛1的行駛路徑為：0-7-3-4-10-8-0，即車(chē)輛先從配送中心出發(fā)，分別為客戶7、客戶3、客戶4、客戶10、客戶8進(jìn)行服務(wù)，然后返回配送中心。車(chē)輛2 的行駛路徑為：0-2-1-5-0，代表了車(chē)輛2 從配送中心出發(fā)，然后分別為客戶2、客戶1，客戶5進(jìn)行服務(wù)，然后返回配送中心。車(chē)輛3的行駛路徑則為0-6-9-0，即車(chē)輛3 從配送中心出發(fā)，分別為客戶6、客戶9進(jìn)行服務(wù)，然后返回配送中心。

3.2 產(chǎn)生初始種群

根據(jù)染色體的構(gòu)造方式，首先對(duì)客戶序號(hào)進(jìn)行隨機(jī)排列，在首尾分別插入0，然后在序列中插入m-1 個(gè)0 來(lái)形成染色體，m為配送車(chē)輛數(shù)。由于配送車(chē)輛有最大載貨量，而且希望使得每輛車(chē)盡可能裝載多的貨物。因此在插入0 過(guò)程中需要計(jì)算當(dāng)前累計(jì)的載貨量，當(dāng)載貨量大于車(chē)輛最大載貨量時(shí)，在該客戶前插入0，然后重新進(jìn)行計(jì)算，直到插入所有0。通過(guò)上述流程可以隨機(jī)生成多個(gè)染色體并組成初始種群。

3.3 適應(yīng)值函數(shù)

種群染色體隨機(jī)生成，其中很多染色體并不滿足設(shè)定的約束條件。約束條件的處理方法是根據(jù)約束條件生成染色體，但是該處理方法復(fù)雜而且效率不高，本文采用懲罰函數(shù)的方法處理。懲罰函數(shù)方法是在違反約束條件方案的目標(biāo)函數(shù)中加入懲罰項(xiàng)。本文需要對(duì)配送車(chē)輛的載重量通過(guò)懲罰項(xiàng)進(jìn)行處理?？紤]到遺傳算法初期種群多樣性大，此時(shí)如果懲罰大的話，染色體的多樣性會(huì)大幅減少，導(dǎo)致過(guò)早收斂，陷入局部最優(yōu)。針對(duì)這個(gè)問(wèn)題，懲罰壓力根據(jù)迭代次數(shù)增加，隨著遺傳算法循環(huán)的次數(shù)增加而加大?？梢缘玫侥繕?biāo)函數(shù)為：

t為遺傳算法迭代次數(shù)，M為較大正數(shù)，qi為客戶i的需求量，Q為配送車(chē)輛的額定載重量。由于需要滿足約束條件，則當(dāng)不符合條件時(shí)Z值會(huì)變大。隨著迭代次數(shù)變大，約束條件對(duì)目標(biāo)函數(shù)的影響會(huì)增大。適應(yīng)值越大越好，因此上述目標(biāo)函數(shù)min Z取倒數(shù)，適應(yīng)函數(shù)可表示為：

3.4 遺傳過(guò)程

3.4.1 選擇算子。在選擇策略中選取了錦標(biāo)賽選擇算法，錦標(biāo)賽選擇算法具有容易實(shí)現(xiàn)、時(shí)間復(fù)雜度小、不需要對(duì)所有適應(yīng)值進(jìn)行排序處理的優(yōu)點(diǎn)。具體步驟如下：

步驟1：根據(jù)適應(yīng)函數(shù)計(jì)算當(dāng)前種群所有染色體的適應(yīng)值。

步驟2：種群中所有染色體被選擇的概率相同，選取3個(gè)染色體。

步驟3：比較選中的3個(gè)染色體的適應(yīng)值，選擇適應(yīng)值最好的染色體。

對(duì)以上步驟重復(fù)操作N遍，生成N條父代染色體用于后續(xù)的交叉和變異，生成下一代的染色體。

3.4.2 交叉算子。通過(guò)對(duì)2 個(gè)父代染色體進(jìn)行交叉重組生成子代染色體。普通的交叉算子一般適用于旅行者問(wèn)題，并不太適應(yīng)多輛車(chē)的路徑優(yōu)化問(wèn)題。在交叉算子的選擇上，希望能夠保留父代優(yōu)秀路徑的信息，并且即使兩父代信息相同也能生成不同的子代，避免過(guò)早陷入局部最優(yōu)的情況。

步驟1：分別在兩個(gè)父代染色體中選擇一段子路徑。

染色體A：

步驟2：把A選擇的子路徑加入B的前段，將B選擇的子路徑加入到A的前段。

染色體A：

步驟3：將A 中與子路徑2 重復(fù)的數(shù)字和后面的0刪除，對(duì)B進(jìn)行同樣的操作。

染色體A：

步驟4：針對(duì)染色體B，在路徑2 后4 個(gè)位置中插入0，可生成4個(gè)路徑方案，計(jì)算4個(gè)路徑方案的適應(yīng)值，將適應(yīng)值最大的作為子代染色體1。通過(guò)相同的操作可以得到子代染色體2。

3.4.3 變異算子。設(shè)定變異概率為a%，在區(qū)間（0，1)生成隨機(jī)數(shù)b，當(dāng)隨機(jī)數(shù)b ＞a時(shí)，對(duì)交叉生成的子代染色體進(jìn)行變異操作。在子代染色體隨機(jī)選取2個(gè)位置進(jìn)行交換生成變異后的子代染色體1，再隨機(jī)選取2個(gè)位置進(jìn)行交換生成變異后的子代染色體2。比較染色體1 和染色體2 的適應(yīng)值，適應(yīng)值高的保留，進(jìn)入子代種群。

3.5 終止條件

遺傳算法的終止條件對(duì)于確定遺傳算法循環(huán)結(jié)束很重要。開(kāi)始時(shí)算法會(huì)進(jìn)行很快，每次迭代會(huì)產(chǎn)生更好的方案，后期會(huì)收斂，改進(jìn)非常小。通過(guò)合理設(shè)定終止條件，以便解決方案在運(yùn)行結(jié)束時(shí)接近最優(yōu)。通?？梢酝ㄟ^(guò)預(yù)設(shè)目標(biāo)，達(dá)到目標(biāo)后終止程序，或者在最優(yōu)方案沒(méi)有提升時(shí)結(jié)束程序。本文采用預(yù)先設(shè)定遺傳循環(huán)次數(shù)作為終止的規(guī)則。

4 算例分析

4.1 算例介紹

配送中心擁有3 輛型號(hào)相同的貨車(chē)，為25 個(gè)客戶進(jìn)行配送服務(wù)。每個(gè)客戶對(duì)貨物需求量不同，并且具有多個(gè)不同的時(shí)間窗。貨車(chē)的額定重量為50，假設(shè)電動(dòng)車(chē)出發(fā)時(shí)間為0，行駛速度恒定為40，貨車(chē)單位行駛成本為5。單位油耗為5，燃油轉(zhuǎn)換系數(shù)為0.4，單位排放二氧化碳成本為1。表2第一列數(shù)據(jù)表示客戶和配送中心的序號(hào)。0 代表配送中心，1，2，…，25分別代表客戶。第二、三列代表了配送中心和客戶的X坐標(biāo)和Y坐標(biāo)；第四列代表客戶的貨物需求量；第五列和第六列代表客戶最大容忍的時(shí)間窗，第七列和第八列代表客戶期待服務(wù)的時(shí)間窗；最后一列代表客戶所需要服務(wù)的時(shí)間。

表2 算例數(shù)據(jù)

圖1為配送中心和客戶的位置分布，其中圓圈代表客戶，三角代表配送中心。

圖1 配送中心和客戶位置分布圖

4.2 算例結(jié)果

本文使用C++11 實(shí)現(xiàn)上述算法程序，并使用該程序?qū)Ρ疚牡乃憷M(jìn)行求解。算法的參數(shù)：種群大小為500，迭代次數(shù)為2 000，交叉概率為0.95，變異概率為0.3。

運(yùn)輸路徑見(jiàn)表3和圖2。

表3 運(yùn)輸路徑

圖2 運(yùn)輸路徑

最終計(jì)算出運(yùn)輸成本為6 943，碳排放成本為2 777，總成本為10 170，客戶平均滿意度為0.726。

改變算法對(duì)超重方案的懲罰壓力為固定值，并且根據(jù)迭代次數(shù)逐漸增加懲罰壓力作對(duì)比，對(duì)比結(jié)果見(jiàn)表4。

表4 算法對(duì)比

5 結(jié)論

本文針對(duì)醫(yī)療物流，通過(guò)綜合考慮各種信息進(jìn)行動(dòng)態(tài)的路徑規(guī)劃，降低物流成本并且保證貨物能按照客戶需求送達(dá)。使用遺傳算法進(jìn)行求解，由于醫(yī)療物流的時(shí)效性，加入模糊時(shí)間窗口和懲罰項(xiàng)來(lái)保證送達(dá)時(shí)間，在實(shí)際應(yīng)用中有一定的參考意義。在遺傳算法實(shí)現(xiàn)過(guò)程中，通過(guò)初期減少懲罰項(xiàng)的權(quán)重能保證前期種群的多樣性，避免過(guò)早收斂，能夠有效提高算法效果；通過(guò)穩(wěn)重的交叉算子能較好保留優(yōu)秀路徑的同時(shí)產(chǎn)生不同子代；加大變異概率對(duì)迭代后期起到較好作用。下一步研究可以考慮不確定影響因素對(duì)路徑規(guī)劃的影響，例如實(shí)際交通狀況和貨物體積。