基于理想点法的多目标最短路求解算法研究

Study of Multi-objective Shortest Path Algorithm Based on Ideal Point Solution

为了简化多目标最短路算法并解决不同度量单位之间存在的换算问题,利用理想点法的优点,探索出一种多目标最短路问题的简便算法。该算法首先确定理想点,计算各目标的k-最短路路径,这些路径组成一个存在可能解的集合,然后对所有的最短路目标值进行归一化处理,并确定所有路径归一化之后的目标值与理想点之间的加权欧几里得距离,从路径集合中寻找与理想点距离最近的路径,该路径即为多目标最短路问题的满意解。最后,给出了算法分析和算法流程,并通过一个虚拟运输网络对算法进行了验证。结果表明:这种算法能够解决多目标最短路问题中不同目标度量单位之间换算或相互矛盾的问题,并能够把复杂的非线性函数转换为简单的线性函数,是一种简单、有效的算法。

In order to simplify the multi-objective shortest path algorithm and solve the conversion problem between different measurement units, we explored a simple algorithm of multi-objective shortest path problem taking advantage of ideal point method. The algorithm determines the ideal points and calculates the corresponding objective k-shortest paths, these paths constitute a set of possible solutions. Then all the target values of the shortest paths are normalized, and the weighted Euclidean distance between each normalized target value and ideal point can be calculated. We can find out the nearest path to the ideal point from the set of paths. That is the satisfactory solution of multi-objective shortest path problem. Finally, we gave the algorithm steps and verified the algorithm through a virtual transport network. The result shows that this algorithm can solve the conversion and mutual contradiction problems among measuring units of different targets on the multi-objective shortest path problem, the algorithm can he able to convert complex nonlinear function to a simple linear function, it is a simple and effective algorithm.