Research On The Problem Of Recommending Fuel-efficient Routes For Long-distance Driving Based On Historical Trajectories

With the development of Internet of Vehicles technology and the popularity of GPS-enabled devices,a large amount of trajectory data becomes available,and it is increasingly important to use such data for route recommendations.Commonly used route navigation services such as Baidu Map and Amap usually give priority to travel time or distance to provide users with the fastest or shortest route recommendations,which largely meet users’ travel needs and bring great convenience to their trips.However,some drivers are more concerned about fuel economy,they expect to receive effective fuel-efficient route suggestions,but few existing route recommendation services can meet their travel needs.In fact,high-quality fuel-efficient route recommendations can not only save drivers’ fuel costs,but also help save energy and alleviate environmental pollution caused by fuel consumption.In view of the outstanding value of fuel-efficient route recommendations in energy conservation and environmental protection,fuel-efficient route recommendations based on trajectory data have gradually attracted widespread attention from the research community.Traditional fuel-efficient route recommendation models treat the fuel-efficient route recommendation problem as a pathfinding problem on graphs and use Dijkstra’s algorithm or heuristic search such as the A*algorithm as the main solution.With suitable heuristic functions,heuristic search algorithms can greatly reduce the search space and achieve lower problem complexity,thus usually have better performance than Dijkstra’s algorithm.However,most existing methods set heuristic functions empirically or using simple statistical methods,making it difficult to integrate other useful information and limiting their flexibility and scalability.To build more flexible heuristics,many studies use machine learning methods to solve the task.Although most methods are able to use appropriate models to describe the dependencies between locations and spatio-temporal information,they are generally shallow computational models that make it difficult to capture complex trajectory patterns.In addition,most existing methods analyze fuel consumption influencing factors only from short-distance trajectories,and the fuel-efficient routes recommended for drivers traveling long distances directly using these methods are of low quality.This is because they ignore the significant differences in road network structure and route composition between long-distance driving and short-distance driving,and it is these differences that determine that the methods of analyzing only short-distance fuel consumption factors are no longer applicable.This paper is dedicated to the problem of recommending fuel-efficient routes for long-distance travel,which faces the following challenges:First,how to identify and represent the potential fuel consumption features that affect long-distance driving?Second,can we make full use of the extracted fuel consumption features to accurately predict fuel consumption and provide high-quality fuel-efficient route suggestions while using the advantages of the heuristic search algorithm?In order to solve these challenges,this paper extracts the potential fuel consumption features of long-distance driving by studying historical trajectory data.On this basis,a novel fuel-efficient route recommendation model for long-distance driving,LDFeRR,is proposed based on the idea of combining deep learning and heuristic search algorithm,i.e.,A*.The LDFeRR model contains four main modules.The first module is feature extraction,which is based on the historical trajectory data of long-distance driving and analyzes three dimensions,namely road,time,and weather,to consider potential features that may affect the fuel consumption of long-distance driving in a more comprehensive way,and provides a reasonable representation of different types of features.The second module is observable cost modeling,and the observable cost in the A*algorithm refers to the cost from the source location to the candidate location.Assuming that the partial trajectory from the source location to the previous location of the candidate location is known,the observable cost modeling problem is converted into a fuel consumption prediction task for a single road segment,and we propose to use a multilayer perceptron（MLP）to solve this task.The third module is the estimated cost modeling,where the estimated cost in the A*algorithm is the cost of the optimal path from the candidate location to the target location.Due to the lack of explicit trajectory information,we first generate the top-K distance shortest routes from the candidate location to the target location.Guided by the K candidate routes,the estimated cost modeling problem is also converted into a road segment sequence modeling task,and we propose to use an attention mechanism-based bi-directional gated recurrent unit（Att-BiGRU）to solve this task.The fourth module is the fuelefficient route search process,which essentially executes the A*algorithm at the cost of fuel consumption to search for the most fuel-efficient route.The main works and contributions of this paper are summarized as follows.1.This paper proposes a long-distance driving fuel-efficient route recommendation model,LDFeRR,which is based on the idea of combining deep learning methods with the heuristic search algorithm A*,and well combines the powerful modeling ability of neural networks and the advantages of the A*algorithm in reducing the route search space for solving long-distance driving fuel-efficient route recommendation task.2.This paper proposes a feature extraction module based on long-distance driving historical trajectory data,which can fully identify and reasonably represent the potential fuel consumption features of long-distance driving.This paper also proposes to automatically learn two cost functions of the A*algorithm using a multilayer perceptron（MLP）and an attention-based bi-directional gated recurrent unit（Att-BiGRU）,to make full use of the extracted fuel consumption features to accurately predict fuel consumption,and then provide high-quality fuel-efficient route recommendations.3.This paper conducts extensive experiments to verify the effectiveness of the proposed LDFeRR model based on two real historical trajectory datasets.The experimental results show that the LDFeRR model significantly outperforms the baseline methods in both evaluation metrics Saving（fuel consumption savings per 100 kilometers）and Improvement（percentage of performance improvement）.This paper also sets up ablation tests on different modules and a real case study,further validating the effectiveness of the model.