考慮多模糊時間窗醫藥物流配送路徑優化

李 晶，邵 倩

（大連海事大學 交通運輸工程學院，遼寧 大連 116026）

1 引言

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

2 數學模型構建

2.1 問題描述

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

根據上述問題設定各個符號的意義，見表1。

表1 模型符號及解釋

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

2.2 模型構建

考慮碳排放因素的多模糊時間窗的車輛路徑問題優化模型可表達為：

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

2.3 約束條件

約束條件可表達為：

式（6）保證每個客戶的滿意度不低于σ，σ是依據經驗給出；式（7）保證每個客戶都只被一輛車服務，服務每個客戶的車輛流量平衡；式（8）表示對每個客戶的時間窗按時間順序排序；式（9）和式（10）表示客戶在時間窗內被服務；式（11）表示每個客戶都有一個時間窗被服務；式（12）表示每輛車的配送總重量不可以超出額定載重量。

3 算法設計

3.1 構造染色體

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

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

3.2 產生初始種群

根據染色體的構造方式，首先對客戶序號進行隨機排列，在首尾分別插入0，然后在序列中插入m-1 個0 來形成染色體，m為配送車輛數。由于配送車輛有最大載貨量，而且希望使得每輛車盡可能裝載多的貨物。因此在插入0 過程中需要計算當前累計的載貨量，當載貨量大于車輛最大載貨量時，在該客戶前插入0，然后重新進行計算，直到插入所有0。通過上述流程可以隨機生成多個染色體并組成初始種群。

3.3 適應值函數

種群染色體隨機生成，其中很多染色體并不滿足設定的約束條件。約束條件的處理方法是根據約束條件生成染色體，但是該處理方法復雜而且效率不高，本文采用懲罰函數的方法處理。懲罰函數方法是在違反約束條件方案的目標函數中加入懲罰項。本文需要對配送車輛的載重量通過懲罰項進行處理。考慮到遺傳算法初期種群多樣性大，此時如果懲罰大的話，染色體的多樣性會大幅減少，導致過早收斂，陷入局部最優。針對這個問題，懲罰壓力根據迭代次數增加，隨著遺傳算法循環的次數增加而加大。可以得到目標函數為：

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

3.4 遺傳過程

3.4.1 選擇算子。在選擇策略中選取了錦標賽選擇算法，錦標賽選擇算法具有容易實現、時間復雜度小、不需要對所有適應值進行排序處理的優點。具體步驟如下：

步驟1：根據適應函數計算當前種群所有染色體的適應值。

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

步驟3：比較選中的3個染色體的適應值，選擇適應值最好的染色體。

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

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

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

染色體A：

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

染色體A：

步驟3：將A 中與子路徑2 重復的數字和后面的0刪除，對B進行同樣的操作。

染色體A：

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

3.4.3 變異算子。設定變異概率為a%，在區間（0，1)生成隨機數b，當隨機數b ＞a時，對交叉生成的子代染色體進行變異操作。在子代染色體隨機選取2個位置進行交換生成變異后的子代染色體1，再隨機選取2個位置進行交換生成變異后的子代染色體2。比較染色體1 和染色體2 的適應值，適應值高的保留，進入子代種群。

3.5 終止條件

遺傳算法的終止條件對于確定遺傳算法循環結束很重要。開始時算法會進行很快，每次迭代會產生更好的方案，后期會收斂，改進非常小。通過合理設定終止條件，以便解決方案在運行結束時接近最優。通常可以通過預設目標，達到目標后終止程序，或者在最優方案沒有提升時結束程序。本文采用預先設定遺傳循環次數作為終止的規則。

4 算例分析

4.1 算例介紹

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

表2 算例數據

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

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

4.2 算例結果

本文使用C++11 實現上述算法程序，并使用該程序對本文的算例進行求解。算法的參數：種群大小為500，迭代次數為2 000，交叉概率為0.95，變異概率為0.3。

運輸路徑見表3和圖2。

表3 運輸路徑

圖2 運輸路徑

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

改變算法對超重方案的懲罰壓力為固定值，并且根據迭代次數逐漸增加懲罰壓力作對比，對比結果見表4。

表4 算法對比

5 結論

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