Page 12 - POSTER FYP MAC-OGOS 2025

APPLICATION OF GENETIC ALGORITHMS IN SOLVING THE

OPEN VEHICLE ROUTING PROBLEM (OVRP) AND

ANALYZING THE EFFECTS OF INITIALIZATION STRATEGIES

42/
K2
ABSTRACT K242/1212

This study applies the Genetic Algorithm (GA) to solve the PROBLEM STATEMENT

Open Vehicle Routing Problem (OVRP), where vehicles are not OBJECTIVES

required to return to the depot after completing deliveries. The

aim is to reduce travel distance and improve route efficiency in To determine the best route in Open Vehicle Routing The Open Vehicle Routing Problem (OVRP) is a complex variation of

logistics operations.Three initialization strategies—Random, Problem (OVRP) using the Genetic Algorithm (GA) method. VRP where vehicles do not return to the depot after deliveries. This

Greedy, and Cluster-First Route-Second—were tested using To determine the distance of the route for initialization makes it difficult to optimize delivery routes, especially when dealing

secondary data from Christofides (2014). Each was run changes by using Genetic Algorithm (GA) method. with large-scale logistics networks, due to its NP-hard and

through GA iterations involving selection, crossover, mutation, combinatorial nature.

and inversion. The results showed that all strategies improved To analyse the best initial population that gives the least Although Genetic Algorithm (GA) is effective in finding near-optimal

route distance, but Greedy Initialization consistently produced impact for Open Vehicle Routing Problem (OVRP). solutions for complex problems like OVRP, its performance is highly

the shortest routes. The total distance was reduced from 7,174 influenced by the quality of the initial population, which plays a
crucial role in guiding the search process.
meters to 4,816 meters. This proves that GA, supported by However, current research lacks a clear comparison of how different

effective initialization, is a powerful method for optimizing initialization strategies impact GA performance in solving OVRP. This

delivery routes in logistics planning.
METHODOLOGY & study aims to analyze and compare three approaches Random,

Greedy, and Cluster-First Route-Second to determine which provides

IMPLEMENTATION the most optimized delivery route.

RESULT AND

DISCUSSION

After 5 iterations using three different initialization strategies, the Greedy Initialization produced

the best results. Route X achieved the shortest distance of 4,816 meters, while Route Y reached

5,658 meters, both using GA operations which include selection, crossover, mutation, and

inversion. The results show that Greedy Initialization is the most effective, with Chromosome X

chosen as the optimal route due to its shorter total distance compared to Chromosome Y. The

selected route for X was: 0-5-7-6-8-14-16-10-9-12-11-1-15-13-3-4-2.

CONCLUSION RECOMMENDATION

The results of this study show that Greedy Initialization is the most

effective strategy when applying the Genetic Algorithm (GA) to solve the Combining Greedy Initialization with clustering techniques or adaptive
approaches could lead to more efficient route generation. Additionally,
Open Vehicle Routing Problem (OVRP). After five iterations, Route X applying the algorithm to larger or real-time datasets would help validate its

reached the shortest distance of 4,816 meters, compared to 5,658 meters effectiveness in more complex and practical logistics scenarios. Integrating

for Route Y. Chromosome X, generated through Greedy Initialization, was machine learning or dynamic adjustment mechanisms to automatically

selected as the optimal solution due to its consistently lower travel generate better initial populations may also improve the algorithm’s accuracy

distance. This confirms that the choice of initialization strategy plays a and reduce computational effort. These improvements can contribute to more

critical role in improving GA performance for route optimization. scalable and intelligent routing solutions in the logistics industry.

SUPERVISOR : NUR AIN ZAWANII

WAN NURFAHIZUL IFWAH BINTI ZULKIFLI

WAN ALIAS