Multi-objective route recommendation method based on Q-learning algorithm

Abstract

With the continuous expansion of city scale and the advancement of transportation technology, route recommendations have become an increasingly common concern in academic and engineering circles. Research on route recommendation technology can significantly satisfy the travel demands of residents and city operations, thereby promoting the construction of smart cities and the development of intelligent transportation. However, most current route recommendation methods focus on generating a route satisfying a single objective attribute and fail to comprehensively consider other types of objective attributes or user preferences to generate personalized recommendation routes. This study proposes a multi-objective route recommendation method based on the reinforcement learning algorithm Q-learning, that comprehensively considers multiple objective attributes, such as travel time, safety risk, and COVID-19 risk, and generates recommended routes that satisfy the requirements of different scenarios by combining user preferences. Simultaneously, to address the problem that the Q-learning algorithm has low iteration efficiency and easily falls into the local optimum, this study introduces the dynamic exploration factor σ and initializes the value function in the road network construction process. The experimental results show that, when compared to other traditional route recommendation algorithms, the recommended path generated by the proposed algorithm has a lower path cost, and based on its unique Q-value table search mechanism, the proposed algorithm can generate the recommended route almost in real time.

Keywords

Route recommendation multi-objective user preferences reinforcement learning dynamic exploration factor

1 Introduction

Route recommendation research has always been a hot topic in the fields of computers and transportation, and it is crucial to urban transportation planning and smart city construction [1 –5]. The traditional approach is to find the shortest geographical route connecting a given origin and destination, namely, the traveling salesman problem [6 –8]. In fact, user preferences play a major role in the generation process of recommended routes [9]. In addition to considering the shortest route as the recommendation objective, the route recommendation algorithm can also consider other attributes as the recommendation objective to satisfy the travel requirements of different user preferences. For example, the route recommended by the route recommendation algorithm aimed at a short travel time or distance can reduce the user’s travel time and cost. The route recommendation algorithm aimed at city sightseeing can provide tourists with scenic tour routes. However, these route recommendation algorithms typically only consider a single attribute as the objective and cannot consider multiple attributes comprehensively. Therefore, multi-objective route recommendation algorithms have emerged that can comprehensively consider the multiple preferences of users and calculate the route to meet the multiple requirements of users.

However, existing multi-objective route recommendation algorithms cannot provide routes that balance multiple objective attributes. For example, when following the user preferences of fuel consumption with less weight, travel time, and environmental index with more weight, the existing multi-objective route recommendation algorithms may suggest a long detour route, which will significantly increase the vehicle’s fuel consumption and travel time. This extreme case was not desired by the user. Simultaneously, most existing multi-objective route recommendation algorithms tend to focus on common indicators, such as travel time, travel distance, and fuel consumption, while ignoring the safety difference between different routes. Traffic accidents on urban roads not only cause personal injury and property damage but also cause serious traffic congestion. In particular, during peak hours, delays caused by traffic jams and accidents on urban roads result in enormous socioeconomic losses. Traffic accidents have become one of the leading causes of death worldwide, with China having one of the highest numbers of traffic deaths. In some cases, route safety must be prioritized. For example, tourists pay more attention to the safety of the route recommended by the system when traveling in a new city. For school bus commutes, schools and parents are more concerned about the safety of the route than the length of the trip. In these cases, high route security is the primary goal. In addition, the global spread of COVID-19 (coronavirus disease 2019) has become the current background, and research on the COVID-19 epidemic has become a research hotspot in various fields. However, few studies have been conducted on route generation algorithms that can avoid high-risk areas of COVID-19.

Reinforcement learning is a very popular research topic in the field of artificial intelligence in recent years. Reinforcement learning is mainly composed of agent, environment, state, action and reward. It aims to simulate the decision-making and learning process of agents in the constantly changing environment, with the goal of maximizing the cumulative reward value of agents. After the agent performs an action, the environment will transition to a new state, for which the environment will give the agent a reward value (positive or negative). The agent then performs the new action according to a certain strategy based on the new state and the reward from environmental feedback. The agent interacts with the environment repeatedly in this manner until the agent receives the last state in the environment.

The process of an agent interacting with the environment and expecting the maximum reward value to reach the final state is similar to the process of a car seeking the best route to the end. The reward feedback mechanism of reinforcement learning can also be used as an evaluation index for the quality of multi-objective optimization results in the route recommendation process. Therefore, based on reinforcement learning theory, this study proposes a multi-objective route recommendation algorithm [6] called MORRBQ (Multi-objective Route Recommendation Method Based on Q-learning). Route security and COVID-19 risk were added as the consideration factors of the system; that is, the three objective attributes of short travel time, low safety risk, and low COVID-19 risk were considered simultaneously, and the route recommendation was made based on user preferences. Simultaneously, the MORRBQ algorithm introduces a dynamic exploration factor σ and initializes the value function in the road network construction process, which is used to solve the defects of the Q-learning algorithm, such as low iteration efficiency and ease of falling into the local optimum.

The main contributions of this study are as follows:

In addition to travel time, safety risk and COVID-19 risk are added as the consideration objectives for the proposed route recommendation algorithm, which is used to facilitate users to assign weights to different objective attributes to obtain personalized recommendation routes. A reward table training algorithm that considers different user preferences is proposed.

A Q-value table initialization algorithm is proposed, which shortens the agents’ iteration time and makes the agents’ choice of road nodes and actions clearer.

A multi-objective route recommendation algorithm based on a dynamic exploration factors is proposed to avoid falling into the local optimum.

A series of experiments are conducted that verify the effectiveness and practicality of the proposed algorithms, and the experimental results show the work performed in this study to be more effective than existing route recommendation methods.

The remainder of this paper is organized as follows. Section 2 discusses related work. Section 3 presents the definitions used in this paper. Section 4 introduces the algorithm framework and the content of the multi-objective route recommendation algorithm. Section 5 presents the experimental results and analyses. Finally, Section 6 concludes the paper and outlines future work.

2 Related work

Extensive research has been conducted on route recommendations resulting in many achievements. Existing route recommendation methods can be divided into two categories: single-objective and multi-objective route recommendations.

2.1 Single-objective route recommendation

Research on single-objective route recommendations has a long history. The commonly used Dijkstra algorithm is used to search for the shortest route, which corresponds to optimizing a single objective and typically only considers one-dimensional costs such as distance, time, and speed [7]. Research by some scholars [5, 6] avoids unnecessary braking of vehicles by using the optimal speed curve to design the control system to improve fuel efficiency on the route from origin to destination and achieve the goal of saving fuel resources. However, the above scholar’s research has a problem of low route recommendation accuracy. To address this problem, Cheng et al. [10] proposed a travel route recommendation algorithm based on interest theme and distance matching. The algorithm first obtains the user’s real historical travel footprints through analysis and then extracts the user’s interest theme preference and distance matching based on the user’s stay time in each scenic spot. Finally, an optimal trip calculation method is designed based on the trip time limit, start point, and end point. Compared to the traditional algorithm, the proposed algorithm has a higher accuracy and recall rate. Wang et al. [11] combined A* algorithm and recursive neural network based on attention mechanism, proposed a travel cost prediction algorithm for estimating candidate locations to destination locations, to recommend travel routes with lower travel costs for users. Zhou et al. [12] proposed a hybrid route prediction and recommendation method to solve route recommendations under a mixed traffic mode. Feng et al. [13] proposed a recommendation algorithm based on DBSCAN using passenger hotspots for profitable taxi cruising route recommendation. Jia et al. [14] proposed an algorithm that combined the weighted shortest route and deep learning to recommend context-aware routes for users. Studies by the above scholars did not consider user preferences. Therefore, Silva et al. [15] proposed a route recommendation method based on user behavior, which mined user preferences through the historical data of user trips and recommended appropriate routes to users. Ji et al. [16] studied the dynamic taxi route recommendation problem as a sequential decision problem and designed an adaptive deep reinforcement learning method that fused the extracted spatio-temporal features through a deep policy network to carry out effective route recommendation. However, these studies did not consider the traffic characteristics of the routes. The literatures [17, 18] deal with single-objective route selection by analyzing different traffic characteristics, with the goal of reducing travel time, fuel consumption, and exposure to air pollutants. Kang et al. [19] considered the road slope of a specific intersection and used a dynamic programming method to determine the optimal speed curve to reduce the fuel consumption. In the above studies, some methods did not consider user preferences, whereas others that considered user preferences did not combine different preferences (such as travel time and fuel consumption) to achieve multi-objective route recommendations. Similarly, some of these scholars’ studies did not consider user preferences, and some methods that considered user preferences still did not combine different preferences.

2.2 Multi-objective route recommendation

Sarker et al. [20] proposed a multi-objective route-recommendation algorithm that considered three different attributes: fuel consumption, travel time, and air quality. Based on the reinforcement learning algorithm and user preferences, the algorithm can generate a personalized recommended route in time. Guo et al. [21] proposed a method to predict the travel time and fuel consumption of different roads using GPS trajectories, and recommended a route for users that comprehensively considered time and fuel efficiency. Zheng et al. [22] proposed a variable neighborhood search algorithm and a hybrid particle swarm optimization genetic optimization algorithm to recommend top-K routes. Huang et al. [23] proposed a flexible multi-task deep travel route planning framework, which constructed heterogeneous networks through the relationship between POI and users and integrated auxiliary information for more effective planning. Based on the particle swarm optimization algorithm, Malik et al. [24] designed a route optimization objective function considering five parameters: distance, road congestion, weather conditions, route popularity, and user preference, which were used to predict the optimal route to the next tourist attraction. Rani et al. [25] combined the K-means clustering method with the traveling salesman problem-solving method to generate travel itineraries by considering both distance and travel time to recommend the optimal route. The above multi-objective route recommendation methods do not consider safety risks and other factors, and because of the high time complexity of the optimization solution calculation, they cannot provide near-real-time optimal routes.

In summary, research in the field of route recommendation mainly focuses on route recommendation methods based on a single objective and route recommendation methods based on multiple objectives. Existing single-objective route recommendation methods cannot consider the multi-preference requirements of users, whereas most multi-objective route recommendation methods do not consider some novel objective attributes, such as safety risk attributes and COVID-19 risk attributes. Owing to the constant variation of the novel coronavirus and continuous spread of epidemic viruses, it has become an urgent concern for users whether the generated recommended routes can avoid high-risk areas. Based on the research status of the above, this study proposes a multi-objective route recommendation method based on reinforcement learning, which considers the travel time and safety risk, and the COVID-19 risk is one of the objective attributes. Simultaneously, it satisfies the demand of user preferences and meets the recommended route under the condition of different scenarios to realize personalized recommendation.

3 Problem description

This section provides background information and problem description.

3.1 Road network model

(1) Road Network

In this study, a road network is abstracted as a network model composed of finite nodes and edges, which is represented by G(V, E) where V is the set composed of the starting and ending points of each road section and is represented by V ={ v₁, v₂, ⋯ , v_n } and E is the set of all edges (road sections connecting two nodes) and is represented by E ={ e_i,j|1 ⩽ i, j ⩽ n }, where e_i,j represents the edge connecting nodes v_i and v_j. Each road section (edge) has a 3-dimensional vector cost_i,j = [t_i,j, s_i,j, c_i,j], which represents the cost value of the road section. This is illustrated in Fig. 1. The three components of this vector t_i,j, S_i,j, and C_i,j represent the cost from node v_i to v_j in terms of the travel time, safety risk, and COVID-19 risk, respectively.

Fig. 1

Cost of road segment.

(2) Route

The set of a series of edges connecting the origin and destination is called a route in the road network, and can be expressed as follows: $τ = {e_{st, 1}, e_{1, 2}, e_{2, 3}, \dots, e_{n, end}}$ (1) where e_st,1 is the edge connecting the source node v_st and v₁ in route τ, and e_n,endis the edge connecting v_n and destination node v_end in route τ.

(3) Total Route Cost

The total route cost refers to the sum of the travel time, safety risk, and COVID-19 risk costs for each section of the route. The higher the value, the higher is the cost of the corresponding attribute of the path. The total path cost is calculated as follows: ${COST}_{τ} = \sum_{e_{i, j} \in τ} W p \cdot {cost}_{i, j}$ (2) where COST_τ is the route τ’s sum of costs of each section, and W _p = [w_t, w_s, w_c] is a 3-dimensional weight vector, where w_t, w_s, and w_c are the preference weights of users on the travel time, safety risk, and COVID-19 risk, respectively.

3.2 Multi-objective model

(1) Travel time

The minimization of travel time is a common optimization goal in various route recommendation algorithms. In this study, the travel time consumption value of the recommended route is calculated based on the length of each road section in the New York Road network data and the average traffic speed of the city road. The traffic time consumption value of each road section in the road network is stored in the traffic time matrix T , where t_i,j(t_i,j ∈ T ) denotes the traffic time consumption value on road section e_i,j.

(2) Safety Risk Index

The occurrence of urban road traffic accidents is inevitable and is affected by certain factors, and the frequency of accidents varies by section. In this model, the probability of traffic accidents, namely, the safety risk index, is approximated by calculating the frequency of traffic accidents for each road section in the historical data. The safety risk index of each road section in the road network is stored in the safety risk matrix S, where s_i,j (s_i,j ∈ S) is expressed as the safety risk index of the road section e_i,j. As shown in Fig. 2, the frequency of traffic accidents in Brooklyn, New York is relatively high, with an annual accident rate of 18,000 on average. Staten Island has a low accident rate, with fewer than 4,000 accidents annually.

Fig. 2

Traffic accidents distribution in New York.

(3) COVID-19 Risk Index

The COVID-19 epidemic has spread and covered the entire world, which has become the background of the current era and an issue that must be paid attention to in social production activities that concern peoples’ lives and safety. Therefore, it is of great research value and social significance to recommend routes to avoid COVID-19 risk areas. Based on public historical data, this study calculated the COVID-19 risk index of each road section based on the time attribute and longitude and latitude coordinates of the COVID-19 risk areas. The COVID-19 risk index of each road section in the road network is stored in the COVID-19 risk matrix C, where c_i,j (c_i,j ∈ C) represents the COVID-19 risk index on the road section e_i,j.

3.3 Description of environment and space

(1) Environment

In this study, the environment, also known as the road network environment, is defined as the updated road network. Each edge e_i,j has three different attribute values, which are stored in the form of [w_tt_i,j, w_ss_i,j, w_cc_i,j], representing the predicted value of the traffic time, safety risk index, and COVID-19 risk index under the given user preference W _p = [w_t, w_s, w_c].

(2) Agent

Under the given road network environment, source node and destination node, the route recommendation algorithm as an agent selects the most appropriate action (i.e., selects an appropriate road section) based on the predicted attributes of each road section and generates an optimal route from the source node to destination node after a series of calculations and selections.

(3) State Space

A state is a summary of the current environment denoted by s. The state space is the set of all possible states denoted by S, where s ∈ S. In this study, the state space is a set of road network environments composed of finite edges and nodes, and each edge contains all the objective attribute values (travel time, safety risk index, and COVID-19 risk index).

(4) Action Space

An action is the choice made by the agent, denoted by a. The action space is the set of all actions denoted by A, where a ∈ A. The action space defines the set of actions (agent selects an edge) that can be selected by the agent in the current state, that is, given node v_i, source node v_st, destination node v_end, and the attribute values of different edges.

3.4 Optimal route

(1) Optimal route under a single objective.

The optimal route under a single objective consists of a limited set of road segments (edges) that connect the source and destination node set by the user, which satisfies the optimal result under a certain objective (e.g., the shortest route between two points is to achieve the goal of minimizing the total distance cost).

(2) Optimal route under multi-objective optimization

Given the road network G = (V, E), each edge has three objective attribute values: road length, safety risk index, and COVID-19 risk index, an optimal route connecting the source node and destination node set by the user is generated, and the total cost of the three objective attributes on this route is minimized.

4 Multi-objective route recommendation algorithm based on q-learning

Based on the Q-learning algorithm, this study proposes a multi-objective route recommendation algorithm based on Q-learning (MORRBQ) to find the optimal route from the source node to the destination node satisfying the multi-objective constraints. As a classical algorithm in the field of reinforcement learning, compared with other traditional methods, the Q-learning algorithm can quickly find the optimal route and save a significant amount of computation time during route selection.

The MORRBQ algorithm calculates the reward value of each road section based on the three objective attributes (travel time, safety risk index, and COVID-19 risk index) and forms a reward matrix. This algorithm uses a route recommendation algorithm as the agent. In the execution process of the algorithm, first, the state and action are constructed into a Q-value table based on the reward matrix and Behrman equation. The Q-value is Q (s_t, a_t), which refers to the expected value of the reward that can be obtained by taking action a_t under state s_t at a certain time t. Subsequently, the Dijkstra algorithm is used to pregenerate the shortest route connecting the source node and destination node, and the nodes passing through the route are used to initialize the Q-value table. Then, the dynamic exploration factor σ and value function are used to update the Q-value table. The environment provides feedback on the corresponding expected reward value Q (s_t, a_t), according to the action taken by the agent. The agent is trained several times to obtain the updated Q-value table. Finally, the agent selects the optimal route from the source node to the destination node by selecting an action that maximizes the Q-value after receiving the state each time according to the Q-value table. The complete framework of the algorithm is shown in Fig. 3.

Fig. 3

Multi-objective route recommendation algorithm framework.

4.1 Data Preprocessing

The algorithm used in this study used three datasets from different sources. First, it must delete abnormal records in the dataset and fill in the missing items. To eliminate the influence of dimensional and numerical size scale differences between datasets, the data should be normalized. y_k represents the value of the objective attribute k. The formula for data normalization is shown in Equation (3). $y_{k}^{,} = \frac{y_{k}}{y_{k}^{\max}}$ (3) where $y_{k}^{,}$ denotes the normalized value of y_k, and $y_{k}^{\max}$ denotes the maximum value of objective attribute k.

4.2 Multi-objective attribute prediction

4.2.1 Travel time prediction

Travel time is one of the most commonly used optimization objectives for route recommendation. In this study, the ratio of the length of each road section to the average speed of vehicles was used as the predicted value of the travel time of this road section, and the calculation formula is expressed in Equation (4). $t_{i, j} = \frac{{len}_{i, j}}{v_{avg}}$ (4) where len_i,j denotes the length of the road segment (edge) e_i,j, v_avg denotes the average speed of the urban road, and t_i,j denotes the predicted traffic time of the road segment (edge) e_i,j.

4.2.2 Safety risk prediction

The safety risk index refers to the probability of traffic accidents occurring on a road section. In route recommendations, users are more inclined to choose road sections with fewer traffic accidents occurred in the past. In existing studies on safety route recommendation, most researchers adopt a calculation method based on the occurrence density of traffic accidents, that is, within a certain radius, the ratio between the number of accidents and area or the average distance between the midpoint of a road section and the location of traffic accidents in the area. The density-based safety risk index calculation method increases the computational cost and time consumption, which is not conducive to the timely feedback of route recommendation results. In the data pre-processing stage, the route recommendation algorithm proposed in this study uses a random forest to classify the safety risk index of each road section. According to the historical data on traffic accidents, the safety evaluation of road sections is divided into four categories. Values from 1 to 4 represent the safety risks from low to high. The safety risk index of road segment (edge) e_i,j is represented by s_i,j, and the safety risk index of road segment can be directly used as a component of the reward value of MORRBQ algorithm. After assigning the safety risk index to each road section in the data pre-processing stage, the computation time and memory consumption of the system can be significantly reduced.

4.2.3 COVID-19 risk prediction

A novel function of the proposed multiobjective route recommendation method is to avoid COVID-19 risk areas when creating routes. Based on the current location of the road (the midpoint coordinates of the road) and the longitude and latitude coordinates of the location of COVID-19 cases, the COVID-19 risk index c_i,j was calculated and added to the reward value. The calculation method for c_i,j is to draw a circle with the midpoint of the road section as the center and the length of the road section as the radius. The average distance between the midpoint of the road section and each COVID-19 case within the circle was calculated and divided by the length of the road section. All roads were assigned a COVID-19 risk index value, calculated as follows: $c_{i, j} = \frac{\sum_{k = 1}^{n} distance (x_{i, j}, g_{k})}{\frac{n}{{len}_{i, j}}}$ (5) where n (n ≠ 0) denotes the number of COVID-19 cases within the radius of each node; x_i,j denotes the midpoint position of road segment e_i,j, and g denotes the list of COVID-19 cases within the radius of each node. When the difference between the time of diagnosis of COVID-19 case g_k and the current time is less than the threshold θ, the function distance (x_i,j, g_k) is used to calculate the distance between x_i,j and the location of g_k, len_i,j is the length of road e_i,j. If there are no COVID-19 cases within the setting range of the current road node (i.e., n = 0), c_i,j will take a minimum value μ. A detailed description of COVID-19 risk prediction is presented in Algorithm 1.

Algorithm 1: COVID-19 risk prediction
Input:G(V, E), θ, g, μ
Output: C
1. Initialize C← Ø;
2. for each e_i,j ∈ E do
3. ifg =∅ then
4. c_i,j ← μ;
5. elseifg≠ ∅ then
6. for eachg_k ∈ gdo
7. ti ← the interval between the time
when case g_k occurred and
the current time;
8. ifti < θ then
9. c_i,j← the COVID risk of e_i,j
calculated by Equation (5);
10. end if
11. end for
12. end if
13.end for
14.return C;

4.3 Reward calculation

The reward value is the immediate reward for choosing a particular action (e.g., edge e_i,j) from a finite set of actions. To determine the immediate reward of the selected edge, the given user preference and all predicted values of the road segment (travel time, safety, and COVID-19 risk) are combined, and the direct distance between the current node v_i and destination node v_end (i.e., Euclidean distance) is considered to ensure that the vehicle drives to the destination as quickly as possible. Therefore, the agent creates a reward table based on the road network, destination node v_end, and given user preferences, namely W _p = [w_t, w_s, w_c].

The reward table is in the form of an adjacency matrix, R _|V|×|V|, , where |V| represents the total number of nodes in the road network. r_i,j (1 ⩽ i, j ⩽ |V|) on behalf of the reward from the current state in table R s_t (i.e., node v_i), the next state s_t+1 (i.e., node v_j) chooses an action (i.e., e_i,j) direct incentive. If nodes v_i and v_j are not connected, that is, e_ij ∉ E, the reward is –∞, which indicates that there is no edge. The method for calculating immediate reward r_i,j is presented in Algorithm 2.

Algorithm 2: Reward table training
Input:G(V, E), W _p ,, T , S, C
Output: R
1. Initialize R ;
2. fori ← 1 to \|V\| do
3. forj ← 1 to \|V\| do
4. ifv_j = v_endthen
5. r_i,j← + ∞;
6. ife_i,j ∈ Ethen
7. r_i,j ← - (w_tt_i,j + w_ss_i,j + w_cc_i,j);
8. else
9. r_i,j← - ∞;
10. end if
11. end for
12. end for
13. return R;

where v_end denotes the destination node. Assume that the user’s preference is W _p = [0.30, 0.30, 0.40]. According to Algorithm 2, the immediate reward was calculated for the road network shown in Fig. 4, and the reward table is listed in Table 1.

Fig. 4

Road network topology.

Table 1

Reward table instance

Current state\Next state	v ₁	v ₂	v ₃	v ₄	v ₅	v ₆
v ₁	–∞	–0.161	–0.100	–∞	–∞	–∞
v ₂	–∞	–∞	–0.191	–0.100	–∞	–∞
v ₃	–∞	–0.191	–∞	–0.144	–0.109	–∞
v ₄	–∞	–∞	–∞	–∞	–∞	+∞
v ₅	–∞	–∞	–∞	–∞	–∞	+∞
v ₆	–∞	–∞	–∞	–∞	–∞	–∞

where row represents state v_i, in which the agent is in, and column represents the actions that the agent can take in the state located at node v_i. For example, in the state of node v₂, the reward value of the agent taking action to reach node v₃ was –0.191.

4.4 Dynamic exploration factor

Using appropriate strategies to select the optimal action is a key point in the field of force-change learning. The Q-learning algorithm uses ɛ-greedy strategies to plan the search and update the environment. In general, ɛ is a fixed hyperparameter, which may cause the agent to not sufficiently explore the environment in the early stage of iterative computation, resulting in a failure to generate the optimal route and failure to converge in the later stage. To solve this problem, a dynamic exploration factor σ was proposed in this study. The size of σ is dynamically adjusted based on the number of iterations during the execution of the algorithm. The specific function expression of σ is given by Equation (6). $σ = K \frac{1}{\sqrt{2 π}} e^{(- \frac{x^{2}}{2 N})}$ (6) where x denotes the number of current iterations, N denotes the maximum number of iterations in a training round, and K denotes a hyperparameter. The introduction of the dynamic exploration factor σ can effectively solve the problem in which the value function easily falls into the local optimum after initialization and can accelerate the convergence speed of the algorithm.

4.5 Q-value table initialization

The process of agent exploration is constantly searching for the optimal strategy, and its operational efficiency will improve with a reduction in the exploration process. Combined with the Dijkstra algorithm, the value function Q(s, a) of Q-learning is initialized using the shortest route result obtained by the algorithm. The initialization of the Q-value table can not only effectively shorten the iteration time of the algorithm but also make the agents’ selection of road nodes and actions clearer. The specific process of the Q-value table initialization is presented in Algorithm 3.

Algorithm 3: Q-value table initialization
Input:G(V, E), v_st, v_end
Output:Q-value table
1. Call the Dijkstra algorithm to generate the shortest route h from v_st to v_end;
2. Record the action a taken by the previous state s to transition to the next state ss’ ’ in the route;
3. for each part inhdo
4. ifn < σ then
5. Q(s, a) = = 0;
6. else
7. Q(s, a)= = -–1;
8. end for
9. returnQ-value table;

4.6 Q-value table update and model training

As shown in Fig. 5, the agent builds a matrix Q-value table of the same order as the reward table, which stores the Q-value corresponding to each state in the environment, and every action taken after receiving the state. From the Q-value table, the agent can take the action corresponding to the largest Q-value after receiving any state. To achieve this goal, the agent used the Behrman equation (i.e., the value function) to update the Q-value table, as shown in Equation (7).

Fig. 5

Q-value table update and model training.

$\begin{matrix} Q (s_{t}, a_{t}) = Q (s_{t}, a_{t}) + α \\ [r_{t} + γ \max_{a_{t + 1}} Q (s_{t + 1}, a_{t + 1}) - Q (s_{t}, a_{t})] \end{matrix}$ (7) where α is a learning rate parameter used to accelerate the convergence of the Q-value in the presence of noise and γ is a discount factor that guarantees the convergence of update rewards for all future edges of the current node.

The Q-value table must be updated several times (the number of iterations is denoted by D). In each iteration, any node was randomly selected as the initial state. Then, based on the value of the dynamic exploration factor σ and the size of the random number generated at each step, the agent selects the action a_t and executes it in the current state s_t, obtains the new state s_t+1 and the current reward r_t+1, and updates the value of Q (s_t, a_t) in the table simultaneously. Iterate until the destination node is reached. The entire algorithm is a process of constantly updating the Q-value table, and then determining which action to take in a certain state is the best choice according to the updated value. A detailed description of the Q-value table construction and multiobjective route recommendation is presented in Algorithm 4.

Algorithm 4: Multi-objective route recommendation
Input: α, γ, D, R , A
Output:Q-value table
1. Initialize Q(s, a) randomly;
2. Q (v_end,) ←0;
3. for eachd in Ddo
4. Initialize state s_t; //s_t : original state in each episode
5. for each step in d do
6. do
7. σ← the search factor calculated by Equation (6);
8. n ← uniform random number between 0 and 1;
9. ifn < σ then
10. a_t+1← random action from A;
11. else
12. a_t+1 ← maxQ (s_t, ·);
13. take action a_t+1, observe reward r_t+1 and choose next
state s_t+1;
14. Q(s_t, a_t)← the Q-value calculated by Equation (7);
15. s_t ← s_t+1;
16. whiles_t is not teminal-state;
17. end for
18.end for
19.returnQ-value table;

4.7 Multi-objective optimal route selection

After training, the system uses the updated Q-value table to select the optimal route from the source node. Specifically, it is based on the current node to find different adjacent nodes, from the Q-value of the update table to retrieve the Q-value, on the edge of the adjacent to the current node, based on certain rules from all possible edges, choosing to have the largest Q-value to reach the next node, repeating the steps until it reaches the destination node, and generating the multi-objective optimal route.

The main operation of the multi-objective optimal route selection is to find the Q-value table and select the action with the largest Q-value in the retrieval process. This search operation significantly reduces the complexity of the multi-objective optimization problem and reduces the solution time to near real time.

4.8 Algorithm complexity analysis

4.8.1 Time complexity analysis

The time complexity of Algorithm 1 primarily depends on two factors: (1) the number of sections (edges) in the road network and (2) the size of the COVID-19 case list within the radius of each road section. Therefore, the time complexity of Algorithm 1 is O (k * m²), where k denotes the number of COVID-19 cases within the radius of each section and m denotes the number of sections (edges) in the road network. Because k ⪡ m, the time complexity of Algorithm 1 is O (m²).

The time complexity of Algorithm 2 primarily depends on the computation cost of the reward value between nodes; therefore, the time complexity of Algorithm 2 is O (n²), where n denotes the number of nodes in the road network.

The time complexity of Algorithm 3 primarily depends on the search of the shortest route; therefore, the time complexity of Algorithm 3 is O (n²), where n denotes the number of nodes in the road network.

The time complexity of Algorithm 4 primarily depends on two factors: (1) the number of training sessions of the Q-value table and (2) the size of the Q-value table. Therefore, the time complexity of Algorithm 3 is O (c * n²), where c denotes the number of training sessions in the Q-value table, c is a constant, and n denotes the number of nodes in the road network. Because c ⪡ n, the time complexity of Algorithm 3 is O (n²).

4.8.2 Space complexity analysis

The space complexity of Algorithm 1 primarily depends on the storage cost of two parts of the data: (1) the number of road segments (edges) in the road network and (2) the number of COVID-19 cases within the radius of each road section. Therefore, the space complexity of Algorithm 1 is O (k * m²), where k denotes the number of COVID-19 cases within the radius of each road section and m denotes the number of edges in the road network. Because k ⪡ m, the space complexity of Algorithm 1 is O (m²).

The space complexity of Algorithm 2 primarily depends on the matrix of the space overhead reward, and the space complexity of Algorithm 4 primarily depends on the Q-value table space overhead reward. The size of the matrix and Q-value table are decided by the road network node number. Therefore, the space complexity of Algorithms 2 and 4 is O (n²), where n denotes the number of nodes in the road network.

The space complexity of Algorithm 3 primarily depends on the storage overhead of the road network G(V, E); therefore, the space complexity of Algorithm 3 is O (n²), where n denotes the number of nodes in the road network.

5 Experiment

5.1 Datasets

Real-world geotagged datasets were used in this experiment, including New York road network data, New York traffic accident data, and New York COVID-19 data.

(1) Road Network data

This dataset was derived from the New York City road network data published by OpenStreetMap, as shown in Fig. 6. It consists of more than one million data records, including the longitude and latitude coordinates of the starting and ending points of the road segments, the length of the road segments, and other characteristics, and the detailed description is shown in Table 2. For example, the data record (2, 886.4, 40.082561, –74.548430, 40.081576, –74.554403) indicates that the total length of the road segment numbered 2 is 886.4 m, and the longitude and latitude coordinates of the starting and ending points are (–74.548430, 40.082561) and (–74.554403, 40.081576).

Fig. 6

Road network in New York.

Table 2

Information of Road network in New York

Id	Len	S_Lat	S_Lng	E_Lat
1	926.7	40.079066	–74.553253	40.079134
2	886.4	40.082561	–74.548430	40.081576
3	344.2	40.080466	–74.549885	40.081977
. . .	. . .	. . .	. . .	. . .
1215612	52.4	41.259713	–73.784339	41.259824

In this study, 20 source-destination node pairs were randomly selected from the New York City road network for the multi-objective route recommendation experiment, and the Euclidean distance between the selected source-destination node pairs should be at least 5 km.

(2) Traffic Accident Data

The dataset is derived from the publicly released traffic accident data from the New York City Police Department and records the traffic accident data of New York City from 2015 to 2017, including a total of 477732 records, the time of the accident, the accident location latitude and longitude coordinates, the number of casualties, and severe level characteristics, including the severity of the traffic accident, ranging from 1 to 4. A higher value indicates a higher accident severity. The composition and recording features of this dataset are presented in Table 3.

Table 3

Information of traffic accidents in New York

Id	Date	Time	Location	Person Injured	Person Killed	Severity
1	01/01/2015	0:20:00	(40.751847,–73.787862)	1	0	1
2	01/01/2015	0:21:00	(40.689444,–73.955121)	1	0	1
3	01/01/2015	8:02:00	(40.839246,–73.870094)	4	1	3
. . .	. . .	. . .	. . .	. . .	. . .	. . .
477732	02/28/2017	9:57:00	(40.814037,–73.948364)	1	0	1

(3) COVID-19 Data

The dataset was from 578 COVID-19 cases published by the New York City government from October 21 to December 27, 2020, and includes features such as the time of COVID-19 risk areas, latitude and longitude coordinates, number of medical visits, and number of deaths. The feature compositions and partial records of this dataset are presented in Table 4.

Table 4

Information of COVID-19 in New York

Id	Date	Latitude	Longitude	Hospitalization	Death
1	10/21/2020	40.750693	–73.997137	2	0
2	10/21/2020	40.731825	–73.989164	6	0
3	10/21/2020	40.599333	–74.166462	19	7
. . .	. . .	. . .	. . .	. . .
578	12/27/2020	40.577599	–73.844553	4	0

5.2 Experiment algorithm

To verify the superiority of the MORRBQ algorithm in the multi-objective route recommendation problem, this study conducted relative comparative experiments between the proposed algorithm and three other traditional route recommendation algorithms. The four algorithms are described as follows:

(1) MORRBQ Algorithm

The MORRBQ algorithm is a route recommendation algorithm proposed in this study. It is implemented based on the reinforcement learning algorithm Q-learning, which introduces the initialization operation of the Q-value table and dynamic search factor σ. In the training phase of the model, 10000 iterations were performed to generate the Q-value table for the experimental phase. In each iteration, a source-destination pair is randomly selected from the set of nodes and edges, and a Q-learning algorithm is used to update the Q-value table accordingly. To achieve the optimal experimental effect, after comparing the experimental results obtained under different parameter settings, γ= 0.7 and α= 0.6 were set in this study.

(2) MORR Algorithm

The MORR algorithm [20] is also a multi-objective route recommendation algorithm based on the Q-learning algorithm, and is the main comparison algorithm of the MORRBQ algorithm proposed in this study. However, the MORR algorithm does not change the core of the Q-learning algorithm, and it also considers common objective attributes (travel time, fuel consumption, and air quality).

(3) PreGo Algorithm.

The PreGo algorithm [24] is a dynamic routing algorithm that suggests the best route by retrieving real-time traffic congestion conditions while minimizing the values of two objective attributes (travel time and fuel consumption) with the same priority. The PreGo algorithm uses the dynamic A* algorithm as an optimization scheme to solve the route problem of binocular objects with the same priority. In the experimental process, the PreGo algorithm was implemented based on the steps of the multipreference shortest-route algorithm in the literature [14].

(4) MORP Algorithm

The MORP algorithm [26] uses a multi-objective optimization scheme to determine the optimal route from the source node to destination node. It considers travel time, fuel consumption, and air quality equally when finding the best route. However, because of the multidimensional hypergrid search for the optimal solution, the MORP algorithm takes longer time (depending on the map size) to provide the optimal solution.

5.3 Experiment Settings

The experimental environment is AMD Ryzen 5 processor, CPU 3.00 GHz, operating platform is Windows 10, this study uses Python programming language to achieve the relevant algorithms in the experiment.

5.3.1 User preference settings

To reflect the daily requirements of users, three different settings of user preference weights were considered in the experiment, as follows:

Scenario 1: W _p = [0.33, 0.33, 0.33]. In this scenario setting, the three attributes of travel time, safety risk, and COVID-19 risk were assigned the same weight.

Scenario 2: W _p = [0.40, 0.40, 0.20]. In this scenario setting, users were more concerned about traffic time and safety risk attributes, and the above two attributes were assigned the same weight, whereas the COVID-19 risk attribute was assigned a lower weight.

Scenario 3: W _p = [0.00, 0.50, 0.50]. In this scenario, users only care about safety and COVID-19 risks and do not require the shortest travel time. This parameter can be used to simulate extreme real-life scenarios.

5.3.2 Evaluation indicators

To quantitatively evaluate the performance of the algorithm, this study uses the running time, convergence time, convergence episodes, reward value variation trend, exploration steps, and route cost as the evaluation indices of the algorithm performance.

(1) Running time

To evaluate the running time of the algorithm, the average of the total running time of the algorithm on multiple routes was calculated, as shown in Equation (8). ${Time}_{avg} = \frac{\sum_{i = 1}^{N} {time}_{i}}{N}$ (8) where time_i denotes the running time used by the algorithm to generate the ith route, N denotes the total number of routes generated by the algorithm, and Time_avg denotes the average running time of the algorithm for generating N routes.

(2) Convergence time and episodes.

To measure the convergence speed of the algorithm, the convergence time and number of convergence episodes are used as evaluation indices, and the convergence time can reflect the execution speed of the route recommendation algorithm. The number of convergent episodes refers to the number of episodes iterated by the agent when the algorithm reached the convergence state. The smaller the number of episodes, the higher the learning efficiency of the agent.

(3) Change trend of the reward of the algorithm

In the process of algorithm execution, with the advancement of iteration, the size and variation trend of the reward value can effectively reflect the excellent degree of the algorithm.

(4) Exploration

The number of exploration steps is the number of actions that the agent must perform to reach the destination node in each round. At the same time interval, the fewer the number of exploration steps of the algorithm, the more training episodes the agent can carry out, and the more environmental information it can obtain.

(5) Route Cost

Route cost refers to the sum of the travel time, safety risk, and COVID-19 risk costs of the route on each road section. The calculation method is shown in Equation (9). ${\begin{matrix} {COST}_{τ}^{t} = \sum_{e_{i, j} \in τ} w_{t} t_{i, j} \\ {COST}_{τ}^{s} = \sum_{e_{i, j} \in τ} w_{s} s_{i, j} \\ {COST}_{τ}^{c} = \sum_{e_{i, j} \in τ} w_{c} c_{i, j} \end{matrix}$ (9) where ${COST}_{τ}^{t}$ denotes the total route cost of route τ for the objective attribute of travel time, ${COST}_{τ}^{s}$ denotes the total route cost of route τ for the objective attribute of safety risk, and ${COST}_{τ}^{c}$ denotes the total route cost of route τ for the objective attribute of COVID-19 risk.

5.4 Experimental result

5.4.1 Time performance

Table 5 shows the time performance of the four algorithms, which were repeated several times, and the average value was taken as the experimental output data. The time performance of the algorithm was evaluated using the running time of the algorithm, time required to achieve convergence, and number of episodes required to achieve convergence.

Table 5
Time performance comparison of the 4 algorithms

Algorithm Running time/min Convergence Time/min Convergence Episodes

MORRBQ 6.86 3.29 6000

MORR 5.65 3.83 6200

PreGo 354.68 226.73 9100

MORP 351.18 210.26 >10000

Algorithm	Running time/min	Convergence Time/min	Convergence Episodes
MORRBQ	6.86	3.29	6000
MORR	5.65	3.83	6200
PreGo	354.68	226.73	9100
MORP	351.18	210.26	>10000

As can be observed from the results in the table, compared with the other three route recommendation algorithms, the time required for the MORRBQ algorithm to achieve convergence and the number of episodes required to achieve convergence are significantly less because the initialization operation of the Q-value table in the proposed method significantly saves computing time and improves the convergence speed of the algorithm. However, the PreGo and MORP algorithms require a significant amount of time to obtain an optimal solution.

5.4.2 Change trend of algorithm’s reward

The reward value realizes the connection between the goal and algorithm by making the task goal concrete and nmerical. In a specific application, with the advancement of exploration steps, the size and variation trend of the reward value can effectively reflect the degree of excellence of the algorithm.

As shown in Fig. 7, the agent obtains a higher reward value at the initial stage of exploration because the MORRBQ algorithm adopts Dijkstra’s algorithm to initialize the Q-value table function. Compared with the other three algorithms, the reward value of the MORRBQ algorithm increased significantly and converged to zero faster. Moreover, the small fluctuation in the reward value growth curve of the MORRBQ algorithm also indicates that it is more directional and effectively speeds up the exploration process of the agent.

Fig. 7

The change trend of reward value of the 4 algorithms.

5.4.3 Algorithm exploration steps

The cost of the algorithm in the optimization process can be expressed as the number of steps required for convergence. The peak and falling speeds of the exploration steps reflect the optimization ability and stability of the algorithm.

As shown in Fig. 8, because the Dijkstra algorithm is used to initialize the value function during road network construction, the peak value of the exploration steps of the MORRBQ algorithm is considerably smaller than that of the other three algorithms, and the number of episodes required to reach the convergence state is also considerably smaller than that of the other algorithms. Compared with the MORR algorithm, the MORRBQ algorithm has higher stability after reaching the convergence state. Overall, the dynamic exploration factor σ enhances the exploration ability of the MORRBQ algorithm at the initial stage of iteration and assists the algorithm to improve the final convergence degree when more environmental feedback information is obtained. Compared with other algorithms, the MORRBQ algorithm shows stronger stability performance and exploration ability.

Fig. 8

Change trend of exploration steps of the 4 algorithms.

5.4.4 Result of route cost comparison

Figures 12 , and 14 show the route cost comparison results of the recommended route generated by the MORRBQ, PreGo, and MORP algorithms, respectively, for different objective attributes under three user preference setting scenarios.

Fig. 12

Route generation results of the 4 algorithms in Scenario 1.

Fig. 13

Route generation results of the 4 algorithms in Scenario 2.

Fig. 14

Route generation results of the 4 algorithms in Scenario 3.

As can be observed from Fig. 9, the route generated by the PreGo algorithm has higher travel time, safety risk, and COVID-19 risk than other methods because the PreGo algorithm discards some of the best routes when using the dynamic A* algorithm to find a solution. The MORP algorithm uses an adaptive ɛ-constrained optimization solution and considers different attributes in isolation.

Fig. 9

Route cost of the 4 algorithms on different target attributes in Scenario 1.

As shown in Fig. 10, in Scenario 2, the experimental results of the MORRBQ and MORR algorithms were better than those of the other two algorithms, and both the PreGo and MORP algorithms did not consider any user preferences. The route recommendation algorithm of the MORRBQ algorithm considers the preferences of a given user for different objective attributes, and the setting based on the given user preferences reduces the travel time in Scenario 2 and reduces the safety risk.

Fig. 10

Route cost of the 4 algorithms on different target attributes in Scenario 2.

As shown in Fig. 11, in Scenario 3, although the route generated by the PreGo algorithm has a low travel time, it has the highest consumption cost in the two objective attributes of safety and COVID-19 risks, which fails to satisfy the setting conditions of Scenario 3; that is, it only considers safety and COVID-19 risks and does not require the shortest travel time. The route generated by the MORR algorithm has a high travel-time cost. The route generated by the MORRBQ algorithm has low safety and COVID-19 risks, which satisfy the user preference settings in Scenario 3.

Fig. 11

Route cost of the 4 algorithms on different target attributes in Scenario 3.

In conclusion, the PreGo algorithm generated routes with longer travel time, higher safety risk, and higher COVID-19 risk. The MORP algorithm provides the Pareto optimal route but does not consider the user’s preference for different objective attributes. Moreover, the MORP and PreGo algorithms require a significant amount of computing time. The results of the MORR algorithm are better than those of the PreGo and MORP algorithms; however, the ɛ-greedy strategy of the MORR algorithm easily falls into a local optimum in the process of finding the route. It can be seen that the route generated by the MORRBQ route recommendation algorithm proposed in this study can consider user preferences for different route attributes and provide route suggestions in near real time.

5.4.5 Visualization results of multi-objective route recommendation

Figures 12 –14 show the recommended routes generated by the four algorithms considering the travel time, safety risk, and COVID-19 risk attributes simultaneously in different scenarios. The red, yellow, green, and black routes are generated by the MORRBQ, MORR, PreGo, and MORP algorithms, respectively. Point A is the source node (starting point), point B is the destination node (end point), and the black marked point is the location of COVID-19 cases. Considering the traffic accident data of New York City as the data source of the thermal map, it can intuitively show the road segments with high traffic accidents, that is, a high safety risk. The brighter the color, the higher is the safety risk of the road segment.

As can be observed from Fig. 12, under the setting conditions of Scenario 1, the routes generated by the MORRBQ and MORR algorithms all avoid road sections with high traffic accidents (i.e., high safety risks) and high COVID-19 risk, and the routes generated by the MORP algorithm do not avoid areas with high safety risks. However, the route generated by the PreGo algorithm has high safety and COVID-19 risks.

The route results generated by the four algorithms in Scenario 2 are shown in Fig. 13. The route generated by the MORRBQ algorithm avoids road sections with high safety risk and has a short traffic time, which satisfies the weight allocation set in Scenario 2. However, the routes generated by the MORR and MORP algorithms did not avoid areas with high safety risks, and the routes generated by the PreGo algorithm consumed the maximum time among the four algorithms.

Figure 14 shows the route results generated by the three algorithms in Scenario 3. It can be observed that the MORRBQ algorithm considers the optimization objectives of safety and COVID-19 risks, and the generated route has low safety and COVID-19 risks. Although the route generated by the MORR algorithm has a low risk of COVID-19, it does not avoid areas with high safety risks. The route generated by the MORP algorithm does not avoid the areas with high safety and COVID-19 risks. Although the route travel time generated by PreGo algorithm is shorter, its safety and COVID-19 risks are the highest compared with the other two algorithms.

6 Conclusion

Based on the reinforcement learning algorithm, this study proposes a multi-objective route recommendation algorithm, MORRBQ, which integrates user preferences. This algorithm not only adopts the common route recommendation optimization objective, which is the travel time, but also adopts the safety and COVID-19 risk objective attributes. Different objective attributes and their weight allocation will result in different route recommendation results. High-weighted travel time attribute will enable the agent to generate a short distance-prior route, high-weighted security risk attribute will enable the agent to generate a safety-first route, and high-weighted COVID-19 risk attribute will enable the agent to generate a route to avoid epidemic areas. Compared with other algorithms, MORRBQ algorithm can balance the impact of travel time, safety risk and COVID-19 risk, and generate personalized recommendation routes while following user preferences. The initialization operation of the Q-value table can effectively shorten the iteration time of the algorithm and clarify the agents’ choice of road node and action. The introduction of the dynamic exploration factor σenhances the exploration ability of the MORRBQ algorithm at the initial stage of iteration and assists the algorithm to improve the final convergence degree when more environmental feedback information is obtained. A series of experimental results on real road network data show that the recommended route generated by the MORRBQ algorithm has a lower route cost than other algorithms, and because of the unique Q-value table search mechanism of the MORRBQ algorithm, it can generate route recommendation results almost in real time. In future work, we will consider the application of a reinforcement learning algorithm in scenic spot recommendation and organically combine it with the route recommendation work in this study.

Footnotes

Acknowledgments

The authors would like to thank the reviewers for their useful comments and suggestions for this paper. This work was supported by the National Natural Science Foundation of China (Grant Nos. 61702010, 61972439), the Anhui Provincial Natural Science Foundation of China (Grant No. 2208085MF164), and the University Natural Science Research Program of Anhui Province (Grant No. KJ2021A0125).

References

Liu

, Han

, Fu

, Zhou

, Lu

and Xiong

, Multi-modal transportation recommendation with unified route representation learning, Proceedings of the VLDB Endowment, 2020, 342–350.

Sarker

, Shen

, Murphy

, Wang

and Rindos

A.J.

, Vehicle routing trifecta: data-driven route recommendation system, Proceedings of the 28th International Conference on Computer Communications and Networks, 2019, 1–9.

, Yang

, Cui

and Wang

, Profitable Taxi Travel Route Recommendation Based on Big Taxi Trajectory Data, IEEE Transactions on Intelligent Transportation Systems 21(2) (2020), 653–668.

, Qin

and Shao

, Personalized travel route recommendation from multi-source social media data, Multimedia Tools and Applications 79(45-46) (2020), 33365–33380.

Ghorbani

, Alinaghian

, Gharehpetian

G.B.

, Mohammadi

and Perboli

, A survey on environmentally friendly vehicle routing problem and a proposal of its classification, Sustainability (Switzerland) 12(21) (2020), 1–72.

Zhang

, Ma

, Zhao

, Huangfu

and Liu

, A Novel Energy Management Strategy based on Dual Reward Function Q-learning for Fuel Cell Hybried Electric Vehicle, IEEE Transactions on Industrial Electronics 69(2) (2021), 1537–1547.

Jeong

, Agrawal

T.K.

, Flores-García

and Wiktorsson

, A reinforcement learning model for material handling task assignment and route planning in dynamic production logistics environment, Procedia CIRP 104(1) (2021), 1807–1812.

Ganti

R.K.

, Pham

, Ahmadi

, Nangia

and Abdelzaher

T.F.

, GreenGPS: A participatory sensing fuel-efficient maps application, Proceedings of the 8th International Conference on Mobile Systems, Applications, and Services, 2010, 151–164.

Yera

and Martínez

, Fuzzy tools in recommender systems: A survey, International Journal of Computational Intelligence Systems 10(1) (2017), 776–803.

10.

Cheng

, A travel route recommendation algorithm based on interest theme and distance matching, EURASIP Journal on Advances in Signal Processing 2021(1) (2021), 1–10.

11.

Wang

, Wu

and Zhao

, Personalized route recommendation with neural network enhanced A* search algorithm, IEEE Transactions on Knowledge and Data Engineering 1(1) (2021), 1–14.

12.

Zhou

, Zhao

, Fang

, Chen

and Zeng

, Hybrid route recommendation with taxi and shared bicycles, Distributed and Parallel Databases 38(3) (2020), 563–583.

13.

Feng

, Yao

, Gu

, Zhang

and Yu

, Environmental benefitsmining based on data-driven taxi cruising recommendation strategy, Journal of Cleaner Production 326 (2021), 129376.

14.

Jia

, Fang

, Tan

, Liu

, Huo

and Ma

, Contextaware route recommendation with weight learning through deep neural networks, IEEE 2020 American Control Conference 2020, 4040–4045.

15.

de Oliveira e Silva

R.A.

, Cui

, Rahimi

S.M.

and Wang

, Personalized route recommendation through historical travel behavior analysis, GeoInformatica 26(3) (2022), 1–36.

16.

, Wang

, Li

and Zheng

, Spatio-temporal feature fusion for dynamic taxi route recommendation via deep reinforcement learning, Knowledge-Based Systems 205(1) (2020), 106302–106313.

17.

Quercia

, Schifanella

and Aiello

L.M.

, The shortest path to happiness: Recommending beautiful, quiet, and happy routes in the city, Proceedings of the 25th ACM Conference on Hypertext and Social Media, 2014, 116–125.

18.

Hendawi

A.M.

, Rustum

and Ahmadain

A.A.

, Smart personalized routing for smart cities, Proceedings of the 33rd International Conference on Data Engineering, 2017, 1295–1306.

19.

Kang

, Qi

, Janecek

and Banerjee

, EcoDrive: A mobile sensing and control system for fuel efficient driving, Proceedings of the 21st Annual International Conference on Mobile Computing and Networking, 2015, 358–371.

20.

Sarker

, Shen

and Kowsari

, A Data-Driven Reinforcement Learning Based Multi-Objective Route Recommendation System, 2020 IEEE 17th International Conference on Mobile Ad Hoc and Sensor Systems, 2020, 103–111.

21.

Guo

, Yang

, Andersen

, Jensen

C.S.

and Torp

, EcoSky: Reducing vehicular environmental impact through eco-routing, IEEE 31st International Conference on Data Engineering, 2015, 1412–1415.

22.

Zheng

, Luo

, Sun

, Yu

, Zhang

and Chen

, A novel multi-objective and multi-constraint route recommendation method based on crowd sensing, Applied Sciences 11(21) (2021), 10497–10511.

23.

Huang

, Xu

and Weng

, Multi-task travel route planning with a flexible deep learning framework, IEEE Transactions on Intelligent Transportation Systems 22(7) (2020), 3907–3918.

24.

Malik

and Kim

D.H.

, Optimal travel route recommendation mechanism based on neural networks and particle swarm optimization for efficient tourism using tourist vehicular data, Sustainability (Switzerland) 11(12) (2019), 3357–3383.

25.

Rani

, Kholidah

K.N.

and Huda

S.N.

, A Development of Travel Itinerary Planning Application using Traveling Salesman Problem and K-Means Clustering Approach, Proceedings of the 2018 7th International Conference on Software and Computer Applications. 2018, 327–331.

26.

Sarker

, Shen

and Stankovic

J.A.

, MORP: Data-Driven Multi-Objective Route Planning and Optimization for ElectricVehicles, Proceedings of the ACMon Interactive Mobile Wearable and Ubiquitous Technologies, 2018, 1–35.

Multi-objective route recommendation method based on Q-learning algorithm

Abstract

Keywords

1 Introduction

2 Related work

2.1 Single-objective route recommendation

2.2 Multi-objective route recommendation

3 Problem description

3.1 Road network model

3.4 Optimal route

4 Multi-objective route recommendation algorithm based on q-learning

4.2.1 Travel time prediction

4.2.3 COVID-19 risk prediction

4.6 Q-value table update and model training

4.8 Algorithm complexity analysis

4.8.1 Time complexity analysis

4.8.2 Space complexity analysis

5 Experiment

5.1 Datasets

5.3 Experiment Settings

5.3.1 User preference settings

5.3.2 Evaluation indicators

5.4.1 Time performance

Table 5 Time performance comparison of the 4 algorithms Algorithm Running time/min Convergence Time/min Convergence Episodes MORRBQ 6.86 3.29 6000 MORR 5.65 3.83 6200 PreGo 354.68 226.73 9100 MORP 351.18 210.26 >10000

6 Conclusion

Footnotes

Acknowledgments

References

Table 5
Time performance comparison of the 4 algorithms

Algorithm Running time/min Convergence Time/min Convergence Episodes

MORRBQ 6.86 3.29 6000

MORR 5.65 3.83 6200

PreGo 354.68 226.73 9100

MORP 351.18 210.26 >10000