In this paper, we introduce the double traveling salesman problem with partial last-in-first-out loading constraints (DTSPPL). It is a pickup-and-delivery single-vehicle routing problem, where all pickup operations must be performed before any delivery operation because the pickup-and-delivery areas are geographically separated. The vehicle collects items in the pickup area and loads them into its container, a horizontal stack. After performing all pickup operations, the vehicle begins delivering the items in the delivery area. Loading and unloading operations must obey a partial last-in-first-out (LIFO) policy, that is, a version of the LIFO policy that may be violated within a given reloading depth. The objective of the DTSPPL is to minimize the total cost, which involves the total distance traveled by the vehicle and the number of items that are unloaded and then reloaded due to violations of the standard LIFO policy. We formally describe the DTSPPL through two integer linear programming (ILP) formulations and propose a heuristic algorithm based on the biased random-key genetic algorithm (BRKGA) to find high-quality solutions. The performance of the proposed solution approaches is assessed over a broad set of instances. Computational results have shown that both ILP formulations have been able to solve only the smaller instances, whereas the BRKGA obtained good-quality solutions for almost all instances, requiring short computational times.

The double traveling salesman problem with partial last-in-first-out loading constraints / Chagas, J. B. C.; Toffolo, T. A. M.; Souza, M. J. F.; Iori, M.. - In: INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH. - ISSN 0969-6016. - 29:(2020), pp. 2346-2373. [10.1111/itor.12876]

The double traveling salesman problem with partial last-in-first-out loading constraints

Iori M.
Membro del Collaboration Group
2020

Abstract

In this paper, we introduce the double traveling salesman problem with partial last-in-first-out loading constraints (DTSPPL). It is a pickup-and-delivery single-vehicle routing problem, where all pickup operations must be performed before any delivery operation because the pickup-and-delivery areas are geographically separated. The vehicle collects items in the pickup area and loads them into its container, a horizontal stack. After performing all pickup operations, the vehicle begins delivering the items in the delivery area. Loading and unloading operations must obey a partial last-in-first-out (LIFO) policy, that is, a version of the LIFO policy that may be violated within a given reloading depth. The objective of the DTSPPL is to minimize the total cost, which involves the total distance traveled by the vehicle and the number of items that are unloaded and then reloaded due to violations of the standard LIFO policy. We formally describe the DTSPPL through two integer linear programming (ILP) formulations and propose a heuristic algorithm based on the biased random-key genetic algorithm (BRKGA) to find high-quality solutions. The performance of the proposed solution approaches is assessed over a broad set of instances. Computational results have shown that both ILP formulations have been able to solve only the smaller instances, whereas the BRKGA obtained good-quality solutions for almost all instances, requiring short computational times.
20-set-2020
29
2346
2373
The double traveling salesman problem with partial last-in-first-out loading constraints / Chagas, J. B. C.; Toffolo, T. A. M.; Souza, M. J. F.; Iori, M.. - In: INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH. - ISSN 0969-6016. - 29:(2020), pp. 2346-2373. [10.1111/itor.12876]
Chagas, J. B. C.; Toffolo, T. A. M.; Souza, M. J. F.; Iori, M.
File in questo prodotto:
File Dimensione Formato  
1908.08494.pdf

accesso aperto

Descrizione: Versione pre print
Tipologia: Pre-print dell'autore (bozza pre referaggio)
Dimensione 1.21 MB
Formato Adobe PDF
1.21 MB Adobe PDF Visualizza/Apri
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

Licenza Creative Commons
I metadati presenti in IRIS UNIMORE sono rilasciati con licenza Creative Commons CC0 1.0 Universal, mentre i file delle pubblicazioni sono rilasciati con licenza Attribuzione 4.0 Internazionale (CC BY 4.0), salvo diversa indicazione.
In caso di violazione di copyright, contattare Supporto Iris

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11380/1210717
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? 2
social impact