Search NASA⌕ Search

SEARCH · Search NASA

Results for “traffic optimization”

Search indexed NASA NTRS and DOE OSTI research on propulsion, heat transfer, battery materials and energy systems. Follow report and document links to the original sources.

Quote a phrase for an exact phrase match. Source license links do not imply unrestricted reuse.

At least 217 records · Page 12

Battery Electric Vehicle Eco-Cooperative Adaptive Cruise Control in the Vicinity of Signalized Intersections

This study develops a connected eco-driving controller for battery electric vehicles (BEVs), the BEV Eco-Cooperative Adaptive Cruise Control at Intersections (Eco-CACC-I). The developed controller can assist BEVs while traversing signalized intersections with minimal energy consumption. The calculation of the optimal vehicle trajectory is formulated as an optimization problem under the constraints of (1) vehicle acceleration/deceleration behavior, defined by a vehicle dynamics model; (2) vehicle energy consumption behavior, defined by a BEV energy consumption model; and (3) the relationship between vehicle speed, location, and signal timing, defined by vehicle characteristics and signal phase and timing (SPaT) data shared under a connected vehicle environment. The optimal speed trajectory is computed in real-time by the proposed BEV eco-CACC-I controller, so that a BEV can follow the optimal speed while negotiating a signalized intersection. The proposed BEV controller was tested in a case study to investigate its performance under various speed limits, roadway grades, and signal timings. In addition, a comparison of the optimal speed trajectories for BEVs and internal combustion engine vehicles (ICEVs) was conducted to investigate the impact of vehicle engine types on eco-driving solutions. Lastly, the proposed controller was implemented in microscopic traffic simulation software to test its networkwide performance. The test results from an arterial corridor with three signalized intersections demonstrate that the proposed controller can effectively reduce stop-and-go traffic in the vicinity of signalized intersections and that the BEV Eco-CACC-I controller produces average savings of 9.3% in energy consumption and 3.9% in vehicle delays.

32 ENERGY CONSERVATION, CONSUMPTION, AND UTILIZATI↗

Resilient design of recharging station networks for electric transportation vehicles

As societies shift to 'greener' means of transportation using electricity-driven vehicles one critical challenge we face is the creation of a robust and resilient infrastructure of recharging stations. A particular issue here is the optimal location of service stations. In this work, we consider the placement of battery replacing service station in a city network for which the normal traffic flow is known. For such known traffic flow, the service stations are placed such that the expected performance is maximized without changing the traffic flow. This is done for different scenarios in which roads, road junctions and service stations can fail with a given probability. To account for such failure probabilities, the previously developed facility interception model is extended. Results show that service station failures have a minimal impact on the performance following robust placement while road and road junction failures have larger impacts which are not mitigated easily by robust placement.

02 PETROLEUM↗

Developing a Hybrid Electric Vehicle Eco-Cooperative Adaptive Cruise Control System at Signalized Intersections.

This study develops an eco-driving strategy for hybrid electric vehicles (HEVs) in the vicinity of signalized intersections, entitled HEV Eco-Cooperative Adaptive Cruise Control at Intersections (Eco-CACC-I). The proposed system computes real-time, energy-optimized vehicle trajectories using HEV vehicle dynamics and energy consumption models. In the proposed system, a simple HEV energy model is used to compute the instantaneous fuel consumption. This HEV energy model is selected since it is general, transferable, and can be easily used to compute instantaneous energy consumption levels for HEVs without the additional input of vehicle engine data or complicated power control strategies. In addition, a vehicle dynamics model is used to capture the relationship between speed, acceleration level, and tractive/resistance forces on vehicles. The energy-optimum problem is formulated as an optimization problem with constraints, which is solved using a moving-horizon dynamic programming approach. The proposed HEV Eco-CACC-I system was tested to evaluate its performance for various speed limits, roadway grades, and signal timings. Lastly, the proposed HEV controller was implemented in a microscopic traffic simulation software to test its network-wide performance. The test results from an arterial corridor with three signalized intersections demonstrate that the proposed system can effectively reduce stop-and-go traffic in the vicinity of signalized intersections producing savings of 7.4% in energy consumption, 5.8% in traffic delay and 23% vehicle stops, respectively.

32 ENERGY CONSERVATION, CONSUMPTION, AND UTILIZATI↗

High-dimensional Data-driven Energy optimization for Multi-Modal Transit Agencies (HD-EMMA) (Final Technical Report)

Public bus transit services in the U.S. are responsible for at least 19.7 million metric tons of CO 2 emission annually. Electric vehicles (EVs) can have a much lower environmental impact than comparable internal combustion engine vehicles (ICEVs), especially in urban areas. Unfortunately, EVs are also much more expensive than ICEVs. As a result, many public transit agencies can afford only mixed fleets of transit vehicles, consisting of EVs, hybrids (HEVs), and ICEVs. Transit agencies that operate such mixed fleets of vehicles face a challenging optimization problem: these agencies need to decide which vehicles are assigned to serving which transit trips. Since the advantage of EVs over ICEVs varies depending on the route and time of day (e.g., the benefit of EVs is higher in slower traffic with frequent stops and lower on highways), the assignment can have a significant effect on energy use and, hence, environmental impact. Through this project, we have developed reference data about energy collections and constructed a set of machine learning models that can accurately predict the energy consumption for the whole fleet at the level of each trip. We have used these models to develop a scheduling and assignment strategy that can rotate the different vehicle types across the transit agencies’ routes. The optimization algorithm ensures that the vehicles are matched to trips considering weather patterns, expected congestion, and road gradients to minimize the overall energy usage. We list the key observations from our project for other practitioners below. Details are available in the report, and the list of source code and our publications are included in the appendix. 1. We have demonstrated the feasibility of collecting, merging and analyzing large volumes of high-resolution real-world telemetry data from a mixed vehicle fleet. To mitigate the inherent noise of the recorded GPS points, the team developed an algorithm that filters data and maps the points onto a street. The algorithm considers previous and subsequent location measurements and different characteristics of nearby streets to determine how likely the vehicle travels on them. Then, the team segmented the time series into disjoint contiguous samples based on adjacent road segments and repeated the outlier detection and removal. For each data point, the team added features corresponding to elevation changes within the samples, weather features, such as temperature, and traffic data, such as speed ratio between actual speed and free-flow speed. 2. We have developed two forms of machine learning models that be used to understand and analyze the energy operations of a mixed vehicle transit fleet. The micro prediction model provides estimates of instantaneous energy prediction for all types of buses (diesel, hybrid, and electric). Such a model is important in evaluating the energy impacts of real-time bus operation strategies, but it is challenging due to diversified driving cycles of transit buses. The model can help the drivers understand the impact of their driving behaviors and short-term congestions. The macro prediction models estimate average energy consumption across the whole trip considering the features: distance traveled, various road-type features, elevation change, day of the week, time of day, various weather features (temperature, humidity, etc.), and traffic features (speed ratio and jam factor). 3. We have demonstrated that it is possible to transfer the machine learning models we have developed in this project to other teams and cities by using inductive transfer learning. We also showed that the performance of the macro energy prediction models can be improved using a multi-task learning approach where the learning parameters are shared between the models being developed for different vehicle types. The advantage of this approach is improved learning performance as the models can exploit common spatio-temporal and environmental characteristics. 4. Finally, we have developed trip and vehicle assignment and scheduling algorithms that use the energy prediction models and develop a trip to vehicle type (diesel, electric, hybrid) assignment for the whole operation to reduce overall emissions and cost. We have shown through simulations that the proposed algorithms can save $\$$ 48,910 in energy costs and 175 metric tons of CO 2 emission annually for CARTA.

32 ENERGY CONSERVATION, CONSUMPTION, AND UTILIZATI↗

A Learning System for Discriminating Variants of Malicious Network Traffic

Modern computer network defense systems rely primarily on signature-based intrusion detection tools, which generate alerts when patterns that are pre-determined to be malicious are encountered in network data streams. Signatures are created reactively, and only after in-depth manual analysis of a network intrusion. There is little ability for signature-based detectors to identify intrusions that are new or even variants of an existing attack, and little ability to adapt the detectors to the patterns unique to a network environment. Due to these limitations, the need exists for network intrusion detection techniques that can more comprehensively address both known unknown networkbased attacks and can be optimized for the target environment. This work describes a system that leverages machine learning to provide a network intrusion detection capability that analyzes behaviors in channels of communication between individual computers. Using examples of malicious and non-malicious traffic in the target environment, the system can be trained to discriminate between traffic types. The machine learning provides insight that would be difficult for a human to explicitly code as a signature because it evaluates many interdependent metrics simultaneously. With this approach, zero day detection is possible by focusing on similarity to known traffic types rather than mining for specific bit patterns or conditions. This also reduces the burden on organizations to account for all possible attack variant combinations through signatures. The approach is presented along with results from a third-party evaluation of its performance.

Computer Network Defense↗

Multi-Commodity Traffic Signal Control and Routing With Connected Vehicles

We report a real-time traffic management policy that integrates traffic signal control and multi-commodity routing of connected vehicles in networks with multiple destinations is developed. The proposed policy is based on a multi-commodity formulation of the store-and-forward model and assumes all vehicles are able to exchange information with the infrastructure. Vehicles share information about their current location and final destination. Based on this information, the strategy determines both optimized signal timings at every intersection and vehicle-specific routing information at every link of the network. The control actions, i.e., signal times and routing information, are updated at every cycle and delivered by a finite horizon optimal control problem cast into a rolling horizon framework. The underlying optimization problem is convex, and thus the method is suitable for real-time operation in large networks. The method is validated via a micro-simulation study in networks with up to twenty intersections and, in all simulations, outperforms a real-time traffic-responsive signal control strategy that is based on a single-commodity store-and-forward model. The scalable computation effort for increasing network sizes and prediction horizon confirms the computational efficiency of the method.

42 ENGINEERING↗

Reducing Communication Overhead in Federated Learning for Network Anomaly Detection with Adaptive Client Selection

Communication overhead in federated learning (FL) poses a significant challenge for network anomaly detection systems, where the myriad of client configurations and network conditions can severely impact system efficiency and detection accuracy. While existing approaches attempt to address this through individual optimization techniques, they often fail to maintain the delicate balance between reduced overhead and detection performance. This paper presents an adaptive FL framework that dynamically combines batch size optimization, client selection, and asynchronous updates to achieve efficient anomaly detection. Through extensive profiling and experimental analysis on two distinct datasets-UNSW-NBIS for general network traffic and ROAD for automotive networks-our framework reduces communication overhead by 97.6%; (from 700.0s to 16.8s) compared to synchronous baseline approaches while maintaining comparable detection accuracy (95.10%; vs. 95.12%;). Statistical validation using Mann-Whitney U test confirms significant improvements (p < 0.05) over existing FL approaches across both datasets, demonstrating the framework's adaptability to different network security contexts. Detailed profiling analysis reveals the efficiency gains through dramatic reductions in GPU operations and memory transfers while maintaining robust detection performance under varying client conditions.

Marfo, William [University of Texas at El Paso]↗

Modeling Freight Traffic Demand and Highway Networks for Hydrogen Fueling Station Planning: A Case Study of U.S. Interstate 75 Corridor

The use of hydrogen as an alternative transportation fuel has gained much interest in recent years. Hydrogen can be utilized in electric vehicles equipped with hydrogen powertrains (including hydrogen internal combustion engines or fuel cells). Given that most of the freight in the U.S. is transported via diesel trucks, transition to hydrogen fuel would help achieve significant environmental benefits as well as accelerate the decarbonization of the freight transportation sector. This paper presents the methodology and results of a case study on modeling freight traffic demand and highway networks based on publicly available data for the Interstate 75 freight corridor. The purpose of this study is to prepare input traffic and network data that can support the planning of a hydrogen fueling station infrastructure. In particular, the data can be used for siting and characterizing an optimized framework of hydrogen fueling stations from candidate diesel stations along the Interstate 75 corridor. The methodologies developed and presented in this paper may be readily expanded and applied to any transport corridor given the data availability. This paper is the first in a series that will build out a comprehensive model to optimize a consolidated national hydrogen refueling infrastructure eco-system targeted at commercial vehicles.

Uddin, Majbah↗

Unconventional Quantum Advantages for Computation (U-QuAC)

While quantum computing offers the promise of exponential advantages, limited quantum speedups are known, especially for practical applications. To open new avenues for quantum advantages, we propose Unconventional Quantum Advantages for Computation (U-QuACs), with respect to unconventional resources such as space (number of bits or quantum bits of memory required to solve a problem), accuracy of solution, communication, or energy consumption. We focus on space-efficient quantum algorithms, where we seek to design algorithms that solve a problem using much less space than the total size of the input. A natural setting in which space is critical is the streaming model of computation, where the input data arrives sequentially in pieces that must each be processed individually. Streaming is motivated by a variety of problems including analysis of internet traffic or social networks. We design the first exponential quantum space advantage for a natural streaming problem, which also constitutes the first quantum advantage for approximating a discrete optimization problem, albeit with respect to space.

97 MATHEMATICS AND COMPUTING↗

Peer-to-Peer Communication Trade-Offs for Smart Grid Applications: Preprint

Peer-to-peer energy management systems for smart grids require developers to consider the trade-offs between the amount of communication traffic generated and the quality and speed of convergence of the control algorithms that are deployed. Employing a fully connected communication causes messages to scale exponentially with the number of nodes, while using a sparse connectivity causes less information dissemination leading to degradation of the algorithm performance. The best communication topology for a particular application lies somewhere in between and often requires empirical evaluation by application designers. Existing methods do not put focus on the needs for smart grid applications, which is information dissemination throughout the network and they do not provide a flexible solution for application developers to prototype and deploy different topologies without modifying the application code. This paper introduces a configurable virtual communication topology framework TopLinkMgr, allowing users to specify any chosen communication topology and deploy peer-to-peer applications using it. It also introduces a self-adaptive, fault-tolerant topology management algorithm, Bounded Path Dissemination that can ensure the dissemination of information to all peers within a specified threshold for a sparsely connected topology. Experiments show that the algorithm improves on convergence speed and accuracy over state-of-the-art methods and is also robust against node failures. The results indicate the possibility of achieving a close-to optimal convergence without overloading the network allowing the realization of peer-to-peer control platforms covering larger and more complex power systems.

Bounded Path Dissemination↗

Optimizing connectivity in reconfigurable networks

A method may include determining whether the topology of a network includes a direct path between a first endpoint and a second endpoint in the network. A direct path may be used to send a first type of traffic from the first endpoint to the second endpoint whereas any currently available path may be used to send a second type of traffic from the first endpoint to the second endpoint. If the topology of the network does not include a direct path, the first type of traffic may be buffered at the first endpoint until the topology of the network is reconfigured to include the direct path. The topology of the network may be reconfigured when at least one switch in the network reconfigures, for example, by switching from one interconnection to another interconnection pattern. Related systems and articles of manufacture are also provided.

Mellette, William↗

Integrating Multi-Source Data for Bi-Level Traffic Simulator Calibration: A Literature Review and Highway Case Study

Traffic simulation serves as a powerful tool for pre-evaluating policies and technologies. In this context, simulation-based Dynamic traffic assignment (DTA) models are capable of capturing traffic dynamics. They are well-known as critical tools in controlling and predicting traffic situations. The reliability of simulation results heavily depends on the calibration process. Most studies in the literature formulate and calibrate simulators based on a single source of collected data or multiple data sets with the same spatiotemporal characteristics. However, in practice, traffic data is collected by various tools with usually different spatial and temporal resolutions. This study introduces a novel approach to taking into account diverse input data from a variety of sources. An iterative bi-level solution is proposed. to equally treat traffic flow and speed data. The upper level solves flow calibration with the exact solution method, and the lower level calibrates the speed with the simultaneous perturbation stochastic approximation (SPSA) algorithm. Subsequently, the effectiveness of the proposed model is investigated using data from a six-mile section of Nashville's I-24 highway in Tennessee. The results demonstrate that our proposed model creates an effective feedback loop between the optimizer and the simulator for calibrating flow and speed to reduce the error between simulated and real data.

42 ENGINEERING↗

Phasor Measurement Units Optimal Placement and Performance Limits for Fault Localization

Here, the performance limits of faults localization are investigated using synchrophasor data. The focus is on a non-trivial operating regime where the number of Phasor Measurement Unit (PMU) sensors available is insufficient to have full observability of the grid state. Proposed analysis uses the Kullback Leibler (KL) divergence between the distributions corresponding to different fault location hypotheses associated with the observation model. This analysis shows that the most likely locations are concentrated in clusters of buses more tightly connected to the actual fault site akin to graph communities. Consequently, a PMU placement strategy is derived that achieves a near-optimal resolution for localizing faults for a given number of sensors. The problem is also analyzed from the perspective of sampling a graph signal, and how the placement of the PMUs i.e. the spatial sampling pattern and the topological characteristic of the grid affect the ability to successfully localize faults. To highlight the superior performance of presented fault localization and placement algorithms, the proposed strategy is applied to a modified IEEE 34, IEEE-123 bus test cases and to data from a real distribution grid. Additionally, the detection of cyber-physical attacks is also examined where PMU data and relevant Supervisory Control and Data Acquisition (SCADA) network traffic information are compared to determine if a network breach has affected the integrity of the system information and/or operations.

42 ENGINEERING↗

Final Report for the project titled "Enabling Supernova Computations by Integrated Transport and Provisioning Methods Optimized for Dedicated Channels"

A high-speed optical circuit network is one that offers users rate-guaranteed connectivity between two endpoints, unlike today’s IP-routed Internet in which the rate available to a pair of users fluctuates based on the volume of competing traffic. This particular research project advanced our understanding of circuit networks in two ways. First, transport protocols were developed for circuit networks. In a circuit network, since bandwidth resources are reserved for each circuit on an end-to-end basis (much like how a person reserves a seat on every leg of a multi-segment flight), and the sender is limited to send at the rate of the circuit, there is no possibility of congestion during data transfer. Therefore, no congestion control functions are necessary in a transport protocol designed for circuits. However, error control and flow control are still required because bits can become errored due to noise and interference even on highly reliable optical links, and receivers can, due to multitasking or other reasons, not deplete the receive buffer fast enough to keep up with the sending rate (e.g., if the receiving host is multitasking between receiving a file transfer and some other computation). In this work, we developed two transport protocols for circuits, both of which are described below. Second, this project developed techniques for internetworking different types of connection-oriented networks, which are of two types: circuit-switched or packet-switched. In circuit-switched networks, multiplexing on links is “position based,” where “position” refers to the frequency, time slot, and port (fiber), while connection-oriented packet-switched networks use packet header information to demultiplex packets and switch them from node to node. The latter are commonly referred to as virtual circuit networks. Examples of circuit networks are time-division multiplexed Synchronous Optical Network/Synchronous Digital Hierarchy (SONET/SDH) and Wavelength Division Multiplexing (WDM) networks, while examples of virtual-circuit networks are MultiProtocol Label Switched (MPLS) networks and Ethernet Virtual Local Area Network (VLAN) networks. A series of new technologies have been developed to carry Ethernet VLAN tagged frames on SONET/SDH and WDM networks, such as Generic Framing Procedure (GFP) and ITU G.709, respectively. These technologies form the basis of our solution for connection-oriented internetworking. The benefit of developing such an architecture is that it allows different providers to choose different connection-oriented networking technologies for their networks, and yet be able to allow their customers to connect to those of other providers. As Metcalfe, the inventor of Ethernet, noted, the value of a network service grows exponentially with the number of endpoints to which any single endpoint can connect. Therefore internetworking solutions are key to commercial success. The technical effectiveness of our solutions was measured with proof-of-concept prototypes and experiments. These solutions were shown to be highly effective. Economic feasibility requires business case analyses that were beyond the scope of this project. The project results are beneficial to the public as they demonstrate the viability of simultaneously supporting different types of networks and data communication services much like the variety of services available for the transportation of people and goods. For example, Fedex service offers a deadline based delivery while the USPS offers basic package delivery service. Similarly, a circuit network can offer a deadline based delivery of a data file while the IP-routed network offers only basic delivery service with no guarantees. Two project Web sites, 13 publications, 7 software programs, 21 presentations resulted from this work. This report provides the complete list of publications, software programs and presentations. As for student education and training (human resources), this DOE project, along with an NSF project, jointly supported two postdoctoral fellowships, three PhDs, three Masters, and two undergraduate students. Specifically, two of the Masters students were directly funded on this DOE project.

99 GENERAL AND MISCELLANEOUS↗

Regulating Intracellular Calcium in Plants: From Molecular Genetics to Physiology

To grow, develop, adapt, and reproduce, plants have evolved mechanisms to regulate the uptake, translocation and sorting of calcium ions into different cells and subcellular compartments. Yet how plants accomplish this remarkable feat is still poorly understood. The spatial and temporal changes in intracellular [Ca2+] during growth and during responses to hormonal and environmental stimuli indicate that Ca2+ influx and efflux transporters are diverse and tightly regulated in plants. The specific goals were to determine the biological roles of multiple Ca pumps (ECAs) in the model plant Arabidopsis thaliana. We had pioneered the use of K616 yeast strain to functionally express plant Ca pumps, and demonstrated two distinct types of Ca pumps in plants (Sze et al., 2000. Annu Rev Plant Biol. 51,433). ACA2 represented one type that was auto-inhibited by the N-terminal region and stimulated by calmodulin. ECA1 represented another type that was not sensitive to calmodulin and phylogenetically distinct from ACAs. The goal to determine the biological roles of multiple ECA-type Ca pumps in Arabidopsis has been accomplished. Although we demonstrated ECA1 was a Ca pump by functional expression in yeast, the in vivo roles of ECAs was unclear. A few highlights are described. ECA1 and/or ECA4 are Ca/Mn pumps localized to the ER and are highly expressed in all cell types. Using homozygous T-DNA insertional mutants of eca1, we demonstrated that the ER-bound ECA1 supports growth and confers tolerance of plants growing on medium low in Ca or containing toxic levels of Mn. This is the first genetic study to determine the in vivo function of a Ca pump in plants. A phylogenetically distinct ECA3 is also a Ca/Mn pump that is localized to endosome, such as post-Golgi compartments. Although it is expressed at lower levels than ECA1, eca3 mutants are impaired in Ca-dependent root growth and in pollen tube elongation. Increased secretion of wall proteins in mutants suggests that Ca and Mn homeostasis in post-Golgi compartments are critical for secretory activities. Moreover, perturbation of the secretory machinery limits growth possibly by upsetting the synthesis, processing and assembly of cell wall components. Analyses of whole genome transcriptome of pollen shows that a subset of Ca pump genes are developmentally regulated. Each ECA Ca pump is localized to distinct endomembrane compartments and regulate Ca and Mn homeostasis required for optimal growth and for tolerance to high Mn stress. Ca and Mn levels within endomembrane lumen appear to be critical for activities of the secretory machinery including post-Golgi compartments that coordinate membrane traffic and sorting of materials to the vacuole and the cell wall. Significance: Thus sorting of Ca/Mn by ECA pumps in endomembranes is critical for membrane trafficking pattern which serves as a central coordinator of plant growth, development and adaptation to abiotic and biotic stress.

59 BASIC BIOLOGICAL SCIENCES↗

A Comparison of Genetic Programming Variants for Hyper-Heuristics

Modern society is faced with ever more complex problems, many of which can be formulated as generate-and-test optimization problems. General-purpose optimization algorithms are not well suited for real-world scenarios where many instances of the same problem class need to be repeatedly and efficiently solved, such as routing vehicles over highways with constantly changing traffic flows, because they are not targeted to a particular scenario. Hyper-heuristics automate the design of algorithms to create a custom algorithm for a particular scenario. Hyper-heuristics typically employ Genetic Programming (GP) and this project has investigated the relationship between the choice of GP and performance in Hyper-heuristics. Results are presented demonstrating the existence of problems for which there is a statistically significant performance differential between the use of different types of GP.

97 MATHEMATICS AND COMPUTING↗

Model for Collaboration among Carriers to Reduce Empty Container Truck Trips

In recent years, intermodal transport has become an increasingly attractive alternative to freight shippers. However, the current intermodal freight transport is not as efficient as it could be. Oftentimes an empty container needs to be transported from the empty container depot to the shipper, and conversely, an empty container needs to be transported from the receiver to the empty container depot. These empty container movements decrease the freight carrier’s profit, as well as increase traffic congestion, decrease roadway safety, and add unnecessary emissions to the environment. To this end, our study evaluates a potential collaboration strategy to be used by carriers for domestic intermodal freight transport based on an optimization approach to reduce the number of empty container trips. A binary integer-linear programming model is developed to determine each freight carrier’s optimal schedule while minimizing its operating cost. The model ensures that the cost for each carrier with collaboration is less than or equal to its cost without collaboration. It also ensures that average savings from the collaboration are shared equally among all participating carriers. Additionally, two stochastic models are provided to account for uncertainty in truck travel times. The proposed collaboration strategy is tested using empirical data and is demonstrated to be effective in meeting all of the shipment constraints.

42 ENGINEERING↗

An Online Approach to Solve the Dynamic Vehicle Routing Problem with Stochastic Trip Requests for Paratransit Services

Many transit agencies operating paratransit and microtransit services have to respond to trip requests that arrive in real-time, which entails solving hard combinatorial and sequential decision-making problems under uncertainty. To avoid decisions that lead to significant inefficiency in the long term, vehicles should be allocated to requests by optimizing a non-myopic utility function or by batching requests together and optimizing a myopic utility function. While the former approach is typically offline, the latter can be performed online. We point out two major issues with such approaches when applied to paratransit services in practice. First, it is difficult to batch paratransit requests together as they are temporally sparse. Second, the environment in which transit agencies operate changes dynamically (e.g., traffic conditions can change over time), causing the estimates that are learned offline to become stale. To address these challenges, we propose a fully online approach to solve the dynamic vehicle routing problem (DVRP) with time windows and stochastic trip requests that is robust to changing environmental dynamics by construction. We focus on scenarios where requests are relatively sparse—our problem is motivated by applications to paratransit services. We formulate DVRP as a Markov decision process and use Monte Carlo tree search to evaluate actions for any given state. Accounting for stochastic requests while optimizing a non-myopic utility function is computationally challenging; indeed, the action space for such a problem is intractably large in practice. To tackle the large action space, we leverage the structure of the problem to design heuristics that can sample promising actions for the tree search. Our experiments using real-world data from our partner agency show that the proposed approach outperforms existing state-of-the-art approaches both in terms of performance and robustness.

32 ENERGY CONSERVATION, CONSUMPTION, AND UTILIZATI↗