网络中供需匹配与多批次取送货车辆路径问题研究

摘要

本论文研究了供需匹配与多批次取送货车辆路径问题。在此问题中，客户点之间的供需匹配关系事先未知；每个客户点的取货请求和送货请求允许通过多次访问该客户点来分批次满足；需做供需匹配决策和车辆路径决策。此问题是经典车辆路径问题的一种复杂衍生体，普遍存在于国际原油运输、烟草制造行业中的生产原料调拨、零售行业中的商品库存重新布局及共享单车系统中的自行车重新分配等网络中。基于此问题高度复杂且受到的关注较少，本文分别从模型建立、启发式算法求解和精确算法求解的角度对此问题进行深入研究。本文的主要研究成果呈现如下：
　　（1）本文所研究的问题包含了两个相互影响的决策：供需匹配和车辆路径。先建立一个混合整数线性规划模型作为基础模型。然后，通过消除两个决策变量之间的耦合关系，提出一个新颖的单元化模型。紧接着，提出一系列多项式型有效不等式来加强单元化模型。实验结果表明，单元化模型比基础模型更容易求解，且所提出的有效不等式显著地提高了单元化模型的性能。最后，验证了所提出的模型和不等式对文献中相关问题的有效性。
　　（2）为快速求解现实中的较大规模的问题，基于所提出的单元化模型，先设计一个贪婪式算法来构建初始解。然后，基于优化供需匹配决策和车辆路径决策的思想，提出7个高效的邻域结构。紧接着，提出一个禁忌搜索算法来改善初始解的质量。为验证该算法的效果，借助于CPLEX设计求解问题下界的方法。实验结果表明，本文所提出的禁忌搜索算法在较短时间内能够对本文所研究的问题提供高质量的解。最后，验证了本文所提出的启发式算法求解文献中相关问题的良好表现及明显优势。
　　（3）基于前面所提出的单元化模型及多项式型有效不等式，先提出6类指数型有效不等式。然后针对每类不等式设计相应的分离算法。紧接着，基于讨论寻找初始上界方法、预处理过程、分支策略及分离算法调用策略；提出一个分支切割算法。实验结果表明，此算法能够求解9个客户点、5种产品的算例，这些算例的规模大于。

目录

声明

1 绪论

1.1 选题背景

1.2 研究目的与意义

1.3 研究方法与技术路线

1.4 论文总体结构与主要内容

1.5 主要创新点

2 国内外相关研究现状

2.1 多批次取送货车辆路径问题研究现状

2.2 供需匹配关系未知的取送货车辆路径问题研究现状

2.3 允许多次访问的取送货车辆路径问题研究现状

2.4 取送货车辆路径问题求解算法研究现状

2.5 本章小结

3 允许多次访问的供需匹配与取送货车辆路径问题模型及有效不等式研究

3.1 引言

3.2 模型建立

3.3 有效不等式

3.4 算例测试及结果分析

3.5 本章小结

4 允许多次访问的供需匹配与取送货车辆问题启发式算法研究

4.1 引言

4.2 初始解构建

4.3 邻域结构

4.4 禁忌搜索

4.5 算例测试及结果分析

4.6 本章小结

5 允许多次访问的供需匹配与取送货车辆路径问题精确算法研究

5.1 引言

5.2 有效不等式

5.3 分离算法

5.4 分支切割算法

5.5 算例测试及结果分析

5.6 本章小结

6 总结与展望

6.1 全文总结

6.2 研究展望

致谢

参考文献

附录1 攻读博士学位期间发表的论文

附录2 攻读博士学位期间参与的科研项目