Title: Efficient clustering-based constructive heuristics for capacitated vehicle routing

Authors: Ankan Bose; Dipak Laha

Addresses: Department of Mechanical Engineering, Jadavpur University, Kolkata, India ' Department of Mechanical Engineering, Jadavpur University, Kolkata, India

Abstract: In this paper, we address the capacitated vehicle routing problem, a generalised variant of vehicle routing problems, in which the routes are assigned to a fleet of vehicles to serve customers meeting their demands in order to optimise certain criterion. Here, we aim to minimise total length of the routes. Although a plethora of research on vehicle routing appeared in the literature over many decades, a few good construction heuristics exist, namely, the heuristics of Clark and Wright (1964), Segerstedt (2014, 2018), which are used for minimising the total length of routes in the capacitated vehicle routing problem. In this paper, we have modified the heuristics of Segerstedt (2014, 2018) using K-means++ clustering in conjunction with a route merging procedure to enhance the solution quality for this problem. The computational results reveal that the modified approaches significantly improve their performance while not affecting their time-complexity.

Keywords: vehicle routing; K-means clustering; K-means++ clustering; heuristics; optimisation.

DOI: 10.1504/IJMOR.2024.138465

International Journal of Mathematics in Operational Research, 2024 Vol.27 No.4, pp.458 - 478

Received: 16 Jul 2022
Accepted: 18 Feb 2023
Published online: 04 May 2024 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article