Natural and extended formulations for the time-dependent traveling salesman problem

DOI10.1016/J.DAM.2011.11.019MaRDI QIDQ496646zbMATH OpenOpenAlexFDO

Authors Maria Teresa Godinho, Pierre Pesneau, Luis Gouveia

Publication date 22 September 2015

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2011.11.019

zbMATH Keywords

projectionextended formulationstime-dependent traveling salesman problem

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Recommendations

• A classification of formulations for the (time-dependent) traveling salesman problem
• The time dependent traveling salesman problem: polyhedra and algorithm
• An integer programming approach for the time-dependent TSP
• On a time-dependent formulation and an updated classification of ATSP formulations
• scientific article; zbMATH DE number 947471

Cites work

• scientific article; zbMATH DE number 3895002 (Why is no real title available?)
• A New Formulation for the Travelling Salesman Problem
• A class of lifted path and flow-based formulations for the asymmetric traveling salesman problem with and without precedence constraints
• A classification of formulations for the (time-dependent) traveling salesman problem
• A comparative analysis of several asymmetric traveling salesman problem formulations
• A new formulation for the traveling deliveryman problem
• Approximate extended formulations
• Classification of travelling salesman problem formulations
• Combined route capacity and route length models for unit demand vehicle routing problems
• Modeling hop-constrained and diameter-constrained minimum spanning tree problems as Steiner tree problems over layered graphs
• Models and branch‐and‐cut algorithms for the Steiner tree problem with revenues, budget and hop constraints
• New tighter polynomial length formulations for the asymmetric traveling salesman problem with and without precedence constraints
• On Tightening the Relaxations of Miller-Tucker-Zemlin Formulations for Asymmetric Traveling Salesman Problems
• On extended formulations for the precedence constrained asymmetric traveling salesman problem
• Technical Note—An n-Constraint Formulation of the (Time-Dependent) Traveling Salesman Problem
• The Delivery Man Problem and Cumulative Matroids
• The Time-Dependent Traveling Salesman Problem and Its Application to the Tardiness Problem in One-Machine Scheduling
• The asymmetric travelling salesman problem: on generalizations of disaggregated Miller-Tucker-Zemlin constraints
• The time-dependent traveling salesman problem and single machine scheduling problems with sequence dependent setup times
• The traveling salesman problem with cumulative costs
• Time‐dependent traveling salesman problem–the deliveryman case

Cited in

(25)

• Solving the traveling delivery person problem with limited computational time
• Exact algorithms for the equitable traveling salesman problem
• Layered graph approaches for combinatorial optimization problems
• Hybrid optimization methods for time-dependent sequencing problems
• The traveling purchaser problem with time-dependent quantities
• A classification of formulations for the (time-dependent) traveling salesman problem
• Facets and valid inequalities for the time-dependent travelling salesman problem
• The travelling salesman problem with positional consistency constraints: an application to healthcare services
• An integer programming approach for the time-dependent traveling salesman problem with time windows
• A meta-heuristic based goal-selection strategy for mobile robot search in an unknown environment
• A branch-and-price algorithm for the minimum latency problem
• Formulations for the clustered traveling salesman problem with \(d\)-relaxed priority rule
• scientific article; zbMATH DE number 947471 (Why is no real title available?)
• Load-dependent and precedence-based models for pickup and delivery problems
• Multirobot search for a stationary object placed in a known environment with a combination of GRASP and VND
• On path ranking in time-dependent graphs
• Formulations and a Lagrangian relaxation approach for the prize collecting traveling salesman problem
• New integer linear programming formulation for the traveling salesman problem with time windows: minimizing tour duration with waiting times
• An enhanced lower bound for the time-dependent travelling salesman problem
• A pattern recognition lexi search approach to generalized time-dependent travelling salesman problem
• Tight lower bounds for the traveling salesman problem with draft limits
• Extended formulations and branch-and-cut algorithms for the black-and-white traveling salesman problem
• Layered graph models for the electric vehicle routing problem with nonlinear charging functions
• Hop-indexed circuit-based formulations for the traveling salesman problem
• On a time-dependent formulation and an updated classification of ATSP formulations

This page was built for publication: Natural and extended formulations for the time-dependent traveling salesman problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q496646)