A Dual-population Evolutionary Algorithm for Multi-objective Vehicle Routing Problems with Three Dimensional Loading Constraints

The Capacitated Vehicle Routing Problems with Three-Dimensional Loading Constraints (3L-CVRPs) present significantly greater complexities when compared to the classical Capacitated Vehicle Routing Optimization Problems (CVRPs). This heightened complexity stems from the necessity to simultaneously address two intertwined objectives: optimizing vehicle routing and cargo loading configurations to maximize loading efficiency, all while adhering to stringent vehicle dimensional constraints (length, width, and height). Both of these subproblems are recognized within the computational complexity class of NP-hard problems. Despite the proven efficacy of evolutionary algorithms in addressing 3L-CVRPs, prevalent methodologies typically adopt a sequential approach, prioritizing route op-timization over loading optimization, thereby overlooking the intrinsic interconnectedness between these two facets. This paper proposes a novel dual-population evolutionary algorithm in response to this limitation. One population is dedicated to refining vehicle routing solutions, whereas the other focuses on enhancing loading efficiency. These two populations undergo a co-evolutionary process to identify optimal solutions for 3L-CVRPs. Empirical evaluations across four diverse datasets reveal that the proposed algorithm surpasses three contemporary algorithms, achieving superior loading efficiency and reduced transportation costs.