第三方配送带软时间窗车辆路径问题的模型与禁忌算法研究

摘要

随着电子商务经济的蓬勃发展，物流产业开始逐步升级，物流活动在企业所有的生产经营活动中所呈现出来的重要性越来越明显。然而社会物流成本逐年攀升居高不下，特别是其中的运输配送成本，占着极大的比重。对车辆路径问题的研究有助于提高企业的运行效率、降低企业的物流成本。以往对车辆路径问题的研究侧重于考虑某个求解问题，而对现实的配送模式考虑略有欠缺。目前，物流运输配送的模式主要包括自营配送、第三方配送和共同配送，其中以第三方配送模式最为常见。此外，用户对企业的配送服务要求也越来越多，特别是软时间窗要求。因此，研究第三方配送下带软时间窗的车辆路径问题更具有现实意义。
　　本文尝试研究在第三方配送下带软时间窗的车辆路径问题，既考虑了第三方配送的多配送中心特征，又考虑了用户的软时间窗要求。在分析目前物流配送的发展背景、第三方配送特点和运作模式、用户的软时间窗特点、车辆路径问题的要素和分类及国内外关于带软时间窗的车辆路径问题的研究的基础上，提出了该问题的数学模型，并构造了禁忌搜索算法求解该问题，最后使用实验分析的方法比较了带软时间窗问题与不带软时间窗问题的结果区别，不同算法的结果比较。本文的主要内容和创新成果如下：
　　（1）本文介绍了目前物流配送的发展背景，引出第三方配送背景下的具有软时间窗的车辆路径问题。对第三方配送和车辆路径问题进行了详细介绍，分析了各自的特征和分类。在详细描述第三方配送背景下的带软时间窗车辆路径问题的基础上，系统的分析和总结了国内外关于带软时间窗车辆路径问题的研究方向、研究方法和最主要的研究成果。
　　（2）对求解第三方配送带软时间窗车辆路径问题的算法（精确算法和近似算法）进行了简单介绍，着重介绍了本文将使用的禁忌搜索算法的基本思想、构成要素和基本过程。
　　（3）研究了第三方配送带软时间窗车辆路径问题的模型及求解思路
　　考虑第三方配送下多配送中心和多车型的特点以及待服务用户软时间窗特征，根据问题的约束条件，设立配送中心最少、等待时间和迟到时间总和最少的双目标，目标通过权重参数设置权重。然后根据约束条件和目标，建立多下标变量的混合整数规划数学模型。
　　考虑该模型是带多配送中心特征的，本文设计了最近距离分配原则的求解策略，将其转化为具有多个单配送中心特征的问题，而不是进行统一的路径分配。
　　（4）研究了第三方配送带软时间窗车辆路径问题的禁忌搜索算法
　　本文为转化成多个单配送中心的带软时间窗车辆问题设计了禁忌搜索算法，该算法利用用户直接排列的编码方式，将生成的初始解带入约束判断是否满足约束来计算评价值。这使得一种编码方式其对应所需派出的车辆可能有多辆，这与确定了车辆数量的编码方式及采用罚函数法的求解方式相比，大大提高了得到最优解的概率。
　　（4）实验分析
　　本文利用相关文献中关于软时间窗车辆路径问题的实验数据，对本文所设计的禁忌搜索算法进行了matlab编程实验计算，并与相关文献进行了结果上的比较。通过带软时间窗和非带软时间窗的算法结果比较，说明本文说设计的算法不仅能在精度上有所提高，而且满足了用户的软时间窗需求，从而提高了用户的满意度；通过使用最近距离分配然后再进行禁忌算法求解与直接进行禁忌搜索算法求解的比较，说明采用最近距离分配原则不仅减少了总行程数，而且使运行速度有所提升。

目录

封面

声明

中文摘要

英文摘要

目录

1 导论

1.1 研究背景

1.2 问题提出

1.3 主要研究内容、意义和创新点

1.4 研究技术路线

2 第三方配送及车辆路径问题文献综述

2.1 第三方配送

2.2 第三方配送车辆路径问题的描述及分类

2.3 第三方配送带软时间窗车辆路径问题的描述及研究综述

3 第三方配送带软时间窗车辆路径问题的算法知识

3.1 精确算法

3.2 近似算法

3.3 禁忌搜索算法

4 第三方配送带软时间窗车辆路径问题的模型研究与求解思路

4.1 第三方配送带软时间窗车辆路径问题的特征和约束条件

4.2 第三方配送多配送中心带软时间窗车辆路径问题的模型

4.3 模型的求解思路：多配送中心特征转化为单配送中心特征

4.4 第三方配送单配送中心带软时间窗车辆路径问题的模型

5 第三方配送带软时间窗车辆路径问题的禁忌搜索算法研究

5.1 配送车辆数量的确定

5.2 禁忌搜索算法的设计与实现

5.3 求解第三方配送带软时间窗车辆路径问题的步骤

6 第三方配送车辆路径问题的实验计算与结果分析

6.1 实验案例描述

6.2 实验计算

6.3 结果分析与比较

7 结论与展望

7.1 研究结论

7.2 本文的贡献点

7.3 本文的不足和未来的研究方向

致谢

参考文献

附 录1

附 录2