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 算法和现有学习方法进行比较，结果表明我们的方法可以找到比基准更短的路径。

学习巡回：运算符设计用于解决方案可行性映射的接送旅行推销员问题

Learn to Tour: Operator Design For Solution Feasibility Mapping in  Pickup-and-delivery Traveling Salesman Problem

The Multi-Agent Path Finding (MAPF) problem entails finding collision-free
paths for a set of agents, guiding them from their start to goal locations.
However, MAPF does not account for several practical task-related constraints.
For example, agents may need to perform actions at goal locations with specific
execution times, adhering to predetermined orders and timeframes. Moreover,
goal assignments may not be predefined for agents, and the optimization
objective may lack an explicit definition. To incorporate task assignment, path
planning, and a user-defined objective into a coherent framework, this paper
examines the Task Assignment and Path Finding with Precedence and Temporal
Constraints (TAPF-PTC) problem. We augment Conflict-Based Search (CBS) to
simultaneously generate task assignments and collision-free paths that adhere
to precedence and temporal constraints, maximizing an objective quantified by
the return from a user-defined reward function in reinforcement learning (RL).
Experimentally, we demonstrate that our algorithm, CBS-TA-PTC, can solve highly
challenging bomb-defusing tasks with precedence and temporal constraints
efficiently relative to MARL and adapted Target Assignment and Path Finding
(TAPF) methods.

该研究通过利用强化学习中用户定义的奖励函数来实现冲突搜索算法（CBS）和任务分配与路径规划，解决了具有优先和时间约束的任务分配与路径规划问题（TAPF-PTC）。通过实验证明，相对于 MARL 和适应性目标分配与路径规划（TAPF）方法，我们的算法 CBS-TA-PTC 有效地解决了具有优先和时间约束的高难度拆弹任务。

利用基于冲突的搜索、优先级和时间约束进行最优任务分配和路径规划

Optimal Task Assignment and Path Planning using Conflict-Based Search  with Precedence and Temporal Constraints

The convex hull cheapest insertion heuristic is known to generate good
solutions to the Euclidean Traveling Salesperson Problem. This paper presents
an adaptation of this heuristic to the non-Euclidean version of the problem and
further extends it to the problem with precedence constraints, also known as
the Sequential Ordering Problem. To test the proposed algorithm, the well-known
TSPLIB benchmark data-set is modified in a replicable manner to create
non-Euclidean instances and precedence constraints. The proposed algorithm is
shown to outperform the commonly used Nearest Neighbor algorithm in 97% of the
cases that do not have precedence constraints. When precedence constraints
exist such that the child nodes are centrally located, the algorithm again
outperforms the Nearest Neighbor algorithm in 98% of the studied instances.
Considering all spatial layouts of precedence constraints, the algorithm
outperforms the Nearest Neighbor heuristic 68% of the time.

本文介绍了基于凸包最便宜的插入启发式算法对非欧几里得旅行商问题的改进，并将其扩展到具有优先级约束的问题，并证明该算法在 TSPLIB 基准数据集中优于常用的最近邻算法。