关键词: 管理科学与工程, 路径计划, 动态规划, 车辆路径问题

Abstract: Vehicle routing problems have been extensively studied due to its extensive application and great value on economy. However, two constraints receive less attention, i.e., vehicle speed will be changed with time, and vehicle can service more than one trip. This paper discusses single vehicle routing problem with these two constraints. A mathematic model the optimal object of which is to find the route schedule which has the earliest task completion time is established. It's hard to achieve exact solutions of the problem. So the paper proposes a greed dispatching strategy for the model to compress solution space, and provides a dynamic programming algorithm with FIFO rule. The numerical examples demonstrate that for our model, the solution provided by dynamic programming algorithm is only a satisfactory solution. The numerical examples also indicate the optimal dispatching time decreases while the vehicle load capacity increases, and it gets the minimum when the vehicle load capacity is larger than customers total demand. That is, using larger capacity vehicle will save more dispatching time than using smaller capacity vehicle.

Key words: management science and engineering, route schedule, dynamic program, vehicle routing problem