Implementation of an H-PSOGA Optimization Model for Vehicle Routing Problem

Introduction

The underlying optimization problem aims at either minimizing or maximizing an objective function subject to certain constraints. This objective function and its constraints can either be linear or nonlinear. In the perspective of Global optimization, the task of finding the best set of appropriate conditions to satisfies an objective under given constraints is paramount with great usefulness in practice. In many applicative scenarios such as Banks (Donkor, Darkwah, Appati, Gakpleazi, & Wisdom, 2018), Gas production (Amoako-Yirenkyi, Ntherful, Fosu, Gogovi, & Appati, 2014), Telecommunications (Boatemaa, Appati, & Darkwah, 2018), with schools as a case study where students and teachers are bused to and from school freely every day, it is the responsibility of management to reduce cost. Traditionally, as the current practice to reduce transportation cost, management of the institution manually plan on the set of routes each bus has to take in order to prevent visiting a single breakpoint more than once while reducing the distance taken by the vehicles on the routes. However, with a proper route schedule which is computationally defined, the distance covered is expected to reduce significantly, thereby reducing the cost of transportation. Many optimization techniques are implemented for solving problems of this kind. Among these techniques are Particle swarm optimization (Marinakis, Marinaki, & Migdalas, 2017; Marinakis, Iordanidou, & Marinaki, 2013; Peng & Qian, 2010; Gupta & Saini, 2017), Genetic algorithm (Mohammed, et al., 2017; da Costa, Mauceri, Carroll, & Pallonetto, 2018) and Simulated annealing (Wei, Zhang, Zhang, & Leungd, 2018; Wang, Zhao, Mu, & Sutherland, 2013; Afifi, Dang, & Moukrim, 2013). As a pro, the Particle swarm optimization (PSO) is easy to implement, and it involves only a few adjustable parameters. However, in some selected cases, the PSO does not guarantee a good optimal solution. This problem from literature is attributable to the lack of the diversity nature in the PSO, which reduces its exploration capability in searching for a wide vector of solutions. In order to extend the exploratory capability of PSO, this study seeks to incorporate two Genetic Algorithm (GA) operators: crossover and mutation into PSO to obtain a hybrid algorithm. This hybrid algorithm is then implemented on a primary sample data taken from the vehicle logbook of Shama Senior High School to validate its effectiveness against PSO and GA implemented in singles.