求解CARP车场选址问题的混合随机搜索算法  

Hybrid random searching algorithm for solving depot-location problem of CARP

作　　者：刘琳[1] 朱征宇[1] 许林[1] 陈飞[1] 

机构地区：[1]重庆大学计算机学院,重庆400044

出　　处：《计算机应用》2010年第6期1508-1512,1605,共6页journal of Computer Applications

基　　金：国家科技支撑计划项目(2007BAH08B04);重庆大学创新性实验计划项目(2008)

摘　　要：针对环保车车场选址问题,提出了一种混合随机搜索算法(HRSA)。新算法利用当车场已知时计算环保车优化行使路线的CARP算法作为车场选址评估函数,为加快收敛速度采用改进的Dijkstra算法计算初始车场地址,进而采用一种局部搜索策略寻找当前车场附近的更优地址,同时为避免陷入局部最优采用一种随机跳变策略探测其他更优地址,实现对解空间的高效搜索。在洒水车车场选址问题上的实验表明,HRSA求解此类问题是有效的。To solve the depot-location of pro-environment vehicles,a Hybrid Random Searching Algorithm （HRSA） was presented.A Capacitated Arc Routing Problem （CARP） algorithm of finding the optimal driven-route of pro-environment vehicles when the depot had been known was used in HRSA as its evaluation function for the current depot.An improved Dijkstra-algorithm of computing its initial depot was also used in HRSA to speed up its convergence rate.The new algorithm can realize an effective searching in the solution space by using a local searching mechanism to find a more optimal depot near the current depot and by using a random searching mechanism to prevent it from getting into a local optimal depot.The validity and efficiency of the HRSA algorithm are shown by the experiments on the depot-location of sprinkler-cars.

关 键 词：弧路径规划问题 车场选址 随机搜索 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构] N945.15[自动化与计算机技术—计算机科学与技术]