城市快递服务的车辆路径规划问题研究

论文摘要

本研究的重点是城市快递递送服务的路径规划问题。在该问题中，存在两种类型的客户：其中一类客户需求固定，存在时间窗的限制；另外一类客户是否存在需求以及需求大小都存在随机性。快递服务中的服务车辆也存在两种类型，两种车辆在总容量以及单位成本上存在差别，并分别只能服务一种类型的客户。在中国的快递行业中，分别称呼使用这两种车辆的快递员为“骑兵”和“步兵”。该问题的一个重要特点是，其中“骑兵”在服务的过程中可以为“步兵”补充快件使其延长服务时间和扩大有效服务半径。不同车辆之间存在交接是当前快递服务中的一个新的服务模式，具有非常重要的价值。优化的目标是建立一个具有鲁棒性的服务策略，在实现总路径成本最小化的同时，保证每天服务路径的相似性，使相同的客户的每一次需求都由同一个快递员在相似的时间提供递送服务。本研究建立了两阶段优化策略，分别称为周期策略与日策略。为了实现规划路径相似以及服务每天随机性需求的双重目标，研究中引入了服务单元的概念。根据客户地理位置，通过聚类算法将客户归入一系列的服务单元，并将服务单元作为周期策略中路径规划的基本节点。同时，我们选择了以一些服务单元作为交接单元，并建立了不同类型车辆之间的交接策略。在周期策略中，通过优化获得固定的服务单元顺序以及交接单元访问顺序；通过日策略，根据每天的实际需求及时调整实际的服务路径，使每天路径最优。为了解大规模复杂问题，本研究提出了采用两阶段方法求解模型。最后，我们开发了仿真模型进行实验分析。通过实验分析了服务单元对于优化效果的影响；分析了交接策略的效果以及优化的效果。实验结果表明，我们的优化策略和算法可以有效解决快递服务路径规划问题。

论文目录

• 摘要
• Abstract
• 第1章 引言
• 1.1 研究背景
• 1.1.1 快递业的高速增长
• 1.1.2 更高的服务质量要求
• 1.1.3 特色的服务模式
• 1.1.4 新的研究方向
• 1.2 快递网络重要概念
• 1.2.1 客户
• 1.2.2 “骑兵”
• 1.2.3 “步兵”
• 1.2.4 快递服务相似性
• 1.3 研究内容
• 1.3.1 研究目标
• 1.3.2 研究思路
• 1.4 研究意义
• 第2章 文献综述
• 2.1 VRP 相关研究
• 2.2 快递服务优化研究
• 2.2.1 概述
• 2.2.2 基于地理分布特点的研究
• 第3章 数学模型
• 3.1 模型描述
• 3.1.1 问题描述
• 3.1.2 模型假设
• 3.1.3 服务单元以及交接单元
• 3.1.4 关键问题
• 3.2 环境参数
• 3.2.1 客户参数
• 3.2.2 车辆参数
• 3.2.3 其他参数
• 3.3 周期策略模型
• 3.3.1 目标函数
• 3.3.2 路径约束条件
• 3.3.3 时间约束条件
• 3.3.4 容量约束条件
• 3.3.5 相似性约束条件
• 3.4 日策略
• 3.4.1 “步兵”服务策略
• 3.4.2 “骑兵”服务策略
• 3.4.3 交接策略
• 第4章 算法实现
• 4.1 服务单元聚类
• 4.1.1 聚类要素
• 4.1.2 K-means 算法
• 4.1.3 改进的 K-means 算法
• 4.1.4 经常性客户与截断概率定义
• 4.1.5 服务单元时间确定
• 4.2 两阶段算法思路
• 4.3 第一阶段路径规划
• 4.4 交接单元确定
• 4.4.1 交接点选择
• 4.4.2 交接量确定
• 4.4.3 交接时间确定
• 4.5 第二阶段路径规划
• 第5章 实验设计和结果分析
• 5.1 实验设置
• 5.1.1 数据坐标
• 5.1.2 客户需求概率
• 5.1.3 时间窗
• 5.1.4 客户点载荷
• 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.4.3 交接时间分析
• 5.5 总路径分析
• 5.6 服务时间分析
• 第6章 总结与展望
• 6.1 研究总结
• 6.2 展望
• 参考文献
• 附录 A
• 附录 B
• 致谢
• 个人简历