基于众包模式的外卖配送路径优化研究

摘要

近年国内外卖市场规模持续扩张吸引大量众包配送员从事外卖配送服务。外卖配送服务既是众包配送员的直接收益来源，也是影响外卖服务质量的关键因素。因此，如何规划外卖配送路径，以保障外卖配送服务质量、提升众包配送员效益己成为一个重要的管理决策问题。同时如何设计在有限时间内实现问题求解的算法也是一个热门研究方向。故本文聚焦众包模式下外卖配送问题，开展外卖配送路径优化及突发性事件应急管理研究。 众包外卖配送路径优化问题具有开放式、取送货、餐馆客户配对有序的特征，同时因配送货物的异质性又具备多配送中心、各点多次访问的特性，加上众包抢单、派单两种模式拥有不同的配送流程，增大了问题求解难度。针对该问题，本文以配送员配送收益与客户满意度最大化为目标，通过建立虚拟点简化配送访问方式，分别构建出具有软时间窗与有序取送货约束的优化模型。考虑到模型的复杂性与众包抢单、派单模式各自的特性，对遗传算法与蚁群算法进行了改进。对于遗传算法，构造染色体编码方式、设计保序交叉操作与双点变异操作，完成对配对有序数据的处理:对于蚁群算法，设计蚂蚁队，以队中各蚂蚁的行为形成外卖任务分派与路径规划方案，用多队蚂蚁行为构成蚁群行为，以蚁群群体行为实现优化求解功能。以此分别完成两种模式下问题的求解。算例分析以及与传统集货配送、单批配送的对比分析表明，模型与遗传算法、蚁群算法有效地优化了众包抢单、派单模式下外卖配送路径，并得出配送速度在达到一定数值后对配送结果的影响较小，载货量对配送结果无显著影响的结论，辅助了外卖配送管理。针对三种突发性事件对优化模型与求解算法予以修正，实现了对外卖配送的应急管理。 本文在对众包模式下外卖配送路径优化问题的研究中，构建出适应各点配对有序、配对任务分派的优化模型，并改进遗传算法与蚁群算法，实现问题求解。这不仅解决了现实众包外卖配送路径优化问题，保障了众包配送员与客户利益，支撑了外卖配送管理，还为与众包模式外卖配送相似的带时间窗多次访问配对有序取送货多车型开放式多配送中心车辆路径问题的研究提供了借鉴与参考。

目录

声明

1 绪论

1.1 研究背景

1.2 研究目的与意义

1.3 国内外研究现状及分析

1.3.1 国内外研究现状

1.3.2 国内外文献综述

1.4 研究内容与方法

1.5 技术路线

1.6 本章小结

2 理论综述

2.1 众包模式外卖配送概述

2.1.1众包抢单外卖配送模式

2.1.2众包派单外卖配送模式

2.2 配送路径优化典型问题概述

2.2.1带能力约束的配送路径问题

2.2.2 带时间窗的配送路径问题

2.2.3多配送中心配送路径问题

2.2.4带取送货的配送路径问题

2.3 配送路径优化典型算法概述

2.3.1传统精确优化算法

2.3.2现代启发式优化算法

2.4 本章小结

3 众包抢单模式下外卖配送路径优化研究

3.1 抢单模式下外卖配送问题分析

3.2 抢单模式下外卖配送情景基础假设

3.3 抢单模式下外卖配送问题数学表述

3.3.1 抢单模式下外卖配送结点虚拟化处理

3.3.2抢单模式下外卖配送流程网络图构建

3.4 抢单模式下外卖配送路径优化数学模型构建

3.4.1目标函数构建

3.4.2 约束函数构建

3.5 抢单模式下外卖配送路径优化的遗传算法设计与改进

3.5.1染色体编码设计

3.5.2染色体遗传改进

3.5.3遗传算法终止条件设计

3.5.4遗传算法流程构建

3.6 抢单模式下外卖配送路径优化算例分析

3.6.1 算例描述

3.6.2 算例分析

3.6.3 对比分析

3.7 本章小结

4 众包派单模式下外卖配送路径优化研究

4.1 派单模式下外卖配送问题分析

4.2 派单模式下外卖配送情景基础假设

4.3 派单模式下外卖配送问题数学表述

4.3.1 派单模式下外卖配送结点虚拟化处理

4.3.2派单模式下外卖配送流程网络图构建

4.4 派单模式下外卖配送路径优化数学模型构建

4.4.1目标函数构建

4.4.2 约束函数构建

4.5 派单模式下外卖配送路径优化的蚁群算法设计与改进

4.5.1蚁群算法改进

4.5.2蚁群算法全局寻优优化

4.5.3蚁群算法终止条件设计

4.5.4蚁群算法流程构建

4.6 派单模式下外卖配送路径优化算例分析

4.6.1算例描述

4.6.2算例分析

4.6.3 对比分析

4.7 本章小结

5 突发性事件下的优化模型与求解算法修正

5.1 突发性事件分析

5.2 路径阻塞事件处理

5.2.1 路径阻塞事件情景分析

5.2.2众包外卖配送路径优化模型修正

5.3 配送车辆故障事件处理

5.3.1 配送车辆故障事件情景分析

5.3.2众包外卖配送路径优化模型修正

5.4 配送任务追加事件处理

5.4.1 配送任务追加事件情景分析

5.4.2众包外卖配送路径优化模型修正

5.5 众包外卖配送路径优化算法调整

5.5.1 众包抢单模式下外卖配送路径优化遗传算法调整

5.5.2众包派单模式下外卖配送路径优化蚁群算法调整

5.6 算例分析

5.6.1路径阻塞事件算例分析

5.6.2 配送车辆故障事件算例分析

5.6.3 配送任务追加事件算例分析

5.7 本章小结

6 结论与展望

6.1 结论

6.2 展望

致谢

参考文献

附录1 遗传算法核心代码

附录2 蚁群算法核心代码

攻读硕士学位期间主要研究成果