An improved heuristic algorithm for multiple vehicle routing problem

Road transportation represents one of the most frequently used modes of commercial transportation within supply chain networks. A large amount of freight is moved across roads via trucks, contributing significantly to the economic development of the United States of America. However, the costs in the trucking industry have been on a steady up climb with costs associated with labor and fuel being the major contributors. An effective way to reduce this cost is to optimize routes for freight delivery. This approach reduces the total distance travelled to deliver goods to customers and would in turn reduce fueling cost and labor hours. Optimal routing of vehicles can be carried out by using either exact algorithms or heuristic algorithms. Due to the inefficiencies associated with exact algorithms, heuristics are preferred and has been proven to be practically applicable due to its reduced computational time. However, because heuristics at best only produce near optimal solutions, opportunities exist to improve the effectiveness of existing algorithms to provide better solutions. The main objective of this research is to improve the effectiveness of a heuristic algorithm for the large size vehicle routing problems developed by Shivani Patil in 2019. The heuristic algorithm is a hybrid of a novel grouping technique and a modified minimal spanning tree. The grouping technique optimally divides the total number of customers into groups while the modified minimal spanning tree technique optimizes the routes within each group. To validate the effectiveness of the modified algorithm, its output was compared with the output of the original algorithm and a hybrid of k-means clustering & genetic algorithm using the same data set