An enhanced lower bound for the time-dependent travelling salesman problem

DOI10.1016/j.cor.2019.104795zbMath1458.90597OpenAlexW2971416083WikidataQ127291010 ScholiaQ127291010MaRDI QIDQ2333147

Tommaso Adamo, Gianpaolo Ghiani, Emanuela Guerriero

Publication date: 11 November 2019

Published in: Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.cor.2019.104795

zbMATH Keywords

travelling salesman problemlower and upper boundsbranch-and-cuttime dependence

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27)

Related Items (6)

Dynamic Programming for the Time-Dependent Traveling Salesman Problem with Time Windows ⋮ The traveling salesman problem with job-times (\textit{TSPJ}) ⋮ On path ranking in time-dependent graphs ⋮ A branch-cut-and-price algorithm for the time-dependent electric vehicle routing problem with time windows ⋮ The mixed capacitated general routing problem with <scp>time‐dependent</scp> demands ⋮ A hybrid mathematical model for flying sidekick travelling salesman problem with time windows

Uses Software

• VRP

Cites Work

• Unnamed Item
• Time-dependent routing problems: a review
• Natural and extended formulations for the time-dependent traveling salesman problem
• A restricted dynamic programming heuristic algorithm for the time dependent traveling salesman problem
• A classification of formulations for the (time-dependent) traveling salesman problem
• An integer programming approach for the time-dependent traveling salesman problem with time windows
• The next wave in computing, optimization, and decision technologies. Papers from the ninth INFORMS Computing Society conference (ICS 2005), Annapolis, MD, USA, January 5--7, 2005.
• The time-dependent traveling salesman problem
• Vehicle dispatching with time-dependent travel times
• Time-dependent asymmetric traveling salesman problem with time windows: properties and an exact algorithm
• A branch-and-cut algorithm for a production scheduling problem with sequence-dependent and time-dependent setup times
• An asymmetric TSP with time windows and with time-dependent travel times and costs: an exact solution through a graph transformation
• An integer programming approach for the time-dependent TSP
• Vehicle Routing
• Some New Branching and Bounding Criteria for the Asymmetric Travelling Salesman Problem
• Time Dependent Vehicle Routing Problems: Formulations, Properties and Heuristic Algorithms
• The Time-Dependent Traveling Salesman Problem and Its Application to the Tardiness Problem in One-Machine Scheduling
• Technical Note—An n-Constraint Formulation of the (Time-Dependent) Traveling Salesman Problem
• The moving-target traveling salesman problem
• A Time-Dependent No-Overlap Constraint: Application to Urban Delivery Problems

This page was built for publication: An enhanced lower bound for the time-dependent travelling salesman problem