Implementation of Genetic Algorithm on Vehicle Routing System

Abstract

This study explores the use of Genetic Algorithms (GAs) to solve the Vehicle Routing Problem (VRP) in logistics. GAs, inspired by evolutionary principles, prove effective in finding efficient routes for a fleet of vehicles serving customers where the goal is to find the most efficient routes for a fleet of vehicles serving customers. Inspired by evolution, GAs prove effective in this task by selecting promising routes, creating new options through crossover and mutation, and evaluating fitness based on objectives and constraints. The study incorporates techniques like reparation, penalties, and adaptive tuning to boost GA performance. Real-world applications in transportation and logistics demonstrate substantial cost savings. The key takeaway is the crucial role of parameter selection, representation design, and fitness function formulation in the success of GAs in solving VRP. The combination of GAs and VRP resolution shows promise in optimizing logistics, improving efficiency, and enhancing service quality. In simpler terms, the study explores a smart way, inspired by nature, to figure out the best routes for delivery trucks, leading to significant cost savings and better service.

Introduction

I. INTRODUCTION

In today’s world, goods and services are travelled through long distances and figuring out the best routes for transportation is a difficult task. The main challenge for the transporters or delivery services is time management and cost efficiency as it directly affect the overall performance.

 In general, the criteria that are needed to be considered to send the product or an item for the delivery services consist of the number of delivery points, recollection of goods, warehouses, cost, logistics, etc., and the location mainly depends on the latitude and the longitude of different places.

A. Vehicle Routing Problem (VRP)

The problem of fleet management of trucks was first addressed by Dantzig and Ramser in 1959. They first introduce the “Truck Dispatching Problem” which is focused on optimizing the routes of a fleet of gasoline delivery vehicles. After five years, In 1964 Clarke & wright extended this problem to a linear optimization problem that is widely used in the field of logistics and transportation. This became the ‘Vehicle Routing Problem’ that is widely studied in the various fields of management science.

 The Vehicle Routing Problem (VRP) is a broad category of problems where the objective is to establish the optimal routes for a fleet of vehicles originating from one or more depots to serve multiple cities or customers scattered across diverse geographical areas. The depot point is the hub where vehicles are dispatched, loaded with goods, and returned after completing their delivery routes, The multitude of delivery points or service stations are spread across the geographical area and each location is associated with specific customer demands.

The goal is not only to find the shortest path but also to the sequence of these locations in a way that maximizes efficiency as it directly impacts fuel consumption and transportation costs.

B. Genetic Algorithm (GA)

Genetic Algorithm is commonly used as a meta-heuristic algorithm. It Is an adaptive algorithm that can be adjusted based on the environment. It is based on genetic and natural selection mechanisms that are applied for a given number of iterations that are used to generate high-quality or optimal solutions for optimization problems. 

The flow of the genetic algorithm is as follows:

1. Initialization: Genetic Algorithm begins with initializing the initial populations (chromosomes). Each solution represents a random solution and the population is randomly generated using specific criteria.
2. Evaluation: The fitness function evaluates the fitness of each population. The fitness function quantifies how well each solution satisfies the problem constraints. The goal is to maximize or minimize the fitness value, depending on the nature of the problem.
3. Selection: Select the individuals from the initial population that serves as parent to the next generation. The selection is based on fitness, with fitter individuals having a higher chance of being selected.
4. Reproduction: 

• Crossover: This imitates the genetic recombination that occurs in nature, in which the offspring are created by combining genetic material from selected parents using the crossover operator.
• Mutation: The genes of generated offspring are altered or random changes are made to explore the new regions of the solution space. It helps in maintaining genetic diversity and prevents premature convergence.

5. Convergence Check: Convergence criteria are checked if the algorithm has reached the termination condition such as the specified number of generations or achieving a satisfactory solution.

Utilizing Genetic Algorithms (GAs) in Vehicle Routing Problems (VRP) emerges as an effective strategy to address the challenges of optimizing vehicle routes. GAs offers an optimal solution for planning delivery routes, providing a dynamic and adaptable approach to route optimization.

Genetic Algorithms operate by identifying and selecting optimal routes from a pool of potential solutions. Through processes such as crossover and mutation, these algorithms generate new options, exploring different combinations of routes. The fitness of each route is then evaluated based on predefined objectives and constraints, ensuring that the generated solutions align with the specific goals and limits set for the VRP.

The varied processes inherent in Genetic Algorithms lead to diverse scenarios, empowering the algorithm to adeptly manage the intricate logistics associated with the Vehicle Routing Problem (VRP). This flexibility is crucial for tackling the inherent variability and challenges in practical vehicle routing situations.

By leveraging the capabilities inspired by genetic evolution, Genetic Algorithms emerge as resilient and effective tools for discovering optimal routes. This, in turn, contributes to improved logistics solutions and heightened operational efficiency.

II. LITERATURE REVIEW

[1] Laporte et al. have introduced an Integer L-shaped algorithm tailored for the vehicle routing problem with stochastic demands, aiming to minimize the expected solution cost while ensuring route demand stays within vehicle capacities. It rigorously solved instances with 25 to 100 vertices and 2 to 4 vehicles, assuming Poisson or normal demand distributions. The success of this approach hinges on robust lower bounds and efficient bounding functionals, yielding high lower bounds at the tree's root and reduced branching despite the problem's complexity. Emphasizing achievable outcomes on moderate-sized instances with realistic assumptions over a holistic solution approach, the research underscores the formidable nature of the stochastic VRP. Future endeavors should gradually relax underlying model assumptions, offering prospects for further investigation and refinement.

[2] Rahul et al., discussed a focused aspect of the Traveling Salesman Problem (TSP) in this study, concentrating on using Genetic Algorithms (GA) for solving the Vehicle Routing Problem (VRP). Notably, when executing the VRP on a multicore architecture, a substantial improvement in program speed was observed. The efficiency, however, depended on the initial and generated populations. Future research aims to explore diverse crossover methods to achieve faster and approximate outcomes. Additionally, investigating specialized GA techniques like non-dominant sorting-based GA (NSGA) and their parallel versions are suggested for obtaining more optimized results swiftly.

[3] In their study, Mahdi Abbasi and colleagues focused on using efficient parallel optimization algorithms for solving vehicle routing problems (VRPs), crucial in minimizing costs for intelligent transportation systems. They introduced an enhanced Genetic Algorithm (GA) tailored for VRP's Traveling Salesman Problem (TSP) and designed it for parallelization on multi-core and many-core systems of Vehicular Cloud Computing (VCC) platforms. Their method concurrently executed GA functions like fitness evaluation, crossover, mutation, and selection on these platforms. By synchronizing kernels on GPU-like processors, they achieved efficient collaborative thread processing. Their findings showed varying performance based on processor types, highlighting that low initial population affected GPU-like processors' efficiency compared to multi-core ones. The study suggests future exploration on optimizing GA computations using CPU/GPU clusters

[4] Gomes et al. applied an adapted Genetic Algorithm to solve a complex logistics challenge in Covilhã, Portugal, dealing with the Multiple Traveling Salesman Problem (m-TSP) in a mountainous area. The aim was to optimize routes for beverage delivery vehicles across approximately 270 establishments over five days a week. By dividing the city into three zones and optimizing daily worker routes, they achieved a 618 km reduction in total weekly travel distance. This approach improved client visits' timeliness, lowered fuel costs, and supported environmental sustainability through shorter logistical routes, contributing to smarter cities.

[5] Dutta et al. explored a crucial aspect of operations—preferring a single solution over multiple ones for time-sensitive tasks. Their study addressed the multi-objective open green vehicle routing problem, emphasizing environmental preservation alongside cost reduction. They proposed a practical variant of the Vehicle Routing Problem (VRP) that aimed to minimize transportation expenses and carbon emissions. Utilizing a hybrid approach combining cluster primary-route secondary method, SPEA2, and VIKOR, they assessed their model's performance against NSGA-II. SPEA2 outperformed NSGA-II based on metrics like generational distance, inverted generational distance, and spread. The study encourages future investigations into uncertainties concerning various parameters in vehicle routing, focusing on sustainability.

[6] Bavar et al. explored a mathematical model in their study to efficiently route cross-docking depots by considering time windows and route pricing. The primary aims were to cut overall costs and minimize freight fares during goods transportation. They employed GAMS software and a genetic algorithm to solve the problem. Comparative analysis showed the genetic algorithm's enhanced efficiency over GAMS, proving suitable for large-scale issues. Their findings emphasized the significance of vehicle routing in cost reduction and distribution system enhancement. Specifically focusing on Chabahar port, their model exhibited the potential to decrease cargo transportation costs.

III. PROPOSED FRAMEWORK

1. CSS (Cascading Style Sheets): CSS is a fundamental technology used in web development to style and format the layout of web pages. It provides the means to customize the appearance of HTML elements, including fonts, colors, spacing, and positioning, enhancing the visual appeal and user experience of websites.
2. JavaScript: JavaScript is a versatile programming language primarily utilized for web development. It empowers interactive elements, dynamic content, and functionality within web pages. With JavaScript, developers can create features such as form validations, interactive maps, animations, and responsive interfaces, enriching the user experience.
3. Node.js: Node.js is a server-side JavaScript runtime environment that enables developers to build scalable and efficient network applications. It leverages an event-driven, non-blocking I/O model, allowing for lightweight and high-performance applications. Node.js is commonly used for real-time web applications, APIs, and server-side scripting.
4. MongoDB: MongoDB is a NoSQL database system designed for managing and storing unstructured or semi-structured data. It utilizes a document-oriented data model, allowing for flexibility in data storage and retrieval. MongoDB's scalability and ability to handle diverse data types make it suitable for applications requiring agile and scalable databases.
5. EJS (Embedded JavaScript): EJS is a templating language that facilitates the creation of dynamic web content by embedding JavaScript code within HTML templates. It simplifies the process of generating HTML pages dynamically by enabling the inclusion of data from the server side, aiding in creating dynamic and data-driven web applications.

IV. FEASIBILITY STUDY

Technological Feasibility: Implemented Project is dependent on a series of technologies and resources, all conveniently accessible and feasible in terms of the requisite technical competencies.

A. Resource Kit:

1. Visual Studio Code
2. Figma (Free version)

B. The Project Requires

1. A laptop for programming purposes
2. Readily available hosting space
3. Easily accessible programming tools
4. Competent programming personnel

V. METHODOLOGY

This study aims to solve the Vehicle Routing Problem (VRP) using a genetic algorithm implemented in JavaScript. The primary goal is to optimize delivery routes for vehicles, minimizing travel distance while efficiently servicing multiple locations.

Showcases the distribution of programming languages used in Development, where JavaScript accounts for 54.4%, EJS comprises 23.0%, and CSS makes up 22.6% of the total.

The initial phase involves defining the problem scope of optimizing vehicle routes in the Vehicle Routing System. It includes understanding the requirements, selecting appropriate algorithms, and setting up the groundwork for implementation in JavaScript. Moreover, the project highlights user interaction and visualization. It allows users to engage with the system, modify locations, and visually observe optimized routes on a canvas.

A. Implementation Overview

The methodology involves distinct components for different functionalities:

1. Route Representation: Random generation of routes incorporating starting depots and fitness calculation based on the covered distance.
2. Genetic Algorithm (GA) Operations: Management of route populations, selection of superior routes, and application of crossover and mutation for evolving solutions.
3. Location Representation: Handling individual delivery locations and their visualization on the canvas and Document Object Model (DOM).
4. User Interface: Providing an interactive interface for user actions related to locations, depot settings, and VRP-solving initiation.

B. Implementation of The Project

1. Chromosome Representation: The Chromosome class generates possible solutions by creating routes for vehicles to visit various locations. It ensures these routes start and end at specific points (depots) and avoids repeating locations. These routes' effectiveness is measured by calculating their fitness based on the total distance covered.
2. Genetic Algorithm Implementation: In the process of implementing the Genetic Algorithm (GA), a series of steps are followed to find the best solutions for the Vehicle Routing Problem (VRP). Initially, a group of chromosomes, each representing a potential solution, is created. This ensures that there are different starting points to explore various possible solutions. These chromosomes' efficiency is then assessed by checking how well their routes perform. Based on this evaluation, the chromosomes are ranked according to their performance, influencing their likelihood of being selected for future steps. The GA uses selection mechanisms, such as roulette wheel selection, to pick chromosomes with better performance for reproduction. Through crossover operations, genetic information is exchanged between selected parent chromosomes to create new chromosomes, aiming to explore diverse solutions. Additionally, introducing mutation helps prevent the algorithm from sticking to less effective solutions too early. After these genetic operations, a new offspring is formed, replacing the previous one. The process continues until certain criteria, like reaching a satisfactory solution or a set number of generations, are met, signifying the algorithm's completion.
3. Chromosome and Genetic Algorithm Integration: The Chromosome class interacts seamlessly with the Genetic Algorithm class to perform the necessary genetic operations such as reproduction (via crossover), mutation, fitness assessment, etc. This ensures a smooth and consistent interaction between these two basic parts of the algorithm. This allows the GA class to easily access and manipulate the Chromosomes represented by the instances of the chromosome class. The GA class can effectively manage the selection of the Chromosomes, perform genetic operations to create new solutions and assess their fitness scores according to predefined criteria. This smooth and consistent integration makes it easier for the algorithm to evolve and refine potential solutions represented by the Chromosomes in the Genetic Algorithm and significantly improves the ability of the algorithm to explore and converge on optimal or near-optimal solutions to the vehicle routing problem (VRP).
4. User Interface Development: The User Interface Development stage focuses on crafting an interactive interface using web basics like HTML, CSS, and JavaScript. This interface enables easy engagement with the Vehicle Routing Problem (VRP) solution. Users can input locations, set depots, and see optimal routes visually. The front-end makes interacting with the VRP solution effortless for a smooth experience. Crucially, it integrates with Backend functionalities, using technologies like Node.js, MongoDB, and EJS for server-side rendering. This integration ensures the front-end aligns with backend processes, managing secure logins, user sessions, and efficient data handling.
5. Location Representation: Location implementation plays a crucial role in managing location data. It defines the Location class responsible for creating and handling individual locations on the map. The class encapsulates essential attributes such as coordinates (x, y), unique identification (ID), and the designation of whether a location serves as a depot or not. Additionally, for visually representing locations on the canvas through geometric shapes and styles HTML5 Canvas API is used. Moreover, the user interface creates and manages DOM elements for each location, which allows users to interact with these locations by setting depots, displaying coordinates, and providing options to delete locations as needed. Overall, the Location class serves as a foundation for managing location-related data and visualization.

VI. IMPLEMENTATION

The optimization process progresses through the following organized steps:

1. Initialize GeneticAlgorithm class with parameters: pool, depot, crossoverRate, mutationRate, populationSize, generationSize, elitism.
2. Set mutationRate, crossoverRate, populationSize, generationSize, pool, depot, elitism, currentGeneration, nextGeneration as class attributes.
3. Define a method go():

a. Invoke createPopulation() method.

b. Invoke rankPopulation() method.

c. Iterate through generationSize:

• Output progress percentage.
• Invoke createNextGeneration() method.
• Invoke rankPopulation() method.

d. Return the currentGeneration.

4. Define createPopulation() method:

a. Loop for populationSize times:

• Create a new Chromosome object using pool, depot, and mutationRate.
• Add the Chromosome to the currentGeneration.

5. Define rankPopulation() method:

a. Set totalFitness to 0.

b. Calculate totalFitness by summing up each chromosome's fitness in the currentGeneration.

c. Sort the currentGeneration based on chromosome fitness in ascending order.

6. Define createNextGeneration() method:

a. Initialize an empty array nextGeneration.

b. If elitism is true, add the highest fitness chromosome to the nextGeneration.

c. Loop until populationSize - 1, incrementing by 2:

• Select parent1 and parent2 using rouletteSelection().
• Perform crossover based on crossoverRate, creating child1 and child2.
• Mutate child1 and child2.
• Add child1 and child2 to nextGeneration.

d. Set currentGeneration to a copy of nextGeneration.

7. Define rouletteSelection() method:

a. Generate a random number randomFitness between 0 and totalFitness.

b. Initialize increasingFitness to 0.

c. Loop through the currentGeneration:

• Increment increasingFitness by the fitness of the current chromosome.
• If increasingFitness is greater than or equal to randomFitness, return the current chromosome.

d. Return the last chromosome in currentGeneration if no chromosome is selected.

VII. RESULT AND ANALYSIS

The result demonstrated from the project:

In the illustrated figure 4, each set of coordinates serves as a geographical marker, representing delivery destinations where vehicles are assigned to transport products or shipments. The adaptability of the solution is evident in its ability to dynamically accommodate additional locations. Users can effortlessly input the latitude and longitude values of new destinations into the system through a user-friendly interface. This streamlined process allows for the seamless addition of fresh delivery destinations to the existing list.

Figure 6, visually presents routes for multiple vehicles, with each route identified by the starting depot point and corresponding coordinates or locations the trucks are directed to visit. This graphical representation enables users to intuitively generate optimized routes for up to 20 vehicles, elevating the user experience and facilitating efficient route planning in logistics operations.

VIII. APPLICATION

Vehicle Routing Problem (VRP) using Genetic Algorithms (GAs) extend across various industries, offering innovative solutions to complex logistics challenges. In the realm of transportation and delivery services, GAs applied to VRP can optimize routes for fleets of vehicles, leading to substantial cost savings, reduced fuel consumption, and improved delivery efficiency. In the context of e-commerce and online retail, GA-driven VRP applications can enhance last-mile delivery, ensuring timely and cost-effective shipment of goods.

Additionally, in the field of waste collection and management, GAs can streamline garbage collection routes, minimizing environmental impact and operational costs. The adaptability of GAs makes them invaluable in scenarios involving dynamic scheduling, such as in healthcare for patient transportation or emergency services for efficient response routes. Overall, the applications of VRP using GAs have the potential to transform various sectors by providing intelligent and optimized solutions to intricate routing problems.

IX. FUTURE SCOPE

The scope for the application of Genetic Algorithms (GAs) in solving the Vehicle Routing Problem (VRP) is promising, with numerous avenues for advancement and refinement. As technology continues to evolve, integrating machine learning techniques and artificial intelligence with GAs could enhance the adaptability and decision-making capabilities of routing algorithms. Real-time data integration, including traffic updates, weather conditions, and dynamic customer demands, could further optimize route planning, making it more responsive to changing scenarios. Additionally, the scalability of GA-driven VRP solutions could be explored to handle larger fleets and more extensive logistical networks. Collaborative efforts with smart city initiatives and advancements in Internet of Things (IoT) technologies may open new frontiers for intelligent and interconnected routing systems. Moreover, there is potential for synergies with autonomous vehicle technologies, paving the way for self-optimizing and self-adaptive routing solutions. The future holds exciting prospects for the continued evolution and refinement of GA applications in VRP, contributing to more efficient, sustainable, and technologically advanced logistics solutions.

X. ACKNOWLEDGEMENT

We thank Prof. Jyoti Parashar* our project's mentor, Dr. Akhilesh Das Gupta Institute of Professional Studies. Whose leadership and support have served as the compass guiding us through the challenging terrain of this research. Her valuable feedback and contribution remarkably enhanced our manuscript.

Conclusion

In summary, the fundamental aim is to revolutionize the logistics landscape by utilizing Genetic algorithms (GAs) to address the complexities of Vehicle routing problems (VRP). The primary focus is to provide a sophisticated yet accessible solution for optimizing the delivery routes, that aims to reshape the complexities of serving customers efficiently. The initiative in research directly benefits logistics stakeholders by introducing a powerful tool that aims to minimize transportation costs, reduce environmental impact, and enhance overall operational efficiency. By deploying the principles of genetic algorithm, it streamlines the route planning process and offers a comprehensive and dynamic approach to find the most optimal path for delivery of vehicles. Genetic Algorithms (GAs) emerge as a fitting meta-heuristic algorithm for addressing the challenges in vehicle routing problems. Alongside Tabu Search and Ant Colony Optimization, GAs are considered suitable for solving logistics operations. The application of these meta-heuristic algorithms is showcased to derive approximate and near-optimal solutions, leveraging the existing routing plan. Within constrained time frames, these algorithms excel in generating revised routing plans, contributing to the efficient resolution of vehicle routing problems. Furthermore, beyond the immediate benefit to individual businesses, it aims to contribute to the broader effectiveness of logistics on a macro scale. By facilitating smarter and more efficient routes, it seeks to drive increased cost-effectiveness, reduced fuel consumption and improved quality of end customers.

References

[1] Laporte, G., Louveaux, F., & Van Hamme, L. (2002). An Integer L-Shaped Algorithm for the Capacitated Vehicle Routing Problem with Stochastic Demands. Operations Research, 50(3), 415–423. https://doi.org/10.1287/opre.50.3.415.7751 [2] Saxena, Rahul & Jain, Monika & Malhotra, Karan & Vasa, Karan. (2020). An Optimized OpenMP-Based Genetic Algorithm Solution to Vehicle Routing Problem. 10.1007/978-981-13-9680-9_20. [3] Abbasi, M., Rafiee, M., Khosravi, M.R. et al. An efficient parallel genetic algorithm solution for vehicle routing problem in cloud implementation of the intelligent transportation systems. J Cloud Comp 9, 6 (2020). https://doi.org/10.1186/s13677-020-0157-4 [4] Gomes, D.E.; Iglésias, M.I.D.; Proença, A.P.; Lima, T.M.; Gaspar, P.D. Applying a Genetic Algorithm to a m-TSP: Case Study of a Decision Support System for Optimizing a Beverage Logistics Vehicles Routing Problem. Electronics 2021, 10, 2298. https://doi.org/10.3390/electronics10182298 [5] Dutta, Joydeep & Barma, Partha & Mukherjee, Anupam & Kar, Samarjit & De, Tanmay. (2022). A hybrid multi-objective evolutionary algorithm for open vehicle routing problem through cluster primary-route secondary approach. International Journal of Management Science and Engineering Management. 17. 1-15. 10.1080/17509653.2021.2000901. [6] Bavar, Farhad & Sabzehparavr, Majid & Ahmadi Rad, Mona. (2021). Routing cross-docking depots, considering the time windows and pricing routes (case study: container transportation of Chabahar port). Nexo Revista Científica. 33. 409-422. 10.5377/nexo.v33i02.10780. [7] Kadar, Abdul & Masum, A.K.M. & Faruque, Md & Shahjalal, Mohammad & Iqbal, Md & Sarker, Iqbal. (2011). Solving the Vehicle Routing Problem using Genetic Algorithm. International Journal of Advanced Computer Science and Applications. 2. 10.14569/IJACSA.2011.020719. [8] V. Praveen, Dr.P. Keerthika, G. Sivapriya, A. Sarankumar, Boddu Bhasker, Vehicle Routing Optimization Problem: A Study on Capacitated Vehicle Routing Problem, Materials Today: Proceedings, Volume 64, Part 1, 2022, Pages 670-674, ISSN 2214-7853, https://doi.org/10.1016/j.matpr.2022.05.185.

Copyright

Copyright © 2023 Tushar Rajora, Abhi Gaur, Tushar Kapoor, Anand Kushwaha, Yogya Prashar, Jyoti Parashar. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.