Multiphase model based on K-means and ant colony optimization to solve the capacitated vehicle routing problem with time windows

Abstract

The delivery of products on time while reducing transportation costs has become an issue for retail companies in Latin America due to the rise of the e-commerce market in recent years. The Vehicle Routing Problem (VRP) is one of the most studied topics in operations research. This work addresses the Capacitated Vehicle Routing Problem with Time Windows (CVRPTW). The problem focuses on finding optimal routes for each vehicle to serve customers on time and minimal transportation costs under capacity and time constraints. Previous research has addressed the issue by proposing non-exact and exact techniques. This paper aims to select a proper approach and algorithms to present a model to solve the CVRPTW in real-world scenarios by incorporating a Google distance matrix, the empirical knowledge of delivery zones, and a solution relatively easy to deploy in a cloud environment. The proposed model consists of four phases: order scheduling, client clustering, delivery route generation, and operator assignment. We use the K-means algorithm to cluster customers and assign them to vehicles and the Ant Colony Optimization (ACO) algorithm to generate optimal routes. The proposed model was validated through a case study for a retail company in Lima, Perú. The results show that the proposed model reduces the route generation execution time by 95% of the average time. It also cuts travel distance and time by around 182 km and 532 min in 5-day periods.