Using Node Combination Method in Time-expanded Networks

sahar abbasi (Department of Industrial Engineering, Najafabad Branch, Islamic Azad University, Esfahan, Iran)

International Journal of Supply Chain Management
Vol 1, No 1 (2012): International Journal of Supply Chain Management (IJSCM)

This study concerns the problem of finding shortest paths in time-expanded networks by repeatedly combining the source nodes 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.