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

DOI10.1016/j.dam.2011.11.019zbMath1331.90066OpenAlexW1990021722MaRDI QIDQ496646

Pierre Pesneau, Maria Teresa Godinho, Luís 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)

Related Items (17)

Layered graph approaches for combinatorial optimization problems ⋮ An integer programming approach for the time-dependent traveling salesman problem with time windows ⋮ The traveling purchaser problem with time-dependent quantities ⋮ 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 ⋮ Load-dependent and precedence-based models for pickup and delivery problems ⋮ On path ranking in time-dependent graphs ⋮ Extended formulations and branch-and-cut algorithms for the black-and-white traveling salesman problem ⋮ Formulations for the clustered traveling salesman problem with \(d\)-relaxed priority rule ⋮ Multirobot search for a stationary object placed in a known environment with a combination of GRASP and VND ⋮ Formulations and a Lagrangian relaxation approach for the prize collecting traveling salesman problem ⋮ Tight lower bounds for the traveling salesman problem with draft limits ⋮ The travelling salesman problem with positional consistency constraints: an application to healthcare services ⋮ Hybrid optimization methods for time-dependent sequencing problems ⋮ Exact algorithms for the equitable traveling salesman problem ⋮ An enhanced lower bound for the time-dependent travelling salesman problem ⋮ Solving the traveling delivery person problem with limited computational time

Cites Work

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

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