一种求解多车型CARP的有效memetic 算法

鉴于多车型限量弧路由问题(heterogeneous vehicle capacitated arc routing problem, HVCARP)广泛的应用，研究了其优化模型及求解算法.首先将HVCARP的路径费用分为可变费用和固定费用，通过车辆惩罚系数将车型和路径紧密相连，形成费用计算公式.针对HVCARP的特点，提出了一种针对车型的同档路径交换车辆算子，该算子根据路径负载以及车队情况，调整服务车型，以实现服务费用的最优化；然后以其为局部搜索算子，设计了用于求解HVCARP的memetic算法；最后，以CARP标准测试集的修改算例进行实验验证，实验结果表明，基于同档路径交换车辆算子memetic算法是有效的.
Abstract：In view of wider application background，heterogeneous vehicle capacitated arc routing problem (HVCARP) and approach for it are investigated in this paper. First, the cost of any route in HVCARP is divided into two parts, i.e., variable cost and fixed cost, and penalty coefficients for vehicles keep the routes and their vehicles close. In view of the characteristic of HVCARP, we propose a local search operator, namely exchanging vehicles among same group routes (EVSGR) for the vehicle，which adjusts the vehicles for routes based on the loads and vehicles of the routes so as to minimize the cost. Then，the EVSGR operator is integrated into memetic algorithm (MA), and the resultant algorithm is used to solve HVCARP. Finally, the proposed algorithm is run on the instances modified from the instances of the benchmark data sets for CARP, and a large number of experimental results show that the EVSGR operator based memetic algorithm is effective for HVCARP.