Journal of Applied Engineering and Technological Science Vol 6.
2025: 1019-1039
A HEURISTIC ENHANCING ARTIFICIAL IMMUNE SYSTEM FOR
THREE-DIMENSIONAL LOADING CAPACITATED VEHICLE ROUTING
PROBLEM
Peeraya Thapatsuwan1.
Warattapop Thapatsuwan2*.
Chaichana Kulworatit3 Department of Computational Science and Digital Technology.
Faculty of Liberal Arts and Science.
Kasetsart University Kamphaeng Saen Campus.
Thailand 1,2 Department of Computer Science.
School of Science.
King MongkutAos Institute of Technology Ladkrabang.
Thailand3 t@ku.
Received: 12 October 2024.
Revised: 11 April 2025.
Accepted: 13 April 2025
*Corresponding Author
ABSTRACT
This study addresses the Three-Dimensional Loading Capacitated Vehicle Routing Problem .
L-CVRP), a highly complex NP-hard problem that combines vehicle routing with spatially constrained threedimensional bin packing.
To tackle this challenge, we propose an enhanced Artificial Immune System (En-AIS) that integrates a novel local search heuristic called AuBring-i-to-j,Ay designed to improve routing feasibility and loading efficiency.
The En-AIS algorithm is further refined through rigorous parameter tuning using a full factorial design and ANOVA analysis.
Comparative experiments were conducted against conventional AIS and the Firefly Algorithm (FA) across 27 benchmark instances.
Results demonstrate that En-AIS consistently outperforms both baseline methods in terms of solution quality, achieving an average improvement of 15Ae20% while maintaining competitive computational times.
These findings highlight the algorithmAos robustness and its practical potential for application in logistics and supply chain optimization tasks involving joint routing and loading decisions.
Keywords: Three-Dimensional Loading Capacitated Vehicle Routing Problem .
L-CVRP).
Artificial Immune System.
Firefly Algorithm.
Metaheuristics.
Bring-i-to-j Heuristic.
Optimization Algorithms.
Introduction Logistics plays a crucial role in the global economy and society by facilitating the efficient movement of goods and people.
Transportation costs significantly influence the price of consumables and commodities, thereby affecting overall economic efficiency.
In 2021, the global logistics market was valued at over C8.
4 trillion and is projected to exceed C13 trillion by 2027, accounting for approximately 10.
7% of the global GDP (Placek, 2.
The escalating complexity of supply and distribution networks has amplified the importance of optimizing packing and routing processes, which are pivotal in determining shipping costs.
Addressing these factors can significantly reduce logistical expenses and enhance overall supply chain Enhancing on-time delivery not only fosters improved customer service but also provides organizations with a substantial competitive advantage.
In this context, the Three-Dimensional Loading Capacitated Vehicle Routing Problem .
L-CVRP) has gained increasing attention due to its practical significance in various industries, including e-commerce, automotive, and express delivery.
The 3L-CVRP is an NP-hard problem that combines the challenges of serving multiple customers with a fleet of vehicles and efficiently loading rectangular boxes into containers, all while minimizing the total travel distance.
The objective is to achieve the lowest overall transportation cost by identifying the shortest route for each vehicle and optimizing the loading sequence.
The 3L-CVRP is not only theoretically complex but also practically impactful.
represents a class of logistics problems where the efficiency of delivery operations depends on the joint optimization of routing and space-constrained loading.
Effectively solving the 3LCVRP can directly lead to reduced transportation costs, improved vehicle utilization, and enhanced customer satisfactionAiparticularly in industries facing tight delivery schedules and spatial constraints, such as e-commerce, grocery distribution, and parcel logistics.
Due to the Thapatsuwan et al A Vol 6.
2025: 1019-1039 problemAos NP-hard nature and real-world relevance, it continues to attract significant attention in combinatorial optimization and logistics research.
The complexity of 3L-CVRP arises from simultaneously optimizing routing decisions and packing strategies within vehicle capacity and stability constraints (Fuellerer et al.
, 2010.
Gendreau et al.
, 2.
Exact optimization methods become impractical for larger problem instances, prompting extensive research into metaheuristic algorithms as viable alternatives.
Nature-inspired metaheuristics have demonstrated robust performance in solving complex combinatorial problems, including vehicle routing problems (VRP).
These algorithms can be categorized into physically-based methods .
Simulated Annealin.
, socially-based methods .
Tabu Searc.
, and biologically-inspired methods .
Genetic Algorithms.
Ant Colony Optimization.
Firefly Algorithm, and Artificial Immune Syste.
(Engin & Doyen, 2004b.
Yang, 2.
While substantial research has employed metaheuristics such as Genetic Algorithms (Chen et al.
, 2.
Tabu Search (Meliani et al.
, 2.
, and Adaptive Large Neighborhood Search (Qi et al.
, 2023.
Wang et al.
, 2.
, relatively few studies have effectively applied Artificial Immune Systems (AIS) or Firefly Algorithms (FA) specifically to the 3L-CVRP, indicating a clear research gap in the current literature (Chi et al.
, 2025.
Leloup et al.
, 2.
Existing AIS implementations typically employ generic mutation and selection processes, often limiting their performance in solving highly constrained and complex loading and routing problems (Freitas & Timmis, 2003.
Garrett, 2005.
Hart & Timmis, 2.
Conventional AIS explores solution spaces via simplistic mutation mechanisms without targeted local optimization, frequently resulting in suboptimal solutions and slower convergence (Timmis.
Recent literature indicates that targeted heuristic improvements and hybridization within AIS can substantially enhance its capability to handle real-world VRP complexities and constraints (Chi et al.
, 2025.
Leloup et al.
, 2025.
Wang et al.
, 2.
This paper proposes a novel heuristic-enhanced AIS algorithm designed explicitly for the 3L-CVRP to bridge this research gap.
Our approach differentiates itself from traditional AIS methods by integrating a specialized local search heuristic termed "Bring-i-to-j.
" This heuristic systematically exploits local improvements by efficiently relocating items within and across vehicle loading sequences, enhancing route feasibility, load stability, and space utilization.
Additionally, our work rigorously fine-tunes algorithm parameters through factorial experimental design, systematically optimizing performanceAian essential step frequently overlooked in previous AIS studies (Aytug et al.
, 2.
Thus, this research significantly contributes by addressing the explicitly identified gap through advanced heuristic integration and rigorous parameter optimization, providing substantial performance improvements over existing approaches.
The remaining sections of this paper are organized as follows.
Section 2 reviews related literature, describes mathematical modeling and presents the details of the proposed heuristic-enhanced AIS.
Section 3 presents experimental results and analysis, while Section 4 concludes the study and outlines directions for future research.
Literature Review 1 Three-Dimensional Loading Capacitated Vehicle Routing Problem CVRP is known to be NP-hard, extending the scope of the classical Traveling Salesman Problem (TSP) by incorporating elements of the Bin Packing Problem (BPP) (Toth & Vigo.
This extension involves finding the shortest route for visiting all customers and efficiently packing goods into vehicles, making it a more complex and realistic representation of logistics problems.
The 3L-CVRP combines the Three-Dimensional Loading Problem .
DLP) and the Capacitated Vehicle Routing Problem (CVRP).
It involves determining a set of vehicle routes and a containment plan for efficiently loading the cargo on each route.
Each route starts and ends at the warehouse, aiming to achieve the shortest total distance between shipments or the minimum traveling cost.
While these objectives are often aligned, they can differ in certain scenarios where, for example, toll roads or fuel costs influence the cost efficiency differently from distance.
Thapatsuwan et al A Vol 6.
2025: 1019-1039 The rectangular cargo will be loaded into the truck's loading area for delivery to the The loading area may not necessarily be square, aligning with the rectangular nature of the cargo.
Packaged goods must not exceed the volume and weight that the vehicle can In the previous literature, 3L-CVRP considers the following assumptions (Bortfeldt.
Doerner et al.
, 2007.
Fuellerer et al.
, 2010.
Gendreau et al.
, 2.
On one route, only one vehicle will be used .
ne car per rout.
Every vehicle will have a container volume, and the payload will be the same.
Boxes or products are rectangular with different sizes.
Products of the same customer must be in the same car or path.
The total weight of the box in each car must not exceed the weight the car can carry.
The total volume of all product boxes in each car must not exceed the volume the car can The edge of the product box must be placed parallel to the edge of the container or parallel to the x, y, and z axes without any part of the box coming out of the container.
The top box supports the bottom and stabilizes it by filling the remaining space in the container with foam rubber.
Boxes that must be delivered to the last customer should not be placed so that it will prevent boxes from reaching the earlier customers by using a first-in, first-out rule.
A mathematical model is based on (Kyk & Topaloglu Yildiz, 2.
, and a mathematical model for minimizing the efficiency of volume usage for vehicle containers has been developed by previous research (Chen et al.
, 1995.
Christensen & Rousye, 2.
The 3L-CVRP is made up of two parts: the transport and the loading or packaging.
Part of product transportation can be explained by the complete graph G = (V.
E), which consists of a set of vertices and edges.
The problem can be described as follows: .
Define the set of N 1 transmission points (V = 0, 1.
N), and let the single depot be at point 0 and the customer at point 1 to N.
Determine E as the set of edges .
, .
connecting all vertex pairs.
Let Dij represent the distance between nodes i to j.
Set K to represent the number of homogeneous vehicles with the same weight and volume limitation.
Assign the volume of packing area as Vol = Lc * Wc * Hc, where Lc.
Wc, and Hc are the respective length, width, and height of cth vehicle containers.
This problem aims to achieve the shortest total distance for the cargo.
In the loading or packaging section is to minimize the number of vehicle containers required to pack the product.
The problem model is described as follows: .
Define a set of rectangular-shaped cargo boxes, the total number of B boxes ( Each box has a Oc length, width, and height in lb, wb, and hb, respectively .
= 1, 2,A.
B).
Set unlimited vehicle containers with length, width, and height in Lc.
Wc, and Hc, respectively .
= 1, 2,A.
K).
The length, width, and height of the box must not exceed the length, width, and height of the vehicle containers .
b O Lc, wb O Wc, and hb O H.
In this research, the product box cannot be rotated for easy loading and unloading of boxes.
Therefore, the last box delivered to the customer should not be blocked using the last-in, first-out (LIFO) rule.
In terms of loading or packaging, assign i to represent each customer, where i = 1, 2, .
Each customer has a demand for b boxes.
Let Bi represent the total number of boxes of customer ith .
= 1, 2, .
Define Iib instead of the item of customer ith, the box bth ( { }), which consists of lib, wib, and hib representing the length, width, and height of the box bth of customer ith.
The total volume of each customer's product is voi = Oc The formulation of the 3L-CVRP is as follows:
Indices:
i, j b, a Customers ith and jth .
, j = 1, 2,A.
N) Vehicle containers cth for each vehicle .
= 1, 2,A.
K) Boxes bth and ath .
, a = 1, 2,A.
Parameters:
Total number of customer service nodes .
, 1, 2.
N), 0 is the depot Total number of vehicles Thapatsuwan et al A Vol 6.
2025: 1019-1039 Vol Maximum vehicle container volume Total volume of each customerAos product Dij Distance from node i to j Fixed costs associated with using the cth vehicle Total number of boxes of customer ith .
= 1, 2, .
Total number of boxes ( Oc lb, wb, hb The length, width, and height of box bth lib, wib, hib The length, width, and height of box bth of customer ith Lc.
Wc.
Hc The length, width, and height of vehicle containers cth xb, yb, zb The coordinates of a back-left-bottom corner that specifies the placement of boxes bth .
b, yb, zb C .
An arbitrarily large number used in Big-M constraints.
Decision variables .
binary variabl.
Equals 1 if the vehicle containers cth travels from node ith to jth .
0 otherwise.
Equals 1 if the vehicle containers cth is selected.
0 otherwise.
lb , lb , lb Equals 1 if the length of the box bth is parallel to the X.
Y, or Z axes.
wbX, wbY, wbZ Equals 1 if the width of the box bth is parallel to the X.
Y, or Z axes.
hbX, hbY, hbZ Equals 1 if the height of the box bth is parallel to the X.
Y, or Z axes.
Equals 1 if the box bth is placed on the left side of the box ath.
0 otherwise.
Equals 1 if the box bth is placed on the right side of the box ath.
0 otherwise.
Equals 1 if the box bth is placed on the back of the box ath.
0 otherwise.
Equals 1 if the box bth is placed in front of the box ath.
Equals 1 if the box bth is placed above the box ath.
0 otherwise.
Equals 1 if the box bth is placed under the box ath.
0 otherwise.
Equals 1 if the item of customer ith, box bth is selected to be placed in the vehicle containers cth.
0 otherwise.
Objective function:
Oc Oc Oc Oc Subject to:
{ }
{ }
Oc Oc
{ }
b * lbX) .
b * wbX) .
b * hbX) O xa .
- beb.
* M.
Ab, a, b<a xa .
a * laX) .
a * waX) .
a * haX) O xb .
- frb.
* M,Ab, a, b<a yb .
b * lbY) .
b * wbY) .
b * hbY) O ya .
- leb.
* M.
Ab, a, b<a ya .
a * laY) .
a * waY) .
a * haY) O yb .
- rib.
* M.
Ab, a, b<a zb .
b * lbZ) .
b * wbZ) .
b * hbZ) O za .
- unb.
* M.
Ab, a, b<a za .
a * laZ) .
a * waZ) .
a * haZ) O zb .
- abb.
* M.
Ab, a, b<a leba riba beba frba abba unba C - 1.
Ab, a, b<a xb .
b * lbX) .
b * wbX) .
b * hbX) O Lc .
- ) * M.
Ab,c yb .
b * lbY) .
b * wbY) .
b * hbY) O Wc .
- ) * M.
Ab,c zb .
b * lbZ) .
b * wbZ) .
b * hbZ) O Hc .
- ) * M.
Ab,c ,Ab B Thapatsuwan et al A Vol 6.
2025: 1019-1039
Oc Oc lb , lb , lb , wb , wb , wb , hb , hb , hb , leba, riba, beba, frba, abba, unba.
Cc, .
Ea .
Ab, a, b < a The objective function in .
is to minimize the total distance of all routes and to reduce vehicles used.
Equations .
ensure that a route in an undirected graph visits each node exactly once and returns to the depot.
In .
, the vehicle must only start and end at the depot.
Equation .
ensures that vehicles entering the node must exit the node.
In .
, the packaged goods must not exceed the vehicle volume and the range of decision variables as in .
Equations .
ensure that the boxes loaded into the containers do not overlap.
Equation .
is applied when box bth and box ath are placed in container cth, with at least one side of box bth and box ath related by six variables .
eba, riba, beba, frba, abba, and unb.
Equations .
ensure that all the boxes fit snugly into the container without overflowing, and .
assures that one carton will be loaded into only one vehicle container.
In .
, container cth will be selected when any box is assigned.
Finally, .
specified the range of the variables.
The variables leba, riba, beba, frba, abba, and unba are only defined for b<a.
The container will have the origin point coordinates at the back-left-bottom corner.
The length Lc of the container is placed along the Xaxis, the width Wc along the Y-axis, and the height Hc along the Z-axis.
The position of the box bth has the coordinates .
b, yb, z.
at the back-left-bottom corner.
2 Metaheuristics Methods Solving real-world problems such as scheduling, packing, and routing can be effective for small-scale instances.
However, as problem size increases, more sophisticated approaches are Nature-inspired metaheuristics have emerged as powerful tools, drawing inspiration from natural processes.
These algorithms can be categorized into three groups (Engin & Doyen, 2004.
: physically-based methods like Simulated Annealing (SA).
socially-based methods like Tabu Search (TS).
and biologically-based methods such as Genetic Algorithms (GA).
Neural Networks (NN).
Particle Swarm Optimization (PSO).
Ant Colony Optimization (ACO).
Shuffled Frog Leaping (SFL).
Firefly Algorithm (FA), and Artificial Immune System (AIS).
These nature-inspired methods have been widely applied to the Three-Dimensional Loading Capacitated Vehicle Routing Problem .
L-CVRP).
For instance.
Gendreau et al.
developed a TS algorithm tailored for 3L-CVRP, while Doerner et al.
combined ACO and TS with fast approximation algorithms to address loading constraints.
Fuellerer et al.
further advanced this by implementing an ACO algorithm with efficient loading heuristics for 3L-CVRP.
Despite the success of TS and ACO, the literature reveals limited use of FA and AIS in this domain, presenting a research gap that this study aims to address by enhancing AIS for 3L-CVRP.
Recent advancements have shifted toward hybrid metaheuristics to tackle increasingly complex 3L-CVRP variants.
Meliani et al.
proposed a TS approach with extreme pointbased first-fit decreasing loading, effectively handling heterogeneous fleet 3L-CVRP with intricate constraints.
Similarly.
Kyk and Yildiz .
introduced a constraint programming model hybridized with evolutionary algorithms, decomposing routing and loading phases to solve benchmark instances efficiently.
Wang et al.
developed a clustering-based NSGAII approach for multi-depot VRP with time windows and 3D loading constraints, optimizing vehicle utilization and reducing costs.
Chen et al.
proposed a hybrid BiogeographyBased Optimization (HBBO) algorithm, co-optimizing bin size and 3D loading layouts, validated with real-world industrial cases.
Qi et al.
integrated Multiobjective Evolutionary Algorithms (MOEA.
with Adaptive Large Neighborhood Search (ALNS) to address transportation planning with unloading constraints and multi-frequency visits.
These hybrid approaches highlight the growing complexity of 3L-CVRP and the need for robust, adaptable solutions.
In a notable study.
Ferreira et al.
tackled the Green Vehicle Routing Problem with Two-Dimensional Loading Constraints and Split Delivery (G2L-SDVRP) using a Variable Neighborhood Search (VNS) metaheuristic.
By integrating environmental objectives like minimizing COCC emissions with routing and loading decisions, their custom local search and Thapatsuwan et al A Vol 6.
2025: 1019-1039 constraint programming approach improved benchmark solutions, offering insights applicable to 3L-CVRPAos operational and sustainability challenges.
Building on this trend.
Gimenez-Palacios et al.
addressed multidrop and split delivery conditions in 2D loading, incorporating axle weight and center-of-gravity constraints relevant to 3D loading extensions.
Among the latest contributions.
Leloup et al.
proposed a three-phase algorithm for the Three-Dimensional Loading Vehicle Routing Problem with Split Pickups and Time Windows .
L-SPVRP-TW).
Combining a savings-based heuristic, route reduction strategies, and General Variable Neighborhood Search (GVNS), their approach optimizes cost and feasibility under time-dependent travel, reachability, and stability constraints.
Wang et al.
introduced a hybrid method for the Collaborative Multidepot Split Delivery Network Design with Three-Dimensional Loading Constraints (CMDSDN-TDLC), using K-nearest neighbor clustering and Adaptive Nondominated Sorting Genetic Algorithm i (ANSGA-.
to balance operating costs, vehicle numbers, and loading rates.
Chi et al.
advanced 3LCVRP with relocation constraints .
L-PCVRP-RC) through a hybrid framework integrating Mixed Integer Linear Programming (MILP) with an improved branch-and-price algorithm and Backward Dynamic Programming (BDP), achieving significant cost savings and volume These studies collectively demonstrate the evolution of hybrid metaheuristics, providing a foundation for further innovation in 3L-CVRP.
The Artificial Immune System (AIS) offers unique advantages for such problems.
Unlike conventional single-directional search methods.
AIS employs a multi-directional search via a population of antibodies .
andidate solution.
Its duplication process clones only high-affinity antibodies, and a double mutation mechanism provides suboptimal solutions a second chance for improvement.
However, researchers like Freitas and Timmis .
Garrett .
Hart and Timmis .
, and Timmis .
have noted that traditional AIS struggles to guarantee global optima in large-scale combinatorial optimization due to its stochastic nature.
In the context of 3L-CVRP, its limited ability to efficiently handle complex 3D loading constraintsAi such as stability, stacking, and orientationAiand the lack of mechanisms to manage routingloading interdependencies may contribute to its underutilization.
Preliminary studies, such as Engin and Doyen .
applying AIS to hybrid flow shop scheduling, demonstrate its potential for multi-dimensional optimization problems, suggesting that with proper adaptation.
AIS could address 3L-CVRP challenges.
Two strategies have been proposed to overcome these limitations: parameter fine-tuning through statistical design (Aytug et al.
, 2003.
Engin & Doyen, 2004.
and hybridization with techniques like local search or genetic algorithms (Jaradat & Langari, 2009.
Sinha & Goldberg, 2.
In the context of 3L-CVRP, such hybridization remains underexplored, offering a promising avenue for this research.
The Firefly Algorithm (FA), introduced by Yang .
, mimics the light-emitting behavior of fireflies with three key rules: unisex attraction, brightness-based attractiveness decreasing with distance, and optimization driven by light intensity (Yang, 2.
While effective for continuous optimization.
FA has seen limited application in 3L-CVRP as it is designed for continuous rather than discrete problems.
Specifically, determining 3D box placements and managing constraints like stability or unloading sequences are challenges FA was not inherently designed to address, likely contributing to its underuse in this domain.
However, preliminary studies like Altabeeb et al.
and Trachanatzi et al.
have shown FAAos effectiveness in solving capacitated VRP, particularly for routing with capacity constraints.
These applications suggest that with modifications to handle discrete 3D loading.
FA could offer valuable insights for 3L-CVRP, though such adaptations remain scarce.
This research proposes an enhanced AIS framework (En-AIS) integrating domainspecific local search, such as the "Bring-i-to-j" heuristic, and problem decomposition to address 3L-CVRPAos complex routing and loading constraints.
By building on the strengths of AIS and addressing its limitations, this approach aims to fill the gap in applying biologically inspired methods to 3L-CVRP, offering a robust alternative to existing metaheuristics like TS.
ACO, and FA.
Research Methods 1 Natural Clonal Selection Thapatsuwan et al A Vol 6.
2025: 1019-1039 In the body's immune system, clonal selection is the process by which immune cells, specifically B cells, that identify certain antigens are chosen to proliferate and differentiate.
When a B cell connects with an antigen, it activates and begins clonal expansion, generating multiple identical cells.
These clones undergo somatic hypermutation, introducing random variations to their receptors.
This mutation enhances receptor diversity and improves the immune system's efficiency in identifying and countering the antigen (Burnet, 1.
Antigen Recognition: Each B cell possesses distinct receptors that can attach to specific When a matching antigen is encountered, the B cell binds to it.
Activation and Proliferation: Upon binding to the antigen, the B cell is activated and enters a phase of rapid division, creating numerous identical clones.
Differentiation: The cloned B cells then specialize into plasma cells and memory B cells.
Plasma cells produce and release antibodies that directly target the antigen, while memory B cells persist in the body, ready to provide a quicker response if the antigen reappears.
Affinity Maturation: Throughout proliferation, somatic hypermutation introduces minor mutations in the receptors of cloned B cells, enhancing receptor diversity.
B cells with receptors of higher affinity for the antigen are preferentially expanded.
Elimination of Self-reactive Cells: B cells that strongly bind to self-antigens .
ormal body molecule.
are generally eliminated through negative selection, helping to prevent autoimmune reactions.
2 Artificial Immune System for 3L-CVRP AIS (Artificial Immune Syste.
is a biologically inspired method that mimics the immune system's ability to recognize and adapt to foreign pathogens.
It is a branch of computational intelligence used for solving complex optimization problems by simulating immune responses (Dasgupta, 2.
CLONALG is a variant of AIS based on clonal selection theory, which focuses on the adaptability of B and T cells to detect and eliminate foreign invaders .
on-self antigens or foreign molecule.
(Burnet, 1.
In the context of this study, each antibody encodes a complete solution to the 3L-CVRP by representing a randomized customer visiting sequence.
For example, an antibody such as C1AeC2AeC3 indicates that the vehicle will visit Customer 1 first, followed by Customer 2, and then Customer 3.
Based on this sequence, the items associated with each customer are packed into vehicles in order.
The algorithm begins loading from Vehicle 1 by attempting to pack all items belonging to the current customer using a three-dimensional packing heuristic.
Specifically, a bottom-left-front (BLF)-inspired spatial heuristic is employed.
The algorithm begins placing items at the bottom-left corner of the container and fills space horizontally to the right.
Once the width is exhausted, it stacks vertically upward.
When vertical space is also filled, it progresses front-to-back along the containerAos depth.
This placement strategy continues until the entire container space is used.
During the optimization process, all solution candidates .
are evaluated based on strict feasibility rules.
The 3L-CVRP incorporates two main categories of constraints: vehicle capacity and loading feasibility.
Vehicle capacity constraints are enforced by ensuring that the total volume of items assigned to each vehicle does not exceed the vehicleAos container capacity.
If an attempted packing exceeds the available space, the algorithm assigns the entire customerAos shipment to the next vehicle.
Loading feasibilityAisuch as placement orientation, stackability, and collision avoidanceAiis inherently handled within the packing heuristic.
The 3D placement routine enforces all physical constraints during the packing process, ensuring that items are placed only when they fit without overlap, orientation violations, or unstable stacking.
As a result, all constructed solutions are feasible by design, and no additional penalty or rejection mechanism is To preserve delivery consistency and operational efficiency, the system is designed to pack all items from the same customer within a single vehicle whenever possible.
If the current Thapatsuwan et al A Vol 6.
2025: 1019-1039 vehicle does not have enough capacity to accommodate the entire set of items, none of them will be partially loaded.
Instead, the algorithm moves all that customerAos items to the next available vehicle.
This grouping constraint not only ensures spatial feasibility but also enhances logistical practicality, aligning the solution with real-world delivery requirements such as last-mile logistics and simplified unloading processes.
This encoding strategy enables the algorithm to jointly optimize both routing and loading in a unified solution representation.
Fig.
1 illustrates this encoding approach, demonstrating how customer-to-item relationships are translated into vehicle-level 3D packing layouts.
Fig.
Antibody encoding in the AIS framework for 3L-CVRP, illustrating customer-to-item mapping and 3D packing layout.
The CLONALG algorithm can be described as follows:
Randomly initialize the antibody population.
For each antibody (A.
, calculate its affinity value (Aff_Va.
The fitness value of Ab can be calculated as the main objective function .
Aff_Val = 1 / Fitness value of Ab Rank the population in descending order of Aff_Val, then calculate a large group of clones according to the clonal factor () and the maximum population from .
Generate clones of these antibodies based on their affinity.
antibodies with higher affinity will produce more clones.
Differentiate these clones by implementing mutation on each clone (Engin & Doyen, 2004.
Add these mutated clones to the Ab population, sort them by their affinity, and select the number of Ab in the top rank of the population for the next generation.
Repeat steps 2 to 6 until a termination criterion is satisfied.
In this study, key parameters of the AISAinamely, population size (A.
, number of generations (G), clonal factor (), and elimination rate (%E)Aiwere not arbitrarily assigned.
Instead, a parameter tuning process was conducted as part of the experimental framework, detailed in Section 4.
A full factorial design was employed to evaluate different parameter Thapatsuwan et al A Vol 6.
2025: 1019-1039 levels systematically.
The selected configurations were chosen based on their statistical significance using Analysis of Variance (ANOVA) across 27 problem instances.
Although the mutation rate was not explicitly isolated as a standalone parameter, its influence is inherently captured through the clonal selection and variation mechanisms.
The mutation strength is implicitly controlled by the number of clones .
nfluenced by ) and the proportion of eliminated antibodies (%E), which determine the extent of diversity introduced per iteration.
These settings enable a balance between exploration and exploitation, thereby improving both convergence speed and solution quality.
Furthermore, the parameter tuning process can be considered a form of sensitivity analysis, as it involves testing multiple combinations of parameters and observing their impact on performance across various problem sizes.
The results from the factorial experiments revealed how different levels of each parameter (AbG, , and %E) influenced solution quality and convergence behavior.
These insights helped identify parameter configurations that consistently performed well, thereby contributing to the robustness of the proposed algorithm.
This study incorporates the AuBring-i-to-jAy local search heuristic into the core optimization process to improve the baseline AIS.
After the mutation step in each generation, a subset of elite antibodies is refined by repositioning one customer within its route.
This local adjustment helps reduce unnecessary detours, shortens the total travel distance, and improves vehicle utilization.
The algorithm intensifies its search around high-potential solutions by embedding this heuristic within the evolutionary loopAibefore the affinity evaluation and selection steps.
As a result, it converges more quickly and consistently produces higher-quality solutions.
This enhancement transforms the AIS into a more efficient and problem-specific solver for the 3L-CVRP.
3 Local Search: Bring-i-to-j Bring-i-to-j is a proposed heuristic that is based on the idea of mutation.
In this heuristic, a random customer i in a solution is randomly selected, and then a random another customer j is Finally, move customer i to the adjacent location next to customer j.
The concept of Bring-i-to-j is to move only one customer while another customer stands for waiting.
This approach differs from traditional mutation operators that randomly swap two customers' positions, potentially causing disruptions to the vehicle routing plan.
By moving only one customer, the Bring-i-to-j heuristic reduces the likelihood of disrupting the vehicle routing plan and improves the algorithm's efficiency.
Bring-i-to-j will be applied to the antibody population after merging with the mutated Fig.
2 describes the idea of this approach to help antibodies find solutions with only one For example, suppose a route where the vehicle will leave depot 0 to deliver goods to customers 1, 3, 4, and 2 at different locations and then return to the depot.
The route improvement will initially randomize two customers as i and j, respectively, and customer i will be moved adjacency to customer j.
Fig.
Bring-i-to-j heuristic illustration: moving customer i closer to j to improve solution feasibility.
Thapatsuwan et al A Vol 6.
2025: 1019-1039 Compared to the proposed En-AIS, the Firefly Algorithm (FA) follows a simpler movement-based mechanism with fewer problem-specific enhancements.
While FA is generally effective for continuous optimization problems, its adaptation to combinatorial scenarios like the 3L-CVRP lacks embedded local search strategies.
This absence limits its capability to refine solutions iteratively, especially in high-dimensional or constraint-heavy instances.
summarized in Table 3.
En-AIS consistently outperforms FA in both average and best-case solution quality across 27 benchmark instances while maintaining a comparable computation These results highlight the importance of integrating domain-specific heuristics, such as Bring-i-to-j, to guide metaheuristic search processes more effectively.
4 AIS enhancing with LS for 3L-CVRP This paper uses the Bring-i-to-j as the local search for the original AIS.
The pseudocode of AIS enhanced with local search (En-AIS) is displayed in Fig.
Fig.
Pseudo-code of En-AIS.
Compared to the traditional AIS, the proposed En-AIS explicitly integrates the Bring-i-toj heuristic into its evolutionary process.
Specifically.
En-AIS applies this local search heuristic after the mutation step in each generation but before evaluating the affinity and selecting the best antibodies.
This refinement step significantly improves the solution quality by reducing unnecessary travel distances and enhancing loading feasibility, enabling the algorithm to converge faster and achieve superior solutions, especially in complex or larger problem 5 Firefly Algorithm for 3L-CVRP The main steps of FA begin with determining the intensity of the flashing light for each In the Firefly Algorithm, light intensity is used as a metaphor for the quality of the Thapatsuwan et al A Vol 6.
2025: 1019-1039 solutionAifireflies with higher light intensity represent better solutions, and other fireflies are attracted to them to explore the search space effectively.
During the dual light intensity comparison loop, each firefly compares its light intensity with others.
Fireflies with lower intensity will move towards those with higher light intensity to improve their solution quality.
The moving distance depends on the attractiveness.
The movement of a firefly i, which is attracted by a more attractive .
, brighte.
firefly j, is determined by the equation .
This equation models how the position of firefly i changes in response to the attraction, ensuring that it moves towards better solutions in the optimization The firefly attractiveness function calculation is displayed in .
, and the distance between any two fireflies i and j at xi and xj, can be defined as a Cartesian distance .
After migration, the new fireflies are assessed based on the quality of their solutions, such as distance minimization or cost optimization, and their light intensity is adjusted accordingly to reflect the updated solution quality.
During the pairwise comparison loop, the best-so-far solution is iteratively updated.
The pairwise comparison process is repeated until the termination criteria are satisfied.
Finally, the best-so-far solution is visualized.
The pseudo-code of the FA applied to solve the 3L-CVRP is illustrated in Fig.
summary, the key steps include initializing the population of fireflies, calculating their light intensity based on solution quality, iteratively moving fireflies towards brighter ones, updating the best-so-far solution, and repeating this process until convergence criteria are met.
) (
An An oc Fig.
Pseudo-code of FA.
Results and Discussions This section was designed to verify the appropriate AIS parameter settings for 3L-CVRP.
It also benchmarks the performance of AIS with the proposed heuristic in terms of computational efficiency and the quality of the solutions obtained.
All algorithms were coded in Thapatsuwan et al A Vol 6.
2025: 1019-1039 C# language, chosen due to its balance of performance, ease of use, and familiarity among the research team.
These algorithms were tested on a set of 27 instances introduced by (Gendreau et al.
, 2.
The number of customers ranged from 15 to 100, vehicles from 4 to 23, and items from 32 to 198.
The computational tests were performed on a computer with an Intel Core i58400 CPU @2.
80GHz with 8 GB of RAM, running Windows 10 as the operating system.
Each run was repeated 10 times, using different random seeds for each run.
1 Experiment A Due to random volatility in evolutionary algorithms such as AIS, which refers to fluctuations in solution quality and variability in convergence, the parameter settings were investigated to fit the 3L-CVRP.
Table 1 displays the full factorial design of AIS parameters.
includes the combination of the number of antibodies and number of generations (AbG), referring to the number of solutions generated and the required processing time.
Therefore, the combination of AbG was defined at 22,500 to limit the computational time required based on prior experimentation and practical limitations observed in similar optimization problems.
The percentage of antibody elimination (%E) and clonal factor () are defined as scaling factors for the number of clones created for selected antibodies.
These parameters are important as they control the population's diversity and the algorithm's convergence rate, impacting both the exploration of the search space and the refinement of candidate solutions.
Table 1 - Experimental factors and levels.
Values Factors Levels Low (-.
Medium .
High ( .
AbG
90*250
150*150
250*90
The computational results were analyzed using analysis of variance (ANOVA), a general linear model.
ANOVA was selected because it effectively determines the influence of multiple factors on outcomes and identifies statistically significant differences among tested instances.
The individual P-values for all 27 instances are summarized in Table 2.
The first four columns of Table 2 include the instance name, total number of customers (Cu.
, vehicles (Ve.
, and items (Ite.
The results indicate that all factors have a statistically significant impact on small to medium-sized problems.
For small problems, assigning values to AbG tends to produce a large number of antibodies, leading to efficient convergence.
However, as the problem size increases, the number of antibodies decreases, requiring more generations to reach convergence.
The clonal factor setting was found to be significant across almost every problem size and becomes increasingly crucial for optimizing very large problems.
A high clonal factor value generates a substantial number of clones, significantly enhancing the search capability but requiring longer computational time.
Depending on the problem size, the computational time can range from several hours to multiple days.
The hypermutation rate () also proved statistically significant, specifically for larger problem sizes.
As the problem complexity and solution space expand, becomes essential for maintaining diversity among solutions, thereby preventing premature convergence.
Without explicit local search, a high value facilitates exploration of a broader solution space, allowing AIS to search deeper and find competitive solutions even without specialized heuristics.
Overall.
Table 2Aos findings underscore the distinct role of each parameter.
For small to medium-sized problems, a high AbG setting accelerates convergence by producing a larger antibody population that efficiently explores smaller solution spaces.
In contrast, larger instances benefit significantly from a high clonal factor, which enables deeper solution exploration, albeit with increased computational time.
remains a critical parameter for the largest problem sizes, ensuring effective exploration across the expanded solution landscape by preventing premature convergence and enhancing search diversity.
Thapatsuwan et al A Vol 6.
2025: 1019-1039 Table 2 also suggests the appropriate setting for each parameter .
hown in parenthese.
Although the p-value for these settings was insignificant, the main effect plot provides insight into the most effective parameter configurations for different problem sizes, guiding parameter selection for improved optimization outcomes.
Name Table 2 - P-values and parameter effects based on main effect plot.
Instances P-Values (Minimum Value.
Cus Veh Item AbG E016-03m E016-05m E021-04m E021-06m E022-04g E022-06m E023-03g E023-05s E026-08m E030-03g E030-04s E031-09h E033-03n E033-04g E033-05g E036-11h E041-14h E045-04f E051-05e E072-04f E076-07s E076-08s E076-10e E076-14s E101-08e E101-10c E101-14s A functional analysis was also conducted to better interpret the impact of each parameter on the algorithm's behavior.
The number of antibodies and generations (AbG) directly controls the population size and overall search breadth.
A high AbG value allows broader exploration but increases computational time, whereas a lower value accelerates the search but may lead to premature convergence due to limited diversity.
Thapatsuwan et al A Vol 6.
2025: 1019-1039 The elimination rate (%E) manages how much of the population is replaced in each A high %E ensures greater diversity by discarding more low-quality antibodies but may disrupt the convergence process.
Conversely, a low %E value helps preserve promising solutions but might cause stagnation.
The clonal factor () governs the number of clones produced from high-affinity A higher increases local exploitation by allowing deeper refinement of reasonable solutions, though it adds computational cost.
Lower values reduce the computational burden but limit the fine-tuning of elite solutions.
Understanding these behavioral impacts helps fine-tune parameter settings beyond statistical significance, ensuring robust performance across a wide range of problem instances.
2 Experiment B This experiment aimed to compare three algorithms: AIS.
En-AIS, and FA, in terms of minimum (Mi.
, average (Av.
, and maximum (Ma.
solutions and computational time usage (Tim.
Both AIS and En-AIS used the parameter settings obtained from Experiment A, while the FA parameters were based on (Yang, 2.
Table 3 summarizes the experimental results for all three algorithms across the 27 benchmark instances.
Each row presents the minimum, maximum, and average total travel distances obtained in 10 independent runs and the average computational time.
These numerical values clearly show performance differences among AIS.
En-AIS, and FA.
Avg Time.
Alg Min Max Avg Time.
AIS
EnAIS
EnAIS
AIS
EnAIS
EnAIS
AIS
EnAIS
AIS
EnAIS
AIS
AIS
EnAIS
AIS
EnAIS
AIS
AIS
EnAIS
EnAIS
AIS
AIS
EnAIS
EnAIS
AIS
AIS
E036-11h
E041-14h
E045-04f
E051-05e
E072-04f
E076
-07s
E022-06m
E023
-03g
E033-05s
AIS
E022-04g E016-03m Max E016-05m Min SolutionsAo Quality of Algorithms E021-04m Alg Problems SolutionsAo Quality of Algorithms E021-06m Problems Table 3 - Experimental results of all algorithms.
E033-04g SolutionsAo Quality of Algorithms Min Max Avg Time.
EnAIS
AIS
SolutionsAo Quality of Algorithms Alg Min Max Avg Time.
EnAIS
AIS
EnAIS E076-08s Alg Problems Vol 6.
2025: 1019-1039
AIS
AIS
EnAIS
EnAIS
AIS
AIS
EnAIS
EnAIS
AIS
AIS
EnAIS
EnAIS
AIS
AIS
EnAIS
E101-10c
E101-08e
E076-14s
E076-10e
EnAIS
EnAIS
AIS
AIS
EnAIS
EnAIS
AIS
EnAIS E101-14s E033-03n E031-09h E030-04s E030-03g E026-08m E023-05s Problems Thapatsuwan et al A The experimental results in Table 3 reported that En-AIS's minimum, maximum, and average solutions were superior to those produced by other algorithms for all problem sizes, with an average improvement of 15-20% in solution quality compared to AIS and FA.
This indicates that En-AIS finds high-quality solutions across various scenarios more effectively.
The Bring-i-to-j heuristic significantly improved the quality of the obtained solution by enhancing local search capabilities and allowing the algorithm to escape local optima more efficiently.
Specifically, the heuristic moves a selected customer to a new position in the route, creating a new neighborhood solution that helps explore different configurations and overcome local On average.
En-AIS achieved a 17.
42% improvement in solution quality over AIS and a 13.
97% improvement over FA across all test instances.
The most significant improvement was observed in instance E033-04g, where En-AIS outperformed AIS by 10.
50% and FA by These results validate the statistical superiority of En-AIS in both minimum and average performance metrics.
Thapatsuwan et al A Vol 6.
2025: 1019-1039 From a computational perspective, the proposed En-AIS demonstrates a favorable balance between solution quality and processing time.
Although the integration of the Bring-ito-j local search and dual mutation introduces additional overhead compared to the baseline AIS, the performance gains justify the moderate increase in computation time.
On average.
EnAIS required approximately 15Ae25% more time than standard AIS or FA .
s shown in Table .
, but consistently delivered better minimum and average solution values across all instances.
This efficiency suggests that En-AIS is suitable for mid-sized and large-scale problems, particularly in planning environments where solution quality is prioritized over runtime optimality.
To statistically verify the observed differences, a one-way ANOVA was conducted using the average values from all 27 benchmark instances for AIS.
En-AIS, and FA.
The results, summarized in Table 4, indicated that the differences among the three algorithms were not statistically significant at the 0.
05 level .
= 0.
Furthermore, a Tukey post-hoc test confirmed that the mean solution qualities of all algorithms fell into the same grouping, suggesting that the average performance differences were not statistically distinguishable.
EnAIS consistently produced lower mean values than the other algorithms, indicating practical advantages in solution quality across diverse scenarios.
Visual summaries of the mean comparisons and confidence intervals are provided in Fig.
5 and 6.
Table 4 - One-way ANOVA results comparing solution quality across 27 instances.
Interval Plot of Value vs Algorithm
95% CI for the Mean
Value Source Algorithm
Error
Total
AIS
En-AIS Algorithm The pooled standard deviation was used to calculate the intervals.
Fig.
Mean solution quality of AIS.
En-AIS, and FA with 95% confidence intervals.
p-value Thapatsuwan et al A Vol 6.
2025: 1019-1039 Fig.
Tukey HSD test results comparing algorithmsAo mean performance.
En-AIS also demonstrated better scalability than other algorithms, consistently providing superior solutions even as the problem size increased.
Specifically.
En-AIS was tested on problem sizes ranging from 15 customers and 4 vehicles to 100 customers and 23 vehicles, consistently outperforming other algorithms.
This scalability makes En-AIS particularly wellsuited for complex real-world logistics problems, such as the 3L-CVRP, where the number of customers, vehicles, and items can vary significantly.
However.
En-AIS required longer computational time than AIS and FA.
While En-AIS may require more time, it is essential to note that computational time is just one of several factors to consider when selecting an algorithm.
The increased computational time is a trade-off for achieving higher solution quality, making En-AIS a better choice when accuracy is a Other factors, such as accuracy, scalability, and complexity, should also be considered when making a final decision.
To further illustrate En-AIS's impact.
Fig.
7 presents the percentage improvement of EnAIS over AIS across various problem instances.
Notable improvements are observed, particularly in high-dimensional problems, with peaks as high as 29.
79% for specific instances.
This visual representation underscores En-AIS's ability to consistently achieve significant performance gains over AIS across all tested scenarios, providing a clear advantage in complex problems where precision and stability are critical.
Thapatsuwan et al A Vol 6.
2025: 1019-1039 Fig.
Percentage Improvement of En-AIS over AIS across various problem instances.
These findings underscore the critical role of incorporating local search mechanisms within heuristic algorithms like AIS.
Without local search.
AIS often converges prematurely or becomes trapped in suboptimal regions of the solution space, particularly in high-dimensional and highly constrained optimization problems.
Integrating local search in En-AIS not only refines the solution quality but also expedites convergence by effectively navigating local This enhancement enables AIS-based algorithms to perform competitively with other advanced metaheuristics, proving that local search is essential for balancing exploration and exploitation, ultimately elevating AIS from a baseline heuristic to a more versatile and powerful optimization tool.
Table 5 presents a consolidated view of the core design elements that distinguish En-AIS from conventional AIS frameworks and typical metaheuristic methods.
Table 5 - Design Features and Performance Benefits of En-AIS Aspect Advantage in En-AIS Dual-mutation strategy increases the ability to escape local optima.
Flexibility Bring-i-to-j local search refines routing and loading feasibility directly.
Precision Selectively accepts only improved solutions, speeding up convergence.
Convergence Speed Partial elimination and regeneration help maintain population diversity.
Diversity Control Integrates local search inside AIS loop, not just as post-processing Hybrid Design Tailored specifically for 3L-CVRP, balancing exploration and exploitation Problem Adaptability These combined features contribute to the proposed approach's overall robustness, adaptability, and effectiveness.
Beyond benchmark performance.
En-AIS holds significant practical potential in realworld logistics and transportation applications.
The algorithm's ability to simultaneously optimize delivery routing and three-dimensional loading makes it suitable for industries such as e-commerce, retail replenishment, and freight logistics, where both spatial constraints and delivery efficiency are critical.
For instance, companies involved in multi-stop deliveries or operating vehicle fleets with space limitations can benefit from En-AIS by reducing the number of required trips, improving vehicle utilization, and adapting to diverse item sizes and delivery Its moderate runtime and scalable structure also enable integration into real-time or semi-real-time decision support systems, enhancing operational flexibility in dynamic logistics This adaptability positions En-AIS as a viable solution for complex and evolving challenges in modern supply chains.
Therefore, the results of this benchmarking exercise indicate that En-AIS is the most suitable choice for solving the 3L-CVRP, despite its higher computational time.
The algorithm's ability to consistently provide superior solutions and its enhanced local search capabilitiesAi Thapatsuwan et al A Vol 6.
2025: 1019-1039 such as more profound exploration of solution neighborhoods and effective diversification strategiesAimake it a more robust option for tackling complex routing and loading problems.
Furthermore, although comparative analysis with popular baseline models such as Genetic Algorithm (GA) or Ant Colony Optimization (ACO) is highly valuable, we deliberately limited our comparisons to algorithms implemented under the same experimental frameworkAi namely AIS and FA.
This is due to the methodological differences among studies in terms of packing heuristics, constraint formulations, and implementation transparency, which may make direct comparisons with external works less interpretable or fair.
Nonetheless, benchmarking with standard metaheuristics remains an important direction for future work, particularly when harmonized loading strategies and benchmark sets become more available.
Conclusion This research introduced an enhanced Artificial Immune System (En-AIS) integrated with the "Bring-i-to-j" local search heuristic to effectively address the complexities of the ThreeDimensional Loading Capacitated Vehicle Routing Problem .
L-CVRP).
The En-AIS framework demonstrated significant improvements in solution quality compared to traditional AIS and the Firefly Algorithm (FA) across a comprehensive set of benchmark instances.
Key structural featuresAiincluding dual-mutation strategies, selective update mechanisms, embedded local search, and controlled antibody replacementAienabled En-AIS to achieve faster convergence and superior solution stability, particularly in large and tightly constrained problem A rigorous experimental analysis, supported by statistical validation using ANOVA and Tukey tests, confirmed the practical advantage of En-AIS despite the lack of statistically significant mean differences at the 0.
05 level.
The practical implications highlighted indicate that En-AIS is well-suited for real-world logistics, particularly for e-commerce, retail replenishment, and freight transportation, where simultaneous optimization of routing and loading under space and delivery constraints is critical.
The method's computational efficiency and adaptability make it a strong candidate for integration into dynamic, real-time logistics planning systems.
However, several potential limitations must be acknowledged.
First, the benchmark instances considered are static and may not fully represent the dynamic and uncertain conditions inherent in real-world logistics, such as fluctuating customer demands, traffic variability, or unexpected operational disruptions.
Second, this study assumes fixed orientations for loaded items and does not explicitly handle practical constraints such as fragility, stacking stability, or loading sequence preferences.
Third, while En-AIS performs well on the evaluated scale, computational time may still present challenges when scaled to extremely large or highly timesensitive operations.
Future research directions include addressing these limitations by extending En-AIS to dynamic and stochastic variants of the 3L-CVRP, incorporating adaptive or machine-learningbased parameter tuning, and exploring hybridization with other optimization frameworks to enhance scalability and robustness.
Additionally, practical testing on real-world datasets and explicit handling of item-specific constraints such as fragility or orientation preferences would substantially strengthen the method's industrial applicability and validation.
In conclusion, the proposed En-AIS represents a significant methodological advancement, providing a robust, flexible, and efficient optimization tool for the complex, multi-dimensional challenges encountered in modern logistics and transportation management.
Acknowledgment The work was supported by the Kasetsart University Research and Development Institute (KURDI).
Kasetsart University.
References