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