多目标相异路径问题进化算法及其应用研究

项目名称： 多目标相异路径问题进化算法及其应用研究

项目编号： No.71361018

项目类型： 地区科学基金项目

立项/批准年度： 2013

项目学科： 管理科学

项目作者： 刘林忠

作者单位： 兰州交通大学

项目金额： 34.5万元

中文摘要： 相异路径问题目前的研究主要集中在相异测度的定义和求解算法，其最初的应用领域主要是确定危险品运输路径, 之后被广泛地扩展到军事、应急疏散、应急物流运输、通讯和计算机网络运输中的路径问题, 其优化目标包括了相异测度、时间和距离等, 该问题属于NP-难问题类, 其难度仅次于著名的旅行商(TSP)问题。 Marti在2009年详细总结了现有算法中存在的一些问题和不足。进化算法在求解NP-难问题中得到了广泛的应用。然而由于相异路径问题的一个解为一个路径集合，且现有的关于路径问题的进化算法中的解的编码和解码操作无法从一个解的编码中解码出一个路径集合，这使得无法将进化算法应用到在求解相异路径问题中去。本研究将设计新的编码方式和解码方式，使之能够解码出一个路径集合，进而将各类进化算法应用到相异路径问题的求解中，以期解决Marti所指出的问题。同时，将所设计算法应用到对前述的应用领域中。

中文关键词： 网络优化；相异路径问题；进化算法；k-最短路问题；

英文摘要： This project investigates the multi-criteria dissimilar paths problem and its application in the hazardous transportation, emergency evacuation transportation, communction network and computer network. The initial purpose of dissimisilar path problem (DPP

英文关键词： network optimization；dissimilar paths problem；evolutionary algorithm；(k-shortest path problem；