Optimal toll design: a lower bound framework for the asymmetric traveling salesman problem

DOI10.1007/S10107-013-0631-6MaRDI QIDQ2452379zbMATH OpenOpenAlexFDO

Authors Alejandro Toriello

Publication date 2 June 2014

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10107-013-0631-6

zbMATH Keywords

traveling salesman problemdynamic programinteger programlower bound techniqueapproximate linear program

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27) Dynamic programming (90C39) Integer programming (90C10)

Recommendations

• The asymmetric bottleneck traveling salesman problem: algorithms, complexity and empirical analysis
• The asymmetric travelling salesman problem and a reformulation of the Miller-Tucker-Zemlin constraints
• Approximation algorithms for the bottleneck asymmetric traveling salesman problem
• Approximation Algorithms for the Bottleneck Asymmetric Traveling Salesman Problem
• An optimal scheme for toll pricing problem
• The effect of the asymmetry of road transportation networks on the traveling salesman problem
• The research of optimal down bound of asymmetrical TSP
• The asymmetric travelling salesman problem: on generalizations of disaggregated Miller-Tucker-Zemlin constraints
• On the Integrality Ratio for the Asymmetric Traveling Salesman Problem

Cites work

• scientific article; zbMATH DE number 176878 (Why is no real title available?)
• A Dynamic Programming Approach to Sequencing Problems
• A restricted dynamic programming heuristic algorithm for the time dependent traveling salesman problem
• Analyzing the Held-Karp TSP bound: A monotonicity property with application
• Approximate extended formulations
• Duality and Existence of Optimal Policies in Generalized Joint Replenishment
• Dynamic Programming Strategies for the Traveling Salesman Problem with Time Window and Precedence Constraints
• Generalized polynomial approximations in Markovian decision processes
• Heuristic analysis, linear programming and branch and bound
• Maximizing a submodular function by integer programming: Polyhedral results for the quadratic case
• On the worst-case performance of some algorithms for the asymmetric traveling salesman problem
• SPLINE APPROXIMATIONS TO VALUE FUNCTIONS
• The Traveling-Salesman Problem and Minimum Spanning Trees
• The traveling salesman problem and its variations
• The traveling-salesman problem and minimum spanning trees: Part II
• The travelling salesman problem as a constrained shortest path problem: Theory and computational experience
• Worst-case comparison of valid inequalities for the TSP

Cited in

(7)

• The research of optimal down bound of asymmetrical TSP
• Network-based approximate linear programming for discrete optimization
• A polyhedral approach to online bipartite matching
• Probabilistic prediction of the complexity of traveling salesman problems based on approximating the complexity distribution from experimental data
• A Polyhedral Approach to Online Bipartite Matching
• Analysis of the Held-Karp lower bound for the asymmetric TSP
• A bilevel programming approach to the travelling salesman problem.

Describes a project that uses

Uses Software

• Concorde

This page was built for publication: Optimal toll design: a lower bound framework for the asymmetric traveling salesman problem

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