Loopwise Route Representation-Based Topology Optimization for the Shortest Path Problems

Abstract

This study investigates the analogy between the electric circuit and roadway traffic analyses based on the loop-wise route representation (LRR). These two seemingly different fields share common aspects in terms of primitive components, system behavior, and underlying principles. Considering this analogy, a novel topology optimization is proposed to solve a shortest path problem by introducing artificial loop variables, which are conceptually analogous to loop current in the electric circuit. Then, the loop-wise route optimization is formulated to minimize the travel cost in both symmetric and asymmetric networks. By virtue of using the LRR, the proposed method can guarantee the flow conservation at each node without imposing any constraint functions. To verify the proposed method, numerical experiments in 10 $\times10$ grid-type networks are conducted under various settings. These results show that the shortest path problems can be solved in a simpler form of unconstrained topology optimization. With further work, the proposed method could be applied to solve general vehicle routing problems such as traveling salesman problems in a more effective way.

Keywords

• Loop-wise route representation
• shortest path problem
• sensitivity analysis
• topology optimization
• vehicle route problem