The precedence-constrained asymmetric traveling salesman polytope

DOI10.1007/BF01585767zbMath0835.90109MaRDI QIDQ1890926

Matteo Fischetti, Egon Balas, William R. Pulleyblank

Publication date: 28 May 1995

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

zbMATH Keywords

traveling salesmanvalid inequalitiesprecedence constraintspolynomial time separation algorithmsprecedence-constrained directed graph

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Related Items (47)

New tighter polynomial length formulations for the asymmetric traveling salesman problem with and without precedence constraints ⋮ Tree based models and algorithms for the preemptive asymmetric Stacker Crane problem ⋮ The traveling salesman problem with pickup and delivery: Polyhedral results and a branch-and-cut algorithm ⋮ Stronger multi-commodity flow formulations of the (capacitated) sequential ordering problem ⋮ A branch-and-cut algorithm for the preemptive swapping problem ⋮ An integer programming approach for the time-dependent traveling salesman problem with time windows ⋮ What are the worst cases in constrained last-in-first-out pick-up and delivery problems? ⋮ Formulations and algorithms for the pickup and delivery traveling salesman problem with multiple stacks ⋮ The multiple Steiner TSP with order constraints: complexity and optimization algorithms ⋮ Load-dependent and precedence-based models for pickup and delivery problems ⋮ On due-date based valid cuts for the sequential ordering problem ⋮ A branch‐and‐cut algorithm for the pickup and delivery traveling salesman problem with multiple stacks ⋮ Exact algorithms for the multi-pickup and delivery problem with time windows ⋮ Coupling ant colony systems with strong local searches ⋮ Valid inequalities and branch-and-cut algorithm for the pickup and delivery traveling salesman problem with multiple stacks ⋮ A branch‐and‐cut algorithm for the pickup‐and‐delivery traveling salesman problem with handling costs ⋮ A branch-and-cut algorithm for the generalized traveling salesman problem with time windows ⋮ A hybrid particle swarm optimization approach for the sequential ordering problem ⋮ Precedence constrained generalized traveling salesman problem: polyhedral study, formulations, and branch-and-cut algorithm ⋮ A branch-and-cut algorithm for factory crane scheduling problem ⋮ Reachability cuts for the vehicle routing problem with time windows ⋮ New formulation and branch-and-cut algorithm for the pickup and delivery traveling salesman problem with multiple stacks ⋮ A heuristic manipulation technique for the sequential ordering problem ⋮ Branch-and-bound for the precedence constrained generalized traveling salesman problem ⋮ New cutting-planes for the time- and/or precedence-constrained ATSP and directed VRP ⋮ The multi-pickup and delivery problem with time windows ⋮ Formulations and exact algorithms for the vehicle routing problem with time windows ⋮ Recent Models and Algorithms for One-to-One Pickup and Delivery Problems ⋮ Revisiting dynamic programming for precedence-constrained traveling salesman problem and its time-dependent generalization ⋮ A linear time algorithm for the \(3\)-neighbour travelling salesman problem on a Halin graph and extensions ⋮ Energy-efficient rail guided vehicle routing for two-sided loading/unloading automated freight handling system ⋮ IFORS' Operational Research Hall of Fame ⋮ The traveling salesman problem with draft limits ⋮ A branch-and-cut algorithm for the pickup and delivery traveling salesman problem with LIFO loading ⋮ Vehicle routing with endogenous learning: application to offshore plug and abandonment campaign planning ⋮ The pickup and delivery problem with split loads and transshipments: a branch-and-cut solution approach ⋮ A branch and cut algorithm for the time-dependent profitable tour problem with resource constraints ⋮ A new VRPPD model and a hybrid heuristic solution approach for e-tailing ⋮ The multi-commodity pickup-and-delivery traveling salesman problem ⋮ A Time Bucket Formulation for the Traveling Salesman Problem with Time Windows ⋮ An MDD-Based Lagrangian Approach to the Multicommodity Pickup-and-Delivery TSP ⋮ Strong cuts from compatibility relations for the dial-a-ride problem ⋮ The multi-commodity one-to-one pickup-and-delivery traveling salesman problem ⋮ Branch-and-cut for the pickup and delivery traveling salesman problem with FIFO loading ⋮ Elevator dispatching problem: a mixed integer linear programming formulation and polyhedral results ⋮ Improving dynamic programming for travelling salesman with precedence constraints: parallel Morin–Marsten bounding ⋮ Branch-and-refine for solving time-expanded MILP formulations

Cites Work

• Facet identification for the symmetric traveling salesman polytope
• A lifting procedure for asymmetric traveling salesman polytope and a large new class of facets
• Multi-Terminal Network Flows

This page was built for publication: The precedence-constrained asymmetric traveling salesman polytope