位势法在交通优化问题中的应用

Application of potential algorithm to traffic optimization

研究了单源多汇交通优化问题及其重要性质,提出了单源多汇交通优化问题的位势法,该算法以关于费用的最短路程为初始势,以非零流的最小费用流为初始流;用标号法找可行的增广链,在标号过程中若某点不满足平衡要求则由到达该点的可行的增广链增广最小费用流的流量;以弧割为工具,计算最小费用流的势的最大调整量,并修改最小费用流的势.算例证明了算法的正确性和复杂性及算法的有效性.

Single origin-many terminus traffic optimization and its importance were studied. Potential algorithm for single origin-many terminus traffic optimization is proposed, in which initialization potential is the shortest distance of cost and initialization flow is a nonzero minimum cost flow. Feasible augmenting chain was searched using labeling algorithm. In the process of labeling, if equilibrium condition of a vertex is not satisfied, flow value of the minimum cost flow is augmented by feasible augmenting chain to this vertex. Optimal adjustive value of minimum cost flow potential is computed using arc cut. And minimum cost flow potential is amended. Correctness and complexity of the algorithm are obtained and proved. And an example explains feasibility of the potential algorithm.