1 张钰涵 李佳瑜 2 李鑫月
1 华北理工大学 管理学院
2 河北经贸大学 管理科学与工程学院 063210
摘要：网上购物的日益普及使消费者们对于快递物流的要求不断提高，这一趋势生出了关于快递配送的路线选择问题，如何规划路线从而使得耗费时间最少、路径最短成为待解决的问题模型。本文关于配送路径的规划提出了两个解答方法，即Dijkstra方法和Lingo模型。类似快递配送的路线规划的问题也普遍存在于现实生活中，而使用Dijkstra方法和Lingo模型可以便捷地解决这类问题。
关键词：最短路径；Dijkstra；Lingo；快递配送
一、前言
伴随着人们物质精神水平的不断提高以及互联网技术应用的飞速发展，在当今社会中，网上购物已经逐渐成为人们日常消费的主要手段之一，人们足不出户就能浏览店家、挑选心仪的商品、货比三家、下单购物。这种相比传统的实体店购物方式更为便捷的网络购物方式，也催生了一大批相关产业的发展，比如物流、快递。
尤其在前段时期的新冠疫情爆发、扩散、情势严峻的时期，由于所居住的村庄、居民区的全方位封闭隔离，以及对人与人之间的近距离接触的杜绝，人们对于日常生存、生活用品的需求只能通过从网上的渠道购得。这使大家对物流快递公司的要求也越来越高。快递公司出于节省时间、提高效率进而节约成本、满足客户要求的迫切需求，不得不面临着优化派送路线的问题。
二、对快递派送路径问题的提出
消费者们拍下消费订单后，除了对商家货物质量优劣的关注外，最大的担忧便是快递派送的问题。这家快递公司的物流配送速度快不快？物流信息的更新及不及时？配送过程的安全保障怎么样？如果因为市场问题而发生货物的损毁灭失谁来向我承担损害赔偿？公司的配送效率高不高？快递工具是火车还是飞机？到达我市后市内的配送路线是什么样的？我的货物会被优先配送吗？消费者与快递公司间的信任关系常常受到一系列类似以上的问题的挑战。
就我本人的真实经历来说，某天上午8点钟物流信息显示包裹到达了我们市里并且正在派送中，按惯例一般1小时左右就能到达快递驿站，而我却一直等到傍晚都依然没有接收到包裹到达的消息通知。当我向快递员打电话询问后才被告知：送件的顺序还没有轮到我所居住的小区。最终那件包裹在临近驿站工作人员下班时间才到达驿站。这件事引发了我对我们市的快递员派送货物路线的思考。我不得不提出疑问：快递员派送货物时制定的路线是否科学而高效？
三、最短路问题Dijkstra模型解法
为研究上述的问题，我制作了一个模型并尝试运用运筹学所学的知识来分析、完善快递配送路径的规划。
假设某快递员当日的派送目的地为v6，而快递公司即出发点为v1，那么如何用Dijkstra来规划出快递员去目的地的最短路线呢？
以图1为示例，基本步骤如下：
(1)首先，将起点标号为[0,1]，即计算起点到起点的最短路长是0。
最短路长为70。
四、用lingo求解快递配送模型
上述示例求起点到终点的最短路径我们可以用Dijkstra方法很简单地解决，但现实生活中是问题往往更为复杂。若可选择的经过地更多、可选择的路径也更多的话，不妨使用lingo模型，求解过程更加简洁准确。
以下图为问题模型，假设v1为快递公司即出发点，v7为目的地，各个地点的距离如图标识，求解最短路径。
采用0-1法，引入决策变量X，当X=1，则表示最短路径经过该顶点；若X=0，则起点到终点的最优路径不经过该顶点。
若X=1，同时也代表指向该点的某条线路是最短路径的一部分，且从该点出发的某条线路也是最短路径的一部分。
若X=0，则无论是到达该点还是从该点出发的路线，都不是最短路径的一部分。
由此得出目标函数：
使用lingo对题目进行求解，
1、lingo代码
代码如下：
MODEL：
SETS:
CITIES/1,2,3,4,5,6, 7/;
ROADS(CITIES, CITIES)/1,2 1,3 2,4 2,5 3,2 3,4 3,6 4,5 4,6 4,7 5,7 6, 7/:W, X;
ENDSETS
DATA:
W=796542521475;
ENDDATA
N=@SIZE(CITIES);
MIN=@SUM(ROADS:W*X);
@FOR(CITIES(I)|I #GT# 1 #AND# I #LT# N:
@SUM(ROADS(I,J):X(I,J))=@SUM(ROADS(J,I):X(J,I)));
@SUM(ROADS(I,J)|I #EQ# 1:X(I,J))=1;
@SUM(ROADS(I,J)|J #EQ# N:X(I,J))=l;
END
2、运行结果
如截图所示：
根据lingo的结果可知：
，即最短路径为
。
五、总结
对于生活中快递员派送路线的问题，使用Dijkstra方法可以解决简单的、小规模的最短路问题，而使用lingo解决复杂的最短路径问题十分简捷易操作。Lingo软件无论是对于线性规划问题还是非线性规划问题，都能顺利解决，方便且准确。
作为网络优化问题重要部分之一的最短路问题，在现实生活中随处可见，且应用广泛，学会应用Dijkstra和lingo的方法，可以有效解决生活中的类似困难，不只局限于快递配送问题。将规划路线的问题与运筹学模型相结合，为项目的时间和运输成本都能提供合理的思路和办法，对现实生活也将会有极大的借鉴和帮助。
参考文献
[1]张波良,张瑞昌,关佶红.道路网上最短路径算法综述[J].计算机应用与软件,2014(10):7-15.
[2]熊文涛,肖应雄.LINGO软件在目标规划实验教学中的应用[J].新疆师范大学学报(自然科学版),2019,38(01):70-74.
[3]陈允峰.利用lingo软件解决最短路问题的两种方法[J].信息技术与信息化,2015,000(010):141-142.
[4]刘淋，多目标问题规划的若干解法及Lingo实现.福建船政交通职业学院，2011.11，第10卷第6期，P20-P22
[5]申婵,崔洪军.基于可靠性最短路的实时定制公交线路优化研究[J].交通运输系统工程与信息,2019.