电子技术与软件工程
Electronic Technology & Software Engineering
数据库技术Database Technology
外卖配送最优路径模型设计
秦昕悦
（南京信息工程大学雷丁学院江苏省南京市210000 ）
摘 要：本文针对外卖订单的送餐人员数量优化以及路线规划问题做出了研究。运用并改进了模拟退火算法，并对其进行了改进，通
过引入波尔兹曼常数q，加快全局最优解收敛速度，提高计算效率，建立了动态规划、多变量优化等模型，并基于马尔可夫决策过程，提 出了关于未来订单配送策略的修正模型，优化配送路径，通过分析计算得出最短配送时间。
关键词：TSP 多变量最优化；模拟退火算法；动态规划MATLAB
1问题的提岀
1. 1问题背景
随着互联网的发展以及人们生活节奏的加快，越来越多的人选
择用手机APP 上的外卖平台购买外卖。由于外卖配送的特殊性， 订单能否准时送达直接关系到顾客的满意程度。如何合理高效地安
排配送路线及配送人员，对于提高商家的竞争力有重要意义。
1. 2问题描述
假设某外卖公司所在城市的路网由边长为500m 的正方形网格 构成，道路可双向行驶。派送员所在的公司位于城市正中心，且在
开始新的一天的工作前必须先去公司签到。派送员骑行速度为20
公里/小时，且最多同时派送两份外卖。此外约定，客户不对10
公里外的商户下单，所有外卖订单的备餐时间均为15mino
根据以上信息，建立模型解决以下问题：某送餐员从公司出发，
为其规划设计配送路线，配送人员要完成全部的123个配送任务， 需要的最短时间？
2问题分析
需要求完成全部订单的最短配送时间，可转化为最短路径
（TSP ）问题，需要为送餐员设计最短配送路线，使得在完成既定
任务的情况下，实现配送效率最高，配送时间最短。由于配送速度 恒定，优化目标转化为求距离的最小值。考虑到摩托车承载能力的
限制，将送餐员的配送路线分为如图1、图2两种情况。
本题为旅行商路径规划问题（TSP ），这里引入并改进了模拟退 火算法以解决此类复杂的NP 完全问题。该算法有较强的局部搜索 能力，程序运行时间短，且能保证最终结果逐步收敛于全局最优解，
比较两种配送路线下的最优解，取最小值为本题的最终解。
3模型假设
（1） 假设送餐员仅能沿正方形网格线行驶，且道路可双向行驶。（2） 假设外卖订单的备餐时间均为15分钟。
（3） 假设送餐员配送速度为20km/ho
（4） 假设问题二中所有订单在同一时刻下单。
（5） 假设忽略配送过程中的一些突发因素，如：用户失联、
临时交通管制、运输工具损坏、天气异常等等。
（6） 假设一个客户的订单只能由一辆车进行配送。（7） 假设不考虑配送员的个体差异性。4建模与求解
4. 1模型准备
为了便于后续建模，首先需要对附件中的参数做出转化，对坐 标的处理如下：
记A （x “yJ, B （x 2,y 2）为任意两点，d 为两点间的距离。由于配外卖订单量怎么提升
送员仅能沿网格线行驶（图3），则d= Ix.-XjHy.-y.lo
将123组商家和客户的坐标参数导入MATLAB，运用上述距 离函数其进行转化，得到一个246*246大小的矩阵，其中记录了商
图1
图2
家••商家，商家■用户，用户■用户，用户■商家的距离。
4.2模型的建立与求解
根据以上分析，问题可转化为求最短路径的TSP 问题，该类 问题用传统方法通常较难处理，本文引入模拟退火算法。该算法原
理简单且易于实现，有较强的适应性，它在搜索过程中引入随机因 素，使结果有一定的概率跳出局部最优解（图4的B 点），收敛全 局最优解（图4的C 点）。图3为距离示意图。
需要注意的是，模拟退火算法有一系列严格条件，如：需要较 高的初始温度，结束时温度需足够低，降温速度不能过快等。在算
法的迭代过程中，为了避免陷入局部最优，需要增强扰动规则的随
机性，对路径优化过程中所有可能的配送路线组合进行统计，很大 程度上增加了算法的运算量。这一系列因素造成了该算法的求解时 间较长⑴。
根据上述对算法的局限性分析，我们引入了波尔兹曼常数
q （q=1.3806488xl0-23）更新移动规则，从而缩短计算时间，提高运行 速度。
421基于模拟退火的路径优化算法⑵
（1） 取温度T 。，使T 。足够大，令T = T 0，记送餐员有k 条初 始配送路线，温度T 的迭代次数为L ；
（2） 对k 条初始配送路线执行步骤（3）〜（6）；
（3） 通过改变配送次序以扰动初始配送路线，记产生的新解 为k'；
（4） 记新解疋与初始配送路线k 的路线长度之差为增量
162
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论