Using Node Combination Method in Time-expanded Networks

Abstract

This study concerns the problem of finding shortest paths in time-expanded networks by repeatedly combining the source node’s nearest neighbor, time-expanded network is derived from dynamic network G= (V,A,T) and contains one copy of the node set of the underlying ‘static’ network for each discrete time step (building a time layer). we use node combination (NC) method in networks which arc costs can vary with time, each arc has a transit time and parking with a corresponding time-varying cost is allowed at the nodes. The NC algorithm finds the shortest paths with three simple iterative steps: find the nearest neighbor of the source node, combine that node with the source node, and modify the costs on arcs that connect to the nearest neighbor. The NC algorithm is more comprehensible and convenient for programming as there is no need to maintain a set with the nodes’ distances.