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

¹ School of Management, Wuhan Textile University, Sunshine Avenue, Jiangxia District, Wuhan, Hubei Province 430200, P.R. China
² Key Research Base of Humanities and Social Sciences of Universities in Hubei Province – Research Center of Enterprise Decision Support, Wuhan 430073, P.R. China
³ Quantitative Methods & Operations Management Area, Indian Institute of Management Kozhikode, IIMK Campus, Kozhikode 673570, Kerala, India
⁴ Hubei Logistics Development Research Center, Hubei University of Economics, No. 8 Yangqiaohu Road, Jiangxia District, Wuhan, Hubei Province 430205, P.R. China

^* Corresponding author: tiqn07@hbue.edu.cn

Received: 7 November 2023
Accepted: 28 May 2025

Abstract

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.