A harmony search-based memetic algorithm for vehicle routing problem with order release dates and flexible time windows

This work studies the vehicle routing problem in the post-pandemic era of E-commerce home deliveries with order release dates and flexible time windows. The order release date indicates when the customers’ goods are ready at the depot for final dispatch. The flexible time windows suggest that the customers receive the products earlier or later than the specified time windows with a given tolerance. This problem not only takes into account the difference in order release dates, but also considers that customers have a certain degree of tolerance for early arrival and delay of service starting time under unforeseen factors, but there will be punished for early arrival and delay, which is more in line with practical needs. We first formulate a mixed-integer linear programming (MILP) mathematical model in this work. Owing to the computational intractability associated with the problem, we propose a harmony search-based memetic algorithm divided into two stages for solving large-sized instances quickly. We test both approaches on a wide range of benchmark problem instances and generated instances. Besides, we perform a detailed sensitivity and statistical analysis to study the impact of order release dates and flexible time windows on the total costs. The results obtained are indeed encouraging.