A scatter search method for heterogeneous fleet vehicle routing problem with release dates under lateness dependent tardiness costs

In this paper, we introduce a heterogeneous fleet vehicle routing problem with release and due dates in the presence of consolidation of customer orders and limited warehousing capacity. Tardiness cost for an order depends upon the magnitude of lateness and the type of the order. A mixed-integer programming model is proposed to minimize the sum of inventory holding, transportation, tardiness, and backorder costs. We demonstrate that customer order characteristics and limited warehousing capacity influence optimal vehicle routes significantly. As the problem is NP-hard, a scatter search (SS) method with strategic oscillation is designed to solve the large-sized instances. Problem-specific characteristics are used to customize the improvement method. Computational experiments suggest that SS finds excellent quality solutions compared to CPLEX in significantly lesser time. SS also performs better than the iterated local search used in the prior literature for the large-sized instances.