Heuristics for Two-Level Hierarchical Transportation Networks

Given a set of points, we wish to design a network consisting of a primary link and a set of secondary links connecting the points to the primary link. The objective of the problem is to find the location and length of the primary link in order to minimize the sum of its weighted length and the weighted lengths of all secondary links. We assume that the weight of the secondary link from any point varies depending on the location of that point. In this paper, we describe efficient algorithms and their computer implementation for two scenarios of this problem. In the first scenario, only direct secondary links are allowed from each point to the primary link. In the second scenario, the secondary link from a point is allowed to pass through other points before reaching the primary link.