ITSC 2025 Paper Abstract

Close

Paper WE-EA-T8.1

Fang, Bowen (Columbia University), Chen, Xu (Columbia University), Di, Xuan (Columbia University)

Learn to Tour: Operator Design for Solution Feasibility Mapping in Pickup-And-Delivery Traveling Salesman Problem

Scheduled for presentation during the Regular Session "S08b-Intelligent Modeling and Prediction of Traffic Dynamics" (WE-EA-T8), Wednesday, November 19, 2025, 13:30−13:50, Coolangata 2

2025 IEEE 28th International Conference on Intelligent Transportation Systems (ITSC), November 18-21, 2025, Gold Coast, Australia

This information is tentative and subject to change. Compiled on October 19, 2025

Keywords AI, Machine Learning for Real-time Traffic Flow Prediction and Management, Data Analytics and Real-time Decision Making for Autonomous Traffic Management, Dynamic Scheduling and Routing for Freight Transport in Urban Environments

Abstract

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.

 

 

All Content © PaperCept, Inc.


This site is protected by copyright and trademark laws under US and International law.
All rights reserved. © 2002-2025 PaperCept, Inc.
Page generated 2025-10-19  16:53:00 PST  Terms of use