Transportation network reduction

Abstract

Network reduction problem is formulated as follows: We are given a transportation network T, a set of important origin – destination relations R and a number q greater than 1. The goal is to find a subnetwork S of the given network T such that all shortest paths between all origin – destination pairs from R using only subnetwork S are not longer than q-multiple of the corresponding distance in original network T. A mathematical model and an exact algorithm of just mentioned task is presented.

Keywords

• network reduction
• OD matrix
• k-shortest paths