Double traveling salesman problem with partial last-in-first-out loading constraintsThis page provides supplementary material related to the research paper:
Abstract: In this paper, we introduce the Double Traveling Salesman Problem with Partial Last-In-First-Out Loading Con-straints (DTSPPL). It is a pickup-and-delivery single-vehicle routing problem, where all pickup operations mustbe performed before any delivery one because the pickup and delivery areas are geographically separated. Thevehicle collects items in the pickup area and loads them into its container, a horizontal stack. After performing allpickup operations, the vehicle begins delivering the items in the delivery area. Loading and unloading operationsmust obey a partial Last-In-First-Out (LIFO) policy, i.e., a version of the LIFO policy that may be violated within agiven reloading depth. The objective of the DTSPPL is to minimize the total cost, which involves the total distancetraveled by the vehicle and the number of items that are unloaded and then reloaded due to violations of the stan-dard LIFO policy. We formally describe the DTSPPL through two Integer Linear Programming (ILP) formulationsand 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. Keywords: Pickup and delivery; Loading constraints; Partial reloading; Mathematical models; Genetic algorithm. Supplementary material:
|
GOAL - Group of Optimization and Algorithms
Department of Computing | Federal University of Ouro Preto
Campus Morro do Cruzeiro | 35400-000 | Ouro Preto - MG, Brazil
Phone: +55 31 3559-1692 | toffolo[ at ]iceb.ufop.br