Computational logistics of the vehicle routing problem with time windows

Prag, Krupa
Journal Title
Journal ISSN
Volume Title
problem is of considerable interest, given its prevalence and importance in today’s interconnected and globalised world. The procedure of servicing a set of customers within their respective specified time windows, whilst minimising both the number of dispatched vehicles and total travelled distance is known as the Vehicle Routing Problem with Time Windows VRPTW. The VRPTW is classified as both a Combinatorial Optimisation Problem COP and Multi-objective Optimisation Problem MOP, as well as, is categorised to be a part of the NP H class. Identifying that a fair comparison of the performance of applied solution techniques cannot directly be made, as the results recorded in the literature are not generated under standardised experimental conditions, a comparative review was conducted. In this research, two metaheuristic solution techniques, Genetic Algorithm GA and Particle Swarm Optimisation PSO algorithm, are comparatively reviewed. After conducting experiments on the same hardware and software, the results record the procured solution’s routes, total travelled distance, accumulated wait time and CPU time. The results were studied to draw conclusions and highlight correlations amongst the dataset types, applied solution techniques and solution evaluation metrics. Comparing the obtained results, the GA was found to be more robust and produce better quality solutions in comparison to the PSO algorithm. In contrast to the solutions obtained using the PSO algorithm, the GA procured solutions which bear resemblance to each other, irrespective of the employed solution evaluation metric, and the solutions were found to converge after a fixed number of iterations. As the problem size scales, inherently the difficulty of the problem increases and intrinsically the produced solutions and CPU time are found to be less consistent in comparison to that of smaller sized datasets. In terms of the CPU time taken in procuring a solution, the PSO algorithm is found to outperform the GA. The stochastic nature of the PSO algorithm is reflected in the inconsistent solutions it produces. The employed solution evaluation metric schemes are both formulated as weighted sum averages which prioritise the number of dispatched vehicles. Due to the similarity of the solution evaluation metrics, their influence on the applied solution techniques were found to be indifferent
Computer Science and Applied Mathematics