内容发布更新时间 : 2024/5/10 8:00:57星期一 下面是文章的全部内容请认真阅读。

龙源期刊网 http://www.qikan.com.cn

基于最优路径算法的快餐配送路径优化问题研究

作者：柯小波

来源：《科技创新与应用》2013年第08期

摘 要：随着快餐业的迅速发展，对快餐业中快餐配送问题的算法研究就愈发重要，快餐的配送问题，本质上就是最优路径问题，现在分析一种最优路径算法的基础上，结合快餐配送的诸多影响因子，对算法进行了优化。 关键词：最优路径算法，快餐配送；研究 1 引言

最优路径算法是GIS在路径分析中最常用的算法之一。车载导航系统、智慧交通系统等都离不开最优路径算法的应用。[1]而在快餐业配送过程中，由于行业的特殊性及配送物品的特殊性，使得其在具有一般配送的特点同时，又具有自身特点。涉及到配送路径方面的问题主要体现在以下几个方面：（1）快餐配送对时间极为敏感。由于客户对快餐的需求都相对较急迫，且快餐本身的食物特性所带来的保温要求，使得快餐的配送要求非常迅速的将食物送达到；（2）点餐客户位置的特殊性。如点餐客户在某个小区的某楼层内，这就要求不能将小区作为点餐点处理，而要以小区门作为关注点，考量从小区门到该客户所在楼房及楼层的距离；（3）快餐配送受时间区段、配送工具、区域交通状况、天气状况等情况的影响。

目前传统的最优路径算法通常将路网模型理想化处理，实用性教差。较少考虑实际行驶过程中的道路属性，如道路限速、红绿灯、道路等级[2]、道路阻值、交通工具限制等。或者考虑不够全面。

2 最优路径算法优化研究 2.1 传统最优路径算法的优化

在按标记法[3]实现Dijkstra 算法的过程中，核心步骤就是从未标记的点中选择一个权值最小的弧段。这是一个循环比较的过程， 如果不采用任何技巧，未标记点将以无序的形式存放在一个链表或数组中。那么要选择一个权值最小的弧段就必须把所有的点都扫描一遍，在大数据量的情况下，这无疑是一个制约计算速度的瓶颈。要解决这个问题，最有效的做法就是将这些要扫描的点按其所在边的权值进行顺序排列，这样每循环一次即可取到符合条件的点，可大大提高算法的执行效率。

2.2 在快餐配送过程中，影响最优路径算法的道路因子[1]

龙源期刊网 http://www.qikan.com.cn

影响路径分析的交通影响因子很多，但是各类因子对计算结果的影响程度是各不相同的，有的只是对道路权值的影响；有的则会改变路径分析过程中路径的行进方向，可分类如下： 2.2.1 影响道路阻值的影响因子。这类因子只会影响道路的权值属性，不会改变路径的连通性，也不会改变路径分析过程中的物体的进行方向，如红绿灯、道路等级、限速[4]、道路阻值等。这类信息可以直接在原始路网模型的基础上进行考量。

若以实际行驶速度为考量单位，下面是只考虑道路等级因素和障碍物因素的算法：[3] V，实际行驶速度；T，选择使用的交通工具；g，经过道路的等级；d，经过道路的长度；t，N分钟商圈（N分钟商圈就是指乘坐某种交通工具，如电动车，以到达某地所需的某个具体时间为标准，这里取N分钟，所形成的一个凸包多边形）；t'，行驶中遇到障碍物的等待时间（如红绿灯）。其中d值通过Dijkstra 算法算出。

2.2.2 影响路网连通性的影响因子。这类因子可直接改变原有路网模型的连通性，会改变路径分析过程中 的进行方向，如单双行线、交通工具限制、斑马线天桥、道路转向等。这些因子需要将其作为路网模型的一部分然后重新建立路网模型。

2.2.3 订餐区域的影响因子。这些因子会影响到达目前大致区域后到达顾客手上这个过程的时间，以小区为例，需要考虑的小区参数：大门口到道路的距离、小区大门口到楼宇质心点的距离，该距离可以预先分派到道路节点上、小区大门到道路的通行情况。

小区道路映射预处理过程：（a）以小区大门为圆心，半径不断迭代增大形成缓冲区，直至与路网相交；（b）搜索缓冲区与路网相交的道路，判断小区大门到该道路是否可达；（c）对于可达的道路，计算其与小区大门距离，取其距离最短的连接点作为小区道路映射点。（d）计算的距离。

另外，为了提高系统的性能，对两两小区质心点间的路径、路径距离、通行时间，调用路网分析算法进行预先计算，结果存储在表中。 3 实际应用分析

在快餐配送的实际应用过程中，通常不单要求计算从店铺到顾客点餐地点的最优路径，还需要根据该店的辐射范围，提前计算出该店的多分钟商圈的范围，如某快餐店将自己所辐射的区域提前划分为5分钟商圈、10分钟商圈，然后可自动根据顾客来电判断处于哪个商圈范围内[5]，这样可以方便统一分配配送任务并可及时准确通知客户所需等待的时间。 N分钟商圈的算法步骤主要为：

（1）划定理想商圈范围。以该店面为圆心，以N分钟行驶距离为半径R画圆，即为理想商圈范围。公式为：R=V*T（V由选择的交通工具类别决定）。

龙源期刊网 http://www.qikan.com.cn

（2）搜索映射点和nodes（道路节点），搜索出所有的小区道路映射点和nodes。 （3）计算最优路径。遍历道路上的nodes，计算机会点到各nodes的最优路径。 i.逐个判断node到机会点的最短距离是否在N分钟行驶距离范围内；Yes则保留，No则舍弃。再根据N分钟行驶距离求出路径上的极值nodes。

ii.考虑实际行驶过程道路参数、小区参数，对nodes再次筛选。并再次计算N分钟行驶距离的极值nodes。

（4）将保留的点做最小覆盖多边形，得到N分钟商圈范围。

（5）对N分钟商圈进行修正。对于位于商圈边界附件的小区，只要小区和N分钟商圈范围相交，就将该小区包含于商圈之中。 4 结束语

本文基于最优路径算法，设计了在快餐业配送过程中最佳送餐路径问题，并且通过该算法的研究，进一步利用最佳送餐路径算法应用于订餐送餐服务，提升了快餐业的服务质量和工作效率。由于送餐路径问题是一个非常复杂的问题，甚至行业内的不同市场定位的快餐企业所考虑的因素都不会完全相同，所以，本文只能结合送餐服务的通用特点，设计了与送餐相关的影响因子，使其与实际结合更加密切。 参考文献

[1]魏海平，等.顾及交通时态属性的最优路径算法与实现[J].测绘学院学报，2004，21（3）：69-72.

[2]陈玉敏，等.多级道路的最优路径算法研究[J].武汉大学学报.信息科学版，2006，25（1）：70-73.

[3]吴正明，等.基于实时交通最优路径算法的研究[J].机械与电子，2001，（10）：20-22. [4]王丰元，等.基于交通限制的路网最优路径算法[J].交通运输工程学报，2005，5（1）：92-95.

[5]廖秋敏，等.GIS支持下的零售商圈分析研究[J].科技情报开发与经济，2004，14（11）：169-170.