新型蚁群优化算法在带时间窗口的车辆路径问题中的应用

摘要

带时间窗口的车辆路径问题(VRPTW)是现实物流问题的一个数学抽象模型。本文将蚁群优化算法(ACO)用于求解该问题。我们的首要目标函数是降低VRPTW中的车辆数，第二目标函数是降低总行驶代价。
　　在本文中，我们改进了基本的蚁群算法以更好求解目标函数。本文主要从以下四个方面做了改进。第一，为了减小解构建过程中的搜索空间，我们提出了域这个概念，且这个概念贯穿于整篇文章。该方法根据问题在时间上的约束，预先排除了时间上不可行的城市。将该概念应用到Solomon问题中，搜索空间平均减小了28％。第二，我们将基于数量的蚁群优化算法(PACO)首次运用于解决VRPTW，并发现该算法性能优于本文中提到的所有蚁群算法。第三，本文针对PACO提出了一种全新的概率初始方法(PI-PACO)。该方法对问题中条件以及实际物流情况建模并最终给出城市间访问的初始信息素。通过实验我们发现，该方法不仅能同时提升两个目标函数的质量也能加速算法的收敛。第四，为了提高解的质量，我们在算法中增加了局部搜索算法并改进了概率初始方法以使两者更好结合（混合式PI-PACO）。该局部搜索算法采用了随机搜索算子选择方法即从三个搜索算子随机选择一个并作用于解产生相应邻域。当我们算法与其他基于蚁群优化的算法比较时，我们的算法比同类算法更优;与复杂算法相比，其在求解基于集群的问题上表现更佳。这表明我们的算法相当有竞争优势。

目录

声明

摘要

ABSTRACT

Table of Contents

List of Tables

List of Figures

List of Algorithm

Nomenclature

Chapter 1 Introduction

1．1 VRPTW

1．2 Algorithms for Solving VRPTWs

1．3 ACO

1．3．1 Basic ACO

1．3．2 EAS

1．3．3 MMAS

1．3．4 ACS

1．3．5 PACO

1．4 Solomon Benchmark

Chapter 2 Improving ACO for Solving VRPTWs

2．1 IACO

2．1．1 Preprocessing

2．1．2 ACO Strategy

2．1．3 Initialization Procedure

2．1．4 Experimental Setup

2．1．5 Experimental Results

2．2 PACO Applied to VRPTWs

2．2．1 Experimental Setup

2．2．2 Comparison Results

2．3 Probability Initialization Of PACO

2．3．1 Probability Density Function

2．3．2 Vhlue Estimation Function

2．3．3 Putting it Together

2．3．4 Effect of Probability Initialization

2．3．5 Results of initialized PACO

2．4 Initialization Effect on Different Problems

2．4．1 Solution fragments generated by initialization

Chapter 3 PI-PACO with Local Search

3．1 Effect of Local Search

3．2 Neighborhood Structures

3．3 Simple Combination of the Initialization and Local Search

3．3．1 Experimental Setup

3．3．2 Experimental Results

3．4 Parameter influence on PI-PACO

3．5 Modifications to initial pheromone values

3．6 Comparison between ACOs and non-ACO algorithms in Solving VRPTW

3．6．1 Difference between PACO and non-ACO algorithms

3．6．2 Difference between PACO and ACO algorithms

3．6．3 Characteristic Analysis and Futu re Work

Chapter 4 Conclusions

References

Thanks

在读期间发表的学术论文与取得的研究成果

中文简介摘要