key: cord-0588547-itzicc95
authors: Mukai, Tatsuro; Ikeda, Yuichi
title: Optimizing travel routes using temporal networks constructed from GPS data
date: 2021-06-01
journal: nan
DOI: nan
sha: 245bb6896b831283646e0b3dc62f5c35288ac0eb
doc_id: 588547
cord_uid: itzicc95

Because of the complexity of urban transportation networks and the temporal changes in traffic conditions, it is difficult to assess real-time traffic situations. However, the development of information terminals has made it easier to obtain personal mobility information. In this study, we propose methods for evaluating the mobility of people in a city using global positioning system data. There are two main methods for evaluating movement. One is to create a temporal network from real data and check the change in travel time according to time zones or seasons. Temporal networks are difficult to evaluate because of their time complexity, and in this study, we proposed an evaluation method using the probability density function of travel time. The other method is to define a time-dependent traveling salesman problem and find an efficient traveling route by finding the shortest path. By creating a time-dependent traveling salesman problem in an existing city and solving it, a traveler can choose an efficient route by considering traffic conditions at different times of the day. We used 2 months of data from Kyoto City to conduct a traffic evaluation as a case study.

One of the major issues confronting urban areas is transportation planning [1] . Smooth transportation contributes significantly to residents' life satisfaction, but transportation planning is becoming more difficult because of the global population growth in urban areas. In addition, the development of tourism has increased the number of visitors to these areas, and a known tourism problem has emerged [2] . This negatively affects both visitors and residents [2] [3] [4] .

Three reasons make road traffic in urban areas difficult [5] . First, the urban road networks are typically complicated. Cities are often densely populated with tunnels and elevated structures that, with numerous roads, form a complex transportation network. Second, travelers may be heading for different destinations. This creates a great deal of uncertainty in transportation planning as the number of travelers increases. Third, the road traffic situation changes over time. Depending on traffic congestion, travelers may change their transportation and traveling route choices, and travel times for the same traveling route can often vary significantly.

However, thanks to the development of information terminals in recent years, it has become easier to obtain mobility data and provide mobility information to individuals. Infor-mation terminals, such as smartphones, are now widely used and carried by most individuals at all times. Therefore, it has become possible to compose big data from the global positioning system (GPS) measured using these devices and use the data to analyze movement [6] .

To analyze human mobility, network science is useful [7] [8] . Networks whose connection status changes with time are called temporal networks [9] . They are more difficult to evaluate than static networks because of their time-varying nature, but since they represent real-world problems well, they have been used in various fields such as interpersonal communication [10] [11] [12] [13] , transmission to an unspecified number of people using SNS and the web [14] [15] [16] [17] , physical contact [18] [19] [20] [21] , and cytology [22] [23] [24] [25] . Temporal networks are also preferred to represent movement as a network, to capture changes in traffic conditions over time. Kujala et al. used temporal networks to evaluate the public transportation system in Helsinki [26] . They constructed the networks from timetables and open map information and evaluated public transportation by focusing on travel time and the number of transfers.

Besides, the shortest path problem can be used to find an efficient travel route. In recent years, the shortest path problem is as a real-world problem with a time component [27] . Heuristic solutions to such a problem, such as the timedependent traveling salesman problem (TDTSP), have been devised [28] [29] [30] [31] .

In this study, we propose two methods: one is to evaluate human mobility using temporal networks constructed from GPS data, and the other is to search for the shortest path by constructing and solving the TDTSP. In both methods, location information measured from smartphones is converted into a timetable of location transitions called "transfer connections", from which an optimal set of paths to the destination is obtained to construct mobility networks. In the evaluation of movement using temporal networks, networks are visualized and compared according to seasons, time zones, and whether the moving person is a resident or a visitor. In a methodology of finding the shortest path, the time weights of the TDTSP are determined from the set of optimal paths, and the ant colony optimization (ACO) method is used to solve the problem. In the application of the ACO method, a congestion level is obtained from GPS and used in the calculation.

The main contributions of this study include the following:

• By applying existing methods for constructing temporal networks and evaluating public transportation, we construct temporal networks from the GPS of smartphones. With the GPS, it is possible to take into account other means of transportation other than public transportation, and it is expected that the evaluation will be realistic, including delays in transportation because of congestion.

With the development of information terminals in recent years, GPS has been commonly used, so it can be easily extended to other cities. Temporal networks can describe real-world problems more precisely than can static networks, but evaluating temporal networks is difficult. In this study, we proposed a new evaluation method for mobile networks using probability density functions. • In this study, we determined the time weights of edges in the TDTSP from GPS data based on the method used to create temporal networks. Although existing studies have created the TDTSP from GPS data, the weights were determined originally. In addition, to apply ACO the TDTSP, we decide a congestion level from the GPS and calculate the transition probability using this level.

Selecting a route is difficult if the destination is crowded at certain times of the day. The rest of the paper is organized as follows. In Section II, we introduce the basic methodology. In Section III, we discuss improvements to the basic methodology. In Section. IV, we describe the proposed method. Following that we discuss the experimental results in Section V. Finally, we conclude our study in Section VI.

Although networks are used in various fields, several realworld networks change over time. Networks, those in which the edge connections change with time are called temporal networks [9] . Temporal networks are often more realistic than static networks and have been used in road traffic analysis. Kujala et al. [26] constructed a temporal network from public transport timetables to model the movement of people. They used a multi-criteria profile connection scan algorithm (mcpCSA) to construct the network. This algorithm is used to compute optimal travels in a dynamic public transportation network, which can represent many events occurring between nodes as a temporal network.

1) CSA: The mcpCSA is an extension of the connection scan algorithm (CSA). The CSA can calculate the fastest time to reach each stop from a given starting point.

Instead of using a graph as Dijkstra's algorithm does, this algorithm uses a single array C of timetable connections sorted by departure time. Upon receiving the origin p s and departure time τ as input, labels τ (p), which represent the shortest arrival time at each stop, are initialized to infinity. Then c ∈ C is scanned to determine whether it is reachable. If it is reachable and the arrival time of c improves the label τ (p arr (c)) of the destination, update the label. Repeat until you have scanned all of C.

2) pCSA: An extension of the CSA for more complex scenarios is the profile CSA (pCSA). This algorithm returns a set of Pareto-optimal (departure time, arrival time) paths from each stop to a certain destination. Pareto-optimal here means that the departure time is optimized to be slower and the arrival time is optimized to be faster.

This algorithm uses an array C of timetable connections sorted in descending order of departure time. Whengiven a destination p t as input, it creates the empty set of Paretooptimal paths for each stop, c ∈ C is scanned in turn, and check if p t is reachable. If it is reachable and (τ dep (c), τ * ) is Pareto-optimal compared to the set of paths held by the starting point of c, it is added to the set. Here τ dep (c) represents the departure time of c and τ * represents the arrival time to p t . Do this until you have scanned all of C.

3) mcpCSA: The mcpCSA is an extension of the pCSA. The mcpCSA extends the Pareto-optimal (departure time, arrival time) treated in the pCSA to the multi-criteria Paretooptimal like (departure time, arrival time, number of transfers).

To reduce traffic congestion, it is important to recommend efficient travel routes to facilitate movement. To determine the travel route, we formulate and solve the TDTSP.

1) Problem Formulation: The TDTSP is a shortest path problem on a time-dependent network represented by the directed graph G = (V, E, W, T ). Here V represents the set of nodes, E represents the set of edges, W represents the set of time weights, and the time interval T is the set of time-varying periods.

The weight w(v i , v j , τ ) ∈ W depends on the starting point v i ∈ V , the ending point v j ∈ V , and the time τ ∈ T . P ath(v 1 , v n ) = [v 1 , v 2 ., v n ] represents the transition permutation of nodes from v 1 ∈ V to v n ∈ V .

When the time starting from v 1 is τ 0 ∈ T , the sum of the time weights of P ath(v 1 , v n ), f τ0 (P ath(v 1 , v n )), is calculated recursively as follows,

The TDTSP is a combinatorial optimization problem to find a path such that f τ0 (P ath(v 1 , v n )) is minimized.

2) ACO: The ACO method [32] can produce a solution to the TDTSP [28] [29] [30] [31] .

In the ACO method, each edge e(v i , v j ) ∈ E has a pheromone σ i,j (τ ) for each time τ ∈ T . The agent k at node i ∈ V at time τ calculates the transition probability p k i,j (τ ) to a next node according to the pheromone, The next node may be randomly determined using a certain probability, to avoid a local solution.

Here Ω is the node that agent k has not visited yet, η ij (τ ) is the heuristic information, and parameters α and β are constants that control the relative importance of pheromone versus heuristic information η ij .

The heuristic information η ij is calculated using the following equation,

.

In this study, we have independently improved the method described in Section II to suit our purposes.

In this study, we used the pCSA to construct a temporal network. It is an algorithm to calculate the optimal traveling route in a dynamic public transportation network. Since this research uses GPS, we processed the GPS data so that the pCSA could use it.

Transfer connections are formed from GPS movements of the same terminal. GPS data show the location by latitude and longitude, but the granularity is too fine, so we divide the map into meshes and form transfer connections by mesh transitions.

In this study, we set a congestion level and obtain the pheromone for each period from the congestion level.

The pheromone σ i,j (τ ) is given as follows:

σ 0(i,j) is the basic pheromone of e(i, j), and θ(τ ) is the congestion level of the destination at time τ .

Congestion is given as a number between 0 and 1, and the more congested a location is, the more difficult it is to be chosen. Congestion is expressed by the following equation,

We can detect the number of people at node j for each time from the GPS data. l max is the number of people at node j per time when the number of people staying at node j was the highest, and l(τ ) is the number of people at node j during time τ . The update of the basic pheromone is represented by the following equation,

ρ is the rate at which the pheromone remains after evaporation. The increment of pheromone ∆σ i,j is determined by ant k,

Q is a constant and γ k is the total moving cost of ant k.

With the development of information terminals, it has become possible to track individual movements. Even handheld ,including smartphones, can use the GPS.

In this trend, it is becoming possible to analyze big data of personal mobility data. It is expected that with large amounts of data, mobility can be evaluated in greater detail, such as when and where people are more likely to move.

In this study, we propose methods for analyzing mobility using temporal networks and creating the TDTSP to search for the shortest path with meta-heuristics, using actual GPS data of individuals. Approximately 80% were Kyoto residents, and 1% were visitors from abroad.

We used GPS data provided by Agoop Inc. These data were obtained from users of a smartphone application who gave their consent. The data are linked to a daily ID that identifies a device and allows it to be tracked for 1 day.

This study used 58 days of data in February and April 2019 measured in Kyoto. In 2019, February was the month when Kyoto had the fewest number of tourists, and April was the month when Kyoto had the highest number of tourists. Table  I shows the amount of data measured in each month. The number of terminals used for the measurement was higher in April, but the number of logs was lower. The GPS data used in this study is obtained when the user performs some action when the application is launched. While the application is running in the background, it measures when a user moves significantly or stays in facilities, or after a certain amount of time, depending on the OS. Since the number of logs depends on user activities, it is difficult to determine the cause of the low number of logs in April. Figure 1 shows the number of logs measured by the hour for all data. It shows that the number of logs is low during the late-night hours when people are immobile, and the number of logs increases as people become mobile around 8:00.

These data are also accompanied by an estimate of the residence location of the terminal owner. The percentage of all logs classified by immigration is shown in Fig. 2 . Twenty percent of visitors were from outside Kyoto Prefecture, and 1% of all visitors were foreigners.

We constructed a temporal network from GPS data and analyzed the movement of people. Figure 3 shows the research flowa, and the details are as follows.

• Sort GPS data by the terminal measured. • Transfer connections formed from the same terminal GPS data, and an array C is created by sorting them in descending order of the departure time. • Calculate sets of optimal paths to the destination p t with the pCSA. • Analyze the resulting set. To use the pCSA, GPS data are converted into transfer connections as described above. In this study, we divided the study area into 50-m square meshes and formed transfer connections between the meshes.

From these transfer connections, the pCSA is used to calculate the optimal path to the destination. The pCSA provides sets of optimized paths to the input p t .

For analysis, we compared the travel time by seasons and time zones by creating a probability density function of the travel time to the destination. This will be discussed in detail in the next section.

The TDTSP from GPS data was used to calculate the shortest path. Figure 3 shows the research flow, and the details are as follows.

• Calculate the optimal path from the GPS data in the same way as described above. • From the obtained sets of optimal paths, determine the travel cost and TDTSP. • Meta-heuristics explore paths with low travel costs around specified points. With the pCSA, we find the optimal sets of paths to move the edges in the network. Afterward, we need to determine the time weight W of the dynamic graph G.

We now consider how to determine the time weight w(v i , v j , τ ) from node v i to v j . We use the pCSA with v j as input, and divide the sets of optimal paths obtained by dividing the sets by time τ ∈ T . Considering real-world scenarios, w(v i , v j , τ ) should be close to the cost of moving directly from v i to v j in that period. Since there are many paths with long travel times formed by connecting intermediate points using the pCSA, we adopt the shortest travel time in the lower probability 5% of subgroups as w(v i , v j , τ ) in this study.

The search for the solution of the TDTSP is calculated on the basis of Eqs. The flow remains the same until the GPS data are preprocessed and the optimal set of paths is formed using the pCSA. In the movement analysis using temporal networks, a set of optimal paths is visualized in a form that can be analyzed. In travel route search using meta-heuristics, a set of optimal paths is used to determine the TDTSP.

frame represent points used in the temporal network movement analysis. Movement from Hyakumanben to Kyoto Station and movement from Ennmachi to Kyoto Station are compared and analyzed. The points surrounded by blue frames represent points taken as nodes for the TDTSP. We explain the case study in detail.

A. Movement analysis with temporal network 1) Analysis by meantime of movement: We obtained sets of optimal paths from the GPS data using the pCSA. From the sets of paths, we can obtain the travel time to the destination for each hour. Here, the travel time includes the waiting time until the next path. For example, at time t 0 , if the next path to the destination has a departure time of t 1 and an arrival time of t 2 , the travel time is t 2 − t 1 plus the time spent waiting for the path t 1 − t 0 , t 2 − t 1 + (t 1 − t 0 ) = t 2 − t 0 . Figure 5 shows the average travel time from Hyakumanben to Kyoto Station in February and April. The locations of Hyakumanben and Kyoto Station are shown in Fig. 4 . They are 6.1 km apart by road, so it is expected that it takes approximately 20 min to get there by car. The average travel time in this study is the monthly average of the hourly travel time for each day. Since it takes only approximately 30 min to get from Hyakumanben to Kyoto Station by bus, any trip that takes more than 120 min is excluded as an outlier. The travel time in the morning is shorter in April, and the travel time is almost the same from around 14:00 onwards. Table  I shows that more people are traveling in April, which is counter-intuitive to this result. However, this result includes the waiting time of the movement. If only a small amount of movement data is measured, the waiting time will be much longer. Although the method for evaluating travel time including waiting time is also effective for evaluating public transportation and other transportation with a predetermined timetable, there is a concern that the results will deviate from reality in this research. Therefore, we will consider an analysis method that is not affected by the waiting time.

2) Analysis using the probability density function of travel time: As a case study, we conducted a comparative analysis of the travel time from the Hyakumanben intersection and Ennmachi intersection to Kyoto Station. The locations of the points are shown in Fig. 4 . The distance from Ennmachi to Kyoto Station is 5.9 km by road, which is almost the same as the distance from Hyakumanben to Kyoto Station. However, the trip from Ennmachi to Kyoto Station can be approximately 10 min by train from Ennmachi Station, 150 m away.

We can obtain the optimal set of paths to our destination using the pCSA with GPS data. If we use the pCSA with Kyoto Station as the destination, we can obtain the optimal set of paths from the Hyakumanben intersection and Ennmachi intersection. A comparative analysis method is used to extract subgroups from the sets that match conditions and compare the density functions of the travel time of the paths included in the subgroups to analyze the trend of absolute travel time without waiting time. Figure 6 shows the travel time from Hyakumanben to Kyoto Station, and Fig. 7 shows the travel time from Ennmachi to Kyoto Station. The density functions are measured for (a) February and April, for (b) Kyoto citizens and visitors, for (c) weekdays and weekends, and for (d) departure times between 8:00 and 13:00 and between 13:00 and 18:00.

In 6(a) and 7(a), we compare the probability density functions of the travel time in February and April. Figure 6 shows that the peak of the probability density function is formed at a shorter distance in February. Compared to that in Fig. 5 , which shows the same comparison in the same interval, the overall travel time was longer in February. In other words, in visitors. Comparing the conditions in (b) of Fig. 6 and Fig. 7 , there are three major characteristics.

• Both tend to move quickly because of visitor residence. • The movement from Hyakumanben and residents from Ennmachi form a peak at a much longer time than expected for travel by a passenger car or public transportation. • The density of visitor movement from Ennmachi peaked at a place with a shorter travel time than others.

Focusing on the density function of the movement from Hyakumanben, both the movement of residents and that of visitors form a peak when the time exceeds 60 min. It takes approximately 20 min to reach Kyoto Station by car from Hyakumanben and approximately 30 min by public transportation, which is considerably longer than the results. In this study, since the routes are calculated using the pCSA with GPS data, the following factors should be considered in addition to traffic congestion and other events that lengthen the travel time.

• the lag between the start and end of a movement and the time a smartphone measures location information. • waiting time, and • impacts of detoured or heavily connected travel formed using the pCSA.

Particular attention should be paid to the impact of longdistance or heavily connected movements. For trips with long distances or from places where few people head directly to the destination, the set of optimal paths includes paths formed by connecting many short paths and detouring paths. These effects are thought to have formed a peak with a travel time longer than the actualtravel time. In contrast, the density of travel for visitors from Ennmachi peaks at a short distance, which is thought to be because it is not affected by detouring paths and paths with many connections. Considering the major difference between travel from Hyakumanben and travel from Ennmachi, there is the fact that visitors can travel from the nearest station in Ennmachi to Kyoto Station on the same train line. Since most of the visitors traveled by train, we can assume that the peak travel time is approximately 20 min. According to the timetable, it takes 7-11 min to travel from Ennmachi Station to Kyoto Station, but it is thought that the peak is formed by a discrepancy of a few minutes because of the lag until the location information is measured by a smartphone in transit and the effect of waiting time.

Next, in (c), we compared the density function created from the weekday data with the one created from the weekend data. The travel time from Hyakumanben tended to be shorter on weekends. When we analyzed travel from Ennmachi to Kyoto Station, we found that a travel time of approximately 20 min, when the peak of visitors seen in (b) was formed, is more frequent on weekdays. It can be inferred that visitors who use this route are mainly business or commuters rather than tourists. In addition, (a) shows that there is the same level of travel time of approximately 20 min in February and April, which confirms this assumption. In (d), we created a figure for the movements that departed between the hours of 8:00 -13:00 and 13:--18:00. From Fig.  1 , we know that the movement of people becomes active at 8:00. Both the movements Hyakumanben and from Ennmachi were found to be shorter from 13:00 to 18:00. When we focus on the movement from Hyakumanben, we find that the weekday movement of residents from (b) and (c) tends to become longer. In other words, the movement in this section is influenced by the morning commute to work and school, as well as daily life and business activities. If we focus on travel from Ennmachi, the travel time of approximately 20 min is more common between 13:00 and 18:00. In other words, it can be inferred that the train travel by visitors seen in (b) is the result of visitors on business using the train on their way home.

Thus, travel analysis using temporal networks allowed us to compare travel times under various conditions. Because of the complexity of road networks and changes in conditions depending on the time zone, it is becoming more difficult to evaluate urban road traffic. Therefore, it is desirable to conduct traffic evaluations such as the one demonstrated in this study under various conditions and to use a method that clarifies the characteristics of traffic in each city or section.

B. Explore the shortest travel route 1) Creating the TDTSP: In this case study, we set up the TDTSP to visit seven locations in Kyoto City and derived the shortest path.

The seven locations of the nodes are shown in Fig. 4 :

Nijyojyo, and v 6 is Yasakajinjya. Starting from v 0 at 8:00, weights are updated every 120 min.

We used the pCSA with each node as an input to obtain Pareto-optimal sets of paths. Afterward, subgroups of travel time are created for each time τ , and the shorter 5% of all transfers was assigned time weight W . This is done so that the sets of Pareto-optimal paths would not be affected by the detours created by the pCSA or by the waiting time included in GPS data. The weights are listed in Table II . The array shows, from front to back, the weights for 8:00 -10:00, 10:00 -12:00, 12:00 -14:00, 14:00 -16:00, and 16:00 -18:00.

For example, it takes approximately 25 min to get from v 0 to v 1 by car if there is no traffic congestion along the way. According to Table II , the smallest weight is 28 min, which is close to the travel time when there is no traffic congestion. In this case study, we assumed that the travel route between nodes is direct without any detours. Therefore, if we take the shorter 5%, we can set time weights close to the assumption.

We checked the number of people staying at each point for each time τ from the GPS and calculated the degree of congestion according to Eq. (6). The calculation results are shown in Table III. 2) Route search based on time spent: We have set up the TDTSP that travels around Kyoto City, but in reality, people often stay at each node. Therefore, we calculate the travel time by varying the time spent at each node. In a static network, the shortest path does not change even if the time spent is taken into account, but in a temporal network, the shortest path may change if the time spent changes.

The maximum stay time is as shown in Table IV , and we obtain the shortest route in each case by varying the multiplier of the stay time.

We run ACO with 100 agents and 200 iterations to find the shortest path; the obtained results are shown in Table V . The route changed when the magnification changed from 0.1 to 0.15, and it remained the same from there. One of the major reasons for this change seems to be that if we take the [v 0 →v 4 →v 5 →v 2 →v 1 →v 3 →v 6 →v 0 ] route when the spent time is short, we have to use v 1 →v 3 when the travel cost of this is 73 min. In this way, it is possible to obtain sets of Pareto-optimal paths from GPS data, define the TDTSP from the sets, and v 0 →v 4 →v 5 →v 1 →v 2 →v 3 →v 6 →v 0 0.05 v 0 →v 4 →v 5 →v 1 →v 2 →v 3 →v 6 →v 0 0.1 v 0 →v 6 →v 4 →v 5 →v 2 →v 1 →v 3 →v 0 0.15 v 0 →v 4 →v 5 →v 2 →v 1 →v 3 →v 6 →v 0 0.2 v 0 →v 4 →v 5 →v 2 →v 1 →v 3 →v 6 →v 0 0.4 v 0 →v 4 →v 5 →v 2 →v 1 →v 3 →v 6 →v 0 0.6 v 0 →v 4 →v 5 →v 2 →v 1 →v 3 →v 6 →v 0 0.8 v 0 →v 4 →v 5 →v 2 →v 1 →v 3 →v 6 →v 0 1.0 v 0 →v 4 →v 5 →v 2 →v 1 →v 3 →v 6 →v 0 prevent travel along a particular segment. Therefore, as the next case study, we consider the case where the time weights of specific edges connecting v 0 to v 6 are extremely increased. Although this is an extreme case, we will analyze how the travel route changes when the time weights Table  IV , we doubled the time weight for each node and performed ACO with 100 agents and 200 iterations to find the shortest path. The obtained results are shown in Table VI . 

and the shortest route.

Route v 0 v 0 →v 4 →v 5 →v 2 →v 1 →v 3 →v 6 →v 0 v 1 v 0 →v 4 →v 5 →v 2 →v 1 →v 3 →v 6 →v 0 v 2 v 0 →v 4 →v 5 →v 2 →v 1 →v 3 →v 6 →v 0 v 3 v 0 →v 6 →v 3 →v 1 →v 2 →v 5 →v 4 →v 0 v 4 v 0 →v 4 →v 5 →v 2 →v 1 →v 3 →v 6 →v 0 v 5 v 0 →v 4 →v 5 →v 2 →v 1 →v 3 →v 6 →v 0 v 6 v 0 →v 4 →v 5 →v 2 →v 1 →v 3 →v 6 →v 0 Table VI shows that, the travel route change only when the time weight w(v 3 , v j , τ ), w(v j v 3 , τ )(v j ∈ V, τ ∈ T ) of the edge connected to v 3 is doubled, otherwise the route remains the same as when some timea were set in Table V . This is because the original route moves from v 1 to v 3 , however, the changed route moves from v 3 to v 1 , and as shown Table II , the travel time can be reduced by choosing the right time to travel.

In this way, we found that a user can change the TDTSP arbitrarily. For example, when deciding on a sightseeing route, people may want to avoid visiting a certain zone at a certain time zone because of congestion. By maximizing the time weights, it would be possible to select a route that avoids congestion. In addition to the assumption of tourist routes, various restrictions and conditions are assumed in transportation planning and route recommendation. Since this research uses GPS data, it is expected that the nodes and conditions of the TDTSP can be tailored to a user's preferred form.

VI. CONCLUSION In this study, we built a temporal network using GPS data to evaluate the movement of people and to find the shortest route. We improved an existing method of creating a network for public transportation and created a network using GPS data obtained from smartphones. To apply the existing method to GPS data, we divided the map into 50-m square meshes and created a timetable of transitions between the meshes. We can evaluate real events such as travel by nonpublic transportation and delays in transportation using real data. For the visualization and evaluation of the network, we took the average travel time and created a probability density function of the travel time to compare travel by seasons and time zones.

We made an original contribution to the method for setting the TDTSP and calculation in the solution method to search for the shortest path. The weights of the TDTSP are determined from the sets of Pareto-optimal paths used to create the temporal network. The congestion measured from the GDP was used to calculate the transition probability in the ACO method used for solving the TDTSP. With the recent development of information terminals, GPS data can be obtained more easily, so we can change the nodes of transportation networks to be patrolled and extend our method to other cities.

The following are possible future extensions.

• formulation and post implementation evaluation of transportation plans • application to vehicle routing problems, and • extension to the TDTSP with time frames Because of the complexity of the study city, it is difficult to understand issues in transportation planning, but the temporal network obtained from GPS can clarify the mobility issues. The method for finding the shortest path problem can be extended to vehicle routing problems. In addition, we set the congestion level in the calculation of the ACO method, and it can be used to set a time frame such that if the congestion level exceeds a certain height, travel to that point is restricted. This is because not only is traffic congestion during travel a problem, but so is the concentration of people at a destination. In addition, there is a growing demand to avoid crowds as a countermeasure to the recent outbreak of COVID-19 infections, and the system (i.e., our methods) can be expected to be expanded to address this.

The sustainable mobility paradigm

The challenge of overtourism

Overtourism: a growing global problem

Over-tourism and the fall of venice as a destination

Traffic-known urban vehicular route prediction based on partial mobility patterns

Design and implementation of an intelligent system for tourist routes recommendation based on hadoop

Network science

Theory and applications of complex networks: Advances and challenges

Temporal networks

Entropy of dialogues creates coherent structures in e-mail traffic

Impact of human activity patterns on the dynamics of information diffusion

On the dynamics of human proximity for data diffusion in ad-hoc networks

Impact of nonpoissonian activity patterns on spreading processes

Tracking information epidemics in blogspace

On the bursty evolution of blogspace

Why we twitter: understanding microblogging usage and communities

What is twitter, a social network or a news media

Social network analysis: Methods and applications

Reality mining: sensing complex social systems

Close encounters in a pediatric ward: measuring face-to-face proximity and mixing patterns with wearable sensors

Highresolution measurements of face-to-face contact patterns in a primary school

Toward the dynamic interactome: it's about time

Inferring dynamic bayesian network with low order independencies

Statistical inference of the time-varying structure of gene-regulation networks

Inferring time-varying network topologies from gene expression data

Travel times and transfers in public transport: Comprehensive accessibility analysis based on pareto-optimal journeys

Ant colony optimization: overview and recent advances

An improved ant colony algorithm for the time-dependent vehicle routing problem

An improved ant colony algorithm for solving time-dependent road network path planning problem

Pheromone modification strategy for the dynamic travelling salesman problem with weight changes

Ant colony optimization with local search for dynamic traveling salesman problems

Ant colony optimization