In recent decades, significant technological advances have made cruise control systems safer, more automated, and available in more driving scenarios. However, comparatively little progress has been made in optimizing vehicle efficiency while in cruise control. In this paper, two distinct strategies are proposed to deliver efficiency benefits in cruise control by leveraging flexibility around the driver’s requested set speed, and road information that is available on-board in many new vehicles. In today’s cruise control systems, substantial energy is wasted by rigidly controlling to a single set speed regardless of the terrain or road conditions. Introducing even a small allowable “error band” around the set speed can allow the propulsion system to operate in a pseudo-steady state manner across most terrain. As long as the vehicle can remain in the allowed speed window, it can maintain a roughly constant load, traveling slower up hills and faster down hills. This strategy reduces the frequency of transient events (e.g. powertrain downshifts, enrichment following fuel cut-off) and the dramatic inefficiencies that result, particularly in ICE applications. The two strategies mentioned differ based on the propulsion control system’s knowledge of the anticipated elevation profile. Where upcoming elevation information is not known, a reactive strategy is used. This maintains efficient optimized steady-state operation for as long as possible, but then takes corrective action when vehicle speed approaches the boundaries of the allowed speed window. Where elevation of upcoming roads is known, a more capable predictive strategy is used. This can anticipate severe grades in advance and make milder corrections over longer time periods to avoid sharp transient behavior. Both strategies demonstrate that significant improvements in fuel economy and EV range can be achieved by relaxing the requirement that cruise control maintain a single constant speed at all times.