时间窗约束下的快递车辆动态调度问题研究

摘要

快递是指快递企业使用陆运、空运等运输方式对客户货物进行快速投递的活动过程，是一种门对门的物流活动。国务院印发的《物流业发展中长期规划（2014-2020年）》中提到提高物流配送效率和专业化服务水平和完善一批快递转运中心，对快递行业的发展提出了新的要求。随着电子商务和快递行业的迅速发展，快递业务量大幅增长，为了提高客户满意度，城市转运中心需要对客户的动态需求做出快速反应。优化客户分区以及车辆调度对降低成本和提高客户满意度具有重大意义。本文以时间窗约束下的快递车辆动态调度问题为研究对象，使用Solomon启发式算法和改进K-means聚类算法，以及Matlab和Arc View GIS等研究工具，对是否采用“二程接驳”以及改进“二程接驳”的快递车辆动态调度模型进行了研究，主要研究工作及成果总结如下:
　　(1)综述了车辆调度问题。给出了车辆调度问题在国内外的研究现状，讨论了车辆调度问题的构成要素和分类，综述了求解车辆调度问题的现代启发式算法。
　　(2)研究了无接驳快递车辆动态调度问题。通过对快递企业的取送货现状进行提炼，构建无接驳快递车辆动态调度问题模型。在该问题中，所有车辆每天必须中途返回城市转运中心一次，卸载所收揽的快递件。车辆第二次返回城市转运中心的时间不得早于规定的最早返回时间。在构建该问题的数学模型基础上，采用Solomon插入启发式算法求解无接驳快递车辆动态调度问题。
　　(3)研究了基于“二程接驳”快递车辆动态调度问题。本文在前人研究的基础上，为了减少取送货车辆往返城市转运中心的次数，降低行驶路程，将“二程接驳”运用到快递车辆动态调度问题，构建了基于“二程接驳”快递车辆动态调度问题模型。在该问题中，所有取送货每天只需返回城市转运中心一次，且不能早于企业规定的最早返回时间;有一定数量的接驳车辆负责取送货车辆的接驳任务，接驳车辆返回城市转运中心的时间不得晚于规定的最晚返回时间。
　　(4)研究了改进“二程接驳”快递车辆动态调度问题。本文针对在基于“二程接驳”快递车辆动态调度问题模型中，接驳车辆每天闲置时间较长、使用率不高的情况，提出了改进“二程接驳”快递车辆动态调度问题模型。在该问题中，不再单独设置接驳车辆，从执行取送货的车辆中选取某几辆车执行接驳任务。
　　(5)研究了快递车辆动态调度问题的应用。根据W快递公司为本文研究所提供的实例数据，进行了无接驳、“二程接驳”和改进“二程接驳”三类快递车辆动态调度问题的应用研究。本文采用Solomon插入算法进行模型的求解。通过实例分析验证了本文提出的改进“二程接驳”快递车辆调度问题模型的有效性和应用价值。

目录

摘要

第1章 绪论

1．1 研究的背景和意义

1．2 国内外研究现状

1．3 对本文研究内容的界定

1．4 研究内容

1．5 论文框架结构

第2章 车辆调度问题及其启发式算法

2．1 车辆调度问题的一般描述

2．2 车辆路径问题构成要素

2．3 车辆调度问题的分类

2．4 车辆调度问题的启发式算法

2．4．1 经典启发式算法

2．4．2 智能启发式算法

2．5 本章小结

第3章 无接驳快递车辆动态调度问题

3．1 问题描述

3．2 求解策略

3．3 数学模型

3．3．1 初始快递车辆静态调度模型

3．3．2 快递车辆动态调度问题的数学模型

3．4 求解算法

3．4．1 客户点的聚类

3．4．2 Solomon的插入启发式算法

3．4．3 插入位置确定

3．4 本章小结

第4章 基于“二程接驳”及改进“二程接驳”快递车辆动态调度问题

4．1 基于“二程接驳”快递车辆动态调度问题

4．1．1 问题描述

4．1．2 求解策略

4．1．3 数学模型

4．1．4 求解算法

4．2 改进“二程接驳”车辆动态调度问题

4．2．1 问题描述

4．2．2 求解策略

4．2．3 数学模型

4．2．4 求解算法

4．3 本章小结

第5章 实证分析-W快递公司快递车辆动态调度优化

5．1 背景介绍

5．2 实例相关参数

5．2．1 客户编号及坐标数据

5．2．2 客户间距离

5．2．2 时间窗

5．2．3 行驶速度及服务时间

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．7 本章小结

第6章 总结与展望

6．1 论文的主要研究内容和研究结论

6．2 进一步研究展望

参考文献

附录1 部分核心代码

附录2 攻读硕士学位期间参与的项目

致谢

声明