Modifying a path into the shortest path

Modifying a path into the shortest path

Duan, Xiaowei (TU Delft Electrical Engineering, Mathematics and Computer Science)

Van Mieghem, P.F.A. (mentor)
Qiu, Z. (graduation committee)

Delft University of Technology

Electrical Engineering

2022-12-20

The inverse shortest path problem (ISPP) is a problem based on graph theory, that is to design link weights in a graph to satisfy that given paths are the shortest between the corresponding node pairs. It can be used in networks of complex systems to solve practical problems such as re-routing in transportation systems and reallocating resources in IP networks. This thesis proposes two new methods based on the simplex algorithm, the split path method (Sp) and the limit constraints method (Lc), to solve the inverse shortest path problem with one predefined path (ISPP-S). The different approaches used to find the constraints in these two methods affect the obtained optimal solution and running time. By analyzing the simulation results (running time, adjustment of link weight as well as the relationship between path length and running time) of these two algorithms in graphs with various structures, we can evaluate the efficiency of Sp and Lc and summarize their applicable networks. After modification, these two methods can be utilized to solve the extended inverse shortest path problem with multiple target paths (ISPP-M) and with target paths in a spanning tree (ISPP-T). In addition, the applicability of these two algorithms is also extended from directed graphs to undirected graphs. The application of Sp and Lc algorithms in a variety of empirical networks is also discussed. Through the analysis of the above problems and the experimental results, we discover that Sp is more suitable to solve ISPP with relatively few constraints (ISPP-S or ISPP in small-sized networks); Lc performs better when solving ISPP with relatively more constraints (ISPP-M or ISPP in large-sized networks).

The inverse shortest path problem
Network
Graph theory
Mathematical optimization
Simplex algorithm

http://resolver.tudelft.nl/uuid:71d23197-e244-4572-9f5a-957a7ecf049f

Student theses

master thesis

© 2022 Xiaowei Duan