道路养护中的带随机时间变量的弧路径规划问题

    Arc Routing Problem in Road Maintenance with Stochastic Time Variables

    • 摘要: 研究高速路网日常维护中的养护车辆路径优化问题,考虑车辆养护服务时间和移动时间的不确定性,通过科学的规划手段和精确有效的决策方法,可以减少以前依赖人工决策导致的资源浪费。将问题定义为一个带随机时间变量的限容量弧路径规划问题,分别使用机会约束规划模型和带修正的随机规划模型进行描述。针对问题的随机性,提出自适应大规模邻域搜索算法,在优化过程中根据各个删除策略和插入策略对解的表现对其进行评分,根据轮盘赌原则自适应地选择删除策略和插入策略。与分支切割算法进行比较,解的差距只有1.45%~3.15%,但计算时间有显著提升,证明了自适应大规模邻域搜索算法的有效性,能够适用于中大规模问题。通过真实路网算例,显示了带修正的随机规划模型在特定情况下相对于机会约束规划模型的优越性。还对置信水平α和变异系数CV这2个重要变量进行了敏感性分析,显示了其对解的影响程度。

       

      Abstract: The vehicle routing optimization problem encountered in daily maintenance operation of a freeway network which considers the uncertainty of service and travel time in road maintenance is studied. By the scientific planning means and accurate and effective decision methods, resource waste caused by the artificial decision can be reduced. The problem is defined as a variation of the capacitated arc routing problem (CARP) and a chance-constrained programming model (CCPM) and a stochastic programming model with recourse (SPM-R) are formulated to describe it. An adaptive large neighborhood search (ALNS) algorithm is proposed due to the randomness of the problem. In the process of optimization, each removal heuristic and insertion heuristic are scored according to their performances on the solution. And at each iteration, the choice of a removal heuristic and of an insertion heuristic is based on a roulette-wheel selection principle. Compared with the branch-and-cut (B&C) algorithm, the average gap between the ALNS solutions and the B&C solutions ranges from 1.45% to 3.15%, but the computation time decreases a lot. So the ALNS is proved to be effective and it can be applied to the medium and large-size problems. The results of the instances of the real road network show the superiority of the SPM-R compared with the CCPM under certain circumstances. Some sensitivity analysis on the two important variables α and CV are conducted, and the results show how they affect the solutions.

       

    /

    返回文章
    返回