药品多车型配送的车辆指派与路径优化研究

刘闪

摘 要：针对医药产品所具有的体积小、重量轻、生命周期短等特点以及多车型配送现状，文章研究带有最后时间限制的多车型指派和配送路径集成优化问题，建立了以配送成本最低为目标函数的整数规划模型，同时使用节约里程法进行求解，并应用实际数据来验证模型和算法的有效性。

关键词：医药物流；多车型车辆路径问题；节约里程法

中图分类号：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.