Premium
New formulation and branch‐and‐cut algorithm for the pickup and delivery traveling salesman problem with multiple stacks
Author(s) -
Sampaio Afonso H.,
Urrutia Sebastián
Publication year - 2016
Publication title -
international transactions in operational research
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.032
H-Index - 52
eISSN - 1475-3995
pISSN - 0969-6016
DOI - 10.1111/itor.12261
Subject(s) - pickup , travelling salesman problem , mathematical optimization , computer science , stack (abstract data type) , branch and cut , traveling purchaser problem , 2 opt , fifo and lifo accounting , container (type theory) , representation (politics) , bottleneck traveling salesman problem , integer programming , algorithm , mathematics , engineering , artificial intelligence , image (mathematics) , mechanical engineering , politics , fifo (computing and electronics) , law , political science , computer hardware , programming language
In this paper, we consider the pickup and delivery traveling salesman problem with multiple stacks in which a single vehicle must serve a set of customer requests defined by a pair of pickup and delivery destinations of an item. The vehicle contains a fixed number of stacks, where each item is loaded at a pickup location and unloaded at the corresponding delivery location. Each stack has finite capacity, and its loading and unloading sequence must follow the last‐in‐first‐out (LIFO) policy, that is, for each stack, just the last item loaded can be unloaded at its corresponding delivery location. We propose a new integer programming formulation for this problem with a polyhedral representation described by exponentially many inequalities and a branch‐and‐cut algorithm for solving the proposed formulation. Computational results show that our approach is competitive with the best algorithm in the literature. Also, three new certificates of optimality are provided and several optimality gaps are reduced.