Vehicle Routing Problem with Uncertain Travel Time and Soft Time Windows Based on Improved Genetic Algorithm

The uncertainty of vehicle travel time on the road affects transport costs, and the timeliness of delivery, therefore, affects customers’ satisfaction. To be more in line with the actual situation, this paper focuses on vehicle routing problem with uncertain travel time which proposed that the travel time between two customers obeys lognormal distribution. Vehicle routing model is constructed to reduce the delivery cost and improve the timeliness of delivery. Genetic Algorithm (GA) is improved in population initialization, crossover and inserting Large Neighborhood Search (LNS), to better solve the proposed problem. Two scenarios of constant speed and uncertain travel time are solved by the standard and improved GA respectively. The results demonstrate that the improvements proposed for GA lead to an average solution quality enhancement of 13.60%. Accounting for uncertainty in vehicle travel times aligns better with reality and improves the fulfillment of time windows for more customers.