Learned upper bounds for the Time-Dependent Travelling Salesman Problem

• URL: http://arxiv.org/abs/2107.13641v1
• Date: Wed, 28 Jul 2021 20:54:59 GMT
• Title: Learned upper bounds for the Time-Dependent Travelling Salesman Problem
• Authors: Tommaso Adamo and Gianpaolo Ghiani and Pierpaolo Greco and Emanuela Guerriero
• Abstract summary: Time-Dependent Travelling Salesman Problem consists in finding a Hamiltonian tour of at least total duration covering the vertices of the graph. We devise an upper bounding technique based on the solution of a classical (and simpler) time-independent Asymmetric Travelling Salesman Problem. The effectiveness of this approach has been assessed through a computational campaign on the real travel time functions of two European cities.
• Score: 0.0
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Given a graph whose arc traversal times vary over time, the Time-Dependent Travelling Salesman Problem consists in finding a Hamiltonian tour of least total duration covering the vertices of the graph. The main goal of this work is to define tight upper bounds for this problem by reusing the information gained when solving instances with similar features. This is customary in distribution management, where vehicle routes have to be generated over and over again with similar input data. To this aim, we devise an upper bounding technique based on the solution of a classical (and simpler) time-independent Asymmetric Travelling Salesman Problem, where the constant arc costs are suitably defined by the combined use of a Linear Program and a mix of unsupervised and supervised Machine Learning techniques. The effectiveness of this approach has been assessed through a computational campaign on the real travel time functions of two European cities: Paris and London. The overall average gap between our heuristic and the best-known solutions is about 0.001\%. For 31 instances, new best solutions have been obtained.

Related papers

• Disentangled Representation Learning with the Gromov-Monge Gap [65.73194652234848]
  Learning disentangled representations from unlabelled data is a fundamental challenge in machine learning. We introduce a novel approach to disentangled representation learning based on quadratic optimal transport. We demonstrate the effectiveness of our approach for quantifying disentanglement across four standard benchmarks.
  arXiv  Detail & Related papers  (2024-07-10T16:51:32Z)
• Learning Temporal Distances: Contrastive Successor Features Can Provide a Metric Structure for Decision-Making [66.27188304203217]
  Temporal distances lie at the heart of many algorithms for planning, control, and reinforcement learning. Prior attempts to define such temporal distances in settings have been stymied by an important limitation. We show how successor features learned by contrastive learning form a temporal distance that does satisfy the triangle inequality.
  arXiv  Detail & Related papers  (2024-06-24T19:36:45Z)
• Damped Online Newton Step for Portfolio Selection [96.0297968061824]
  We revisit the classic online portfolio selection problem, where at each round a learner selects a distribution over a set of portfolios to allocate its wealth. Existing algorithms that achieve a logarithmic regret for this problem have per-round time and space complexities that scale with the total number of rounds. We present the first practical online portfolio selection algorithm with a logarithmic regret and whose per-round time and space complexities depend only logarithmically on the horizon.
  arXiv  Detail & Related papers  (2022-02-15T17:01:55Z)
• Machine-learning-based arc selection for constrained shortest path problems in column generation [5.08128537391027]
  In this work, we propose a new pricing algorithm based on machine learning. The objective is to reduce the size of the network and accelerate the PP, keeping only the arcs that have a high chance to be part of the linear relaxation solution. The method has been applied to two specific problems: the vehicle and crew scheduling problem in public transit and the vehicle routing problem with time windows.
  arXiv  Detail & Related papers  (2022-01-07T16:49:12Z)
• Spatio-Temporal Joint Graph Convolutional Networks for Traffic Forecasting [75.10017445699532]
  Recent have shifted their focus towards formulating traffic forecasting as atemporal graph modeling problem. We propose a novel approach for accurate traffic forecasting on road networks over multiple future time steps.
  arXiv  Detail & Related papers  (2021-11-25T08:45:14Z)
• Learnable Graph Matching: Incorporating Graph Partitioning with Deep Feature Learning for Multiple Object Tracking [58.30147362745852]
  Data association across frames is at the core of Multiple Object Tracking (MOT) task. Existing methods mostly ignore the context information among tracklets and intra-frame detections. We propose a novel learnable graph matching method to address these issues.
  arXiv  Detail & Related papers  (2021-03-30T08:58:45Z)
• Time-Series Imputation with Wasserstein Interpolation for Optimal Look-Ahead-Bias and Variance Tradeoff [66.59869239999459]
  In finance, imputation of missing returns may be applied prior to training a portfolio optimization model. There is an inherent trade-off between the look-ahead-bias of using the full data set for imputation and the larger variance in the imputation from using only the training data. We propose a Bayesian posterior consensus distribution which optimally controls the variance and look-ahead-bias trade-off in the imputation.
  arXiv  Detail & Related papers  (2021-02-25T09:05:35Z)
• A Reinforcement Learning Approach to the Orienteering Problem with Time Windows [0.0]
  The Orienteering Problem with Time Windows (OPTW) is an optimization problem where the goal is to maximize the total score collected from different visited locations. This study explores the use of Pointer Network models trained using reinforcement learning to solve the OPTW problem.
  arXiv  Detail & Related papers  (2020-11-07T00:38:06Z)
• Quantum computing approach to railway dispatching and conflict management optimization on single-track railway lines [0.4724825031148411]
  We consider a practical railway dispatching problem: delay and conflict management on a single-track railway line. We introduce a quadratic unconstrained binary optimization (QUBO) model of the problem in question, compatible with the emerging quantum annealing technology. As a proof-of-concept, we solve selected real-life problems from the Polish railway network using D-Wave quantum annealers.
  arXiv  Detail & Related papers  (2020-10-16T08:17:57Z)
• Extending the Multiple Traveling Salesman Problem for Scheduling a Fleet of Drones Performing Monitoring Missions [4.477547027158141]
  We show how to schedule the travel path of a set of drones across a graph where the nodes need to be visited multiple times at pre-defined points in time. The proposed formulation can be applied in several domains such as the monitoring of traffic flows in a transportation network, or the monitoring of remote locations to assist search and rescue missions. In a detailed evaluation, it is observed that the greedy algorithm has near-optimal performance as it is on average at 92.06% of the optimal, while it can potentially scale up to settings with hundreds of drones and locations.
  arXiv  Detail & Related papers  (2020-06-02T09:17:18Z)
• Street-level Travel-time Estimation via Aggregated Uber Data [2.838842554577539]
  Estimating temporal patterns in travel times along road segments in urban settings is of central importance to traffic engineers and city planners. We propose a methodology to leverage coarse-grained and aggregated travel time data to estimate the street-level travel times of a given metropolitan area.
  arXiv  Detail & Related papers  (2020-01-13T21:14:38Z)

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.