带服务水平和容量约束的区域规划问题研究

综合考虑服务水平约束、养护车辆工作时长限制,建立了养护服务区域规划的混合整数规划模型,即选址弧路径规划模型。考虑对区域划分的要求,设计一个基于扫描算法的多项式时间混合启发式算法对问题进行求解。算法的第一阶段对各段道路进行聚类,第二阶段根据服务水平和惩罚成本将各个类分配给备选点,最后一个阶段对备选点进行合并,确定养护站选址及其负责的区域。经实验分析,混合启发式算法区域规划解总成本比分支切割算法高7.89%,其区域重叠度和紧凑度均好于分支切割算法。此外,考虑道路服务时间服从正态分布,对模型和算法进行改进。实验结果表明改进的算法能够以成本为代价降低超额工作量。