Marko Đurasević

Leon Stjepan Uroić, Marko Đurasević

Permutation-based metaheuristics are widely used for electric vehicle routing, where candidate solutions are represented as ordered sequences of customers. Such sequences, however, do not directly define feasible vehicle routes: they must be decoded by choosing where to split the permutation into routes and where to insert charging-station visits, subject to cargo capacity and battery constraints. These decisions are inherently interdependent, since each return to the depot both separates consecutive routes and restores the vehicle battery. This paper formalizes the task as the Fixed-Permutation Splitting and Charging Problem and proposes an exact forward labeling algorithm that constructs a minimum-distance feasible decoding of a fixed customer permutation using dynamic programming with dominance pruning. We further derive restricted variants representing increasingly simplified decoding strategies: first separating route splitting from charging-station insertion, and then additionally limiting each inter-customer segment to at most one charging-station visit. Computational experiments on benchmark and randomly generated instances, including comparisons with heuristic decoders from the literature, confirm that the exact decoder remains tractable in practice and reveal a clear hierarchy among decoding strategies. The most restrictive variant achieves runtimes close to those of heuristic decoders while delivering substantially higher decoding success rates and better solution quality. Less restrictive variants further improve quality and robustness at the cost of additional runtime. The exact joint decoder provides the optimal reference for each fixed permutation, clarifying the trade-offs introduced by common decoding simplifications.

Ivan Milinović, Leon Stjepan Uroić, Marko Đurasević

The Electric Vehicle Routing Problem (EVRP) extends the capacitated vehicle routing problem by incorporating battery constraints and charging stations, posing significant optimization challenges. This paper introduces a Trilevel Memetic Algorithm (TMA) that hierarchically optimizes customer sequences, route assignments, and charging station insertions. The method combines genetic algorithms with dynamic programming, ensuring efficient and high-quality solutions. Benchmark tests on WCCI2020 instances show competitive performance, matching best-known results for small-scale cases. While computational demands limit scalability, TMA demonstrates strong potential for sustainable logistics planning.

Marko Đurasević, Domagoj Jakobović

Today scheduling problems have an immense effect on various areas of human lives, be it from their application in manufacturing and production industry, transportation, or workforce allocation. The unrelated parallel machines scheduling problem (UPMSP), which is only one of the many different problem types that exist, found its application in many areas like production industries or distributed computing. Due to the complexity of the problem, heuristic and metaheuristic methods are gaining more attention for solving it. Although this problem variant did not receive much attention as other models, recent years saw the increase of research dealing with this problem. During that time, many different problem variants, solution methods, or other interesting research directions were considered. However, no study has until now tried to systematise the research in which heuristic methods are applied for the UPMSP. The goal of this study is to provide an extensive literature review on the application of heuristic and metaheuristic methods for solving the UPMSP. The research was systematised and classified into several categories to enable an easy overview of the different problem and solution variants. Additionally, current trends and possible future research directions are also shortly outlined.