An exact algorithm for efficient online optimization of HGV path, speed profile and stops for minimising fuel consumption and emissions under time-varying conditions

Abstract

Heavy Goods Vehicles are a major contributor to both fuel consumption and polluting emissions. Freight transport by all modes accounts for around a third of GHG emissions, with HGVs responsible for up to a half of these (FTA, 2010). In this paper we seek to optimise the behaviour of trucks ⎯ in terms of the sequence of roads they follow, the time-of-day they travel, and their speed profile(s) ⎯ using real-time predictive information, in order to reduce such impacts. This research aims to minimise fuel consumption of HGVs on long journeys by 1. Optimising speed and acceleration profiles along each link. Include impact of within-link gradient (undulations). Account for link entry/exit speeds, speed limits and other restrictions. 2. Optimising route, accounting for predictive constraints i.e. downstream conditions that will be encountered if the chosen link sequence and speed profiles are followed. Additionally, we allow for updating of downstream link conditions (hence costs/constraints) with real-time travel time information, plus we include departure and arrival time costs/constraints, and the option to stop en-route. We find optimal solutions (not heuristic) and have implemented the approach on a realistic size network.

Context Our focus is not real-time powertrain control, as typically found in eco-driving which optimises how a vehicle is driven along a given path (Damiani et al., 2014). Nor is it, at the other extreme, the Pollution Routing Problem (PRP) which considers optimal planning of pickups/deliveries on a tour (Dabia et al., 2016; Franceschetti et al., 2013). Typically, PRP lacks explicit representation of all links available in the underlying road network, with stop locations joined by single ‘links’ on which fuel consumption depends only on link-speed, which is assumed constant (even if travel times are time-dependent). Our focus is large trucks making long, inter-urban freight journeys (though the methodology is more general). We therefore consider an intermediate scale of analysis whereby, given real-time information, (re-)planning is made of a single leg of the vehicle’s tour (a leg being between a single pair of pickup/delivery locations). Importantly, given the time-varying nature of traffic congestion, we consider downstream impacts we may try to avoid. When considering fuel consumption for the whole leg, it may in some cases be better to go faster than the instantaneously fuel-optimal speed on one link, in order that the truck passes a downstream link before the onset of a recurrently-congested period, in which (if the truck did not avoid this period) stop-and-start traffic would burn more fuel than is lost on the upstream link. If notified of an incident ahead, it may be preferable to switch to an alternative route, or to delay the start-time of the leg if it has not yet commenced.

Thus our work has a similar starting point to that of Nie and Li (2013) and Miao et al. (2018). Nie & Li (2013) identify the importance of acceleration events for fuel consumption and note the difficulty in explicitly including such detailed factors in path-planning. They assume a simple, universal acceleration profile, with optimal timeindependent speed for each link i.e. no choice of speed, and within-link gradients are ignored. The resulting constrained shortest path problem is illustrated on a small example; difficulties in developing algorithms for general networks are noted. Miao et al. (2018) consider a detailed powertrain-based fuel consumption model, motivated by the effects of traffic signals in an urban setting. They discuss the difficulties in applying conventional shortest path methods due to the inter-dependent impacts of multiple factors (speed, gradient, etc.), and due to spatial interdependencies arising from the gear-shifting schedule or from the vehicle’s management system. They set out a problem of joint optimization of a vehicle’s path and speed profile, subject to an upper bound on travel time, constrained by instantaneous real-time estimates of speeds at detector locations. A heuristic (genetic) algorithm is proposed, and a restricted form of the approach suggested for real-time applications, with the methods tested by implementing them in a traffic simulator. While this work (Miao et al., 2018) may indeed be implemented conditional on time-dependent data, which would give paths that potentially vary by departure time, they use instantaneous constraints on vehicle speeds. That is to say, for a given path and departure time t, it is assumed that the speed profile along the path is constrained by point speeds along the route at current time t, rather than by the predicted speeds at the time the vehicle would pass downstream detectors (a phenomenon we call predictive constraints). Predictive constraints are substantially more complex to incorporate since they introduce a kind of ‘circularity’ – in order to determine an optimal speed profile for a given path, we must define the speed constraints in the optimisation, but in order to define the active time-dependent constraints at a given location, we must know the speed profile. This problem has been solved for a single path (Hvattum et al., 2013) but the problem greatly increases in complexity when speed profile optimization is combined with path choice, since the optimal link speeds

are then in general path-dependent, and then the challenge is to avoid the computational burden of having to enumerate all paths. The time-dependent path and speed profile optimization problem is thus highly challenging when combined with predictive constraints.

Similarly to Miao et al, we wish to represent the impact of detailed acceleration events on fuel consumption; however our different focus on inter-urban journeys and HGVs means our interest is more on the detailed interaction of acceleration events and gradient profiles, rather than their (urban-focused) study of gears and traffic signals. Compared to their urban context, the links we will use are thus potentially relatively long, reflecting the relative sparsity of path options for large heavy vehicles on inter-urban journeys, and thus we must include considerable detail within a link (e.g. a gradient profile rather than the assumed constant link gradient of Miao et al). Unlike (Nie and Li, 2013) and (Miao et al., 2018) we wish to handle time-dependent predictive constraints (as defined above), rather than assuming the simpler instantaneous constraints. However, we wish to do so without compromising on the fidelity of the speed recommendations and fuel consumption model, i.e. avoiding the constant speed assumptions of (Watling et al., 2019). A distinctive element of our method is that we wish to exploit real-time predictive information on time-dependent travel times. Unlike the previous cited works, we wish to develop an exact algorithm with guaranteed optimality. Nevertheless it must be sufficiently efficient to be implementable in a real-time context.

The approach developed comprises two key elements: (i) link optimisation with constraints (ii) build ESTEN and find shortest path.

Link optimization with constraints Consider a link of length , with speed limit . The continuously varying link gradient is ( ), with distance along the link . Given initial speed , and link travel time , we optimise the acceleration profile to minimise fuel consumption (. ). min ( ( ), ( ), ( )) (1) ( )

Since ( ) = + ( ) , link length constraint = ( ) and link exit speed = ( )= + ( ) . Location ( ) = ( ) gives time-dependent gradient, ( ). We discretise using time step and formulate the optimisation in terms of the bounded acceleration vector: = , … , ! where #$ ≤ & ≤ '$ .

Any appropriate instantaneous fuel consumption model can be used for (. ). We use the model form below (based on VT-CPFM (Park et al., 2013)) fitted to simulation data for a 40 tonne HGV:

( ) = (( + () ) + (* sin + (, )) ) + (- (( + () ) + (* sin + (, ) + (. !/

( = 0.0003446368 () = 0.0000005433

Fuel Consumption [L/100km] (* = 0.0428225444 (, = 0.0067086633 (. = 0.0023279163 (- = 0.3190970807

Resulting fuel consumption curves (litres/100km) are shown below. Optimal cruising speed is marked [65.72km/h]. Note instantaneous fuel consumption is bounded below by zero. To illustrate the importance of capturing acceleration and within-link gradient, we consider an undulating link of length 50km with zero net gradient i.e. link-ends have the same elevation. Our example elevation profile is randomly generated, inducing a maximum gradient of 3.16 degrees.

Figure 1: Road profile versus link distance (note vertical axis in m, horizontal in km). Dots mark 30s timesteps.

We solve for optimal acceleration with 30 second timestep, to avoid artificially flattening out hills. This is sufficient, given our focus on long journeys with a network comprising long links.

Acceleration

Speed [km/h]

Instant FC [L/s]

Figure 2: Optimal accceleration profile [top], speed profile [middle], instantaneous fuel consumption [bottom]. End node speeds [5km/h, 90km/h]. Timestep 30s.

For each link, we compute the optimal acceleration/speed profile minimising fuel consumption. We repeat this for permissible travel times (here in 1-minute increments) and all combinations of link-end speeds.

Table 1: Optimal fuel consumption for different travel times and link-end speed combinations

[link entry speed (km/h), link exit speed (km/h)] Assume Link Equivalent constant Travel average link- [5,5] [5,50] [5,90] [50.5] [50,50] [50,90] [90,5] [90,50] [90,90] Time speed speed (s) (km/h)

2000 90.00 18.23 17.79 17.96 17.47 17.35 17.57 16.83 16.65 16.74 16.16

2060 87.38 17.87 17.51 17.69 17.16 17.24 17.16 16.44 16.36 16.53 15.94

2120 84.91 17.25 17.28 17.39 16.88 16.79 16.96 16.14 16.25 16.33 15.75

… … … … … … … … … … … …

5880 30.00 20.54 20.76 21.37 21.02 20.84 21.96 23.89 25.49 24.58 20.13 Note that other objective functions could easily be adopted e.g. instantaneous emissions models (see e.g. (Bektaş and Laporte, 2011)), or a weighted combination of travel time, fuel consumption and emissions.

Build ESTEN and find shortest path Above, we compute the optimal acceleration/speed profiles for every link, :, for each link travel time & ∈ < & &= , & >, and for each combination of link end speeds1. We then construct an extended space-time expanded network (ESTEN). Each physical node is replicated at each time point and each node transition speed, labelled by the triple (node number, time, node speed). Node speed determines the link-exit speed of incoming links, and the link-entry speed of outgoing links.

We populate an adjacency/cost matrix for these ESTEN nodes with links: link (:, , & ) → (@, + , A ) exists when it’s possible to travel from physical node : (link entry speed = & ) to node @ (link exit speed = A ) in time . The corresponding matrix element is set to the relevant cost (optimal fuel consumption) computed above.

Minimum travel time (maximum speed) can simply be defined using the link speed limit, or can vary dynamically. From historical data we compile a “link travel-time timetable” (LTTT see e.g. (Qian and Eglese, 2016)) which records link travel times throughout a typical week. We use the LTTT to determine the expected minimum travel time attainable when entering a link at time , and construct ESTEN links accordingly. In a period of recurrent congestion, the minimum travel time will be greater than during free flow conditions, and hence the minimum fuel consumption will be higher. It is similarly straightforward to include time-of-day varying speed limits, temporal link restrictions, etc by including/deleting space-time links. Stops are included by creating zero-cost links joining (:, , 0) with (:, + 1,0). Maximum link travel time is taken from the minimum practical/legal speed for each link, except when exceeded by the LTTT which is then used as the bound for those times.

A given ESTEN link uniquely specifies a physical A-node and B-node, the time departing A, the time arriving at B (hence link travel time), the speed at A (link entry speed) and the speed at B (link exit speed). Hence the ESTEN link cost can be read from the optimal fuel consumption table generated above.

Solving the shortest path problem on this ESTEN then gives the optimal route, minimising fuel consumption.

1 We have investigated impact of number of link-end speeds used.

Simple Example To illustrate key attributes of our approach, we consider a simple two-route network where each route comprises two links. The elevation of node 2 is (approx 1000m) above nodes 1,3,4 which are all at the same elevation. Link 1 has an overall uphill gradient of +2 degrees, with link 2 (of almost the same length) having an average gradient of 2 degrees i.e. downhill.

Min Max Net Rout Route Lin Lengt [km/h [km/h Slop e [km] k h [km] ] ] e

1 31.92 25 50 +2 1 63.97 2 32.05 25 70 -2

3 48.96 40 110 0 101.1

4 52.20 40 110 0

Figure 3: Example network specification

We construct a link travel-time timetable (1 minute timestep):

Time Link01 Link02 Link03 Link04 ____________________ ______ ______ ______ ______ 12-Jul-2019 08:00:00 38.10 21.37 26.71 28.47 12-Jul-2019 08:01:00 38.10 21.37 26.71 28.47 12-Jul-2019 08:02:00 38.10 21.37 26.71 28.47

Origin, destination and stopping nodes are set to have low node speed (here 5km/h). A ‘ghost’ origin (node 0 in Figure 4) captures departure time choice. Departure time costs/constraints are encoded by the costs on links outgoing from 0. Similarly, arrival time costs/constraints can be encoded by adding a ‘ghost’ destination.

Figure 4: ESTEN illustrative snippet

From LTTT node 1 to node 2 minimum travel time is 38 minutes, then there are links from (1,1,0) → (2,39, ) and for permissible longer travel times (1,1,0) → (2,40, ) etc, but there is no link connecting (1,2,0) → (2,39, ).

Example 1. Assume links have constant gradient (zero or non-zero) and all node speeds fixed at 5km/h.