A metaheuristic for the double traveling salesman problem with partial last-in-first-out loading constraints

Blas Mardones, Gustavo Gatica, Carlos Contreras-Bolton

Research output: Contribution to journalArticlepeer-review

3 Citations (Scopus)

Abstract

This paper addresses the double traveling salesman problem with partial last-in-first-out (LIFO) loading constraints. A vehicle picks up items in the pickup area and loads them into its container, a horizontal stack. Once all the pickup operations are done, the vehicle can deliver the items to the delivery area because pickup-and-delivery areas are geographically separated. Additionally, the loading and unloading operations also follow a partial LIFO policy. The aim is to find a Hamiltonian cycle that satisfies the loading and unloading policy described above in order to minimize the distance traveled by the vehicle in both areas and the cost of the rearrangements that are performed across the routes. The state-of-the-art algorithm finds good solutions to the existing instances. However, finding good-quality solutions in large instances requires longer computing times. Therefore, we propose an iterated local search that considers two additional components to the classical components, the intensification and restart procedure. The first helps in a more thorough examination of promising neighborhoods, while the second helps in the complete diversity of the solutions in the hopes of escaping the local optima. Moreover, a new unique decoding approach for the solution representation is proposed to effectively generate feasible solutions. The proposed algorithm's performance is evaluated on an existing set of instances and in two new additional sets of larger instances that are proposed. The computational results obtained on the three test sets show that the proposed algorithm outperforms the state-of-the-art algorithm in terms of computing time required to find good-quality solutions.

Original languageEnglish
Pages (from-to)3904-3929
Number of pages26
JournalInternational Transactions in Operational Research
Volume30
Issue number6
DOIs
Publication statusPublished - Nov 2023

Keywords

  • iterated local search
  • loading constraints
  • metaheuristic
  • partial reloading
  • pickup and delivery

ASJC Scopus subject areas

  • Business and International Management
  • Computer Science Applications
  • Strategy and Management
  • Management Science and Operations Research
  • Management of Technology and Innovation

Fingerprint

Dive into the research topics of 'A metaheuristic for the double traveling salesman problem with partial last-in-first-out loading constraints'. Together they form a unique fingerprint.

Cite this