Approximation Algorithm for 3-Dimensional Vehicle Routing Problem for Fleet of Multi-Agents
Résumé
In this paper, we discuss a 3-Dimensional Vehicle Routing Problem (VRP) for a fleet of multi-agents which doing a surveillance mission above a certain terrain. The fleet must performs routes to visit a set of points while respecting constraints. Since VRP is classified as an NP-hard optimization problem, we propose an approximation algorithm to find a best solution to this combinatorial optimization problem. Thus, we select Genetic Algorithm (GA) to answer this challenge. And to boost-up the performance of GA, we decide to add Saving Algorithm (SA) in constructing the initial population. Also, we use Netlogo as the tool for the experiment and simulation as well. The Experimental result shows that GA can be chosen for finding the optimal flyable route in the 3D environment. And it's combination with SA give a very encouraging result in this project.