Abstract:

The vehicle routing problem (VRP) has become one of the focus issues in operations research and management sciences over the past two decades. One of its principal branches is the dynamic vehicle routing problem (DVRP), which can receive new order requests during the service process and make a timely response, unlike static vehicle routing problems (SVRP) where all information is known before the optimization starts. In this paper, we solve DVRP while using an enhanced genetic algorithm (GA) that tries to increase both diversity and global searching ability. The maximum saving method and the nearest neighbor method are adopted in the crossover operation to improve the path selection. Considering the near distance priority service principle (NDPSP) in the actual operation, a new assessment scheme with penalty factors is applied to our individual assessment. In addition, a paired-t test as a non-parametric statistical analysis is implemented to demonstrate the efficiency of the enhanced genetic optimization algorithm, based on a publicly available VRP benchmark, which includes 21 data sets. Analysis results show that our approach outperformed the published approached based on optimizing results.