Strategic Route Planning to Manage Transit’s Susceptibility to Disease Transmission

Abstract

Transit agencies have experienced dramatic changes in service and ridership because of the COVID-19 pandemic. As communities transition to a new normal, strategic measures are needed to support continuing disease suppression efforts. This research provides actionable results to transit agencies in the form of improved transit routes. A multi-objective heuristic optimization framework employing the non-dominated sorting genetic algorithm II algorithm generates multiple route solutions that allow transit agencies to balance the utility of service to riders against the susceptibility of routes to enabling the spread of disease in a community. This research uses origin–destination data from a sample population to assess the utility of routes to potential riders, allows vehicle capacity constraints to be varied to support social distancing efforts, and evaluates the resulting transit encounter network produced from the simulated use of transit as a proxy for the susceptibility of a transit system to facilitating the transmission of disease among its riders. A case study of transit at Oregon State University is presented with multiple transit network solutions evaluated and the resulting encounter networks investigated. The improved transit network solution with the closest number of riders (1.2% more than baseline) provides a 10.7% reduction of encounter network edges.

Transit agencies have experienced dramatic changes in service and ridership because of the COVID-19 pandemic. Current mitigation actions are primarily operational, but as communities transition to a new normal, strategic measures are needed to support continuing disease suppression efforts. Strategic measures that are to be implemented in the pursuit of disease mitigation need to balance potentially competing interests like efficiency, effectivity, and privacy.

Prior research examined the potential for a better understanding of disease transmission among transit riders. This research expands that analysis to provide actionable results to transit agencies in the form of improved transit routes. A multi-objective heuristic optimization framework employing the non-dominated sorting genetic algorithm II (NSGA-II) generates multiple route solutions to planners. The route solutions allow transit agencies to balance the utility of service to riders against the susceptibility of routes to enabling the spread of disease. Where other research focuses primarily on individual riders, the route solutions generated by the proposed multi-objective heuristic optimization framework facilitate the disease mitigation goals of a transit agency while not taking actions against any rider on an individual basis. A case study of transit at Oregon State University (OSU) is presented with multiple transit network solutions evaluated and the resulting encounter networks investigated.

Background

This research draws from two distinct and well-explored areas: the Urban Transit Routing Problem (UTRP) and the network modeling of disease transmission. The intersection between these two areas occurs when the individuals served by a UTRP solution represent nodes in a network model of disease transmission. By using metrics derived from the disease transmission network model as an objective in a UTRP, the two representations, one of the transit network and the other of the disease transmission network, evolve to provide a feasible UTRP solution that delivers a network model of disease transmission favorable to mitigating the spread of disease through transit.

Urban Transit Routing Problem

Fundamentally, the UTRP aims at improving transit routes for a defined objective or a set of objectives. However, the UTRP manifests in various forms. In addition to route improvement, for example, some approaches focus on stops, service schedule, and vehicle outputs, among other associated decisions. A UTRP can be either single- or multi-objective, with metrics contributing to the perspective of riders, operators, or both.

In 2008, Guihaire and Hao ( 1 ) published a review paper that synthesized prior work addressing the UTRP dating back to 1925. In this work, the authors attribute the first use of evolutionary optimization (e.g., a genetic algorithm) to Xiong and Schneider ( 2 ). Approaches have evolved since Xiong and Schneider’s work, but the fundamental aim of improving a transit network for economic efficiency has remained consistent.

Some UTRPs do not even consider route improvements. Mahmoudzadeh and Wang ( 3 ) developed a cluster-based scheduling approach to improve the alignment of a university shuttle service with travel behaviors and class times. Using automated passenger counter and automatic vehicle location data from a campus shuttle service, they selected months during which travel patterns appeared consistent (e.g., middle of a term at the university), and used both supervised and unsupervised clustering methods to assess different approaches to schedule departure times to improve efficiency. Mahmoudzadeh and Wang’s entire work achieved its goal without a single change to the physical route.

The UTRP can be adapted to model the characteristics of a specific real-world problem. For example, a variant of the UTRP known as the School Bus Routing Problem (SBRP) manifests similar characteristics to the problem addressed with the multi-objective heuristic optimization framework proposed in this research. More specifically, both problems have riders with known origins and destinations, time constraints for when those riders are to be transported, a fixed number of available vehicles, and flexibility in stop location assignment.

School Bus Routing Problem

An application of the SBRP that gathered significant coverage in the general media ( 4 – 6 ) involved the bus network of the Boston Public Schools ( 7 ). The authors introduced another variation of the UTRP called bio-objective routing decomposition (BiRD) to model and obtain feasible solutions to the bus time selection problem. Breaking optimization problems into sub-problems to be optimized, recognizing the different issues faced at each stage, is not unique to BiRD.

Lemos et al. ( 8 ) explored the effect of different heuristic optimization methods (i.e., ant colony, honey bee, and greedy randomized optimizations) when finding feasible solutions to the SBRP. The results showed no heuristic optimization approach to be dominant, which suggests that situational interests (e.g., number of buses, distance traveled, etc.) drive which approach is best suited. Although this outcome does not lead to any specific heuristic being selected for this research, it suggests that multiple heuristics are capable of providing feasible solutions.

In another study, Leksakul et al. ( 9 ) used machine learning and evolutionary optimization to plan bus stops and routes for a factory shuttle, which is, effectively, an SBRP. The proposed approach reduced employees’ walking distance to bus stops by 79%. Again, breaking a problem of stop identification and route determination into sub-problems to employ appropriate optimization methods (be they heuristic, a machine learning method, integer optimization, etc.) proves an effective approach to solving the greater problem.

The breadth of approaches to find optimal solutions to the UTRP is evident in research performed for various areas of focus within transportation. Rider choice is not always addressed with a UTRP, but Liu et al. ( 10 ) employed data from taxi and bus trips in Beijing, China, in a three-phase approach to predict bus route demand and optimize route planning to suit rider demands. Although Liu et al. used origin–destination (O-D) data in a manner that is typical of SBRP research, they recognized that riders have a mode choice and used that recognition to employ an objective that aimed at maximizing the number of riders that choose mass transit.

Network Analysis of Disease Transmission

The disease network needed for this research differs from how disease networks are often constructed. Disease networks that show a temporal quality, where most research is focused, adopt either a susceptible–infectious–recovered (SIR) or susceptible–infectious–susceptible (SIS) network model depending on the disease of focus ( 11 ). SIR and SIS network models have nodes that evolve their state based on their stage in the epidemic. These network models have temporal qualities that are useful when studying how epidemics spread. For this research, rather than investigating how a disease spreads and affects the state of a node, the focus is on minimizing the metrics of a cumulative encounter network so that disease has little opportunity to spread.

Encounter networks exist to represent an interaction between nodes. Some are temporally evolving, like those used in SIR and SIS disease network models. Others are fixed at a time point of interest, like those looking back at a past period of contacts ( 12 ). Knowledge about what constitutes an encounter for the intended use of the encounter network dictates when an edge is to be created between nodes and what attributes those edges may hold. In addressing disease transmission within an encounter network, the results are invariably driven by decisions made about the generation of the encounter network.

The cumulative encounter network does not evolve with time, for it represents all encounters as if they have already occurred. By recognizing how a disease is allowed to spread in an encounter network, transit can be designed to produce a resulting encounter network that minimizes transit’s contribution to the spread of disease. The difference between those with interest in a cumulative encounter network and an evolving encounter network is described thus by Keeling and Eames ( 11 ): “the research in graph theory and social sciences generally considers an understanding of the network itself to be the ultimate goal; in contrast, epidemiological interest is focused on the spread of the disease, in which case the network forms a constraining background to the transmission dynamics.” While the focus of the multi-objective heuristic optimization framework presented in the following sections is on the epidemiological spread, understanding the disease network is more aligned with other fields.

Regardless of the approach, the goal is to reduce the spread of disease. Xu et al. ( 13 ) modeled a hub-based transportation system to investigate the effects of mitigating the spread of disease and concluded that reducing the likelihood of infected travelers using transit is not sufficient to stop an outbreak. Instead, reducing an outbreak can be achieved by increasing system efficiency (i.e., reducing contact between travelers) or reducing overall travel by the population. While approaches that target individuals may serve to limit the spread of disease effectively ( 14 – 16 ), the implications from both a privacy and a civil liberties perspective are concerning. Therefore, strategic and systemic measures that do not target individuals should be considered to limit the spread of disease within transit.

Disease Transmission in Transit

Reducing the spread of disease in pandemic environments requires multi-faceted approaches. “What Bus Transit Operators Need to Know about COVID-19” ( 17 ) is a resource for transit organizations to address their needs during pandemics for minimizing the overall effects of infectious diseases. The report intentionally does not give prescriptive measures for transit agencies to take but rather outlines the areas transit agencies should focus on to prepare for the impacts of a pandemic. The interventions and actions suggested are largely tactical and operational and reflect the immediate requirements of transit agencies to protect riders, workers, and their community.

Identifying the operational risks is one strategy for minimizing the spread of disease. Goscé and Johansson ( 18 ) showed a neighborhood-level correlation between the amount of time spent in enclosed stations by residents and the rates of influenza-like illness in the neighborhood. Bóta et al. ( 19 ) proposed a three-stage approach to detect components (e.g., stops and trips) of a public transit system most contributing to the spread of disease with a follow-up proposing a more efficient approach ( 20 ). The commonality between these two studies is the recommendation to increase surveillance and mitigation measures on the vehicle trips identified as most likely to spread disease ( 19 , 20 ). All three studies identify the link between specific places in transit (stations in [18] and vehicle trips in [ 19 , 20 ]) and the spread of disease; however, other than operational surveillance, they do not address strategic changes to reduce the existence of problematic places.

Rather than identify problematic places in transit, Shoghri et al. ( 21 ) identified problematic patterns of people. Simulating various kinds of passengers, primarily belonging to the groups “returners” and “explorers,” the impacts of different passenger qualities on the spread of disease were assessed. The most significant contribution to the spread of disease came from “large distance returners,” and the smallest contribution was from “small distance returners.” These results led the researchers to conclude that the latter group could be excluded from containment measures. This study is an example where the changes proposed to the transit system are not merely operational but would force the targeting of individuals and assign risk to their actions. Perhaps a redesign of transit to not enable problematic passenger patterns would serve to address their existence without specifically targeting individuals strategically, but such changes are not mentioned.

Perhaps the most comprehensive work on the spread of disease, and timely as it focuses on the specific epidemiological characteristics of COVID-19, was authored by Mo et al. ( 22 ) in which a susceptible–exposed–infectious–recovered–susceptible (SEIRS) disease model was used. The SEIRS disease model introduced both a “novel theoretical solving framework for the epidemic dynamics with time-varying and heterogeneous network structure,” allowing population-size analysis with what is characterized as “low computational costs,” and an evaluation of both public health and transportation policies that affect the spread of disease. Control policies evaluated include adjusting parameters that proxy individual and medical provider behavior, varying trip occurrence rate, changing the distribution of individual passenger departure times, closing bus routes (employing a variety of route selection strategies), limiting maximum passenger load in vehicles, and isolating specific individuals identified as likely to have a high impact on the spread of disease. Researchers concluded that “[t]he most effective approach is isolating influential passengers at the early stage.” Strategic changes investigated did not show the same effectiveness as targeting individuals. Perhaps individual targeting will prove to be most effective, but until all non-individualized options are assessed, it is premature to sacrifice the societal cost of individualized measures.

Proposed Framework to Generate Transit Route Options

The framework introduced in this research serves to ingest O-D mobility data and use it to present feasible route solutions to transit planners that balance the two objectives of (a) maximizing the number of observed trips served by transit, while (b) minimizing the susceptibility of transit to spreading disease. The framework uses a multi-objective UTRP heuristic optimization with an encounter network metric as one of the objectives. Every candidate solution represents the existence of two interconnected networks. The first is the transit network that defines the candidate solution, and the second is an encounter network generated from the simulation of trip mode choice using the candidate transit network.

Figure 1 depicts the main stages of the framework, which begins with the processing of WiFi session data. The inferred trips define the geographic area for which a navigable network must be generated. The navigable network defines potential stops that constitute the decision vector’s values that the evolutionary optimization evolves. The objective calculation sits outside the evolutionary optimization process, and when called to evaluate the fitness of a decision vector, employs the inferred trips and navigable network to assess objective values. The output is the improved routes once the stopping criterion, a defined number of generations without change to the cumulative Pareto front, is met.

Figure 1.

Main stages of the multi-objective heuristic optimization framework.

Data Collection and Generation

Two data sources are used as the main inputs. The first data source consists of WiFi user sessions covering the area of interest. The WiFi user session data is used to infer trips that occur between locations within the area of interest. The second data source is a network representation of navigable paths. The scope of the network is defined once the scope of mobility in the WiFi user session data is known. Therefore, the WiFi user session data must be prepared first before any subsequent steps. The two datasets interface later in the framework to assess if an inferred trip occurs faster over the network by foot or by using a candidate solution transit route.

Trip Inference

Trip inference occurs by identifying when WiFi user sessions established by personal wireless devices (PWDs) are logged as ending in one building and WiFi user sessions are logged as starting in another. The data logged for each WiFi user session are shown in Table 1. All recorded WiFi user sessions during the period of analysis are used. In establishing which WiFi user session pairs constitute trips between locations, considered factors include session duration (including prior, current, and subsequent sessions), distance between WiFi user session access points (APs), and temporal order of WiFi user sessions. Every PWD is assumed to represent an individual, so a single individual with multiple PWDs establishing and terminating WiFi user sessions would be analyzed as multiple people. Future work may better address both individuals with multiple PWDs and those without any PWD.

Table 1.

Relevant Fields of the WiFi User Session Data

Field name	Data type	Description
MacPIN	String	Anonymized representation of the MAC address of a personal wireless device (PWD).
SessionStart_Epoch	Unix timestamp	Date and time a PWD initiated a connection with an access point (AP).
SessionEnd_Epoch	Unix timestamp	Date and time a PWD terminated a connection with an AP.
AP_Mac	String	MAC address of AP network back haul.
BuildingCode	String	Building abbreviation where AP is located on campus.

Road Network Generation

Road network data was generated from OpenSteetMap data using the OSMnx package ( 23 ). A spatial envelope slightly larger than the area that contained the locations of WiFi user sessions was used to limit the size of the road network. To best represent the roads available to transit, the OSMnx network designation of ’drive_service’ was used, providing all drivable streets as edges with all intersections as nodes.

Every node in the road network is considered a potential stop node and potential stop nodes are assigned index values. Figure 2 illustrates the procedure to assign index values to potential stop nodes. The solid black line, which moves from the southwest to the northeast corner of the road network, facilitates searching nearby potential stop nodes represented by the orange circles. Potential stop nodes are assigned an incremental index value as they are intersected by the moving black line with Figure 2 showing example values.

Figure 2.

Process to assign indices to road network nodes.

Evolutionary Optimization

Finding feasible solutions for UTRP-like problems using evolutionary optimization heuristics is an area well explored in recent research ( 1 , 8 , 24 –28).

The parallel optimization library used for the island model evolutionary optimization of this framework was pygmo. pygmo is based on the C++ library PaGMO for parallel optimization, which uses an asynchronous island model ( 29 ). The pygmo library was developed by a team at the European Space Agency to facilitate high-dimension global optimization problems for spacecraft trajectories and part design. Yet, the universality of the approach and the available algorithms make it easily employed in other global optimization problems.

NSGA-II and Island Model Parallel Optimization

The parallelization of the multi-objective evolutionary algorithm (MOEA) known as NSGA-II ( 30 ) is implemented in pygmo through the use of an approach known as the island model ( 31 ). In the island model, multiple parallel optimizations are run (i.e., the islands), and candidate solutions are shared between the islands through a defined graph topology (i.e., the archipelago). Each candidate solution within an island is referred to as an islander, with the solution’s values being the islander’s decision vector. Using the parallelization that pygmo facilitates, the optimization can scale an archipelago to utilize all available cluster resources while still operating within the constraints of any single island process. The latter is done by limiting the size of an island’s optimization to be within the available node resources. While many multi-objective heuristic optimization algorithms exist, NSGA-II was selected for its prevalence as a benchmark against which other multi-objective heuristic optimization algorithms are measured. Future work could investigate other algorithms and parallelization approaches, but such is not the focus of this work.

Heuristic Optimization Objectives

Balancing the needs of providing transit to a population against the aim of minimizing the spread of disease is the purpose of this work. To accomplish both, quantifiable objectives are defined. Maximizing the provision of transit is measured by simulating potential rider mode choice using inferred trips and the candidate transit network and counting the number of trips served by the candidate transit network, as shown in Equation 1. Minimizing the spread of disease is accomplished by minimizing the number of encounters in shared spaces resulting from transit use (i.e., minimizing the number of edges in the encounter network), as shown in Equation 2. Table 2 outlines the notation employed in the objectives.

Table 2.

Heuristic Optimization Objectives Notation

Notation	Meaning
$G$	Encounter network
$E (G)$	Edge count of $G$
$s$	Inferred trip
$S$	Set of inferred trips
$m_{s}$	Mode of trip $s$

Maximize : \sum_{s \in S} [m_{s} \neq ” walking ”]

(1)

Minimize : E (G)

(2)

Rider Mode Choice Simulation

The first step in calculating the objective metric is to take the routes defined in the islander’s decision vector and assign all the trips in the dataset to either a transit route or to walking. Trips are assigned to either the transit route that takes the least amount of time or exclusively walking. Trip assignments that involve a transfer between routes are not considered. An example is shown in Figure 3, where the trip would be assigned to use Route A. If Route A were not an option, the trip would walk rather than taking the longer Route B. The process of assigning trips to the fastest option occurs for every trip in the dataset.

Figure 3.

Assessing trip timelines.

Maximizing the count of trips assigned to a transit route as the fastest option is the first objective.

Transit Encounter Network

Once trip assignments are made, an encounter network of transit users can be generated. Using the original departure time (i.e., the end time of a WiFi user session), timestamps are generated from the simulation for (a) the duration of the walk to the origin transit stop, (b) the duration of the wait at the origin transit stop, and (c) the duration of the ride in the transit vehicle. From the timestamps and the associated stops and vehicle for all trips using transit, an encounter network is generated from all trips whose timestamps establish a shared presence at either a transit stop or a vehicle. A visualization of a portion of the encounter network is shown in Figure 4, with each node being a user and an edge indicating an encounter occurred.

Figure 4.

Encounter network sample.

Remaining generalized in the assumptions about disease transmission, any shared presence at a transit stop or in a transit vehicle is considered an encounter. By defining the objective as the minimization of edges in the encounter network, fewer opportunities exist in those environments for direct transmission of disease. Future work could be more tailored to the transmission properties of a specific disease or could expand the encounter analysis beyond waiting at the origin transit stop or sharing a transit vehicle.

Limitations of Selected Approach

Worth recognizing, in addition to the above decision justification, are the limitations inherent in this work. Most prominent is the source of O-D trip data. Using WiFi user session data as the source of O-D trip data presents a large sample size but also a sample limited to those associated with the source network. In environments like universities or large corporate campuses where many within the area of interest are associated with the organization and carry with them devices that associate to the organization’s network, this presents a low-investment approach to highly detailed mobility data. In other environments where many within the area would not establish an association with the prevailing WiFi network, using WiFi user session data would not provide a useful capture of mobility. As the heuristic optimization only relies on trips existing within the area of interest, other means of trip generation can be used when WiFi user session data is not well suited. For example, Bóta et al. ( 19 ) took one day’s a.m. peak trips dataset and repeated it four times to generate a representative a.m. peak trips for a workweek.

Next to consider is the use of a disease network model. While standard disease network models like SIS, SIR, and SEIRS can be used in agent-based modeling (or a simplification thereof as done in Mo et al. [22]), doing so requires both significant computational resources and disease-specific knowledge. By simply minimizing the number of direct encounters transit users experience (while some assumptions about latent infectiousness of a place are made), other assumptions about the spread of disease are avoided, and a high-caution approach is taken (e.g., no minimum for the duration of contact and the assumption that an encounter occurs every time a space is shared). The edge count of an encounter network is less computationally intensive than an agent-based simulation using the same encounter network.

Lastly, only encounters while using transit in the area of focus are considered. This is less of an issue for this research than for work where agent-based modeling is used ( 19 , 20 , 22 ) as no assumption of disease status is made about parties to an encounter. Mo et al. ( 22 ) try to address the shortcoming of outside-of-transit interactions for an agent-based model by considering shared origins and destinations but require significant assumptions to be made. The downside of using the edge count of an encounter network is that encounters that may have been perfectly safe (e.g., between two susceptible but not infectious individuals) are treated the same as an encounter where disease could spread (e.g., between a susceptible individual and an infectious individual). This downside may needlessly limit encounters that would not have contributed to the spread of disease.

Case Study Results

A case study was conducted with WiFi user session data collected during the fall 2017 quarter at OSU. A workweek was chosen with the most inferred trips to demonstrate the application of the proposed multi-objective heuristic optimization framework under the campus’s busiest state. The busiest five consecutive weekdays in the dataset were Monday, October 9, 2017 to Friday, October 13, 2017. On Saturday, October 14, 2017, there was a home football game, which may explain an increased level of campus activity on the days leading up to the game. The week is also roughly the middle of the fall 2017 quarter, with mid-term preparations contributing to campus activity. During the busiest five consecutive weekdays, 79,879 trips were inferred.

Characteristics of Inferred Trips

The trips inferred for the week of interest have patterns that could be expected of a university campus. Figure 5a shows the distribution of the day-of-week in which the inferred trips occurred. The Thursday peak is not regularly witnessed in other weeks, and it could possibly be attributed to football game-related activities; the Friday level is also atypical as other weeks will have reduced activity on Fridays. Both discrepancies suggest this week is not representative of a typical workweek, but that does not impede the utility of testing the multi-objective heuristic optimization framework against the campus’s busiest week. Figure 5b shows the distribution of the trip start times. The peak observed in the morning with the greatest number of trips around 10 a.m. is typical of workweeks at the OSU campus, likely associated with class schedules. The late-night peak increasing from 6 p.m. to 11 p.m. may be associated with coordinated evening activities on campus. Figure 5c shows the observed duration of the inferred trips (i.e., WiFi user session end time in origin building to WiFi user session start time in destination building). The long tail demonstrates a limitation of using WiFi user sessions to infer intra-campus trips. For trips with origins or destinations outside of campus, if the device identifier establishes a new WiFi user session during the same day, it is inferred that an intra-campus trip occurred. To limit the effect of outside-of-campus trips, only trips with an observed duration of 60 min or less are used to calculate objectives.

Figure 5.

Temporal distributions of inferred trips: (a) day-of-week distribution, (b) trip start time distribution, and (c) observed trip durations.

Comparison with Existing Routes

As the proposed multi-objective heuristic optimization aims to improve the routes used by transit, a baseline comparison is made against the routes contemporary to the WiFi user session data. Figure 6 plots the set of non-dominated solutions that constitute the Pareto front alongside the baseline routes subjected to the objective calculations. The baseline routes are dominated by multiple solutions provided by heuristic optimization. The feasible solution with the closest number of riders (1.2% more than baseline) provides a 10.7% reduction of encounter network edges; the feasible solution with the closest number of encounter network edges (0.7% fewer than baseline) provides a 5.8% gain in riders. Figure 7 plots the routes of the feasible solution with the closest number of riders (when compared with the baseline) and the baseline routes onto the road network of the OSU campus for comparison. The gray lines in Figure 7 represent the road network edges with every intersection being a node. Each non-gray line plotted atop the road network is a bus route. The routes produced by the feasible solution appear less centralized than the baseline routes that at some point each operate adjacent to the campus’s football stadium.

Figure 6.

Pareto front comparison with baseline.

Figure 7.

Closest rider count solution comparison with baseline.

Encounter Network Comparison

Assessing the performance of the framework can be done by comparing the encounter network metrics of the baseline existing routes to a non-dominated solution serving a similar number of riders. The two distributions are compared in Figure 8.

Figure 8.

Encounter network distributions: (a) node degrees, and (b) total encounter times.

Figure 8a depicts the distribution of node degrees in the encounter networks. Aside from reducing the number of edges in the encounter network of the feasible solution, the distribution of node degrees also changes. While there are fewer nodes with degree greater than 10, there is an increase in the number of nodes with degree 10 or less. Although there is not necessarily a direct connection between the number of nodes in the encounter network and the number of inferred trips served by transit, the difference between the two distributions suggests minimizing edges in encounter networks while still serving trips is done through the reduction of riders having encounters with many others. This concept is similar to the idea of reducing super-spreaders suggested in other research (14 –16, 22 ).

Figure 8b is the distribution of total contact time between nodes in the encounter networks. Compared with the change in node degree distribution, the difference between the baseline and the feasible solution’s encounter network is stark. Over the analyzed week, the feasible solution’s encounter network almost eliminates cumulative encounters between nodes that last less than 80 s, whereas the baseline encounter network experiences a peak in that area. The change in distribution indicates a shift in cumulative encounters toward riders that are to find each other having more prolonged encounters and edges in the encounter network that are fleeting being all but eliminated.

Comparison with Network Growth Models

The Pareto front in Figure 6 shows growth in encounter network edges as the number of nodes (i.e., riders) increases. Comparing the growth of the Pareto front to known social network models provides an indication of the performance of the proposed multi-objective heuristic optimization framework at minimizing encounter network edges. The selection of the comparative model is dependent on the generalized representation of the environment in which the proposed multi-objective heuristic optimization framework’s encounter network grows. Social contact networks are often scale-free networks ( 15 , 32 ). Since the encounter network of the proposed multi-objective heuristic optimization framework has a fixed number of nodes (i.e., riders), it is possible to further specify a suitable model as a bounded scale-free network ( 15 , 33 ). Figure 9 shows a comparison of the Pareto front, earlier used in Figure 6, to the typical bounds of a social contact scale-free network, where the probability $P$ of node degree $k$ is approximated by a power-law distribution of the form $P (k) ~ k^{- γ}$ . The shaded region between the lines where $γ = 2$ and $γ = 3$ shows where social contact networks that exhibit bounded scale-free network characteristics typically reside. The use of a scale-free network as a comparative model is further supported by the empirical distributions shown in Figure 8a that align with a power-law distribution. Figure 9 shows that below 1500 riders served, the proposed multi-objective heuristic optimization framework returns expected or better than expected levels of performance when measured by the number of encounter network edges. Above 1500 riders, the proposed multi-objective heuristic optimization framework returns more edges than expected of a typical bounded scale-free network.

Figure 9.

Bounded scale-free network growth comparison.

The shift from out-performing to under-performing a bounded scale-free network may be the result of another property of the environment not considered in the bounded scale-free network model, that is, finite encounter spaces. Regardless of size of the encounter network, the number of spaces where an encounter can occur (i.e., an origin bus stop or vehicle) is fixed. When only a relatively low number of riders use transit, the fixed number of encounter spaces is not an impacting constraint. As the number of riders increases, the number of spaces does not, likely forcing an increase in the number of encounters each rider experiences (i.e., the mean degree of nodes increases). A network model addressing the fixed number of encounter spaces could not be identified.

Heuristic Optimization Stopping Criteria

Selecting stopping criteria is central to implementing an MOEA well, and a parallelized MOEA is no exception. Gutierrez et al. ( 34 ) examined stopping criteria for multiple MOEA, including NSGA-II, and developed new stopping criteria that they demonstrated reduced the amount of time needed to achieve comparable results to prior common stopping criteria. Of the three common stopping criteria cited by the authors, only one does not require significant prior knowledge about anticipated results, that is, “stopping when no significant improvement in the quality of the solution set can be obtained by performing further generations.” For this research, the stopping criterion was assessed using a cumulative set of non-dominated solutions. If the cumulative set of non-dominated solutions did not improve for a defined number of generations, then the stopping criterion was met. A chart of the resulting Pareto front from four different stopping criteria is shown in Figure 10. Figure 11 shows the time needed by the heuristic optimization to meet the stopping criterion.

Figure 10.

Pareto front variations with stopping criteria.

Figure 11.

Heuristic optimization duration for stopping criteria.

Changing the stopping criteria by increasing the number of generations needed without a new non-dominated solution results in solutions with additional simulated transit riders but at the cost of a substantial increase in the amount of computational time. Importantly, the solutions of faster stopping criteria are comparable in edge count for a given number of riders. Recognizing that the methods explored in this research would be implemented in environments where there is an interest in minimizing the spread of disease, the solutions with the lower encounter network edge counts are likely of greater interest to planners. While it should be recognized that more computational resources would be necessary for solutions providing higher ridership, the options with a stopping criterion requiring a lower computational time will provide comparable solutions in the areas planners are likely to seek.

Conclusion and Future Work

This research has introduced a multi-objective heuristic optimization framework that provides actionable results to transit agencies to balance the utility of service to riders against the susceptibility of routes to enabling the spread of disease in a community. A case study using empirical WiFi user session data to infer trips on a university campus showed how the proposed framework could be applied. The choice of which route set to implement is ultimately up to the transit planner with the framework allowing for a mix of defined and framework-generated routes to provide additional flexibility.

Multi-objective heuristic optimizations of the UTRP allow for the addition or removal of objectives as desired. This work includes encounter network analysis in the heuristic optimization, which the researchers believe is novel for UTRP. Future work into integrating encounter network objectives into other UTRP landscapes would enable transit agencies to add a disease transmission component to the other objectives they are already pursuing. Other UTRP variables such as improving equipment assignment efficiency or dynamic route schedules are feasible with the existing objective, but require an expansion of the heuristic optimization search space demanding additional computational resources. Additionally, using the encounter network generated in this framework, other encounter network characteristics could be used as objectives such as encounter duration or repeated encounters that may better represent disease susceptibility.

Footnotes

Acknowledgements

The authors would like to thank Béatrice Moissinac, Robin Pappas, Johan Reinalda, Josh Crowl, David Barber, and the rest of OSU’s Information Services for their assistance.

Author Contributions

The authors confirm contribution to the paper as follows: study conception and design: S. Hoover, C. Fuentes; data collection: S. Hoover, D. Porter; analysis and interpretation of results: S. Hoover, D. Porter; draft manuscript preparation: S. Hoover, D. Porter. All authors reviewed the results and approved the final version of the manuscript.

Declaration of Conflicting Interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) received no financial support for the research, authorship, and/or publication of this article.

Data Accessibility Statement

The data that support the findings of this study are available from Oregon State University but restrictions apply to the availability of these data, which were used under license for the current study, and so are not publicly available. Data are however available from the authors on reasonable request and with permission of Oregon State University.

References

Guihaire

Hao

J.-K.

Transit Network Design and Scheduling: A Global Review. Transportation Research Part A: Policy and Practice, Vol. 42, No. 10, 2008, pp. 1251–1273. https://doi.org/10.1016/j.tra.2008.03.011.

Xiong

Schneider

J. B.

Transportation Network Design Using a Cumulative Genetic Algorithm and Neural Network. Transportation Research Record: Journal of the Transportation Research Board, 1992. 1364: 37–44.

Mahmoudzadeh

Wang

X. B.

Cluster Based Methodology for Scheduling a University Shuttle System. Transportation Research Record: Journal of the Transportation Research Board, 2020. 2674: 236–248.

Larkin

2 MIT Engineers Use Math to Plot a Path for Boston’s School Buses. 2017. https://www.wbur.org/edify/2017/07/27/mit-quantum-boston-bus-routes.

Joi

Ito

. What the Boston School Bus Schedule Can Teach Us about AI. 2018. https://www.wired.com/story/joi-ito-ai-and-bus-routes/.

Grossman

How an Algorithm Made the Buses in Boston Better. 2019. https://www.popularmechanics.com/technology/infrastructure/a28689713/algorithm-boston-buses/.

Bertsimas

Delarue

Martin

Optimizing Schools’ Start Time and Bus Routes. Proceedings of the National Academy of Sciences, Vol. 116, No. 13, 2019, p. 201811462. https://doi.org/10.1073/pnas.1811462116.

Lemos

J. Y.

Joshi

A. R.

D’Souza

M. M.

D’Souza

A. D.

Design a Smart and Intelligent Routing Network Using Optimization Techniques. In Data Management, Analytics and Innovation ( Balas

V. E.

Sharma

Chakrabarti

, eds.), Springer, Singapore, 2019, pp. 297–310.

Leksakul

Smutkupt

Jintawiwat

Phongmoo

Heuristic Approach for Solving Employee Bus Routes in a Large-Scale Industrial Factory. Advanced Engineering Informatics, Vol. 32, 2017, pp. 176–187. https://doi.org/10.1016/j.aei.2017.02.006.

10.

Liu

Yuan

N. J.

Duan

Xiong

Intelligent Bus Routing with Heterogeneous Human Mobility Patterns. Knowledge and Information Systems, Vol. 50, No. 2, 2017, pp. 383–415. https://doi.org/10.1007/s10115-016-0948-6.

11.

Keeling

M. J.

Eames

K. T.

Networks and Epidemic Models. Journal of the Royal Society Interface, Vol. 2, No. 4, 2005, pp. 295–307. https://doi.org/10.1098/rsif.2005.0051.

12.

Firestone

S. M.

Ward

M. P.

Christley

R. M.

Dhand

N. K.

The Importance of Location in Contact Networks: Describing Early Epidemic Spread Using Spatial Social Network Analysis. Preventive Veterinary Medicine, Vol. 102, No. 3, 2011, pp. 185–195. https://doi.org/10.1016/j.prevetmed.2011.07.006.

13.

McCluskey

C. C.

Cressman

Spatial Spread of an Epidemic through Public Transportation Systems with a Hub. Mathematical Biosciences, Vol. 246, No. 1, 2013, pp. 164–175. https://doi.org/10.1016/j.mbs.2013.08.014.

14.

Sun

Axhausen

K. W.

Lee

D.-H.

Cebrian

Efficient Detection of Contagious Outbreaks in Massive Metropolitan Encounter Networks. Scientific Reports, Vol. 4, No. 1, 2015, p. 5099. https://doi.org/10.1038/srep05099.

15.

Zhang

Wang

Fang

Modeling Epidemics Spreading on Social Contact Networks. IEEE Transactions on Emerging Topics in Computing, Vol. 3, No. 3, 2015, pp. 410–419. https://doi.org/10.1109/TETC.2015.2398353.

16.

Song

Y.-R.

Jiang

G.-P.

How Clustering Affects Epidemics in Complex Networks. Proc., 2017 International Conference on Computing, Networking and Communications (ICNC), Silicon Valley, CA, IEEE, New York, 2017, pp. 178–183. https://doi.org/10.1109/ICCNC.2017.7876123.

17.

National Center for Immunization and Respiratory Diseases (NCIRD), and Division of Viral Diseases. What Bus Transit Operators Need to Know about COVID-19. 2020. https://www.cdc.gov/coronavirus/2019-ncov/community/organizations/bus-transit-operator.html.

18.

Goscé

Johansson

Analysing the Link between Public Transport Use and Airborne Transmission: Mobility and Contagion in the London Underground. Environmental Health, Vol. 17, No. 1, 2018, p. 84. https://doi.org/10.1186/s12940-018-0427-5.

19.

Bóta

Gardner

L. M.

Khani

Modeling the Spread of Infection in Public Transit Networks: A Decision-Support Tool for Outbreak Planning and Control. Presented at 96th Annual Meeting of the Transportation Research Board, Washington, D.C., 2017.

20.

Bóta

Gardner

L. M.

Khani

Identifying Critical Components of a Public Transit System for Outbreak Control. Networks and Spatial Economics, Vol. 17, No. 4, 2017, pp. 1137–1159. https://doi.org/10.1007/s11067-017-9361-2.

21.

Shoghri

A. E.

Liebig

Gardner

Jurdak

Kanhere

How Mobility Patterns Drive Disease Spread: A Case Study Using Public Transit Passenger Card Travel Data. Proc., 2019 IEEE 20th International Symposium on “A World of Wireless, Mobile and Multimedia Networks” (WoWMoM), Washington, D.C., 2019, pp. 1–6. https://doi.org/10.1109/WoWMoM.2019.8793018.

22.

Feng

Shen

Tam

Yin

Zhao

Modeling Epidemic Spreading through Public Transit Using Time-Varying Encounter Network. arXiv Preprint arXiv:2004.04602 [physics, q-bio], 2004. http://arxiv.org/abs/2004.04602.

23.

Boeing

OSMnx: New Methods for Acquiring, Constructing, Analyzing, and Visualizing Complex Street Networks. Computers, Environment and Urban Systems, Vol. 65, 2017, pp. 126–139. https://doi.org/10.1016/j.compenvurbsys.2017.05.004.

24.

Fan

Mumford

C. L.

Evans

A Simple Multi-Objective Optimization Algorithm for the Urban Transit Routing Problem. Proc., 2009 IEEE Congress on Evolutionary Computation, Trondheim, Norway, 2009, pp. 1–7. https://doi.org/10.1109/CEC.2009.4982923.

25.

Mumford

C. L.

New Heuristic and Evolutionary Operators for the Multi-Objective Urban Transit Routing Problem. Proc., 2013 IEEE Congress on Evolutionary Computation, Cancun, Mexico, 2013, pp. 939–946. https://doi.org/10.1109/cec.2013.6557668.

26.

Chew

J. S. C.

Lee

L. S.

Seow

H. V.

Genetic Algorithm for Biobjective Urban Transit Routing Problem. Journal of Applied Mathematics, Vol. 2013, 2013, pp. 1–15. https://doi.org/10.1155/2013/698645.

27.

John

M. P.

Mumford

C. L.

Lewis

An Improved Multi-Objective Algorithm for the Urban Transit Routing Problem. In Evolutionary Computation in Combinatorial Optimisation ( Blum

Ochoa

, eds.), Springer, Berlin, Heidelberg, 2014, pp. 49–60.

28.

Cooper

I. M.

John

M. P.

Lewis

Mumford

C. L.

Olden

Optimising Large Scale Public Transport Network Design Problems Using Mixed-Mode Parallel Multi-Objective Evolutionary Algorithms. Proc., 2014 IEEE Congress on Evolutionary Computation (CEC), Beijing, China, 2014, pp. 2841–2848. https://doi.org/10.1109/cec.2014.6900362.

29.

Biscani

Izzo

A Parallel Global Multiobjective Framework for Optimization: Pagmo. Journal of Open Source Software, Vol. 5, No. 53, 2020, p. 2338. https://doi.org/10.21105/joss.02338.

30.

Deb

Pratap

Agarwal

Meyarivan

A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation, Vol. 6, No. 2, 2002, pp. 182–197. https://doi.org/10.1109/4235.996017.

31.

Manderick

Spiessens

Fine-Grained Parallel Genetic Algorithms. Proc., 3rd International Conference on Genetic Algorithms, Fairfax, VA, 1989, pp. 428–433.

32.

Barabási

A.-L.

Pósfai

Network Science. Cambridge University Press, 2016.

33.

Pastor-Satorras

Vespignani

Epidemic Dynamics in Finite Size Scale-Free Networks. Physical Review E, Vol. 65, No. 3, 2002, p. 035108. https://doi.org/10.1103/PhysRevE.65.035108.

34.

Gutierrez

J. C. T.

Adamatti

D. S.

Bravo

J. M.

A New Stopping Criterion for Multi-Objective Evolutionary Algorithms: Application in the Calibration of a Hydrologic Model. Computational Geosciences, Vol. 23, No. 6, 2019, pp. 1219–1235. https://doi.org/10.1007/s10596-019-09870-3.