This paper aims to develop a learning method for a special class of traveling
salesman problems (TSP), namely, the pickup-and-delivery TSP (PDTSP), which
finds the shortest tour along a sequence of one-to-one pickup-and-delivery
nodes. One-to-one here means that the transported people or goods are
associated with designated pairs of pickup and delivery nodes, in contrast to
that indistinguishable goods can be delivered to any nodes. In PDTSP,
precedence constraints need to be satisfied that each pickup node must be
visited before its corresponding delivery node. Classic operations research
(OR) algorithms for PDTSP are difficult to scale to large-sized problems.
Recently, reinforcement learning (RL) has been applied to TSPs. The basic idea
is to explore and evaluate visiting sequences in a solution space. However,
this approach could be less computationally efficient, as it has to potentially
evaluate many infeasible solutions of which precedence constraints are
violated. To restrict solution search within a feasible space, we utilize
operators that always map one feasible solution to another, without spending
time exploring the infeasible solution space. Such operators are evaluated and
selected as policies to solve PDTSPs in an RL framework. We make a comparison
of our method and baselines, including classic OR algorithms and existing
learning methods. Results show that our approach can find tours shorter than
baselines.

本文旨在开发一种用于一类特殊旅行推销员问题（TSP）的学习方法，即接送 TSP（PDTSP），该方法通过一系列一对一接送节点找到最短路径。我们利用可行解算空间中的操作符来解决 PDTSP，这些操作符将一个可行解映射到另一个可行解，从而限制解决方案搜索范围。通过与经典 OR 算法和现有学习方法进行比较，结果表明我们的方法可以找到比基准更短的路径。