Neuro-Ins: A learning-based one-shot node insertion for dynamic routing problems

Publication Type

Journal Article

Publication Date

9-2025

Abstract

The rise in instant delivery services necessitates efficient route planning in last-mile delivery scenarios, where new orders arrive dynamically and need to be integrated into existing routes. In such contexts, complete re-optimization of routes are not permitted, and node insertion to existing route sequences is the only viable option. However, many existing heuristics for node insertion, such as the Cheapest Insertion (CI) method, are myopic and often result in suboptimal solutions retrospectively. This paper presents Neuro-Ins, an initial yet novel attempt at harnessing a learning-based framework to handle the insertion of new orders for the Pickup and Delivery Problem (PDP). In contrast to CI, which considers only one node at a time for insertion, Neuro-Ins leverages an Attention-Mechanism (AM) based encoder-decoder structure to collectively consider all nodes to be inserted, thereby enhancing the quality of the eventual solution. To further improve the model’s representation of the current route, we introduce a position embedding to enrich the node feature embedding with positional information of the route. Experiments on synthetic and real-world datasets demonstrate that Neuro-Ins, trained by PPO, consistently outperforms CI without compromising computational speed, and it also surpasses the performance of state-of-the-art solution methods implemented in the industry. Our findings emphasize the importance of explicitly considering all nodes to be inserted along with the en-route nodes and their positions in the route, showcasing the efficacy of the proposed AM-based framework in optimizing the instant delivery routes.

Keywords

dynamic routing, pickup and delivery problem, node insertion, deep reinforcement learning, attention mechanism, encoder–decoder models, instant delivery, last-mile logistics, PPO, neural combinatorial optimization

Discipline

Artificial Intelligence and Robotics | Operations Research, Systems Engineering and Industrial Engineering

Research Areas

Intelligent Systems and Optimization

Publication

IEEE Transactions on Knowledge and Data Engineering

Volume

37

Issue

9

ISSN

1041-4347

Identifier

10.1109/TKDE.2025.3580640

Publisher

Institute of Electrical and Electronics Engineers

This document is currently not available here.

Share

COinS