基于改进Dijkstra算法的医药物流配送网络优化

罗威 张晓蓉 张甜

摘要：配送是医药物流的重要环节，时效性是衡量医药物流配送质量的一个重要标准。省时、省力的配送路径规划对提高医药物流配送时效性问题具有决定性作用。本文应用改进Dijkstra算法使其能遍历所有节点，并运用Matlab软件解决算法时间复杂度问题，在计算方法和搜索效率两个方面提高医药物流运作效率，以成都市医药物流配送案例加以论证和分析。改进后的Dijkstra算法将能运用于更多领域的配送路径规划问题的解决。

Abstract： Distribution is an important part of pharmaceutical logistics. Timeliness is an important criterion for measuring the quality of pharmaceutical logistics distribution. Time-saving and labor-saving distribution route planning plays a decisive role in improving the timeliness of pharmaceutical logistics distribution. In this paper， the improved Dijkstra algorithm is used to traverse all nodes， and Matlab software is used to solve the problem of time complexity of the algorithm. The efficiency of medical logistics operation is improved in both computational methods and search efficiency. The case of Chengdu pharmaceutical logistics distribution is demonstrated and analyzed. The improved Dijkstra algorithm will be applied to the solution of distribution path planning problems in more fields.

关键词：Dijkstra算法;医药物流;路径规划

Key words： Dijkstra algorithm;pharmaceutical logistics;path planning

中图分类号：F274                                        文献标识码：A                                  文章编号：1006-4311（2019）21-0121-02

0  引言

据相关数据显示，2017年我国人均卫生费用3712.2元并呈上升趋势。人民对健康生活的需求极大促进了医药行业的发展，但物流配送的时效性仍制约着行业更进一步。医药物流路径规划优化标准主要有最短距离、最少配送时间及最低配送费用等[1]。因此Dijkstra算法及其改进算法在医药物流配送路径规划的应用中凸显其重要性[2]。本文改进 Dijkstra 算法使得其遍历所有节点[3]并以成都市医药物流配送案例加以论证，最终利用Matlab软件求解。

1  Dijkstra算法的改进

1.1 传统Dijkstra算法的思路

Dijkstra算法是单源点的最短路径算法，其主要特点是以原点为中心向外逐步扩展，每次取最小距离直到扩展到终点找出最短距离位置[4]。它局限于一个节点到其余某一个点的最短路径，无法完成到多个点甚至遍历整个网络结构结点的求解。

1.2 改进的Dijkstra算法的设计

本文对Dijkstra算法进行改进设计时，解决了传统Dijkstra算法无法遍历所有节点的问题，并借助Matlab软件解决了算法的时间复杂度问题，主要从计算方法和搜索效率两个方面求解多节点配送的最短路径。具体算法步骤如图1。

①初始化。节点的标记为Vj，且起点V0=0。

②输入配送需求的医药物流节点，检测节点数量并判断已保存结果路线中是否包含输入节点，且在线路中是否连续。如果已保存线路中包含输入节点，且在线路中连续，输出结果;否则，执行下一步。

③运算Dijkstra算法计算当前节点到未计算节点时间权值，并取其最小值dijst（i），则最小总时间Dj=Dj+dijst（i），判断是否经过所有节点，如果没有，循环执行本步骤直至遍历所有节点，得到最短時间D1=Dj+Dj0（Dj0为返程最短时间）及路线[5]。

④判断节点数量是否大于2，如果是，则初始化数据，令Vj=V0，n=0逆向按照改进后的Dijkstra算法循环运算路线时间，得到逆向最短时间D2=Dj+Dj0及路线。

⑤判断并取值min（D1，D2）输出最终最短时间D及路线，保存路线以便下次访问。

2  改进的Dijkstra算法的应用

2.1 问题描述

成都市人口众多，医药卫生药品的需求巨大。医药冷链运输应用广泛，为响应节能环保的号召，采用新能源汽车——纯电力冷藏车运输药品，其运输成本与运输时间成正相关关系。因此采用改进后的Dijkstra算法根据节点间的时间权值求得最短时间路径在医药物流配送路径选择具有重大意义。本案例选取国控四川医药物流中心（V0）及8个周边区县级人民医院（双流区第一人民医院、天府新区人民医院、龙泉驿区第一人民医院、青羊区人民医院、锦江区人民医院、新都区人民医院、青白江区人民医院、郫都区人民医院，分别记为Vj，j=1，2，…，8）作为医药物流配送节点具有一定的代表性。

假定路面畅通，车速一定，且无天气等不可抗力因素影响的前提条件下，由国控四川医药物流中心使用纯电力冷藏车向8个区县级人民医院配送同种药物。

利用ArcGIS软件得出医药物流配送节点交通道路电子地图（如图2），其次利用Dijkstra算法和百度地图得出任意两个节点间的最短时间权值（如表1）。

2.2 结果及分析

利用物流节点间的时间权值，在Matlab软件环境下运行程序得出配送路线为D1：V0→V8→V6→V7→V5→V4→V2→V1→V3→V0，总运输时间为413min。

将V3作为第一个配送点，逆向运行程序得到D2：V0→V3→V5→V4→V6→V7→V8→V1→V2→V0，总运输时间为411min。

所以最终线路为国控四川医药物流中心→龙泉驿区第一人民医院→锦江区人民医院→青羊区人民医院→新都区人民医院→青白江区人民医院→郫都区人民医院→双流区第一人民医院→天府新区人民医院→国控四川医药物流中心（如图3）。

图中路线虽然有闭环回路，造成配送里程加长，但本文着重于运输时间的最短化，且运输成本与运输时间呈正相关关系，所以运输成本减少，为医药物流企业盈利提供一定的指导意义。同时，采用纯电动冷藏车配送药品契合可持续发展的目标。

3  结论

本文在以规划医药物流配送路径为目的，在处理多节点问题中提出了新的解决途径，即运用任意物流节点间的运输时间权值，在Matlab软件环境下运行程序以改进后的Dijkstra算法得出最短运输时间及运输路线，以达到减少运输成本，提高物流活动效率的目的。同时运用纯电力冷藏车配送符合綠色物流和可持续发展的要求，兼具经济效益和社会生态效益。

参考文献：

[1]苏永云，晏克非，黄翔，等.车辆导航系统的动态最优路径搜索方法研究[J].系统工程，2000，18（4）：32-37.

[2]彭定旭，冀肖榆.Dijkstra算法的java实现方式及优化[J].黑龙江科技信息，2017（4）：166-167.

[3]韩海玲.基于城市路网的最短路径算法研究与应用[D].山西：中北大学，2017.

[4]石晓达，孙连英，葛娜.应急资源配送中Dijkstra改进算法的研究[J].北京联合大学学报，2018，32（4）：61-66.

[5]李擎，宋顶立，张双江，等.两种改进的最优路径规划算法[J].北京科技大学学报，2005，27（3）：367-370.