Technical report: genetic algorithm for solving capacitated vehicle routing problem / Mohd Faris Mohd Zaki and Muhammad Ammar Zulqornain Abdul Rashid

• Main Authors: Mohd Zaki, Mohd Faris, Abdul Rashid, Muhammad Ammar Zulqornain
• Format: Student Project
• Language: English
• Published: 2017
• Subjects: Study and teaching; Sequences (Mathematics); Analysis
• Online Access: https://ir.uitm.edu.my/id/eprint/109757/1/109757.pdf; https://ir.uitm.edu.my/id/eprint/109757/

The capacitated vehicle routing problem (CVRP) is one of the most important problems in the optimization of distribution networks. The main objective for Capacitated Vehicle Routing Problem (CVRP) is to deliver goods to a set of customer with known demands through min­imum vehicle distance routes, starting and ending with the same depot and carrying limited capacity of the goods. Since it is difficult to solve this problem directly, we used Genetic Al­gorithm for Capacitated Vehicle Routing Problem (CVRP) as to get the optimized route with minimum distance travel without exceeding capacity constraint. The outcomes of GA achieve better result. There are several step in methodology which input data by using operator selection and randomly choose two routes. From the data, we conduct iteration process which consist of crossover, selection and mutation process. Based on the study, we believe that minimum distance for P is 396.66 and the selected order routes is 1-14-2-4-5-8-7-6-16-19-1-12-11-15-3- 13-9-17-18-10-l. The capacity carried for route 1 is 150 and route 2 is 160. While minimum distance for Q is 397.47 and the selected order routes is 1-2-5-3-4-15-7-8-9-19-1-11-12-13- 14-6-16-17-18-10-1. The capacity carried for route 1 and 2 are 159 and 151. Both capacity were valid since it does not exceed our capacity decision which the vehicle cannot carry more than 160. The result that are encoded in Matlab, we found that the best order of the route is 1-5-13-17-4-18-9-12-11-15-1-19-8-3-14-10-6-16-7-2-1 which distance travel is 294.52 and the capacity for route 1 and 2 are 151 and 159 From the result, It can be conclude that GA method can be apply to large city routes.