基于进化计算的洒水车路径优化问题的求解

在利用进化计算对容量限制弦路径车辆行驶问题（Capacitated Arc Routing Problem,CARP）进行研究的基础上,对其数学模型、可行化算子进行改进,以适应实际生活中洒水车车辆路径优化问题。针对此问题,设计了局部搜索（Local Search）算子,此算子在染色体进化中有着显著的作用。来自于现实生活中的某市政环卫部门的实验数据真实可靠。通过进化计算对数据的求解,不仅得到了满意的结果,而且证明了该算法的可靠性及稳定性。在把计算后得出的优化路径用于实际洒水车线路安排后,其环卫部门节约了一定的人力物力,取得了一定的经济效益。根据实验分析,该算法能有效求解一定规模的CARP,并且具有一定的实用价值。

Optimization of sprinkler car routing problem based evolutionary computing

Evolutionary computing is a tool of choice for solving middle or large instances of the NP-hard problem.This paper illustrates how to use the Evolutionary Computing(EC) to resolve the Capacitated Arc Routing Problem(CARP) with the case of a real life problem in the assigning the routing of sprinkler cars.It presents basic components which are combined into the powerful EC method for solving the CARP by improving the existent algorithm and contriving the new method just as local search.The proposed routing plan gives the answer to the real life problem of routing assigning and provides significant economic benefits for the department.