CS Paper Radar

Customizable and Jointly Optimized Route Planning: A Deep Architecture Enabling Differentiable Shortest-Path Search

Rui Zhao, Chao Chen, Longfei Xu, Chenguang Ji, Hengbin Cui, Kaikui Liu, Xiaolong Li

cs.AI ·submitted 2026-09-17 10:04 UTC · v1

Abstract

With the widespread use of online navigation and ride-hailing services, achieving optimal route planning for diverse user preferences has recently attracted increasing attention. Classic graph algorithms for pathfinding use heuristic cost functions to define edge weight, thus providing no optimality guarantee of route quality. Prior data-driven approaches equating ground truth of the optimal route with user trajectory, which is however moderately influenced by the navigation service, suffers from the feedback loop problem. To address these issues, we propose a deep architecture that is able to jointly optimize cost functions and route-ranking model towards any route preference. First, we run a multi-objective Dijkstra algorithm offline to collect the set of Pareto optimal routes, deeming it as the complete candidate set. Exploiting the property of such a set, we design a neural network structure that emulates shortest-path search and route ranking in an end-to-end differentiable manner. Second, we define route preference as a task of constrained optimization of route attributes, and propose a novel loss function that optimizes a single-objective variable, with other variables strictly under constraints. We conduct extensive experiments on real-world datasets. The results show that our architecture significantly outperforms state-of-the-art methods in route quality and customizability.

Closest papers

Nearest neighbours by meaning across the whole index.

A Decision-Focused Neural Optimization Framework for Personalized Route Reproduction from Vehicle Trajectories

cs.LG ·2026-10-06 ·Gyeongjun Kim, Yeseul Kang, Keemin Sohn
similarity 0.72
Abstract

This study formulates individual route reproduction as a shortest-path problem over learned driver-specific latent link costs. The central idea is that, once such latent costs are inferred from contextual information, observed routes can be reproduced without enumerating alternative route sets. We propose a neural pipeline that includes a perception model that embeds context covariates, which comprises individual characteristics, trip-specific attributes, and network-level traffic states, into the personalized link costs. A constrained optimization (CO) layer, which determines the shortest path (SP) based on these estimated costs, follows the perception encoder. To enable end-to-end training, we employ decision-focused learning to align the predicted shortest paths with observed routes. The implicit maximum likelihood estimation (iMLE) provides an approximate gradient of the loss function that contains the non-differentiable CO layer. Furthermore, a regularization term anchors the latent cost distribution to the empirical scale of observed link travel times, mitigating the scale ambiguity inherent in shortest-path supervision. Empirical evaluations demonstrate that the proposed framework outperforms baseline route choice models in path reproduction. The learned latent costs, interpreted as proxies for perceived travel costs, provide plausible explanations for heterogeneous route choices.

0.17

Improving Cross-Problem Vehicle Routing with Locally Augmented Preferences and Representation Disentanglement

cs.LG ·2026-08-25 ·Arthur Corrêa, Paulo Nascimento, Samuel Moniz
similarity 0.65
Abstract

Multi-task vehicle routing problem (VRP) solvers seek to handle multiple VRP variants within a single unified model, avoiding the need to train a separate model for every variant. In spite of recent progress, current approaches remain limited on two fronts. On the training side, reinforcement learning suffers from reward-scale disparities and shrinking advantage signals as policies improve, whereas preference optimization stagnates once sampled tours become near-identical and thus fundamentally limited by the quality of the policy's own generated solutions, leaving both paradigms with weak supervision as training progresses. On the architecture side, existing fully shared encoders entangle constraint-dependent representations across heterogeneous variants, which limits generalization. We address these gaps with two model-agnostic contributions. First, we propose Preference Optimization with Locally Augmented Refinement (POLAR), a novel training algorithm that applies a local search refinement pass to the best decoded tour before forming preference pairs, yielding much more informative pairwise margins. Second, a Progressive Layered Extraction (PLE) encoder routes each encoder layer through one shared expert and a set of task-specific experts via a gating mechanism, progressively separating common routing structure from constraint-specific encodings. Through extensive experiments on various VRP variants, we show that POLAR and PLE together elevate the current state-of-the-art among neural multi-task solvers. We reduce the average gap to reference solutions by 21.3% relative to the strongest published baseline on 16 in-distribution variants, and outperform prior neural methods on 27 out of 32 unseen variants. Ablation studies confirm the efficacy of each contribution, showing that both improve cross-problem generalization across multiple backbone model architectures.

0.17

Smart routes: a system for development and comparison of algorithms for solving vehicle routing problems with realistic constraints

cs.LG ·2026-08-14 ·Andrew Soroka, German Mikhelson, Alexander Mescheryakov, Sergey Gerasimov
published similarity 0.64
Abstract

The problem of route optimization with realistic constraints is becoming extremely relevant in the face of global urban population growth. While we are aware of approaches that theoretically provide an exact optimal solution, their application becomes challenging as the problem size increases because of exponential complexity. We investigate the Capacitated Vehicle Routing Problem with Time Windows (CVRPTW) and compare solutions obtaining by exact solver SCIP with heuristic algorithms such as LKH, 2-OPT, 3-OPT, the ORTools framework, and the deep learning model JAMPR. We demonstrate that for problem of size 50 deep learning and classical heuristic solutions became close to SCIP exact solution but requires less time. Additionally for problems with size 100, SCIP exact methods around 13 times slower that neural and classical heuristics with the same route cost and on around 50% worse for the first feasible solution on the same time. To conduct experiments, we developed the Smart Routes platform for solving route optimization problems, which includes exact, heuristic, and deep learning models, and facilitates convenient integration of custom algorithms and datasets.

0.22

AoI-Guaranteed Dynamic Route Planning for Connected Vehicles

eess.SY ·2026-08-13 ·Sajedeh Norouzi, Maryam Ansarifard, Farshad Zeinali, Ali Nouruzi, Nader Mokari +2 more
similarity 0.63
Abstract

The advancement of Intelligent Transportation Sys- tems (ITS) has been significantly driven by progress in radio communication technology. Dynamic route planning, a key com- ponent of ITS, traditionally focuses on metrics such as route capacity and travel time. This paper presents a novel dual- factor approach that integrates travel time estimation and radio resource availability into an innovative route-planning scheme for connected vehicles (CVs). To address this dual-objective route planning challenge, we employ Deep Reinforcement Learning (DRL). Our approach, called AoI-Guaranteed Dynamic Route Planning (AGDRP), effectively balances travel time and Age of Information (AoI), enhancing route planning performance through adaptive learning over time. Simulation results demon- strate that AGDRP outperforms the baseline scheme, which solely focuses on travel time optimization. In fact, we show that incor- porating AoI minimization significantly enhances route planning performance beyond conventional travel-time-based approaches.

0.04

GREAT-ESDD: Graph Edge Attention Network for Effectively Steered Delivery Decisions

cs.AI ·2026-10-10 ·Attila Lischka, Ze Zhou, Xuegang, Ban, Balázs Kulcsár
similarity 0.63
Abstract · 28 pages, 12 figures

Online, same-day delivery requires operators to constantly update their routes, and the routing cost for deliveries increases with the number of customers. Out-of-home (OOH) delivery options can help companies handle increasing customer numbers while keeping delivery costs low. We develop a dynamic pricing-and-routing framework for this online ordering scenario with home and OOH delivery options. First, we develop a neural solver for the capacitated vehicle routing problem (CVRP) based on the Graph-Edge-Attention-Network (GREAT). We train it to solve CVRP with varying instance sizes and starting conditions, allowing it to reoptimize partially executed routes under changing conditions. It is fast while achieving solution quality competitive with traditional baselines. Our solver processes several CVRP instances in parallel in batches and we use it to solve the candidate routing problems that arise from an incoming customer's choice of home or OOH delivery. This provides an estimate of the delivery cost increase per option, which we use to set dynamic prices. Further, it directly provides the updated route once the customer decides. We trade off delivery fees against routing costs and steer customers toward OOH delivery when home delivery would be costly. However, effective steering requires us to know the customer preferences. To learn those online, we use Thompson sampling with a Laplace-approximated posterior. We call the resulting framework GREAT-ESDD (GREAT for Effectively Steered Delivery Decisions). Compared to a traditional routing solver, it increases profit by around 11% under a similar pricing decision time budget. Moreover, we show that we can estimate customer preferences successfully, outperforming a static pricing strategy after only 5 days of simulated operations.

0.28

GNN-Guided Network Reduction for Centralized Urban Traffic Routing

cs.LG ·2026-10-27 ·Nikolai Antonov, Lukáš Chrpa, Andrii Nyporko, Jan Hůla
similarity 0.63
Abstract · Submitted for review to Computers & Operations Research

We consider the centralized traffic routing (CTR) problem, where a central planner assigns routes to origin-destination (OD) vehicle flows to minimize congestion-dependent segment cost. Prior work formulates CTR efficiently as a mixed-integer linear program (MILP), but scaling this formulation to the full road network is computationally prohibitive within an operational time budget. Bounded Routes and Smart Routes speed up optimization using precomputed reduced networks; however, these methods do not account for vehicle information within each OD flow. Motivated by this gap, we propose a learning-based urban network reduction approach. A dedicated graph neural network (GNN) first scores road segments for each OD flow using the road network and vehicle-flow information. Highly ranked segments are then incorporated into complete OD routes, and the original segment-flow MILP is solved on the resulting reduced road network. The GNN thus guides the reduction of the road network, while the solver enforces feasibility and determines the routing. Experiments on four real urban networks -- Prague-Dejvice, London, New York, and Sydney -- show that the proposed approach achieves the smallest relative objective difference to the $30$-second full-graph reference in every city under both traffic regimes. Averaged across cities, this difference is more than six times lower than that of the best competing method. Moreover, traffic simulation results show that the optimization gains of the proposed method lead to more efficient routing, with the highest aggregate arrival rate and a competitive trip duration per arrival percentage point.

0.16

Behavior2Trip: Towards Personalized Travel Planning via User Behavior Trajectory

cs.CL cs.AI ·2026-08-27 ·Zihao Cheng, Yingyu Shan, Hongru Wang, Zeming Liu, Xinyi Wang +4 more
top venuebenchmarkcode/data similarity 0.62
Abstract · Accepted by EMNLP 2026 Findings

Travel planning agents assist users in generating personalized travel plans by modeling their individual preferences. Existing agents either rely on explicit user instructions or engage in multi-turn clarification to elicit user preferences. However, both approaches overlook the rich behavioral signals latent in users' past behaviors, which implicitly encode their preferences. This over-reliance on active user input increases interaction burden and limits plan personalization. To bridge this gap, we introduce a new task, Behavior-Aware Travel Planning, which infers user preferences directly from past behaviors and generates personalized travel plans. To facilitate research on this task, we introduce Behavior2Trip, a benchmark constructed from one of the largest Chinese online travel platforms, comprising 11,400 instances. Each instance represents an average of 39.8 past user behaviors spanning 14 attributes across 5 preference dimensions. We further propose B2T-Agent, a reinforcement learning-based agent that leverages user behavior trajectories, interacts with external tools for preference-aligned retrieval, and maintains an internal memory module. Experiments on Behavior2Trip show that GPT-4.1 achieves a full-constraint pass rate of only 0.5\% on the hardest tasks, while B2T-Agent built upon Qwen3-8B outperforms all baselines, highlighting the substantial challenge of this task. Moreover, Qwen3-8B trained with B2T-Agent also outperforms GPT-4.1 on the TravelPlanner benchmark, demonstrating strong generalization. Code and data are available at https://github.com/BUAA-IRIP-LLM/Behavior2Trip

0.76

From Comparison to Selection: Enhancing Cross-Scale Generalization of Pointer Networks Trained with Reinforcement Learning for Capacitated Vehicle Routing Problem

cs.AI ·2026-10-20 ·Sofiene Lassoued, Devara Tertia, Stefan Lier, Andreas Schwung
similarity 0.62
Abstract · 12 pages

Vehicle routing in delivery and logistics remains challenging as the number of clients varies. Classical approaches based on mixed-integer programming and heuristics can scale poorly or require problem-specific design, motivating learning-based alternatives. Reinforcement learning is particularly promising, provided a single policy can generalise across problem sizes without retraining. Although attention-based Pointer Networks are inherently size-agnostic, their solution quality degrades under both upscaling and downscaling. Using the Capacitated Vehicle Routing Problem (CVRP) as a controlled proxy, we investigate this degradation and identify three contributing factors: shifts in node density, attention dispersion, and dilution of the mean-pooled graph context. We systematically compare architecture-wide, encoder-side, and decoder-side modifications to address these limitations and propose a learned, permutation-invariant graph-context aggregation mechanism, implemented as a weighted average and as Set2Set. Results reveal distinct requirements for transfer in each direction: entropy-based attention scaling reduces the CVRP20-to-CVRP100 performance gap by 1.41 percentage points, while the proposed aggregation methods achieve the largest improvement on the more challenging CVRP100-to-CVRP20 transfer, approximately 0.9 percentage points. Exploiting this complementarity, we introduce an approach selector that chooses the best model for each training-target size pair. The selector reduces cost relative to the reference model across all nine seen train-test pairs and eight of nine pairs involving unseen sizes (CVRP35, CVRP75, and CVRP200), achieving improvements of up to 3.2%.

0.15