藥品多車型配送的車輛指派與路徑優化研究

劉閃

摘 要：針對醫藥產品所具有的體積小、重量輕、生命周期短等特點以及多車型配送現狀，文章研究帶有最后時間限制的多車型指派和配送路徑集成優化問題，建立了以配送成本最低為目標函數的整數規劃模型，同時使用節約里程法進行求解，并應用實際數據來驗證模型和算法的有效性。

關鍵詞：醫藥物流；多車型車輛路徑問題；節約里程法

中圖分類號：F252 文獻標志碼：A 文章編號：2095-2945（2018）35-0063-02

Abstract： According to the characteristics of pharmaceutical products such as small size， light weight， short life cycle and the current situation of multi-vehicle distribution， this paper studies the integrated optimization problem of multi-vehicle assignment and distribution path with final time constraints. The integer programming model with the lowest distribution cost as the objective function is established， and the mileage saving method is used to solve the problem， and the actual data is used to verify the validity of the model and the algorithm.

Keywords： pharmaceutical logistics； multi-vehicle routing problem； mileage saving method

1 概述

隨著我國醫藥需求量的增長，醫藥物流行業面臨著前所未有的機遇與挑戰，配送作為醫藥物流的關鍵環節也受到愈來愈多的關注。如何設計合理的車輛調度方案和行車路線是所有醫藥物流企業所面臨的共同問題。本文以醫藥物流企業所面臨的藥品配送成本高、效率低的問題為研究對象，考慮到醫藥產品所具有的體積小、重量輕、生命周期短等特點以及物流企業使用多種類型車輛配送的現狀，通過建立數學模型來描述問題，并用啟發式算法對其進行求解，以期能夠降低配送成本，提高配送效率。

2 數學模型構建

2.1 模型假設與約束條件

模型假設：（1）所有藥品均可以一起配送的；（2）配送中心及各個客戶的具體地理位置是確定的；（3）各客戶的需求是已知的；（4）配送車輛的規格是已知的；（5）忽略單行線對配送中車輛行駛的影響，即認為所有道路都是可以往返通行的；（6）運輸費用和行駛里程線性相關。

約束條件：（1）同一配送路線中所需配送的藥品的總體積不得超出配送車輛的最大裝載體積；（2）每個客戶點所需求的藥品必須得到滿足，且由一輛車配送；（3）配送方案中使用的車輛數不得超過公司配送車輛總數目；（4）每輛外出配送的車都必須從配送中心出發，在完成任務后返回配送中心；（5）每輛配送車輛一次配送的總時間不超過額定工作時間。

其中，公式（1）為目標函數，即所有車輛的配送成本最小。公式（2）和（3）表示每一個客戶點只能由一輛車來服務，并且保證車輛完成服務后離開；公式（4）是指所使用的各類型的車輛不超其可用數量；公式（5）是保證每個客戶點的需求都得到滿足，每個客戶點都被服務；公式（6）和（7）是為了保證不違反車輛容量與配送時間約束；公式（8）-（10）定義了決策變量的取值。

3 求解方法

車輛路徑問題作為一個NP難題，會因客戶點數量的增加而產生大量的可選擇方案，難以用精確算法進行求解，啟發式算法是解決實際問題的常用算法。節約里程法屬于逐次逼近法，計算步驟簡單，能夠在短時間內得到計算結果，且易于考慮各種實際問題，具有較好的擴充性。考慮到節約里程法這一特點，確定用其對模型求解，具體步驟如下：

步驟1初始化基本輸入數據，如客戶位置、需求，車輛容積、成本等。

步驟2將公司的任意兩個客戶點i和j連接在一起，利用公式Sij=d0i+d0j-dij，計算節約值，得出節約里程集合S={s（i，j）|s（i，j）>0}，并按照降序對集合S中的元素進行排序。

步驟3若S=Φ，則算法結束，否則依次查看集合S中的第一個客戶點是否滿足以下三個條件之一，若滿足其中之一則轉到步驟4，否則轉到步驟8。

（1）顧客點i和j都不在已確定的路線上。

（2）顧客點i和j有一個在已確定的路線上，一個不在已確定路線上，在已確定路線上的客戶點是該線路的起點或終點。

（3）客戶點i和j屬于已確定的不同路線，并且一個是線路中的第一個顧客點，另一個是線路中的最后一個顧客點。

步驟4計算連接客戶點i和j之后，判斷配送時間是否滿足約束條件，若滿足則轉到步驟5；否則轉到步驟8。

步驟5考察安排客戶點i和j 之后，線路上的配送車輛會不會超出載容量，若vij？燮Vk，則轉到步驟6，否則跳轉到步驟8。

步驟6把客戶點i和j安排到同一路線上。

步驟7將含有客戶點i和j的集合中的元素刪除。

步驟8若所有客戶點對都被考察，則轉至步驟9，否則轉至步驟3。

步驟9為該路徑安排容積最接近其貨物總量的車輛，更新可用車輛的信息。

步驟10若集合S為空集，則算法結束，否則跳轉至步驟3。

步驟11查看是否有遺留的客戶未被安排到路徑中，若有，則為其安排路徑，否則，結束算法。

4 模型求解結果分析

4.1 測試算例

為驗證模型及算法的有效性，使用真實案例中的數據來進行仿真實驗。算例中的車輛信息如表1所示，算例中的客戶數量為90個，本實驗在matlab R2016b平臺下進行，實驗所用計算機參數配置為Intel CoreTMi5-8250U CPU @ 1.60GHz 1.80GHz。

4.2 結果分析

對本文所提出算法的驗證和評價是將算法所得方案與原始方案進行比較，評價指標為：配送所用車輛數，平均裝載率和總配送成本。

經過10次仿真實驗，將實驗結果匯總在表2，分析發現，算法所得最優方案中的配送所用車輛數從8輛減少為6輛，車輛裝載率從53.9%提高到84.37%，提高了30.47%，總配送成本由3375.5降低為2245.71，減少了1129.79，且10次實驗的平均解與原始方案相比也有明顯的優化效果，裝載率平均提高29.85%，總配送成本平均減少1116.13，說明算法具有穩定性和有效性。

5 結束語

本文針對醫藥產品的配送問題，建立了以包括車輛的固定使用成本和基于里程的變動成本在內的總配送成本最小化為目標，同時求解車輛指派方案和車輛行駛路徑方案的數學模型，并使用節約里程法對該模型進行求解，最后以醫藥物流公司的實際情況為案例，對其配送方案進行優化。通過大量的仿真實驗，證明了所提出模型和算法的可行性和現實有效性。

參考文獻：

[1]Clarke G， Wright J W. Scheduling of Vehicles from a Central Depot to a Number of Delivery Points[J]. Operations Research， 1964，12（4）：568-581.

[2]葛顯龍，許茂增，王偉鑫.多車型車輛路徑問題的量子遺傳算法研究[J].中國管理科學，2013，21（01）：125-133.

[3]張錦，謝克明.蟻群算法在醫藥物品配送路徑優化中的應用[J].太原理工大學學報，2009，40（6）：600-603.