  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 one 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, i.e., 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.
