关键词: 随机弧路径规划问题, 机会约束规划模型, 带修正的随机规划模型, 自适应大规模邻域搜索算法

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.

Key words: stochastic arc routing problem, chance-constrained programming model, stochastic programming model with recourse, adaptive large neighborhood search algorithm