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

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) is to find the transportation route of hazardous materials. Afterward, its application field was extended into finding the transportation routes of the military, emmergance evacution, communication network and computer network. The objectives of DPP include the dissimilary measure, transportation time, transportation distance and so on. The DPP belongs to the problems set known as NP-hard. The degree of difficulty to solve DPP is outranked only by the well known TSP. Marti has summarized the issues in the existing algorithms for DPP in 1999.The evolutionary algorithm has been widely applied in solving the problems in NP-hard. However, Because a solution of DPP is a set of paths and only one path can be obtained from a represent of solution by the decode operation in the existing evolutionary algorithms for shortest path problems, the evolution ideas in these algorithms can't be adopted in the designing of evolutionary algorithm for DPP.This reaearch will focus on developing an encoding approach and a decoding approach such that a set of path can be obtained from the represent of the solution by decoding operation and, consequently, extends the evolutionary algorithms into the solution algorithm of DPP and resolve the indicated issues by Marti in the existing algorithms for DPP.

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

在网络优化中, 存在着大量的 NP-难问题, 例如著名的旅行售货员问题 (traveling salesman problem, TSP). 求解这类问题的算法一直是国内外学者重点研究的内容。 本项目研究的是这些 NP-难问题之一, 即相异路径问题 (dissimilar paths problem, DSP). 该问题最初的应用领域主要是确定危险品运输路径, 之后被广泛地扩展到军事、应急疏散、应急物流运输、通讯和计算机网络运输中的路径问题。 DSP 问题的一个解为一个路径集合, 其目标函数一般呈现为多目标问题, 其中一个目标为相异测度; 按照其求解算法的复杂性, DSP 问题属于强 NP-难问题类, 其难度高于 TSP 问题。. 对 DSP 问题的研究, 主要集中在相异测度的定义和求解算法，其优化目标包括了相异测度、时间和距离等。 Marti 在 2009 年详细总结了现有算法中存在的一些问题和不足。进化算法在求解 NP-难问题中得到了广泛的应用。然而由于相异路径问题的单个解为一个路径集合，且现有的关于路径问题的进化算法中的解的编码和解码操作无法从一个解的编码中解码出一个路径集合，这使在之前的研究中无法将进化算法应用到在求解相异路径问题中去。本研究成果包括了如下几个方面: 1. 设计出了求解 DSP 问题的进化算法; 2. 得到了关于 k-最短路问题 (k-shortest path problem, k-SPP) 算法的改进的实现技术, 进而提高了已有的基于 k-SPP 的 DSP 问题算法的效率; 3. 为了处理 DSP 问题中给定的相异测度阈值, 对约束优化问题进行了研究, 得到了关于多目标约束优化问题的一种一般的约束处理技术; 4. 应用相关的研究成果。. 本研究得到了如下重要成果:. 1. 通过采用一种基于支撑树的新的编码方式, 设计了一种求解 DSP 问题的遗传算法;. 2. 通过对目前应用非常广泛的基于优先权编码的求解路最短径问题遗传算法的改进, 将该算法扩展到对 DSP 求解;. 3. 得到了 k-SPP 算法的新实现技术, 极高的提高了已有的基于 k-SPP 算法的求解 DSP 问题算法的效率;. 4. 研究除了一种全新的多目标约束优化方法.