冯树民，吴海月，王弟鑫

(哈尔滨工业大学　交通科学与工程学院，黑龙江　哈尔滨　150090)



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

冯树民，吴海月，王弟鑫

(哈尔滨工业大学交通科学与工程学院，黑龙江哈尔滨150090)

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

关键词：交通工程；多目标最短路; 理想点法; k-最短路; 加权欧几里得距离

0引言

现实生活中许多问题都属于多目标最优化问题，如工程设计、货物运输、经济规划、金融决策、资源分配等。由于各个目标之间通常存在一些冲突，不可能同时达到最优，因此多目标优化问题一般不存在最优解集，而是一个满意解集，也称为Pareto解集[1-2]。多目标最短路问题属于特殊的多目标最优化问题，如交通网络上的货物运输问题，它需要同时考虑成本、风险、时间等因素并且尽可能使它们最小。……