基于遗传算法的多目标外卖路径规划

龚艺冉　金超　侯明明

摘要：本文针对外卖配送服务的车辆调度问题，根据外卖配送服务建立了路径最短的带时间窗约束的车辆路径模型，利用遗传算法对模型进行求解，以国内某外卖商家实际数据进行了仿真实验，通过对实验结果分析，验证了算法的合理性和有效性。该方法也适用于不同外卖配送模式下的车辆调度。

[关键词]外卖配送 路径规划 遗传算法 时间窗

1绪论

1.1研究背景

前瞻产业研究院发布的《中国在线外卖商业模式与投资战略规划分析报告》统计数据显示，2015-2018年中国在线外卖收入年均增速约为117.5%，是传统餐饮业的12.1倍，我国在线外卖收入从2015的458亿元增长至2018年的4712亿元左右，占全国餐饮业收入比重从1.4%提高到10.6%。

随着外卖逐渐普及，问题也随之涌现。作为主要消费群体的白领阶层和学生对服务体验的要求较高，而配送慢是他们对外卖服务最为直观的感受。从商家的角度看，外卖配送也是最棘手的问题。

现如今主要存在三种配送模式，各配送模式提供方不同、服务人群与范围不同，各自的作用也不同。

自运营配送模式：商家在接到顾客订单后，由商家自身员工或是商家招聘的兼职人员负责外卖的配送，外卖平台只负责线上整合商家信息。

合作加盟配送模式：由于存在商家的自营外卖配送模式不能满足顾客需求的情况，外卖平台则会根据具体情况与第三方物流配送团队进行合作加盟，为这些商家提供物流支持。

众包物流配送模式：每一个自愿兼职且通过考核认证的个人都可以成为外卖配送员，也就是现在的“骑手”。这种模式通过利用社会的零散人力能够有效的整合资源，使得人力资源成本大大降低，即使在送餐高峰期，也有充足的人力满足外卖的配送，外卖平台也不必增加额外的运营成本。但外卖平台对这一模式的配送环节无法进行实施监控，骑手会因个人原因导致配送出错、配送不及时、服务质量差等一系列问题。

本文以众包物流配送模式作为研究对象，基于物流路径规划提出以遗传算法提高配送速度的配送方案，借以提高用户用餐体验，实现商家与用户的双赢。

1.2国内外现状分析

1.2.1国外现状分析

以国外外卖020标杆的Grub Hub为例，Grub Hub在模式上两头兼顾，在发展客户服务的同时也为商家提供优质可靠的服务。面向用户的终端，Grub Hub实现了标准化服务，规范有序忙而不乱，并提供TrackYourGrub，使得用户能够在终端直观监测外卖的配送情况，这一点国内外卖平台设计中值得借鉴。面向商家，Grub Hub商家系统提供商户统计、安排订单等基础服务，还提供了对订单数、利润率、重复订餐率等数据进行综合分析为商家提出相应合理的调整建议功能，这吸引了美国市场份额超过6成的个体餐厅加入Grub Hub。

1.2.2国内现状分析

对于国内外卖市场而言，小餐饮商家和品牌餐饮几乎囊括整个外卖市场，而两者面向消费者的意愿存在较大差异，使得比较成熟的轻模式平台都在向轻重结合的混合模式转变。大部分商家会选择加入多家第三方外卖平台，但问题出现了，不同平台有不同的配送解决方案，甚至有的第三方平台并未提供配送解决方案，这样从一台打印机中出来的订单得按照平台不同区分开来给不同平台配送团队，而未提供配送解决方案平台的订单配送还要自己消化，繁琐至极，极易出乱。

总的来说，在配送方面，较为成熟的第三方O2O外卖平台都在发展自己的配送业务，但由于存在内部竞争关系使得对于整个外卖配送环节的高度整合难以实现。此外，我国消费者普遍付费意识比较差，消费者对有偿配送服务收取佣金的接受程度很低，使得商家在配送环节的花费的成本居高不下。开发一套整合配送服务增加客户体验降低配送成本的解决方案显得尤为重要。

国内王荃菲[1]重点研究了针对城市复杂路况的外卖配送路径的优化问题。楚尚轩[2]研究了外卖和快递共同配送的问题。沙小卜[3]对外卖配送网络进行了研究。

本文将基于遗传算法，针对“众包”配送模式提出一种路径优化方法，并且使得各外卖平台配送方案不统一问题得到解决。

2问题描述和数学模型

2.1模型假设

外卖配送的实际运行是一个复杂的过程，受诸多因素影响，为了建立调度模型，本文做如”下假设。

（1）外卖配送更多的是服务特殊群体，所以本文认为外卖配送是一种预约型配送，即在进行调度安排前，已经获取了所有顾客的地理信息。

（2）在实际运行中，顾客的出行分布具有很强的时空特征，但本文更注重方法论的介绍。所以，假设服务区域内的顾客地理位置分布在时间和空间上都服从均匀分布。

（3）外卖配送车辆的调度与路网条件息息相关，为了简化模型以及便于说明设计思路，忽略路网对调度的影响。Quadrifogli等已经证明“对角”路径能够反映车辆真实的运行情况。本文假设车辆按“对角"路径运行，即车辆只能沿水平或垂直方向运行。

（4）可配送车辆常用于低密度区域，顾客购买总量小，所以为了简化模型不考虑车辆的容量约束。

2.2模型建立

外卖配送的车辆调度是在确定总的配送计划之后，根据顾客的位置信息，解决“每个车次服务哪些顾客，怎么配送”的问题。外卖配送从运营者和顾客角度出发建立双层规划模型，运营者希望在投入下能够服务更多的顾客，顾客则希望送达的时间越短越好。

假如有一个取餐地点以及送餐地点n，配送车辆每经过一段距离的配送成本c，取餐地点和送餐地点距离d;能够参与配送的车辆数量为m，把表示取餐地点的这个点当作0點，送餐地点当作1，2，…，n，定义变量为：

在表示目标函数的公式（2）中，其结果代表外卖配送车辆从起始点到最终的目的地所花销的总成本。利用公式（3），公式（4）和公式（5）让不同地点的顾客至少有一辆车前往配送，公式（6）是指外卖配送车辆在配送的过程中总的花费时间小于限制时间。