An additive bounding procedure for the asymmetric travelling salesman problem

Keywords

Bounding overwatch, Travelling salesman problem, Mathematics, Simple (philosophy), Combinatorics

References

• AN ADDITIVE APPROACH FOR THE OPTIMAL SOLUTION OF THE PRIZE-COLLECTING TRAVELLING SALESMAN PROBLEM. VEHICLE ROUTING: METHODS AND STUDIES. STUDIES IN MANAGEMENT SCIENCE AND SYSTEMS - VOLUME 16Matteo Fischetti, Paolo Toth — 1988
• An Additive Bounding Procedure for Combinatorial Optimization ProblemsMatteo Fischetti, Paolo Toth — 1989
• Finding optimum branchingsRobert E. Tarjan — 1977
• A restricted Lagrangean approach to the traveling salesman problemEgon Balas, Nicos Christofides — 1981
• The Traveling-Salesman Problem and Minimum Spanning TreesMichael Held, Richard M. Karp — 1970
• A branch and bound algorithm for the multiple depot vehicle scheduling problemG. Carpaneto, Mauro Dell’Amico, Matteo Fischetti — 1989
• Algorithms and codes for the assignment problemG. Carpaneto, Silvano Martello, Paolo Toth — 1988
• Technical Note - Bounds for the Travelling-Salesman ProblemNicos Christofides — 1972
• On dual solutions of the linear assignment problemG.A.P. Kindervater, A. Volgenant, G. de Leve — 1985
• The k best spanning arborescences of a networkP. M. Camerini, L. Fratta, Francesco Maffioli — 1980
• The traveling-salesman problem and minimum spanning trees: Part IIMichael Held, Richard M. Karp — 1971
• Pathology of Traveling-Salesman Subtour-Elimination AlgorithmsMandell Bellmore, John C. Malone — 1971
• New lower bounds for the Symmetric Travelling Salesman ProblemG. Carpaneto, Matteo Fischetti, Paolo Toth — 1989
• Packing rooted directed cuts in a weighted directed graphD. R. Fulkerson — 1974
• A note on finding optimum branchingsP. M. Camerini, L. Fratta, Francesco Maffioli — 1979
• A man-machine approach toward solving the traveling salesman problemPatrick D. Krolak, Wayne Felts, George Marble — 1970
• Depth-First Search and Linear Graph AlgorithmsRobert E. Tarjan — 1972
• Some New Branching and Bounding Criteria for the Asymmetric Travelling Salesman ProblemG. Carpaneto, Paolo Toth — 1980
• Combinatorial optimization: networks and matroidsEugene L. Lawler — 2021
• Erratum: The Traveling Salesman Problem: A Guided Tour of Combinatorial OptimizationE. Lawler, J. Lenstra, A. H. G. Rinnooy Kan — 1986

Cited by

• Combinatorial optimization of elk habitat effectiveness and timber harvest volumePete Bettinger, Kevin Boston, John Sessions — 1999
• Combinatorial Optimization — Eureka, You Shrink!Jünger, Michael, Giovanni Rinaldi — 2003
• The design and implementation of a system for the automatic generation of narrative debriefs for AUV MissionsN. Johnson — 2011
• Arc Routing Problems, Part II: The Rural Postman ProblemH. A. Eiselt, Michel Gendreau, Gilbert Laporte — 1995
• Modelowanie systemów przewozowych w zastosowaniu do projektowania obsługi transportowej podmiotów gospodarczychDariusz Pyza — 2012
• Résolution de problèmes d'optimisation combinatoire mono et multi-objectifs par énumération ordonnée. (Solving single and multi-objective combinatorial optimization problems by ordered enumeration)Lyes Belhoul — 2014
• Um melhor limite inferior para o problema do caixeiro viajante assimétrico baseado no problema da afectaçãoAna Ramires, João Soares — 2005
• Improving the Asymmetric TSP by Considering Graph StructureJean-Guillaume Fages, Xavier Lorca — 2012
• Embedding Relaxations in Global Constraints for Solving TSP and TSPTWFilippo Focacci, Andrea Lodi, Michela Milano — 2002
• Wybrane aspekty racjonalizacji systemów przewozowych w łańcuchu dostaw przy ograniczonych zasobachDariusz Pyza — 2011
• Optimization-Oriented Global ConstraintsFilippo Focacci, Andrea Lodi, Michela Milano — 2002
• Operations research techniques in constraint programmingvan Hoeve — 2005
• Polyhedral results and exact algorithms for the asymmetric travelling salesman problem with replenishment arcsVicky Mak‐Hau, Natashia Boland — 2007
• The traveling salesman problem: An overview of exact and approximate algorithmsGilbert Laporte — 1992
• A lift-and-project cutting plane algorithm for mixed 0–1 programsEgon Balas, Sebastián Ceria, Gérard Cornuéjols — 1993
• An exact algorithm for the capacitated shortest spanning arborescencePaolo Toth, Daniele Vigo — 1995
• Cluster based branching for the asymmetric traveling salesman problemJens Lysgaard — 1999
• Models, relaxations and exact approaches for the capacitated vehicle routing problemPaolo Toth, Daniele Vigo — 2002
• Exact Solution of Large Asymmetric Traveling Salesman ProblemsDonald L. Miller, Joseph F. Pekny — 1991
• A heuristic algorithm for the asymmetric capacitated vehicle routing problemDaniele Vigo — 1996

Related papers

• Cycles Merging Algorithm for Metric Maximum Traveling Salesman ProblemАнатолий Васильевич Панюков, Юлия Федоровна Леонова — 2021
• The travelling salesman problemKaja Zupanc — 2012
• An Approximation Algorithm for the Maximum Traveling Salesman ProblemA.Yu. Evnin, N.I. Yusova — 2017
• Design of a Decision Support System for Performance Appraisal of Civil Servants with a Fuzzy Multi Attribute Decision Making ModelM. Syahputra — 2020
• Approximation Algorithm for the Traveling Salesman ProblemRoland Forson — 2017
• A New Exact Algorithm for Traveling Salesman Problem with Time Complexity Interval (O(n^4), O(n^3*2^n))Yunpeng Li — 2014
• Hybrid Parallel Genetic Algorithm for Traveling Salesman ProblemKi-Tae Kim, Geon-Wook Jeo — 2011
• An empirical investigation into randomly generated Euclidean symmetric traveling salesman problemsMegha Sharma, Diptesh Ghosh — 2006
• The approximation ratio of the greedy algorithm for the metric traveling salesman problemJudith Brecklinghaus, Stefan Hougardy — 2014
• A SOLUTION METHOD FOR THE TRAVELING SALESMAN N PERSON M TOWN PROBLEM (TSP(N/M)) USING THE GENETIC ALGORITHMYutaka Karasawa, Yusa Matsuda, Aiura, Nobunori — 1997