论文部分内容阅读
综合考虑服务水平约束、养护车辆工作时长限制,建立了养护服务区域规划的混合整数规划模型,即选址弧路径规划模型。考虑对区域划分的要求,设计一个基于扫描算法的多项式时间混合启发式算法对问题进行求解。算法的第一阶段对各段道路进行聚类,第二阶段根据服务水平和惩罚成本将各个类分配给备选点,最后一个阶段对备选点进行合并,确定养护站选址及其负责的区域。经实验分析,混合启发式算法区域规划解总成本比分支切割算法高7.89%,其区域重叠度和紧凑度均好于分支切割算法。此外,考虑道路服务时间服从正态分布,对模型和算法进行改进。实验结果表明改进的算法能够以成本为代价降低超额工作量。
Considering the constraint of service level and the limitation of working hours of vehicle maintenance, a hybrid integer programming model of maintenance service area planning is established, namely the arc path planning model of site selection. Considering the requirement of region division, a polynomial-time hybrid heuristic algorithm based on scanning algorithm is designed to solve the problem. In the first stage of the algorithm, each section of road is clustered. In the second stage, each class is assigned to candidate points according to service level and penalty cost. In the last stage, candidate points are merged to determine the location of maintenance station and its responsible area. The experimental results show that the total cost of hybrid heuristic algorithm is 7.89% higher than that of the branch-cut algorithm, and the overlap degree and compactness of the hybrid heuristic algorithm are better than the branch-cut algorithm. In addition, consider the road service time obeying the normal distribution, and improve the model and algorithm. Experimental results show that the improved algorithm can reduce the excess workload at the expense of cost.