锁启凤，张仲荣，窦 站

(1.兰州交通大学数理学院，兰州 730070; 2.中国科学院海西研究院泉州装备制造研究所，泉州 362200；3.北京化工大学机械工程学院，北京 100029)

在交通路网中选择一条最短路径问题被称为标准最短路径(shortest path, SP)问题，该问题可以通过一些有效的算法得到最优解决，如Suzuki等[1]通过启发式算法解决多目标车辆路径优化问题。Zhao等[2]提出多目标启发式函数的蚁群算法解决冷链物流配送路径优化问题。然而出行者希望选择的路径不仅最节约时间，而且其他资源(如长度、油耗等)不能超过预设值，则有了约束最短路径(constrained shortest path, CSP)问题。CSP问题最早由Witzgall、Goldman和Joksch提出并研究[3]，该问题包含一个或多个有上限的附加约束，在实际生活中应用广泛[4-5]。附加的约束使得CSP问题是一个NP难(non-deterministic polynomial hard)问题[6]，因此CSP问题与SP问题不同，不能直接通过标号设置或标号修正算法来解决。近几十年来，研究人员提出了一些有效的算法来求解CSP问题。如Rivera等[7]利用动态规划方法求解单边约束的CSP问题，提出了基于流程的模型和集合划分模型。现实路网中存在不确定因素，如通过某路段的时间、疏散人员的数量以及道路通畅情况等。近年来，研究人员对CSP问题中的不确定因素很感兴趣，Liu[8]系统地提出了不确定随机网络的概念。Wang等[9]考虑到疏散时间的不确定性，提出了一种计算每条路径的模糊期望行程时间的有效方法。Shen[10]考虑交通路网中的诸多不确定因素提出城市物流配送路径优化模型。

目前CSP问题大多仅在确定性条件下考虑，随机条件下的CSP问题得到关注较少。……