CS Paper Radar

An Island-Based Parallel Biased Random-Key Genetic Algorithm for the Three-Dimensional Trailer Loading Problem

A. del Río, L. Díaz, L. C. de Vicente, J. Cameselle, B. Fernández

cs.NE cs.DCmath.OC ·submitted 2026-09-30 08:24 UTC · v1
unusual

Abstract

The Three-Dimensional Trailer Loading Problem (3D-TLP) involves determining the optimal placement and orientation of heterogeneous items within the confined space of a trailer while maximizing volume utilization and satisfying a wide range of complex logistical and safety constraints. The 3D-TLP is NP-hard, rendering exact optimization approaches computationally impractical for large-scale industrial applications. To address this challenge, we propose an enhanced Biased Random-Key Genetic Algorithm (BRKGA) accelerated through a novel island-based parallelization framework, PANGEA. The proposed method combines the search efficiency and robustness of BRKGA with a multi-population evolutionary scheme for genetic algorithms. This island-model strategy promotes population diversity, mitigates premature convergence, and significantly reduces computational times. The proposed solution was validated in a real trailer loading process, providing an effective solution approach for real-world large-scale logistics.

Closest papers

Nearest neighbours by meaning across the whole index.

Node-Shift-Encoding Genetic Algorithm with fuzzy-enhanced reference tour to solve the bi-objective service-oriented TSP

cs.CE ·2026-09-10 ·Souad Abdoune, Menouar Boulif
similarity 0.53
Abstract · 22 pages, 13 figures

The Travelling Salesman Problem (TSP) remains a key area of research in combinatorial optimization, with applications in logistics, manufacturing, and service delivery. This paper addresses a bi-objective service-oriented TSP in which the clients' ranks in the delivery path matter. Unlike conventional depot-based TSP formulations, the considered problem does not assume a distinguished depot or a fixed tour origin. To address this setting, we adapt the Miller--Tucker--Zemlin (MTZ)-based formulation and derive an original linearization of the resulting model, enabling its solution with off-the-shelf integer linear programming solvers. This adaptation avoids the rigid tour origin imposed by the conventional MTZ formulation, for which fixing the starting node does not affect the tour cost but can affect the objective in a customer-rank-sensitive TSP. To solve this problem, we present a Node-Shift-Encoding (NSE)-based Genetic Algorithm augmented with fuzzy reasoning to update the reference tour throughout the evolutionary process. Experimental evaluation on TSPLIB benchmarks demonstrates that the proposed method achieves improved performance compared with the classical NSE approach.

0.25

Insights from Multi-tasking the EAX Algorithm for the Travelling Salesperson Problem

cs.NE ·2026-08-13 ·Liam Wigney, Aneta Neumann, Yew-Soon Ong, Frank Neumann
top venue similarity 0.53
Abstract

Evolutionary multitasking allows several related problems to be solved in a single run of an algorithm. In this paper, we investigate integrating evolutionary multitasking with Edge Assembly Crossover (MT-EAX) to solve the classical Travelling Salesperson Problem (TSP). To fairly compare MT-EAX against standard EAX under strict compute budgets, we evaluate three scaling methods: generation scaling, population scaling, and balanced scaling. Our results show that generationally scaled MT-EAX is highly effective compute-wise in the early stages of the search, saving $60\%$ to $90\%$ of compute for equal or better solution quality. We observe that instance geometry has a significant impact, with clustered, normally distributed instances securing larger improvements than uniformly distributed ones. However, when scaling by population or utilising explicit solution transfer, the results are negative due to population starvation and incompatible cross-instance parent selection. We demonstrate that the advantage of MT-EAX derives from increased diversity through parallel search in early generations, which can be successfully preserved using a decoupled configuration to often strictly outperform or match standard EAX performance at final convergence.

0.29

A Graph Neural Network--Guided Genetic Algorithm for Physical Internet Supply Chain Optimization under Cost Uncertainty

cs.NE cs.LG ·2026-08-10 ·Faezeh Ardali, Gerald M. Knapp
published similarity 0.53
Abstract · 6 pages

Inventory and distribution planning in Physical Internet networks requires coordinating factory-hub assignments, factory supply, lateral transshipment among collaborative hubs, retailer deliveries, and shortages. The problem combines discrete assignment decisions with interdependent continuous flows, while uncertain operating costs make robust planning more difficult. This study formulates deterministic and min-max regret models for a three-echelon network of factories, hubs, and retailers and develops a graph neural network-guided genetic algorithm (GNN-GA) for the assignment decisions. The GNN estimates hub-specific factory-selection probabilities that are used to construct the initial GA population and adapt mutation according to prediction uncertainty. Each previously unseen candidate assignment is evaluated by solving the remaining continuous-flow problem to LP optimality. Simulated annealing, a standard GA, and GNN-GA are compared on 15 instances using matched random seeds and fixed limits on distinct assignment evaluations. Because the evaluation budgets for test Instances 13-15 are smaller than the nominal population size, these experiments primarily assess the quality of learned initialization rather than multi-generation evolutionary search. A separate 400-evaluation experiment on exact test Instance 13 permits three complete offspring generations and a partial fourth pass, with GNN-GA outperforming GA in all 10 matched runs. Three independently generated exact-solvable instances provide a separate test of transfer. Ablation results show that learned initialization provides most of the improvement, while entropy-guided mutation has a smaller, instance-dependent effect. Per-instance solution times include GNN inference and search but exclude model training and one-time model setup.

0.24

Evolutionary Giant Tour for CVRP using NSE and ML Heuristic]{Evolutionary Giant Tour approach for CVRP using Node Shift Encoding and Machine Learning repair heuristic

cs.NE ·2026-10-01 ·Souad Abdoune, Menouar Boulif
benchmark similarity 0.53
Abstract · 21 pages, 16 figures

The Capacitated Vehicle Routing Problem (CVRP) remains a central concern in logistics research, as route optimisation under rigid capacity and fleet restrictions directly affects operational performance. Genetic Algorithms are widely used for this problem, yet their effectiveness depends heavily on the choice of solution encoding and on the mechanisms used to preserve feasibility during the search. This paper proposes a sequential framework that separates the evolutionary process from route construction. We adapt Node Shift Encoding (NSE) to the CVRP giant-tour setting and benchmark it against Path Representation and Double Chromosome. We further propose an unsupervised machine-learning repair heuristic that restores fleet feasibility after an unconstrained linear split, and compare this pipeline against fleet-constrained split taken from the literature. Computational tests on standard benchmark instances show that NSE consistently outperforms the other encodings in solution quality and feasibility. The repair heuristic restores feasibility in approximately 72\% of cases, and the Linear-Split-ML-Heuristic pipeline proves more robust than the constrained split, delivering lower costs and higher feasibility rates.

0.28

Hybrid GA/MSDLO Approach to Solve a Greenfield Robotized Machine Tending Layout

cs.CE ·2026-09-29 ·Ramez Awad, Joshua Beck
published similarity 0.52
Abstract · Accepted for publication at "Hybrid GA/MSDLO Approach to Solve a Greenfield Robotized Machine Tending Layout", 19th CIRP Conference on Intel…

Meta-heuristics like genetic algorithms (GAs) effectively explore solution spaces but often yield suboptimal results and are sensitive to parameter tuning. In contrast, the mass-spring-damper layout optimization (MSDLO) method is fast and excels in locally optimizing resource arrangements, though its effectiveness depends on the initial resource placement. This paper first employs genetic algorithms to establish an optimal resource placement in a greenfield layout. We then apply MSDLO to fine-tune the positions and orientations of these resources. The results are presented and discussed, highlighting this approach's practicality in effectively addressing industry needs.

0.43

Fine-Grain GPU Parallelization of the Generalized Partition Crossover for Large-Scale Traveling Salesman Problems

cs.AI cs.NE ·2026-08-21 ·Swetha Varadarajan, Darrell Whitley
publishedbenchmark similarity 0.51
Abstract · accepted to NiHPC, PPSN 2026. Draft in preparation for a journal article

The Traveling Salesman Problem (TSP) is one of the most extensively studied NP-hard optimization problems. Genetic Algorithm (GA)-based solvers, such as the Edge Assembly Crossover (EAX), achieve state-of-the-art performance on many benchmark instances. However, the scalability of these approaches in massively parallel architectures remains limited because crossover operations involve irregular memory access patterns, graph traversals, and sequential dependencies. Existing GPU-based TSP solvers primarily exploit population-level parallelism and are limited to relatively small problem sizes. This work presents a fine-grain GPU implementation of the partition phase of the Generalized Partition Crossover (GPX) operator for large-scale TSP instances. The proposed approach reformulates GPX partitioning as a graph-parallel problem using coalesced memory layouts, ghost-node transformations, and connected-component analysis. The im- plementation parallelizes the union of parent tours, the splitting of degree- four vertices, the deletion of common edges, and the identification of recombining components using CUDA. Experimental results on instances ranging from 10,000 to 2 million cities demonstrate substantial acceleration over a naive sequential CPU imple- mentation. The proposed GPU partitioning achieves speedups between 48x and 625x while significantly reducing memory overhead. The re- sults demonstrate that operator-level parallelism can substantially im- prove the scalability of GA-based TSP solvers on modern many-core architectures.

0.29

Matrix-Based Ant Colony Search with Batched Decoding for Hierarchical Replenishment Routing: A Stylized Case Study Based on Korean City Data

cs.NE cs.AIcs.CEmath.OC ·2026-11-11 ·Jun Zhang, Wei-Jie Yu, Tong Qian, Eui Jeong Kwak, Sang-Woon Jeon +5 more
benchmark similarity 0.49
Abstract · 9 pages, 6 figures, 4 tables; code, data and raw records in the ancillary files

We study a stylized single-vehicle replenishment-routing problem in which the cities of a national logistics network are both demand points and supply points: a vehicle of limited capacity delivers to every city once, and when its load is insufficient for the next city it must detour to a city already served that can still supply goods. A 100-node benchmark is built from Korean population and geographic data, with the cities divided into 10 levels; the per-visit supply coefficient and the allowed number of stops decrease geometrically with the level. Building on matrix-based ant colony optimization, we keep the states of the whole colony in arrays, couple route construction with a fixed greedy replenishment-decoding policy, and evaluate the candidate moves of a local search in batches. With frozen parameters and 30 runs on seeds never used for tuning, the matrix-based ant colony search with the batch local search (MACO) reaches a mean total distance of 3081.7 km; a genetic algorithm equipped with the same local search at the same frequency reaches 3074.9 km (no significant difference), and a MAX-MIN ant system with the same local search 3142.2 km. Ablation identifies the batch local search as the main contributor to solution quality; a load-aware transition factor gives no significant gain. Within the parameter ranges tested, raising the supply coefficients of the cities below the top level shortens the route more than relaxing the stop limits, which are not binding here.

0.24

Holistic Diversity Management in LLM-Guided Evolutionary Search

cs.CL ·2026-10-28 ·Seockbean Song, Youngsik Yoon, Sungjae Lee, Siwei Wang, Wei Chen +1 more
similarity 0.49
Abstract

LLM-guided evolutionary search iteratively selects existing programs, uses LLMs as mutation operators to generate a new program, and evaluates it to guide subsequent search. To preserve diversity and reduce the risk of premature convergence, it often adopts the island model, in which groups of programs, called islands, evolve separately. However, this structure alone does not guarantee distinct search directions, as islands may start from similar programs or converge toward similar solutions during evolution. This suggests that diversity must be considered throughout the search process, from initializing islands with distinct programs to developing island trajectories and sharing discoveries across islands. To this end, we propose HoliDivEvolve , a holistic approach to establishing and effectively utilizing island diversity throughout evolutionary search. Specifically, we introduce diverse initialization to establish different initial programs, trajectory adaptive island selection to allocate computation based on current score, recent growth, and the remaining search budget, and growth adaptive migration to share alternative ideas across islands. Experiments across diverse benchmarks show that HoliDivEvolve achieves competitive performance on most evaluated tasks. We further conduct controlled analyses to examine how our design choices affect search behavior and final performance.

0.21