Skip to main content
Open Access Publications from the University of California

UC Berkeley

UC Berkeley Previously Published Works bannerUC Berkeley

Spatial transportation networks with transfer costs: asymptotic optimality of hub-and-spoke models


Consider networks on n 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 n 13/10. Alternatively, constraining the average number of hops to be 2 forces the network length to grow slightly faster than order n3/2. Finally, if we require the network length to be O(n) then the mean number of hops grows as order log log n. 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. © 2008 Cambridge Philosophical Society.

Many UC-authored scholarly publications are freely available on this site because of the UC's open access policies. Let us know how this access is important for you.

Main Content
For improved accessibility of PDF content, download the file to your device.
Current View