关键词: 禁忌搜索算法, 开放式车辆路径问题, 需求拆分, 车辆路径问题

Abstract: The traditional Open Vehicle Routing Problem(OVRP) assumes that the demand of the clients can not be split and the type of vehicles is the same, but in the practical logistics distribution, the type of vehicles is not exactly the same, sometimes the transportation cost can be reduced by splitting the demand of clients to make the best of the loading capacity of vehicles. This paper proposes the Split Delivery Open Vehicle Routing Problem with Heterogeneous Vehicles(SDOVRPHV), presents mathematic model of the integer programming of the problem, solves it with Tabu search algorithm and improves the generation of the initial solution and neighborhood structure in the algorithm. By experiments, the validity of the model is validated, and the results are compared with the traditional OVRP which indicates that the algorithm can reduce effectively the transportation cost.

Key words: Tabu search algorithm, Open Vehicle Routing Problem(OVRP), split delivery, Vehicle Routing Problem(VRP)