第36卷第10期 北京科技大学学报 Vol.36 No.10 2014年10月 Journal of University of Science and Technology Beijing 0ct.2014 应急救援物资车辆运输路线多目标优化 盖文妹)，蒋仲安)四，邓云峰)，李竞》，杜焱》 1)北京科技大学土木与环境工程学院，北京1000832)国家行政学院，北京1000893)中国安全科学生产研究院，北京100012 ☒通信作者，E-mail:jzal963@263.net 摘要运用运筹学中图论及多目标优化的理论和方法建立应急救援物资车辆最佳运输路线的选择模型，并基于启发式算 法求解该模型.从静态网络应急物资车辆运输路线的双目标优化问题入手，设计适合本文模型的算法，并将之推广至含有三 个及三个以上优化目标的路线选择问题.引入时间扩展图的概念，将动态网络中的最佳运输路线问题转化为静态网络中的路 径选择问题.算法实质是通过构造辅助决策函数实现Djst算法的调用，并在辅助函数构成的搜索空间上寻找最优解，是一 种快速的、近似的算法.利用随机路网和真实路网测试本文算法，测试结果与本文的理论分析一致，证明本文算法在应急救援 物资车辆运输路线的多目标优化问题中可行且有较好的应用效果. 关键词应急救援：多目标优化：车辆路线：数学模型：最短路算法 分类号X913.1 Multi-objective route optimization of transporting emergency goods and materi- als for rescue GAI Wen-me.2,JIANG Zhong-n)a,DENG Yun-feng》,LI Jing》,DU Yan” 1)School of Civil and Environmental Engineering.University of Science and Technology Beijing,Beijing 100083,China 2)Chinese Academy of Government,Beijing 100089,China 3)China Academy of Safety Science and Technology,Beijing 100012,China Corresponding author,E-mail:jzal963@263.net ABSTRACT A mathematical model of the optimum route for transporting goods and materials during a disaster period was built by using the graph theory and multi-objective optimization method.For the simple case of a dual-objective optimization,an approximate and fast algorithm was proposed based on the heuristic algorithm and then we extended the promotion to other transportation route optimization problems,which contain 3 and more than 3 optimization goals.The dynamic network routing problem was transferred into a static network routing problem by introducing the time-expanded graph in dynamic network flow analysis,which can provide an appro- priate method for selecting the optimum route of transporting emergency goods and materials.The purposes of the algorithm are to call Dijstra algorithm to calculate the model by constructing several decision support functions and to find the optimal solution in the search space constituted by the auxiliary functions,so the algorithm is a fast and approximate algorithm.The algorithm was tested in a random road network and a real road network,and the results are consistent with theoretical analysis in the text.The test results show that the algorithm has a better effect in solving the multi-objective route optimization problem of transporting emergency goods and materials and its solution efficiency is higher. KEY WORDS emergency rescue:multi-objective optimization:vehicle routing;mathematical models;shortest path algorithm 在我国，自然灾害、事故灾难、公共卫生、社会安全等突发事件时有发生，如“5·12”汶川特大地震、 收稿日期：20130925 基金项目：国家自然科学基金资助项目(71173198)：国家科技支撑计划课题资助项目(2012BAK03B05,2012BAK20B02) DOI:10.13374/j.issn1001-053x.2014.10.016:http://journals.ustb.edu.cn第 36 卷 第 10 期 2014 年 10 月 北京科技大学学报 Journal of University of Science and Technology Beijing Vol． 36 No． 10 Oct． 2014 应急救援物资车辆运输路线多目标优化 盖文妹1，2) ，蒋仲安1) ，邓云峰2) ，李 竞3) ，杜 焱1) 1) 北京科技大学土木与环境工程学院，北京 100083 2) 国家行政学院，北京 100089 3) 中国安全科学生产研究院，北京 100012  通信作者，E-mail: jza1963@ 263． net 摘 要 运用运筹学中图论及多目标优化的理论和方法建立应急救援物资车辆最佳运输路线的选择模型，并基于启发式算 法求解该模型． 从静态网络应急物资车辆运输路线的双目标优化问题入手，设计适合本文模型的算法，并将之推广至含有三 个及三个以上优化目标的路线选择问题． 引入时间扩展图的概念，将动态网络中的最佳运输路线问题转化为静态网络中的路 径选择问题． 算法实质是通过构造辅助决策函数实现 Dijstra 算法的调用，并在辅助函数构成的搜索空间上寻找最优解，是一 种快速的、近似的算法． 利用随机路网和真实路网测试本文算法，测试结果与本文的理论分析一致，证明本文算法在应急救援 物资车辆运输路线的多目标优化问题中可行且有较好的应用效果． 关键词 应急救援; 多目标优化; 车辆路线; 数学模型; 最短路算法 分类号 X 913. 1 Multi-objective route optimization of transporting emergency goods and materi￾als for rescue GAI Wen-mei1，2) ，JIANG Zhong-an1)  ，DENG Yun-feng2) ，LI Jing3) ，DU Yan1) 1) School of Civil and Environmental Engineering，University of Science and Technology Beijing，Beijing 100083，China 2) Chinese Academy of Government，Beijing 100089，China 3) China Academy of Safety Science and Technology，Beijing 100012，China  Corresponding author，E-mail: jza1963@ 263． net ABSTＲACT A mathematical model of the optimum route for transporting goods and materials during a disaster period was built by using the graph theory and multi-objective optimization method． For the simple case of a dual-objective optimization，an approximate and fast algorithm was proposed based on the heuristic algorithm and then we extended the promotion to other transportation route optimization problems，which contain 3 and more than 3 optimization goals． The dynamic network routing problem was transferred into a static network routing problem by introducing the time-expanded graph in dynamic network flow analysis，which can provide an appro￾priate method for selecting the optimum route of transporting emergency goods and materials． The purposes of the algorithm are to call Dijstra algorithm to calculate the model by constructing several decision support functions and to find the optimal solution in the search space constituted by the auxiliary functions，so the algorithm is a fast and approximate algorithm． The algorithm was tested in a random road network and a real road network，and the results are consistent with theoretical analysis in the text． The test results show that the algorithm has a better effect in solving the multi-objective route optimization problem of transporting emergency goods and materials and its solution efficiency is higher． KEY WOＲDS emergency rescue; multi-objective optimization; vehicle routing; mathematical models; shortest path algorithm 收稿日期: 2013--09--25 基金项目: 国家自然科学基金资助项目( 71173198) ; 国家科技支撑计划课题资助项目( 2012BAK03B05，2012BAK20B02) DOI: 10． 13374 /j． issn1001--053x． 2014． 10． 016; http: / /journals． ustb． edu． cn 在我国，自然灾害、事故灾难、公共卫生、社会安 全等突发事件时有发生，如“5·12”汶川特大地震