Economically Optimal Road Subnetwork

Abstract

The paper deals with the following situation: An area is served by a transportation network, usually the road one. The current quality of the network is not satisfactory for the owner (e.g. a company or public administration), but the reconstruction or recovery of the whole network is not feasible for the economic reasons. Managers, who are responsible for the network, make decisions how to reduce the network and then to reconstruct or recover it meeting certain conditions and minimizing costs. The condition is formulated by means of the set W of important pairs of sources and sinks of transport flows and by the number q ≥ 1 representing the maximal acceptable elongation rate of routes between nodes (vertices) from the set W.

Such a problem can be met e.g. in rural road network reduction for winter maintenance, choice of tram or trolleybus network as a subnetwork of the bus one etc.

The paper describes the mathematical support for that decision making. The mathematical model of the problem is presented. Then a depth-first search type exact method is proposed and verified. Afterwards, a heuristics is described and verified as well. Finally, linear programming version of the problem is added.

The results were applied to urban bus network of Slovak town Piestany.