The Quadratic Shortest Path Problem and its Genetic Algorithm

Authors

Linzhong Liu, Institute of System Engineering, Lanzhou Jiaotong University, Lanzhou 730070, China and Department of Mathematical Sciences, Tsinghua University, Beijing 100084, ChinaFollow
Bing Wu, The West Logistic Corporation Limited of Gansu, Lanzhou 730000, China
Yinzhen Li, Institute of System Engineering, Lanzhou Jiaotong University, Lanzhou 730070, China
Jianning Yu, Institute of System Engineering, Lanzhou Jiaotong University, Lanzhou 730070, China

Document Type

Article

Abstract

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.

Recommended Citation

Liu, Linzhong; Wu, Bing; Li, Yinzhen; and Yu, Jianning, "The Quadratic Shortest Path Problem and its Genetic Algorithm" (2005). ICEB 2005 Proceedings (Hong Kong, SAR China). 156.
https://aisel.aisnet.org/iceb2005/156