摘要
综合考虑服务水平约束、养护车辆工作时长限制,建立了养护服务区域规划的混合整数规划模型,即选址弧路径规划模型。考虑对区域划分的要求,设计一个基于扫描算法的多项式时间混合启发式算法对问题进行求解。算法的第一阶段对各段道路进行聚类,第二阶段根据服务水平和惩罚成本将各个类分配给备选点,最后一个阶段对备选点进行合并,确定养护站选址及其负责的区域。经实验分析,混合启发式算法区域规划解总成本比分支切割算法高7.89%,其区域重叠度和紧凑度均好于分支切割算法。此外,考虑道路服务时间服从正态分布,对模型和算法进行改进。实验结果表明改进的算法能够以成本为代价降低超额工作量。
Considering both the service level and time duration constraints, the problem of designing service sectors was formulated with a mixed integer linear programing as a location arc routing problem（LARP）. Based on the sweeping method,a polynomial hybrid heuristic algorithm （HHA）with sector design component was developed. The first stage is to decide the clusters,and the second stage is to assign the clusters to the potential sites of depots based on minimum penalty cost criteria and required service level. Finally, the locations of depots and their respective service sectors are determined in the third stage. An experiment on a real network demonstrates that although the total cost of the HHA solution is 7. 89% higher than the total cost of the branch-and-cut solution, it outperforms the branch-and-cut algorithm in terms of both overlap and compactness. Besides, the model and algorithm are improved considering service time normally distributed. The computational results demonstrate that the work overload is decreased at the expense of cost.
出处
《工业工程与管理》
CSSCI
北大核心
2017年第4期120-126,共7页
Industrial Engineering and Management
基金
国家自然科学基金资助项目(71271130)
关键词
区域规划
混合启发式算法
扫描算法
弧路径规划
选址
sector design
hybrid heuristic algorithm
sweeping method
arc routing problem
location
