Document Type



The quadratic shortest path (QSP) problem is to find a path from a node to another node in a given network such that the total cost includes two kinds of costs, say direct cost and interactive cost, is minimum. The direct cost is the cost associated with each arc and the interactive cost occurs when two arcs appear simultaneously in the shortest path. In this paper, the concept of the quadratic shortest path is initialized firstly. Then a spanning tree-based genetic algorithm is designed for solving the quadratic shortest path problem. Finally, a numerical example is given.