Complexity analysis and optimization of the shortest path tour problem

DOI10.1007/S11590-010-0258-YMaRDI QIDQ691420zbMATH OpenOpenAlexFDO

Authors Paola Festa

Publication date 30 November 2012

Published in Optimization Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s11590-010-0258-y

zbMATH Keywords

network flow problemsshortest path problems

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Programming involving graphs or networks (90C35)

Recommendations

• Solving the shortest path tour problem
• An efficient exact approach for the constrained shortest path tour problem
• The constrained shortest path tour problem
• A generalized shortest path tour problem with time windows
• Constrained shortest path tour problem: branch-and-price algorithm

Cites work

• A dual algorithm for the constrained shortest path problem
• A note on two problems in connexion with graphs
• An Auction Algorithm for Shortest Paths
• Buckets, Heaps, Lists, and Monotone Priority Queues
• Handbook of applied optimization
• Negative-cycle detection algorithms
• Network flows. Theory, algorithms, and applications.
• Polynomial auction algorithms for shortest paths
• Properties of Labeling Methods for Determining Shortest Path Trees
• Shortest path algorithms
• Shortest path methods: A unifying approach
• Shortest paths algorithms: Theory and experimental evaluation
• Shortest-path algorithms: Taxonomy and annotation
• Shortest-Route Methods: 1. Reaching, Pruning, and Buckets
• Shortest-Route Methods: 2. Group Knapsacks, Expanded Networks, and Branch-and-Bound
• Some observations about the extreme points of the generalized cardinality-constrained shortest path problem polytope
• The constrained shortest path problem

Cited in

(21)

• A note on the tour problems in two-terminal series-parallel graphs
• The quadratic shortest path problem: complexity, approximability, and solution methods
• The coolest path problem
• A generalized shortest path tour problem with time windows
• Constrained shortest path tour problem: branch-and-price algorithm
• Shortest path tour problem with time windows
• Solving the shortest path tour problem
• Route intelligent recommendation model and algorithm under the Pythagorean hesitant fuzzy linguistic environment
• New formulations for the elementary shortest-path problem visiting a given set of nodes
• The constrained shortest path tour problem
• scientific article; zbMATH DE number 1558116 (Why is no real title available?)
• AN APPROACH TO TRIP- AND ROUTE-PLANNING PROBLEMS
• An efficient exact approach for the constrained shortest path tour problem
• Fine-grained Complexity Analysis of Two Classic TSP Variants
• Optimal tour planning with specified nodes
• On universal shortest paths
• Constrained shortest path tour problem: models, valid inequalities, and Lagrangian heuristics
• The constrained forward shortest path tour problem: Mathematical modeling and GRASP approximate solutions
• Algorithms for shortest path tour problem in large-scale road network
• Algorithms for shortest path tour problem
• The ripple-spreading algorithm for shortest path tour problems

This page was built for publication: Complexity analysis and optimization of the shortest path tour problem

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