Jul 2026· Proceedings of the Genetic and Evolutionary Computation Conference Companion· pp. 1277-1284· 0 citations· 10 references
TL;DR
A systematic empirical evaluation of the nested neighborhood structures demonstrates that the N8-based LS consistently outperforms other structures in terms of makespan reduction, and substantiates the practical utility of the nested neighborhood design, establishing the N8 structure as a potent intensification tool for manufacturing scheduling.
Abstract
The Job-shop Scheduling Problem (JSSP) is a classical combinatorial optimization problem with significant implications for modern high-mix, low-volume manufacturing. Given its NP-hard complexity, local search based on critical-path-oriented neighborhood structures—specifically N5 through N8—has become a cornerstone of state-of-the-art metaheuristics. However, while existing literature focuses on their integration into complex frameworks like Tabu Search, their performance as standalone, basic local search (LS) is not yet fully understood. This obscures whether their efficacy is intrinsic to the neighborhood structures or dependent on the metaheuristic framework. Moreover, as these neighborhoods are nested, the incremental contribution of each additional move operator to objective function improvement has not been rigorously quantified. This paper presents a systematic empirical evaluation of the neighborhoods to elucidate their standalone effectiveness. Through extensive computational experiments on 28 standard benchmark instances, we comprehensively evaluate the impact of typical improvement strategies and neighborhood evaluation orders on search performance. Our findings demonstrate that the N8-based LS consistently outperforms other structures in terms of makespan reduction. Furthermore, a contribution analysis substantiates the practical utility of the nested neighborhood design, establishing the N8 structure as a potent intensification tool for manufacturing scheduling.
The bin packing problem (BPP) is a well-known NP-hard combinatorial optimization problem with long-standing relevance in logistics and manufacturing. In this paper, we address limitations of Ant Colony Optimization (ACO) when applied to the BPP. While ACO is a competitive approach for this problem, it often suffers from premature convergence and insufficient exploitation of packing patterns. We propose a hybrid ACO approach that combines local search with a construction phase guided by frequent packing patterns extracted from elite solutions. Instead of relying solely on pheromone information, the algorithm explicitly exploits recurring item combinations that are empirically associated with good packings. Solution refinement is performed through a set of local improvement procedures, including a local branching-based intensification strategy that explores structured neighborhoods around high-quality solutions to reduce the number of bins further. The method was evaluated on several well-established benchmark sets, including Falkenauer, Scholl, Schwerin, and Wäscher instances, and compared with a Mixed Integer Programming (MIP) baseline and a Max-Min Ant System (MMAS). The results show higher success rates and more stable performance across independent runs, indicating that the proposed hybrid strategy improves solution quality for the BPP, while also achieving lower root mean square error and standard deviation.
C. Alves, Israel Mendonça, Pedro Henrique González· Proceedings of the Genetic a...· 0 citations
This paper investigates the scalability of a multi-criteria optimization for the Service Team Transport Scheduling (STTS) problem, minimizing total travel time, maximum vehicle worktime, and total vehicle engagement time. The mathematical model of the problem is provided. A simplified problem representation and two graph-based representations along with problem properties are formulated. Using these properties, we propose two complementary frameworks: a declarative Constraint Optimization Problem (COP) solved via Gurobi, and a metaheuristic Tabu Search (TS) incorporating a Constraint Satisfaction Problem (CSP) and an auxiliary greedy method for obtaining initial feasible solutions. Additionally, the population-based NSGA-II algorithm is implemented as an evolutionary baseline. The solving methods are evaluated under a strict 300-second operational limit using 280 realistic instances. The results reveal clear tractability thresholds. The COP solver obtains high-quality Pareto fronts but experiences a combinatorial collapse beyond 8 customer locations, hitting a 0% success rate for instances with size 15 or more. Conversely, the proposed hybrid CSP-TS framework demonstrate high robustness, maintaining a 90–100% operational success rate up to 50 locations. Specifically, the expansive large-neighborhood TS variant excels at medium scales (14–40 locations), while the compact small-neighborhood TS variant achieves the highest Hypervolume Indicator (HVI) at large scales (45 or more locations). Pure population-based approaches like NSGA-II are consistently outperformed by the specialized local search neighborhood structures. These quantitative findings define scale-aware algorithmic boundaries essential for real-time decision support systems.
Jarosław Rudy, G. Radzki· IEEE Access· 0 citations
Many real-world problems involve several objectives that conflict with each other. In such cases, the goal is not to find a single best solution, but a set of solutions that represent different trade-offs. Although parameterized complexity is a well-established framework for studying hard optimization problems, it has rarely been applied to multi-objective optimization. In this paper, we study the Multi-Objective Traveling Salesperson Problem (MO-TSP) from a parameterized complexity perspective. We focus on two common operators, namely 2-opt and swap. We consider restricted versions of these operators using a distance parameter r, and define (k,r)-neighborhoods that allow up to k applications of the operator. For both operators, we analyze the problem of finding an improved solution with respect to Pareto dominance. We prove that this problem is fixed-parameter tractable when parameterized by k, r, and the maximum edge weight W. These results provide new insight into the complexity of multi-objective optimization and show that parameterized analysis is a useful tool in this setting.
Narges Tavassoli Kejani, Julien Baste, Marie-Emilie Voge et al.· Proceedings of the Genetic a...· 0 citations
This paper compares six different strategies identified in a recent survey, categorizing them as either global strategies (GS), which treat the decision vector as a unified type, or decomposition-based strategies (DS), which split the problem into continuous and discrete subproblems.
Thomas Lang, Denis Pallez· Proceedings of the Genetic a...· 0 citations
This work investigates how balancing the number of decomposed subproblems and ants impacts performance under a fixed computational budget and introduces MOEA/D-AM, a hybrid algorithm that adapts this decomposition strategy for partial classification rule induction.
Adel Abdelkader Mokadem, Marie-Éléonore Kessaci, Laetitia Jourdan et al.· Proceedings of the Genetic a...· 0 citations
ABSTRACT Last-mile delivery-the final and most critical stage of fulfilling customer orders-is typically the most costly and time-consuming component of the distribution process. Optimizing this stage is therefore essential for improving the overall efficiency and sustainability of logistics operations. This study begins with a comprehensive review of the principal contributions to last-mile delivery optimization. Building on insights from existing models and metaheuristics, we propose a new two-level framework in which customers are served through distribution centers, ensuring that each customer location lies within a designated coverage area. The framework consists of two interconnected levels: depot to distribution center routing and distribution center to customer delivery. To support this structure, we develop a new optimization model and a Simulated Annealing-based metaheuristic inspired by the vehicle routing problem with time windows and tailored specifically to last-mile customer service operations. Computational results demonstrate that the proposed approach provides both economic benefits-through reduced travel distance-and environmental advantages through lower CO2 emissions. Moreover, the routing plan generated at the second level allows for the quantification of customer satisfaction-averaging 72.5% for the optimization model and 100% for the metaheuristic-thereby providing a more comprehensive and robust evaluation of delivery.
José Rodriguez-Melquiades· Pesquisa Operacional· 0 citations