考虑网络流量的最优路径求解模型和算法

本文旨在解决交通网络中群体车辆的路径选择问题．即为每个车辆寻求最优行驶路径．使之在起迄点间的旅行时间最短．考虑到网络流量对路段旅行时间的影响，先进行流量分配，再同时为各个车辆寻求最短路径．为此，首先给出了考虑流量影响的网络模型，然后建立了基于路段的用于流量分配的变分不等式模型．该模型的解给出了车辆按照最优路径行驶时分配到各路段上的车辆数目．由于该模型是完全基于路段的，从而克服了基于路径方法必须进行路径穷举的缺陷．最后给出了最优路径选择算法，并证明了算法的正确性．本文给出的模型和算法适用于交通畅通、交通拥挤等各种情况．实验结果表明本文提出的模型和算法是非常有效的．

A Model and Algorithm for the Optimal Path Problem Considering the Network Flow

In this paper, we will solve the path choice problem for a group of vehicles in the traffic network, i.e., determining an optimal path for each vehicle whose travel time is the shortest. The influence of network flow on the link travel time is considered. We first assign the flow to traffic network and then determine an optimal path for each vehicle. Therefore, a network model considering the network flow is first stated. Then we formulate a link based variational inequality model for the flow assignment, whose solution is the link flow when all vehicles select the corresponding optimal paths. Since the model is completely link based, that is, its objective function and constraint conditions have no path variables, we needn't enumerate all the paths to evaluate this model. We then put up an algorithm to find an optimal path for each vehicle and verify the algorithm. The model and the algorithm are suitable for the traffic conditions that are expedite, congested, etc. Finally, we present a test example and show that the model and the algorithm we put forth are quite effective for the path choice problem.