摘要： 传统的开放式车辆路径问题假设客户的需求不可拆分、车辆类型相同，但在实际的物流配送中，车辆类型不完全相同，对需求的拆分能充分利用车辆的装载能力，降低运输成本。为此，提出需求可拆分的不同种车辆的开放式车辆路径问题，给出整数规划的数学模型，利用禁忌搜索算法对该问题求解，改进算法中初始解和邻域结构的产生过程。通过实验验证模型的有效性，并将结果与传统的开放式车辆路径问题进行比较，表明该算法可有效减少运输成本。

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

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)

中图分类号: 

• TP18