潘义勇，马健霄

(南京林业大学 汽车与交通工程学院，江苏 南京 210037)

随机交通网络最小期望-均方差路径问题罚函数解法*

潘义勇，马健霄

(南京林业大学 汽车与交通工程学院，江苏 南京 210037)

为了反映交通网络中考虑可靠性的路径选择行为，基于数学规划理论建立随机交通网络环境下最优路径问题的数学模型并构造罚函数法求解该约束优化问题。首先，在路径目标函数中加入了均方差以反映路径的可靠性，建立随机网络环境下最小期望-均方差路径问题的数学规划模型；其次，引入罚函数和罚因子，把非线性约束优化问题转换为无约束优化问题；第三，构造拟牛顿法求解无约束优化问题，最终获得原问题的精确解；最后，针对实际交通网络开展了数值实验并对数值结果进行了分析。数值结果表明：提出的算法是能获得最优路径的精确解。

交通运输工程；随机网络；最优路径；罚函数；拟牛顿法

0 引 言

交通网络最优路径问题是车辆导航系统的核心问题[1]。交通网络最优路径问题的建模有两个关键环节，首先是建立能够准确反映交通网络耗时随机特性的网络模型，通过数据采集获取并拟合网络模型参数，实现网络模型的数值化计算；其次是在交通网络模型基础上建立最优路径模型，选择合理的路径目标函数准确反映实际交通网络路径选择行为。其中，前者发展已经很成熟，随机网络[2]指网络的边的权值是服从一定概率分布函数的随机变量，反映交通网络行程时间的随机特性。……