When money beats time: the effect of length-dependent costs on transport driven by long-range connections

Finding the optimal route between pairs of spatially-separated points is a prevalent problem in technology (transport and communication networks) and nature (foraging and migration). In many situations, each segment of a route is associated with a stochastic waiting time determined by the frequency of making connections over a given distance (the jump rate), and a deterministic travel cost which is a growing function of the connection length (the cost function). The optimal route minimizes a weighted combination of time and cost. When deterministic costs are ignored, broad jump-rate distributions which fall off slowly with distance can dramatically speed up optimal routes: nearly all the distance between origin and destination is covered in a single segment which can be found in a short time. However, introducing a deterministic cost makes these long connections prohibitively expensive, and less useful for optimal routing. We study the trade-off between broad jump rate distributions and growing cost functions in a model that generates ensembles of optimal routes for specified jump rates and cost functions. We find that even gently-growing cost functions (which grow slower than linearly with distance) can strongly suppress the acceleration due to broad jump-rate distributions.