藥品多車型配送的車輛指派與路徑優(yōu)化研究

劉閃

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

關(guān)鍵詞：醫(yī)藥物流；多車型車輛路徑問題；節(jié)約里程法

中圖分類號：F252 文獻標(biāo)志碼：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 概述

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

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

2.1 模型假設(shè)與約束條件

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

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

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

3 求解方法

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

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

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

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

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

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

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

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

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

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

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

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

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

步驟10若集合S為空集，則算法結(jié)束，否則跳轉(zhuǎn)至步驟3。

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

4 模型求解結(jié)果分析

4.1 測試算例

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

4.2 結(jié)果分析

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

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

5 結(jié)束語

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

參考文獻：

[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].中國管理科學(xué)，2013，21（01）：125-133.

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