## 3 Energy-Efficient Dynamic Routing Algorithm  
The routing application determines the best route the vehicles should take based on a predefined criterion (travel time, distance or fuel consumption). The environmental and economic effect of the transportation system has become an important factor in all decision-making processes. It is of high importance to decrease the fuel/energy consumption of the transportation sector. Energy-efficient routing is a mean of accomplishing this objective where vehicle routes are chosen based on their fuel consumption cost. Fixed routing calculates the best routes based on the given road segments' cost. The costs used in the fixed routing algorithm could be a historic data of the average cost on the specified road network or could be the cost of travelling with the free flow speed. The traffic mobility patterns are very dynamic and thus require adaptive or dynamic routing algorithms. An important step in dynamic routing is to obtain the real-time periodically updated cost of travelling on a road segment. This requires the vehicles to be able to identify which road segment it is on at any point in time and to be able to communicate the cost of travelling on a road segment. At each of the update intervals, the costs are collected, the routing algorithm is run again using the updated costs, and new routes are produced. The traffic will be assigned the new routes if their costs are better than the old routes.  
The routing problem can be modeled as a shortest path problem and is solved using the Dijkstra algorithm [18]. The Dijkstra algorithm is applied periodically with the current road segments' costs collected from the probe vehicles. In order to prevent the frequent change of routes (oscillating routes), a traffic assignment algorithm is utilized. The routing algorithm produces the top five different best routes. The traffic is randomly distributed between these five routes. Then, the update period is divided into five sub-periods. At each of these sub-periods, the recent costs of the road segments are collected and used to update the current costs. Then, the routes are recalculated using the recent updated costs. In this way, at each updated sub-period, only one fifth of the traffic demand will be updated with the new routes. Another factor that prevents the frequent change of routes is that vehicles do not change their routes unless the new route's cost is better than the old route's cost with a predefined threshold.  
The fuel consumption of a road segment can be calculated using simplified macroscopic analytical or data-driven models using the average speed on the road segment. A microscopic approach is to use the second-by-second speed and acceleration to calculate the fuel consumption of each vehicle. The microscopic approach provides more accurate calculation but with more computation steps. We adopted the Virginia Tech Comprehensive Power-based Fuel Consumption Model (VT-CPFM) [19] microscopic model to calculate the second-by-second fuel consumption of each vehicle. The details of the fuel consumption model is described in the next section. We used the average fuel consumption of the vehicles that traversed the road segment as a representative of the cost of the fuel consumption on that road segment.