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

DOI10.1111/ITOR.12876MaRDI QIDQ6071059zbMATH OpenOpenAlexFDO

Authors Jonatas B. C. Chagas, Túlio A. M. Toffolo, M. J. F. Souza, Manuel Iori

Publication date 27 November 2023

Published in International Transactions in Operational Research (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1908.08494

zbMATH Keywords

genetic algorithmloading constraintsmathematical modelspartial reloadingpickup and delivery

Mathematics Subject Classification ID

Operations research, mathematical programming (90-XX)

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 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.

Recommendations

• A metaheuristic for the double traveling salesman problem with partial last‐in‐first‐out loading constraints
• Multiple pickup and delivery traveling salesman problem with last-in-first-out loading and distance constraints
• A branch-and-bound algorithm for the double travelling salesman problem with two stacks
• Approximation of the double traveling salesman problem with multiple stacks
• The double travelling salesman problem with multiple stacks - formulation and heuristic solution approaches
• Exact solutions to the double travelling salesman problem with multiple stacks
• Efficient algorithms for the double traveling salesman problem with multiple stacks
• The pickup and delivery traveling salesman problem with first-in-first-out loading
• Polyhedral results and a branch-and-cut algorithm for the double traveling salesman problem with multiple stacks
• The double traveling salesman problem with multiple stacks: A variable neighborhood search approach

Cites work

• A biased random-key genetic algorithm for the unequal area facility layout problem
• A branch-and-bound algorithm for the double travelling salesman problem with two stacks
• A branch-and-cut algorithm for the pickup and delivery traveling salesman problem with LIFO loading
• A branch-and-cut algorithm for the pickup and delivery traveling salesman problem with multiple stacks
• A dynamic programming based local search approach for the double traveling salesman problem with multiple stacks
• A parallel multi-population biased random-key genetic algorithm for a container loading problem
• A variable neighborhood search heuristic algorithm for the double vehicle routing problem with multiple stacks
• An Additive Branch-and-Bound Algorithm for the Pickup and Delivery Traveling Salesman Problem with LIFO or FIFO Loading
• An exact method for the double TSP with multiple stacks
• Biased random-key genetic algorithms with applications in telecommunications
• Efficient algorithms for the double traveling salesman problem with multiple stacks
• Exact algorithms for the double vehicle routing problem with multiple stacks
• Exact solutions to the double travelling salesman problem with multiple stacks
• Formulations and algorithms for the pickup and delivery traveling salesman problem with multiple stacks
• scientific article; zbMATH DE number 5829047 (Why is no real title available?)
• scientific article; zbMATH DE number 1131224 (Why is no real title available?)
• Metaheuristics. From design to implementation.
• New formulation and branch-and-cut algorithm for the pickup and delivery traveling salesman problem with multiple stacks
• Non-elementary formulations for single vehicle routing problems with pickups and deliveries
• Polyhedral results and a branch-and-cut algorithm for the double traveling salesman problem with multiple stacks
• Routing problems with loading constraints
• The double traveling salesman problem with multiple stacks: A variable neighborhood search approach
• The double travelling salesman problem with multiple stacks - formulation and heuristic solution approaches
• The pickup and delivery traveling salesman problem with handling costs
• The traveling salesman problem. A computational study.
• The tree representation for the pickup and delivery traveling salesman problem with LIFO loading
• Variable neighborhood search for the pickup and delivery traveling salesman problem with LIFO loading

Cited in

(2)

• A branch‐and‐price‐based heuristic for the vehicle routing problem with two‐dimensional loading constraints and time windows
• Biased random-key genetic algorithms: a review

This page was built for publication: The double traveling salesman problem with partial last‐in‐first‐out loading constraints

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6071059)