单层搜索方法解决多埠与分离递送车辆路径优化问题

摘要

本文研究的是车辆路径优化问题(VRP)的两个分支——多埠车辆路径优化问题(MDVRP)和分离递送车辆路径优化问题(SDVRP)，并阐述了两种解决策略：传统的双层搜索方法和新的单层搜索方法。双层搜索方法是将问题分成两个独立的子问题，在两个阶段分别处理；相反，我们提出的单层搜索方法将两个阶段整合在一起，根据问题的条件，配合禁忌搜索算法，取得了很好的效果。实验数据表明，单层搜索方法明显优于传统的双层搜索方法，并在某些数据中，接近问题的最优解。另外，本文提出的单层搜索方法经过改进后，可以广泛地应用在其他VRP类问题中。

目录

文摘

英文文摘

第1章绪论

1.1问题介绍

1.2研究目的与范围

1.3研究流程

第2章文献综述

2.1 MDVRP文献介绍

2.2 SDVRP文献介绍

2.3车辆路径问题(VRP)的求解策略

2.4禁忌搜索算法(Tabu Search)

第3章多埠车辆路径优化问题

3.1问题定义

3.2双层搜索方法(Two Stage Approach)

3.2.1顾客分组算法

3.2.2路径优化算法

3.3单层搜索方法(One Stage Approach)

3.3.1顾客分组思想

3.3.2路径优化的改进

3.3.3单层搜索算法描述

3.4样例数据分析

第4章分离递送车辆路径优化问题

4.1问题定义

4.2 SDVRP解的特性

4.3双层搜索方法(Two Stage Approach)

4.3.1路径优化阶段

4.3.2分离递送阶段

4.4单层搜索方法(One Stage Approach)

4.4.1建立初始解

4.4.2邻域函数

4.4.3单层搜索算法描述

第5章实验结果与分析

5.1多埠车辆路径优化问题(MDVRP)

5.1.1数据来源

5.1.2实验结果

5.1.3实验结果分析

5.2分离递送路径优化问题(SDVRP)

5.2.1数据来源

5.2.2实验结果

5.2.3实验结果分析

5.3实验环境

第6章总结

参考文献

攻读学位期间所发表的论文

感谢

原创性声明