Computational logistics of the vehicle routing problem with time windows
Date
2019
Authors
Prag, Krupa
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
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
Description
Computer Science and Applied Mathematics