Utility theory offers an elegant and powerful theoretical framework for design and analysis of autonomous adaptive communication networks. Routing of messages in such networks presents a real-time instance of a multi-criterion quasi-optimization problem in a dynamic and uncertain environment. In this paper, we examine several heuristic decision functions that can be used to guide messages along a near-optimal (e.g., minimum delay) path in a large network. We present an analysis of properties of such heuristics under a set of simplifying assumptions about the network topology and load dynamics. In particular, we identify the conditions under which one such utility-theoretic heuristic function is guaranteed to route messages along an optimal (minimum delay) path in a network with uniform load except for a single hotspot (when it is assumed that the network load stays constant during the time-frame of interest). We derive bounds on the cost of a sub-optimal path (relative to the cost of an optimal path) as well as the probability that a resulting route between a randomly chosen source-destination pair is suboptimal. We then present a modified heuristic function that is guaranteed to eliminate sub-optimal routes under the same set of assumptions about network topology, load, and load dynamics. We conclude with a brief discussion of the relevance of the theoretical results presented in the paper to the design of intelligent autonomous adaptive communication networks and an outline of some directions of future research.