Computer Engineering and Applications ›› 2014, Vol. 50 ›› Issue (20): 74-80.

Previous Articles     Next Articles

Research on multi-objective optimization models and hybrid heuristic algorithm of ELRP

SUN Jun1,2, TAN Qingmei1   

  1. 1.School of Economics and Management, Nanjing University of Aeronautics and Astronautics, Nanjing 210016, China
    2.School of Business Administration, Wuxi Institute of Commerce, Wuxi, Jiangsu 214153, China
  • Online:2014-10-15 Published:2014-10-28

ELRP多目标优化模型及其混合算法

孙  君1,2,谭清美1   

  1. 1.南京航空航天大学 经济与管理学院,南京 210016
    2.无锡商业职业技术学院 工商管理学院,江苏 无锡 214153

Abstract: To maximize the time benefits mainly and to minimize the costs as a secondary goal, considering a great many uncertainties of post-disaster, Emergency Location Routing Problem (ELRP) multi-objective optimization model is developed based on a series of assumptions and constraints firstly. Secondly, with the thinking of location-allocation first vehicle-routing second, emergency transfer stations are located and rescue points are allocated in consideration of time window, distance, road resistance and other factors, and then ACO-GA hybrid heuristic algorithm is designed to arrange the routes for global or local path optimization. Lastly, the SOLOMON standard test data is used to test the feasibility of model and algorithm, which then used to solve the numerical example based on Jiangsu earthquake disaster simulations. The computational results show that the model and the improved algorithm have good performance, and solution quality and stability are improved significantly, and its operation results can be used as the theoretical support of the local government emergency response decision-making.

Key words: emergency location routing problem, multi-objective optimization model, ant colony-genetic hybrid algorithm, emergency transfer station, rescue point

摘要: 以时间效益最大化为主要目标、成本最小化为次要目标,考虑灾后纵多不确定因素,基于系列假设和约束条件构建ELRP多目标优化模型;采用先定位分配,再安排路线的思路,首先根据时间窗、距离和路阻等因素进行应急中转站定位和救援点分配,再设计ACO-GA混合启发式算法进行全局和局部路径寻优;运用SOLOMON标准测试数据测试模型和算法的可行性,最后将其用于求解以江苏地震灾害为背景的仿真实例。研究结果表明,优化模型和改进算法具有较好性能,解的质量和稳定性有明显改进,其运算结果可以作为地方政府应急救援决策的理论支持。

关键词: 应急定位-路径问题, 多目标优化模型, 蚁群-遗传混合算法, 应急中转站, 救援点