3.3.1 The Q-learning based, Shortest-path Generation Algorithm

The calculation of the shortest path between two nodes is one of the classic problems in graph theory. The DQSR uses the Global Positioning System (GPS) location, i.e., the latitude and the longitude, of all the customers to calculate each customer’s all ‘$x$’ nearest neighbor customers’ respective locations. Then, it uses the Q-learning-based, shortest-path generation algorithm (Algorithm 1) to generate the shortest path between each customer and this customer’s nearest neighbor customers and find this path’s length.

The inputs to the Algorithm 1 are given in line 1 of the algorithm. In particular, the RL agent requires the road network represented by a directed graph, $G\left(V,E\right)$, road network length graph, i.e., the road network with the each of its edge having the corresponding length, list of customers to visit (in terms of their corresponding edges), each customer’s nearest neighbor customers list, ‘n’ Q shortest-path tables \{$Q_{\colon 1},Q_{\colon 2},\ldots ,Q_{\colon n}\}$to store the updated state-action value for each of the ‘n’ customers, respectively, distance table $\left(D_{Route}\right)~ $to store the length of the shortest path between each customer and this customer’s nearest neighbor customers, path table $\left(P_{Route}\right)~ $to store the shortest path between each customer and this customer’s nearest neighbor customers, and maximum number of random walks the RL agent can take before terminating the ‘while’ loop. Notably, the Q shortest-path tables each have the same state transition probability matrix as that of the road network. In contrast, the distance and path tables each have the same state transition probability matrix as that of each customer and this customer’s nearest neighbor customers, i.e., with size $n\times x.$ The $i^{th}$ Q shortest-path table, $Q_{\colon i}\,,$ stores the Q-value update for the path from the $i^{th}$ customer’s all ‘$x$’ nearest neighbor customers to the $i^{th}$ customer. In particular, the $Q_{\colon i}$ is used to calculate the shortest path and distance from the $i^{th}$ customer’s all ‘$x$’ nearest neighbor customers to the $i^{th}$ customer; here ‘$\colon $’ represents the list of the $i^{th}$ customer’s nearest neighbor customers. Also, the output of the algorithm includes the updated path and distance tables. In addition, the algorithm requires specifying the learning rate, discount factor, initial epsilon value, epsilon decay rate, and minimum epsilon.

The working of Algorithm 1 is shown in lines 4 to 24 of the algorithm. The first ‘for loop’ loops through all the customers to visit, as mentioned in line 4 of the algorithm. The RL agent copies the $i^{th}$ customer’s Q shortest-path table and the road network length graph as the reward table with the sign of its each edge length changed to negative, in lines 5 and 6 of the algorithm, respectively. The second ‘for loop’ loops through the $i^{th}$ customer’s all ‘$x$’ nearest neighbor customers, as mentioned in line 7 of the algorithm. Since the goal of the RL agent is to reach the $i^{th}$ customer’s nodes, we manipulate the reward table by adding extra positive reward to each edge that is connected to any of these nodes, as in line 8 of the algorithm. This extra reward enables the RL agent to learn effectively. Q shortest-path table update for the path from the $i^{th}$ customer’s all ‘x’ nearest neighbor customers to the $i^{th}$ customer is presented in lines 7 to 20 of the algorithm. First, the RL agent starts its functioning from the assigned current state and random-walks one step at a time until its termination according to the ‘while’ condition given in line 11 of the algorithm. In other words, the RL agent’s random walking is terminated either when the number of agent random walks completed exceeds the maximum number of random walks the agent can take (max_steps) or when the agent reaches the end state. Meanwhile, the RL agent chooses the action ($a$) at the current state ($s$) (as mentioned in line 12 of the algorithm), based on the $\varepsilon $-greedy selection, which enables the agent to either explore or exploit depending on the epsilon value. The RL agent then performs the chosen action and moves to the next state ($s')$, as in line 13 of the algorithm. Subsequently, the RL agent updates the previous Q-value, according to Eq. (2), as in line 14 of the algorithm. Further, the RL agent checks if the state $s'$ is the end state and changes the termination parameter (goal)’s value accordingly, as in lines 15 and 16 of the algorithm, respectively. Next, the RL agent replaces the current state with the next state and decrements the max_steps. The epsilon value is then updated after the termination of the RL agent’s path search, as in lines 18 and 19 of the algorithm. The entire process of Q-value update, as in lines 10 to 19 of the algorithm, is repeated $T$ (an user-defined number) times by the ‘for loop’ (in line 10 of the algorithm). These $T~ $repetitions allow the RL agent to learn the correct shortest-path from the $i^{th}$ customer’s all ‘$x$’nearest neighbor customers to the $i^{th}$ customer. The RL agent then calculates the path and distance from the $i^{th}$ customer’s all ‘$x$’nearest neighbor customers to the $i^{th}$ customer, in line 20 of the algorithm, based on the Algorithm 3 (given subsequently in this paper). Finally, the RL agent updates the $i^{th}$ component of the distance and path tables (in lines 22 and 23 of the algorithm, respectively).

An example of the Q-learning based generation of the shortest path from each customer’s nearest neighbor customers to this customer is shown in Figs. 1(a)-(d). In particular, Fig. 1(a) shows an arbitrary road network with five customers. Each customer’s starting and end nodes are represented by ‘green’ and ‘light blue’ color dots, respectively. The RL agent then updates the shortest path from each customer’s nearest neighbor customers to this customer by visiting each customer once and returing to the starting customer.

The process of updating the Q shortest-path table for each customer is shown in Fig. 1(b). Fig. 1(b) also shows the list of the respective Q shortest-path table updates for all the five customers. In particular, the first image in Fig. 1(b) shows the learned Q-value for the path from the respective end node of all the customer $d_{1}$’s nearest neighbor customers to $d_{1}.$ In addition, each edge’s width represents this edge’s Q-value compared to other edges. Since, the Q-value grows when reaching the destination, keeping the Q shortest-path table update for the path from each customer’s nearest neighbor customers to this customer in one Q shortest-path table is possible and doesn’t contradict when exploiting the Q shortest-path table to generate the shortest path. Fig. 1(c) shows each customer to this customer’s each nearest neighbor customer transitional distance-table. Similarly, Fig. 1(d) shows each customer to this customer’s each nearest neighbor customer transitional path-table. Notably, the paths in this table are reversed when the states are reversed.

Fig. 1. An example of the Q-learning based generation of the shortest path from each customer’s nearest neighbor customers to this customer and the shortest route connecting all the customers.Fig. 1(a)is an arbitrary road network with five customers.Fig. 1(b)shows the list of the respective Q shortest-table updates for all the five customers and each edge’s width represents this edge’s Q-value compared to other edges.Fig. 1(c)shows each customer to this customer’s each nearest neighbor customer transitional distance-table.Fig. 1(d)shows each customer to this customer’s each nearest neighbor customer transitional path-table.Fig. 1(e)shows the Q-value transition between each customer and this customer’s nearest neighbor customers.Fig. 1(f)shows the shortest route from the customer $d_{1}$, generated based on theAlgorithm 3and the final Q-routing table fromFig. 1(e).

Algorithm 1. Q-learning based, Shortest-path generation.

3.3.2 The Q-learning based, Shortest-route Generation Algorithm

Algorithm 2 is for the Q-learning based generation of the shortest route from any customer to other customers by visiting each other customer once and returning back to the starting customer. The inputs to the algorithm are given in line 1 of the algorithm. The RL agent requires the Q-routing table having each customer and this customer’s nearest neighbor customers’ state transition, the distance routing and path routing tables from the Algorithm 1, the reward table having its state transitions same as those of the Q-routing table with the initial reward value as -1, the list of customers to visit, the maximum number of random walks for the RL agent, the total number of episodes, and the starting customer. The output of the algorithm includes the shortest route and distance. The algorithm also requires specifying the learning rate, discount factor, initial epsilon value, epsilon decay rate, and minimum epsilon.

The working of Algorithm 2 is shown in lines 4 to 38 of the algorithm. The algorithm consists of five subparts: the global variable setup, episode variable setup, Q-value update, the global variable’s update by comparing the episode variables, and route and route distance generation. The Q-routing and reward tables are copied as the best Q-routing and reward tables, as in line 4 of the algorithm. Then, the global variable for the number of visited customers and the distance covered, respectively, is initialized, as in line 5 of the algorithm.

Algorithm 2. Q-learning based, Shortest-route generation.

Algorithm 3. Path/route generation and the corresponding distance calculation.

The ‘for loop’ loops through all the available episodes, as shown in line 8 of the algorithm. The episode variables are updated in each episode, as in lines 7 to 11 of the algorithm. The Q-value update during each loop is similar to the Q-value update of Algorithm 1 and is shown in lines 12 to 26 of the algorithm. The RL agent starts its functioning from the assigned current state and random-walks one step at a time until its termination according to the ‘while’ condition given in line 12 of the algorithm. The RL agent is terminated either when its completed number of random walks exceeds the maximum number of random walks the agent can take (max_steps) or when the agent reaches the end state. The agent then chooses an action ($a$) at the current state ($s$), based on the $\varepsilon $-greedy selection which enables the agent to either explore or exploit based on the epsilon value, as in line 13, and selects the next state, as given in line 14 of the algorithm. Subsequently, the episode reward table is updated, as in lines 15 to 22 of the algorithm. A negative reward is assigned between the current and next states if the RL agent visits all the customers and ends at a different customer than the starting customer, as in lines 15 and 16 of the algorithm. In addition, the reward table is updated with a negative reward if the RL agent visits the same customer more than once, as in lines 19 and 20 of the algorithm. On the other hand, a positive reward is assigned if the RL agent visits the starting customer’s each other customer once and returns to the starting customer, as in lines 17 and 18 of the algorithm. Then, the next to visit customer is removed from the to-visit customers list, as in lines 21 and 22 of the algorithm. The RL agent subsequently updates the previous Q-value, based on the current and next customer states and using Eq. (2), as in line 23 of the algorithm. Also, the RL agent replaces the current state with the next state and decrements the max_steps, as in line 26 of the algorithm. Finally, the number of customer locations visited (VD) by the RL agent is counted after the Q-learning process is terminated. Further, the global route and global route distance variables are calculated based on the VD, as in lines 28 to 35 of the algorithm. If the VD is equal to the previous global_visited_path, no changes in the best reward and the Q-routing tables are made. Otherwise, if the VD is greater than the previous global_visited_path, the length of the global route distance is set to negative infinity, and the best reward and Q-routing tables are replaced by the episode reward and Q-routing tables, respectively, as in lines 29 to 31 of the algorithm. This step is followed by assigning a global_visited_path equal to the VD. Further, if the episode route distance (episode_distance) is greater than the global route distance, then the global route distance is replaced by the episode route distance, and the best reward and Q-routing tables are replaced by the episode reward and Q-routing tables, respectively, as in lines 33 to 35 of the algorithm. The epsilon value is then updated after the termination of the RL agent’s route search, as in lines 36 and 37 of the algorithm. Finally, the RL agent generates the shortest route and distance after the Q-value update for all the possible episodes is completed, based on Algorithm 3. An example of the shortest route generation is shown in Figs. 1(e) and 1(f). Fig. 1(e) shows the Q-value transition between each customer and this customer’s nearest neighbor customers. Subsequently, the shortest route from any customer to other customers is generated based on Algorithm 3 andthe final Q-routing table from Fig. 1(e).

Algorithm 3 is for the path/route generation and the corresponding distance calculation. The inputs to the algorithm are the updated Q-value table, starting and ending nodes, and distance table (the road length graph for the path generation and the distance routing table for the route generation), as in line 1 of the algorithm. The output of the algorithm is the path/route generated and its corresponding distance, as in line 2 of the algorithm. The working of the algorithm is shown in lines 3 to 14 of the algorithm. The current state, path, and distance are assigned their initial values in lines 3 to 5 of the algorithm. In addition, the variable ‘goal’ is set to False initially, as in line 6 of the algorithm. Notably, the RL agent calculates the path/route according to lines 7 to 13 of the algorithm. In particular, the RL agent goes through the ‘while loop’ until the terminating condition is met. The RL agent then calculates the next state from the current state by using the Q-value table through exploitation, as in lines 8 and 9 of the algorithm. Subsequently, the path and distance are updated, as in lines 10 and 11 of the algorithm. In addition, the RL agent checks if the next state is the end state during each ‘while loop’, as in line 12 of the algorithm. If the next state is the end state, the variable ‘goal’ is set to ‘True’, as in line 13 of the algorithm, and the ‘while loop’ terminates. Finally, the path/route and its corresponding distance are returned by the algorithm.

4.3.1 Route Visualization

The road network and the route information are the two data required for the route visualization on the QGIS application. The road network is generated through the QGIS application or can be found in the government portal. Notably, we generated the road network from scratch for the Yeonsu-gu, Incheon, South Korea, and stored it as a shape (.shp) file. The route result is generated using a python program. The route result contains three data fields (i) a list of road links or edges through which the RL agent should travel through, (ii) the sequence number denoting the order in which the agent should travel, and (iii) a flag to separate the agent-selected road links from the total road links list. The route information is finally stored as a comma-separated value (CSV) file.

Meanwhile, the python program and QGIS have not been embedded together in this work. Rather, the route result from the python program is manually uploaded to the QGIS application for route visualization. First, the shapefile containing the road network information is loaded to the QGIS through the ‘Add Vector Layer’ function. In particular, the road network layer consists of fields, such as the road link id, node id, location information, etc. Similarly, the route information file is uploaded to QGIS through the ‘Add Vector Layer’ function. It consists of fields like road link id, sequence number, and flag. Next, we join the route layer to the road network layer based on a common field. Consequently, two new data fields, namely sequence number and flag, are added to the road network layer. Also, the road link id in the road network layer is categorized into two groups based on the flag data field: (i) the one selected for the agent to travel through and (ii) the one not included in the route planning. This categorization of the road link is performed through the QGIS Symbology properties, and the road sequence level’s categorization is performed through the QGIS Label properties.

Fig. 3 shows the visualization of the shortest routes from the DQSR and Q+TSP algorithms, respectively. In particular, these results are visualized on a QGIS map. The ‘black’ lines represent the road network, ‘green’ dots represent the illegal-parking locations, and dotted ‘blue’ lines represent the customer links or the customers for the DQSR-based RL agent to visit. Fig. 3(a) shows the shortest route covering all the customers and returning to the starting customer (‘red’ line). In addition, the numbers mentioned in the road network show the order in which the DQSR-based RL agent had to follow the road links to visit all the mentioned customers and return to the starting customer. Correspondingly, the DQSR-based RL agent’s shortest route is 58155.14 m long. In addition, the DQSR-based RL agent had to visit 600 out of the total 2152 road links, for the shortest route. Importantly, the DQSR-based RL agent could choose to travel through previously traveled road links without concerning that the agent would visit a previously visited customer. The agent was allowed to make such a choice if and only if the path through a customer revisited is the shortest path connecting two other customers. Fig. 3(b) shows the zoomed-in visualization of the region within the ‘purple circle’ of Fig. 3(a). This zoomed-in image of Fig. 3 (b) is more intuitive and easier to visualize. Since the DQSR-based RL agent visited the road links multiple times, only the last sequence numbers of the road links in the route are displayed in the image.

Fig. 3. Route visualization on QGIS: (a) The DQSR algorithms based shortest-route; (b) The zoomed-in visualization of the region within the ‘purple circle’ ofFig. 3(a); (c) The Q+TSP algorithm based shortest-route; (d) The zoomed-in visualization of the region within the ‘purple circle’ ofFig. 3(c). The dark purple arrows inFig. 3(d)highlight some of the differences in the shortest-route generation by the DQSR and Q+TSP algorithms, respectively.

Fig. 3(c) shows the shortest route generated by the Q+TSP algorithm. In particular, this shortest route is represented by the ‘purple’ line of Fig. 3(c). The numbers in the road network show the sequence in which the agent had to travel the road links to complete the shortest route. Notably, the Q+TSP algorithm required 55703.39 m for the route connecting all the customers. In addition, the Q+TSP agent visited 597 out of the total 2153 road links in generating the shortest route. Meanwhile, the Q+TSP agent was allowed to go through the same road links without violating the condition of visiting an already visited customer. Fig. 3(d) is the zoomed-in image of the region within the ‘purple circle’ of Fig. 3(c), which is more intuitive for the reader to understand the shortest route. Further, Fig. 3(d)’s dark purple arrows highlight some of the differences in the shortest-route generation by the DQSR and Q+TSP algorithms, respectively.

Table 4 summarizes the algorithms’ respective performances. The table includes the physical distance of the shortest route generated by each of the algorithms and also provides the algorithms’ respective time complexities in generating the shortest routes. Hence, the Q+TSP algorithm provides the shortest route in terms of travel distance which is approximately 55.7 km for this route, whereas the DQSR’s shortest route overshot the Q+TSP algorithm’s travel distance by approximately 3 km. But, a 3 km overshoot is merely 0.5 % of the Yeonsu-gu region’s total road length of 557.49 km. Therefore, we can argue that both the DQSR and Q+TSP algorithms respectively generate the shortest route. However, DQSR is more preferred compared to the other two algorithms when the time complexity is taken into account. Table 4 shows that the DQSR required 237 s to calculate the shortest path between each customer and this customer’s nearest neighbor customers and required another 209 seconds to calculate the shortest route connecting all the customers, i.e., a total time of 446 s. In contrast, the Q+TSP algorithm required 1412 s to calculate the shortest path between each customer and all other customers and 0.23 s to calculate the shortest route connecting all the customers, i.e., a total time of 1412.23 s. Since the road network for our case study is very large with very high network depth, the Dijkstra+TSP’s Dijkstra algorithm couldn’t generate the shortest path in 6 h. Therefore, we chose to terminate the algorithm.