Research on the Time-dependent Multi-depot Open Vehicle Routing Problem with Time Windows
A time-dependent multi-depot open vehicle routing problem with time windows is studied.Based on the traffic conditions,the travel speed function is established.Considering the constraints of vehicle capacity,the distance of vehicles and customer time windows,a mixed integer programming model is established.The objective function is to minimize total cost which includes vehicle travel time cost and vehicle fixed departure cost.A hybrid genetic algorithm(HGA)with two-dimensional coding method is proposed,for which a multi-segment single point crossover strategy,dynamic insertion operator and local search strategy are designed.Finally,27 test cases are generated based on the Solomon VRPTW benchmark dataset,and the hybrid genetic algorithm is used to solve them.The numerical experimental results indicate that the proposed model has not only a significant impact on the total travel time of vehicles by considering the traffic conditions,choosing a reasonable departure time and avoiding the congestion period,but also the HGA is capable to obtain a satisfying solution.