Spatial Transportation Networks with Transfer Costs: Asymptotic Optimality of Hub and Spoke Models
arXiv:cond-mat/0702502
Abstract
Consider networks on vertices at average density 1 per unit area. We seek a network that minimizes total length subject to some constraint on journey times, averaged over source-destination pairs. Suppose journey times depend on both route-length and number of hops. Then for the constraint corresponding to an average of 3 hops, the length of the optimal network scales as . Alternatively, constraining the average number of hops to be 2 forces the network length to grow slightly faster than order . Finally, if we require the network length to be O(n) then the mean number of hops grows as order . Each result is an upper bound in the worst case (of vertex positions), and a lower bound under randomness or equidistribution assumptions. The upper bounds arise in simple hub and spoke models, which are therefore optimal in an order of magnitude sense.