New formulation and branch-and-cut algorithm for the pickup and delivery traveling salesman problem with multiple stacks: new formulation and branch-and-cut algorithm

Research output: Contribution to journalArticleAcademicpeer-review

11 Citations (Scopus)

Abstract

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.
Original languageEnglish
Pages (from-to)77-98
Number of pages22
JournalInternational Transactions in Operational Research
Volume24
Issue number1-2
Early online date1 Jan 2016
DOIs
Publication statusPublished - 2017

Keywords

  • integer programming
  • transportation
  • traveling salesman
  • valid inequalities

Fingerprint

Dive into the research topics of 'New formulation and branch-and-cut algorithm for the pickup and delivery traveling salesman problem with multiple stacks: new formulation and branch-and-cut algorithm'. Together they form a unique fingerprint.

Cite this