The pickup and delivery problem: Faces and branch-and-cut algorithm

DOI10.1016/S0898-1221(97)00090-4zbMath0894.90128OpenAlexW1980244058MaRDI QIDQ1368475

K. S. Ruland, Ervin Y. Rodin

Publication date: 7 September 1998

Published in: Computers \& Mathematics with Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0898-1221(97)00090-4

zbMATH Keywords

valid inequalitiesbranch-and-cutpickup and delivery problempolyhedral structuredial-aride problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Integer programming (90C10) Combinatorial optimization (90C27)

Related Items (26)

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 ⋮ Static pickup and delivery problems: a classification scheme and survey. (With comments and rejoinder) ⋮ A branch‐and‐cut algorithm for the pickup and delivery traveling salesman problem with multiple stacks ⋮ The time-dependent capacitated profitable tour problem with time windows and precedence constraints ⋮ Interrelated trips in the rural dial-a-ride problem with autonomous vehicles ⋮ The dial-a-ride problem with private fleet and common carrier ⋮ A branch‐and‐cut algorithm for the pickup‐and‐delivery traveling salesman problem with handling costs ⋮ An Additive Branch-and-Bound Algorithm for the Pickup and Delivery Traveling Salesman Problem with LIFO or FIFO Loading ⋮ A multi-commodity, capacitated pickup and delivery problem: the single and two-vehicle cases ⋮ Mobility allowance shuttle transit (MAST) services: MIP formulation and strengthening with logic constraints ⋮ Recent Models and Algorithms for One-to-One Pickup and Delivery Problems ⋮ A GRASP with adaptive large neighborhood search for pickup and delivery problems with transshipment ⋮ EFFICIENT NEIGHBORHOOD SEARCH FOR THE PROBABILISTIC MULTI-VEHICLE PICKUP AND DELIVERY PROBLEM ⋮ Counting feasible solutions of the traveling salesman problem with pickups and deliveries is \#\(P\)-complete ⋮ Dynamic optimization of the operation of single-car elevator systems with destination hall call registration. II: The solution algorithm ⋮ A heuristic two-phase solution approach for the multi-objective dial-a-ride problem ⋮ A branch-and-cut algorithm for the pickup and delivery traveling salesman problem with LIFO loading ⋮ The pickup and delivery traveling salesman problem with first-in-first-out loading ⋮ Decision diagrams for solving traveling salesman problems with pickup and delivery in real time ⋮ Strong cuts from compatibility relations for the dial-a-ride problem ⋮ The multi-commodity one-to-one pickup-and-delivery traveling salesman problem ⋮ The pickup and delivery problem with transfers: formulation and a branch-and-cut solution method ⋮ Branch-and-cut for the pickup and delivery traveling salesman problem with FIFO loading ⋮ Pickup and delivery problem with incompatibility constraints ⋮ Elevator dispatching problem: a mixed integer linear programming formulation and polyhedral results

Uses Software

• MINTO

Cites Work

• Unnamed Item
• Facet identification for the symmetric traveling salesman polytope
• The pickup and delivery problem with time windows
• MINTO, a Mixed INTeger Optimizer
• Survey of facial results for the traveling salesman polytope
• The graphical relaxation: A new framework for the symmetric traveling salesman polytope
• k-interchange procedures for local search in a precedence-constrained routing problem
• Clique Tree Inequalities and the Symmetric Travelling Salesman Problem
• A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems
• Optimizing Single Vehicle Many-to-Many Operations with Desired Delivery Times: I. Scheduling
• Optimizing Single Vehicle Many-to-Many Operations with Desired Delivery Times: II. Routing
• The Crown Inequalities for the Symmetric Traveling Salesman Polytope
• Exact And Heuristic Procedures For The Traveling Salesman Problem With Precedence Constraints, Based On Dynamic Programming
• The General Pickup and Delivery Problem
• Solution of a Large-Scale Traveling-Salesman Problem

This page was built for publication: The pickup and delivery problem: Faces and branch-and-cut algorithm