带后进先出限制的配送收集旅行商问题的树形表示

摘要

配送收集旅行商问题(TSPPD)是一个非常经典的组合优化问题，已有相当多的文献对此问题进行了研究。在现存的大部分文献中，TSPPD的合法解都是使用线性序列来表示，并且需要执行一些特殊操作来确保解的合法性。
　　 本文研究的问题是TSPPD的变种，名为带后进先出限制的配送收集旅行商问题(TSPPDL)。TSPPDL是在TSPPD的基础上增加了配送收集过程必须满足后进先出的限制。TSPPDL被认为是一个比TSPPD更为复杂的问题，原因是在判断表示为线性序列的解的合法性的时候，不仅要检查配送点和对应收集点的先后顺序，还要检查解是否满足后进先出的约束。本文证明了TSPPDL的合法解与TSPPDL解的树形表示之间存在一一映射关系。该树形数据结构从本质上揭示了TSPPDL的特性，并且使得基于线性表示方式的操作更容易被理解和实现。
　　 本文基于树形表示方式，提出了一个有效的变邻域搜索(VNS)算法。该算法运用了多个新颖可行的操作，而这些操作都是利用了树形表示方式的优点。实验结果表明，本文的VNS算法在解的质量上要优于当今求解TSPPDL的最有效的启发式算法。

目录

文摘

英文文摘

声明

第1章绪论

1.1研究背景及意义

1.2国内外研究现状

1.3本文的主要贡献和章节安排

第2章问题描述

2.1问题定义

2.2问题的复杂性

2.3数学模型

2.4本章小结

第3章问题分析

3.1合法解的树形表示方式

3.2合法解的数目

3.3 TSPPDL树与TSPPDL合法解的等价关系

3.4本章小结

第4章求解TSPPDL的变邻域搜索算法

4.1变邻域搜索算法概述

4.2基本操作

4.3多路重置(multi-relocate)操作

4.4新操作

4.5 VNS-Tree算法框架

4.6本章小结

第5章实验分析

5.1实验数据

5.2实验建立

5.3实验结果与分析

5.4本章小结

第6章结束语

6.1总结

6.2进一步研究方向

参考文献

研究生阶段的研究工作

致谢