Manuel Iori

Renan Fernando Franco da Silva, Vinícius Loti de Lima, Rafael C. S. Schouery et al.

Cutting and packing problems are fundamental in manufacturing and logistics, as they aim to minimize waste and improve efficiency. The Cutting Stock Problem (CSP) concerns material cutting, whereas the Bin Packing Problem (BPP) concerns packing items into bins. Since the 1960s, these problems have been widely studied because of their industrial relevance and computational complexity. Over time, exact algorithms, often based on mixed-integer programming (MIP), have become able to solve increasingly large instances, often with hundreds of items, within minutes. In 2016, Delorme et al. showed that the algorithm BELOV, combined with a modern version of CPLEX, could solve all benchmark instances available at that time within ten minutes. Motivated by this progress, they introduced two new classes of instances, AI and ANI, which proved extremely challenging for all exact solvers and have guided research on CSP and BPP over the past decade. Despite significant subsequent advances, 13 out of 500 of these instances remain unsolved by state-of-the-art algorithms within a one-hour time limit. In this paper, we show that although AI and ANI instances are particularly hard for MIP-based methods, the BPP restricted to these classes is not strongly NP-hard. We present polynomial-time algorithms for the AI class and pseudopolynomial-time algorithms for the ANI class. Our best algorithms solve all benchmark instances from these classes orders of magnitude faster than previous approaches. They are also straightforward to adapt to the Skiving Stock Problem (SSP), which can be seen as a counterpart of the CSP. Additionally, they can be used as preprocessing routines in exact methods, as their runtime is independent of the instance class, although they are guaranteed to return an optimality status only for instances belonging to the class for which they were designed.

Jonatas B. C. Chagas, Túlio A. M. Toffolo, Marcone J. F. Souza et al.

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.

Fábio Cruz, Anand Subramanian, Bruno P. Bruck et al.

The static bike rebalancing problem (SBRP) concerns the task of repositioning bikes among stations in self-service bike-sharing systems. This problem can be seen as a variant of the one-commodity pickup and delivery vehicle routing problem, where multiple visits are allowed to be performed at each station, i.e., the demand of a station is allowed to be split. Moreover, a vehicle may temporarily drop its load at a station, leaving it in excess or, alternatively, collect more bikes from a station (even all of them), thus leaving it in default. Both cases require further visits in order to meet the actual demands of such station. This paper deals with a particular case of the SBRP, in which only a single vehicle is available and the objective is to find a least-cost route that meets the demand of all stations and does not violate the minimum (zero) and maximum (vehicle capacity) load limits along the tour. Therefore, the number of bikes to be collected or delivered at each station should be appropriately determined in order to respect such constraints. We propose an iterated local search (ILS) based heuristic to solve the problem. The ILS algorithm was tested on 980 benchmark instances from the literature and the results obtained are quite competitive when compared to other existing methods. Moreover, our heuristic was capable of finding most of the known optimal solutions and also of improving the results on a number of open instances.