Clustering and Routing in Cross-docking: A Bi-step Methodology for Capacitated VRP with Time Windows

The vehicle routing problem,VRP with time windows commonly known as the CVRPTW is a widely research topic in the cross docking systems. In this paper we present a two-step approach for CVRPTW, the proposed process involves first grouping the customers into clusters, and then solving the CVRPTW for each cluster separately. Clustering technique is used to group similar customers together, based on some criteria such as proximity and demand. This helps in the reduction of the problem given-size and make it more tractable. The clustering algorithms implied for CVRPTW include k-means and k-medoids algorithms. After the clustering step, a routing algorithm is applied to each cluster separately. These algorithms are designed to find the optimal routes for a given set of customers, considering the TW i.e. the time windows and vehicle capacity constraints. The two-step approach has found to be useful in solving large-scale CVRPTWs, as it allows for a more efficient use of computational resources and can lead to improved solutions. In this paper the results of clustering are presented and analyzed by using different configurations in order to find appropriate clusters to be used as an input for further processing and later Parallel Cheapest Insertion[PCI) heuristic is applied for the routing of vehicles and analysis of the resultant distance obtained after routing.