A Parallel Non-dominated Sorting Genetic Algorithm-II for Vehicle Routing Problem in Supply Chain

Transportation of materials is a complex problem at all times. In some pandemic situations, transportation of products becomes a very complex issue for material shipments. The Vehicle Scheduling Problem or the traversal of vehicles is one of the most difficult problems in the transportation and distribution world. The main objective of the Vehicle Scheduling Problem is to obtain a set of the shortest distance routes among customers by satisfying certain constraints. This paper proposes a sequential and GPGPU based Non-Domination Sorting Genetic Algorithm-II approach to solve the Bi-objective Vehicle Scheduling Problem with Time Windows. The objectives of the Vehicle Routing Problem are to minimize the total traveling distance and maximize customer satisfaction by delivering products within specified time windows, by satisfying a set of constraints. Our proposed NSGA-II algorithms performance is compared and analyzed with the standard Solomon benchmark dataset found in the literature. The results demonstrate that both approaches yield superior results. The speedup achieved with the General-Purpose Graphics Processing Unit (GPGPU)-based NSGA-II approach is nearly 4 times faster.