Scalable Solution of the Stochastic Multi-path Traveling Salesman Problem via Neural Networks

• URL: http://arxiv.org/abs/2605.14662v1
• Date: Thu, 14 May 2026 10:16:55 GMT
• Title: Scalable Solution of the Stochastic Multi-path Traveling Salesman Problem via Neural Networks
• Abstract summary: The objective of the problem is to determine a Hamiltonian tour that minimizes the expected total cost under uncertainty.<n>The innovation of this work is the integration of neural network-based surrogate models to approximate the expected value of the second-stage recourse problem.
• Score: 1.5484595752241122
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The multi-path Traveling Salesman Problem with stochastic travel costs arises in hybrid vehicle routing applications designed for Smart City and City Logistics, where multiple paths exist between each pair of locations. Travel times along these paths are typically affected by real-time traffic conditions and therefore modeled as stochastic. The objective of the problem is to determine a Hamiltonian tour that minimizes the expected total travel cost under uncertainty. In this work, we adopt a two-stage stochastic programming formulation. In the first stage, a predefined route specifying the sequence of locations to be visited is determined, while taking into consideration a second-stage recourse problem that selects the optimal path from the feasible set of alternative paths for each pair of locations, once real-time traffic conditions are realized. To reduce the computational burden imposed by the large number of scenarios required to capture travel time uncertainty, the innovation of this work is the integration of neural network-based surrogate models to approximate the expected value of the second-stage recourse problem. Different architectures and training strategies for the neural networks are proposed and analyzed, with performance evaluated in terms of computation time, solution quality, and generalization capability. Preliminary findings demonstrate the enhanced scalability and practical applicability of the approach for complex vehicle routing problems under uncertainty.

Related papers

• AutoPath: Learning Transferable Goal-Conditioned Stochastic Path Prior for Safe Navigation Without Human Demonstrations [103.61864552260316]
  Real-time navigation in dynamic environments requires collision-free and dynamically feasible motion under limited perception.<n>We formulate navigation as learning a transferable goal-aligned path prior that models a reusable distribution over goal-aligned geometry-consistent local paths conditioned on local observations.<n>We develop a structured prior learning framework that parameterizes local paths using a geometry-aware polar action manifold and incorporates risk-sensitive utility shaping with multi-goal distributional rollouts for stable and safety-aware planning.
  arXiv  Detail & Related papers  (2026-07-13T16:00:41Z)
• NaviFormer: A Deep Reinforcement Learning Transformer-like Model to Holistically Solve the Navigation Problem [53.70554593151033]
  NaviFormer is a deep reinforcement learning model that solves the global navigation problem by predicting both high-level routes and low-level trajectories.<n>Results show competitive accuracy from NaviFormer since it can understand the constraints and difficulties of each subproblem.<n>Its superior computation speed proves its suitability for real-time missions.
  arXiv  Detail & Related papers  (2026-04-18T11:32:34Z)
• Collision-Free Velocity Scheduling for Multi-Agent Systems on Predefined Routes via Inexact-Projection ADMM [0.0]
  In structured multi-agent projects, agents often must follow predefined routes, making rerouting or impossible.<n>This paper addresses route-constrained multi-agent coordination by optimizing waypoint times while preserving each agent's assigned waypoint order and nominal route assignment.
  arXiv  Detail & Related papers  (2026-03-23T12:34:18Z)
• Learning Minimally-Congested Drive Times from Sparse Open Networks: A Lightweight RF-Based Estimator for Urban Roadway Operations [0.0]
  This paper develops a lightweight estimator for minimally-congested car travel times.<n>It integrates open road-network data, speed constraints, and sparse control/turn features within a random forest framework.<n>It preserves point-to-point fidelity at metropolitan scale, reduces resource requirements, and supplies defensible performance estimates.
  arXiv  Detail & Related papers  (2026-01-04T09:54:44Z)
• Accelerating Vehicle Routing via AI-Initialized Genetic Algorithms [53.75036695728983]
  Vehicle Routing Problems (VRP) are a fundamental NP-hard challenge in Evolutionary optimization.<n>We introduce an optimization framework where a reinforcement learning agent is trained on prior instances and quickly generates initial solutions.<n>This framework consistently outperforms current state-of-the-art solvers across various time budgets.
  arXiv  Detail & Related papers  (2025-04-08T15:21:01Z)
• Contextual Stochastic Vehicle Routing with Time Windows [47.91283991228738]
  We study the vehicle routing problem with time windows (VRPTW) and travel times. We introduce the contextual VRPTW, which minimizes the total transportation cost and expected late arrival penalties conditioned on the observed features. We present novel data-driven prescriptive models that use historical data to provide an approximate solution to the problem.
  arXiv  Detail & Related papers  (2024-02-10T14:56:36Z)
• TOP-Former: A Multi-Agent Transformer Approach for the Team Orienteering Problem [47.40841984849682]
  Route planning for a fleet of vehicles is an important task in applications such as package delivery, surveillance, or transportation.<n>We introduce TOP-Former, a multi-agent route planning neural network designed to efficiently and accurately solve the Team Orienteering Problem.
  arXiv  Detail & Related papers  (2023-11-30T16:10:35Z)
• Dynamic Origin-Destination Matrix Estimation in Urban Traffic Networks [0.05735035463793007]
  We model the problem as a bi-level optimization problem. In the inner level, given a tentative travel demand, we solve a dynamic traffic assignment problem to decide the routing of the users between their origins and destinations. In the outer level, we adjust the number of trips and their origins and destinations, aiming at minimizing the discrepancy between the counters generated in the inner level and the given vehicle counts measured by sensors in the traffic network.
  arXiv  Detail & Related papers  (2022-01-31T21:33:46Z)
• Data Driven VRP: A Neural Network Model to Learn Hidden Preferences for VRP [9.434400627011108]
  We use a neural network model to estimate the arc probabilities, which allows for additional features and automatic parameter estimation. We investigate the difference with a prior weighted Markov counting approach, and study the applicability of neural networks in this setting.
  arXiv  Detail & Related papers  (2021-08-10T10:53:44Z)
• Learning-based Preference Prediction for Constrained Multi-Criteria Path-Planning [12.457788665461312]
  Constrained path-planning for Autonomous Ground Vehicles (AGV) is one such application. We leverage knowledge acquired through offline simulations by training a neural network model to predict the uncertain criterion. We integrate this model inside a path-planner which can solve problems online.
  arXiv  Detail & Related papers  (2021-08-02T17:13:45Z)
• Do Neural Optimal Transport Solvers Work? A Continuous Wasserstein-2 Benchmark [133.46066694893318]
  We evaluate the performance of neural network-based solvers for optimal transport. We find that existing solvers do not recover optimal transport maps even though they perform well in downstream tasks.
  arXiv  Detail & Related papers  (2021-06-03T15:59:28Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.