The asymmetric traveling salesman problem with replenishment arcs
European Journal of Operational ResearchPublished 1 June 2000
Natashia Boland, Lloyd W. Clarke, George L. Nemhauser
Citations37
SJR quartileQ1
SJR score2.24
SNIP2.62
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
A constrained asymmetric traveling salesman problem with knapsack-like constraints on subpaths of the tour with an exponential number of variables that correspond to feasible sub paths is considered and a branch- and-price-and-cut algorithm for solving it is presented.
Abstract
We consider a constrained asymmetric traveling salesman problem with knapsack-like constraints on subpaths of the tour. This problem arises in routing aircraft. We formulate the problem with an exponential number of variables that correspond to feasible subpaths. We study certain polyhedral aspects of the reformulation and present a branch-and-price-and-cut algorithm for solving it. We test the algorithm on both random instances and real instances that arise in the airline application.
Keywords
Engineering
Journal of the Operational Research SocietyInteger and Combinatorial Optimization
5,548 Citations1990H. P. Williams, George L. Nemhauser +1 more
Operations ResearchBranch-and-Price: Column Generation for Solving Huge Integer Programs
2,189 Citations1998Cynthia Barnhart, Ellis L. Johnson +3 more
This work discusses formulations of integer programs with a huge number of variables and their solution by column generation methods, i.e., implicit pricing of nonbasic variables to generate new columns or to prove LP optimality at a node of the branch-and-bound tree and presents classes of models for which this approach decomposes the problem, provides tighter LP relaxations, and eliminates symmetry.
Journal of Research of the National Bureau of Standards Section B Mathematics and Mathematical PhysicsMaximum matching and a polyhedron with 0,1-vertices
1,723 Citations1965Jack Edmonds
The emphasis in this paper is on relating the matching problem to the theory of continuous linear programming, and the algorithm described does not involve any "blind-alley programming" -which, essentially, amounts to testing a great many combinations.
Journal of the Operational Research SocietyThe Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization
1,701 Citations1986
Operations ResearchA New Optimization Algorithm for the Vehicle Routing Problem with Time Windows
1,180 Citations1992Martin Desrochers, Jacques Desrosiers +1 more
This paper presents a new optimization algorithm capable of optimally solving 100-customer problems of the vehicle routing problem with time windows VRPTW and indicates that this algorithm proved to be successful on a variety of practical sized benchmark VRPTw test problems.
Mathematical programming studiesLagrangean relaxation for integer programming
1,089 Citations1974Arthur M. Geoffrion
Bulletin of the London Mathematical SocietyINTEGER AND COMBINATORIAL OPTIMIZATION
1,042 Citations1989David Connolly
Lagrangian Relaxation for Integer Programming
978 Citations2009Arthur M. Geoffrion
It is a pleasure to write this commentary because it offers an opportunity to express my gratitude to several people who helped me in ways that turned out to be essential to the birth of [8].
NetworksAlgorithms for finding paths with multiple constraints
395 Citations1984Jeffrey M. Jaffe
Two approaches to meeting or approximating the length and weight constraints are given and an objective function is defined which evaluates a path's distance from meeting the constraints.
Transportation ScienceFlight String Models for Aircraft Fleeting and Routing
365 Citations1998Cynthia Barnhart, Natashia Boland +4 more
A single model and solution approach is presented to solve simultaneously the fleet assignment and aircraft routing problems and is robust in that it can capture costs associated with aircraft connections and complicating constraints such as maintenance requirements.
Handbooks in operations research and management scienceChapter 2 Time constrained routing and scheduling
361 Citations1995Jacques Desrosiers, Yvan Dumas +2 more
Computational Optimization and ApplicationsSolving binary cutting stock problems by column generation and branch-and-bound
222 Citations1994Pamela H. Vance, Cynthia Barnhart +2 more
An algorithm is presented that employs both column generation and branch-and-bound to obtain optimal integer solutions for the binary cutting stock problem and a branching rule is formulated that can be incorporated into the subproblem to allow column generation at any node in the branch- and-bound tree.
Annals of Operations ResearchThe aircraft rotation problem
207 Citations1997Lloyd W. Clarke, Ellis Johnson +2 more
The aircraft rotation problem (ARP) is solved by Lagrangian relaxation and subgradient optimi-zation and computational results on real data from a major airline are presented.
European Journal of Operational ResearchA new approach for crew pairing problems by column generation with an application to air transportation
204 Citations1988Sylvie Lavoie, Michel Minoux +1 more
Operations ResearchAirline Crew Scheduling: A New Formulation and Decomposition Algorithm
185 Citations1997Pamela H. Vance, Cynthia Barnhart +2 more
This paper presents a new model based on breaking the decision process into two stages, which provides a tighter linear programming bound than that of the conventional set partitioning formulation but is more difficult to solve.
RePEc: Research Papers in EconomicsA faster algorithm for finding the minimum cut in a graph
102 Citations1992Jianxiu Hao, James B. Orlin
This work considers the problem of finding the minimum capacity cut in a network G with n nodes, and shows how to reduce theRunning time of these 2n - 2 maximum flow algorithms to the running time for solving a single maximum flow problem.
Mathematical ProgrammingAn analytical comparison of different formulations of the travelling salesman problem
90 Citations1991Manfred Padberg, Ting‐Yi Sung
This result is used to analytically compare various formulations of the asymmetric travelling salesman problem to the standard formulation due to Dantzig, Fulkerson and Johnson which are shown to be “weaker formulations” in a precise setting.
Mathematical ProgrammingA lifting procedure for the asymmetric traveling salesman polytope and a large new class of facets
53 Citations1993Egon Balas, Matteo Fischetti
A general procedure for identifying new classes of facet inducing inequalities for P(G) by lifting inequalities that are facet inducing forP(G′), whereG′ is some induced subgraph ofG.
Handbooks in operations research and management scienceChapter II Linear programming
47 Citations1989Donald Goldfarb, Michael J. Todd