A MULTI-TASK GRAPH NEURAL NETWORK FOR JOINT-PREDICTION OF ZONE-BASED AND OD-BASED RIDE-HAILING DEMAND
Siyuan Feng, Hong Kong University of Science and TechnologyShow Abstract
Jintao Ke, Hong Kong University of Science and Technology
Hai Yang, Hong Kong University of Science and Technology
Ride-hailing service has witnessed a dramatic growth over the past decade but meanwhile raised various challenging issues, one of which is how to provide a timely and accurate short-term prediction of supply and demand. While the predictions for zone-based demand (namely, demand originating from each zone) have been extensively studied, much less efforts have been paid to the predictions for origin-destination (OD) based demand (namely, demand originating from one zone to another). However, OD-based demand prediction is even more important and worth further explorations, since it provides more elaborate trip information in the near future as reference for fine-grained operations, such as the routing and matching of shared ride-hailing services that pick up and drop off two or more passengers in each ride. Moreover, zone-based and OD-based demands closely interact with each other, and thus one can naturally expect that a joint-prediction of zone-based and OD-based demand has potentials to improve the predictive accuracy of both tasks. To address these issues, we propose a multi-task graph neural network (MT-GCN), which consists of two major components: (1) a GCN (graph convolutional network) basic module that captures the spatial correlations among zones on a graph via mixture-model graph convolutional (MGC) network, and (2) a decoder module for multi-task predictions of zone-based and OD-based demand. By evaluations on the real-world on-demand data in Manhattan (which is partitioned into various irregular zip-code based zones), we show that the proposed model outperforms the state-of-the-art benchmark methods in both zone- and OD-based predictions.
Modeling and Managing Ride-hailing Curbside Pick-ups and Drop-offs with a Novel Bi-Modal User Equilibrium Model
Koutian Huang, Carnegie Mellon UniversityShow Abstract
Wei Ma, Hong Kong Polytechnic University
Sean Qian (email@example.com), Carnegie Mellon University
Recent years have witnessed the rise of ride-hailing services in almost all major cities. The use of ride-hailing services require pick up and drop off passengers at curbside, which could cause additional congestion for both ride-hailing vehicles and conventional private vehicles. This issue is particularly crucial in downtown areas of mega-cities. Curbside utilization by ride-hailing services could substantially influence other private vehicles in terms of both driving and parking along curbs, which further alters the travelers' choices in modes/routes and consequently network traffic patterns. However, there is a lack of theories to evaluate the effects of curbside ride-hailing stops in networks, and ultimately to manage ride-hailing pickups and dropoffs for network performance optimum. In view of this, this paper develops a novel bi-model network equilibrium (BMUE) model that considers both driving and ride-hailing modes. To model the impact of limited curbside capacity, we propose a curbside queuing model to study the waiting time and queue lengths of ride-hailing pick-ups and drop-offs. This paper also explores the option to regulate the amount of curbside stops due to ride-hailing trips by imposing a curb use fee. To determine the optimal prices, a sensitivity analysis-based gradient descent method is proposed to minimize the total network social cost. The proposed methods are examined on two networks. Both BMUE and optimal pricing problems can be solved efficiently and accurately, and the results are interpretable. We further observe that the policy of curbside pricing works the best when network is moderated congested. The developed models could help public agencies to understand the impacts of ride-hailing pick-ups and drop-offs on curbside space and provide policy implications for curbside regulations.
A school bus routing problem with a mixed ride, mixed load, and heterogeneous fleet
Mengyun Li, Stantec Consulting Services, Inc.Show Abstract
Joseph Chow, New York University
Special education students are usually routed on different buses than non-disabled general education students. To make the routes more efficient, this study proposes serving general students and special-education students on the same bus at the same time (mixed ride) while allowing heterogeneous fleets and mixed loads. ESIR Location-Allocation tools and Google OR tools are used for bus stop selection, route generation and bus stop optimization. Parallel Cheapest Insertion heuristic and metaheuristic, Simulated Annealing, are adopted to generate school bus routes. The effectiveness of the mixed ride approach is tested for three schools with 178 synthetic students’ locations data (including 12 with wheelchair) in New York City using a fleet of 14 buses spread over four types. The results show the mixed ride approach 14.32% reduction in total travel distance and 10.46% reduction in total travel time and demonstrate that the mixed ride approach tends to return solutions with fewer vehicles, less bus stops and less average travel distance and average travel time.
Spatial Pricing of Ride-sourcing Services in a Congested Transportation Network
Fatima Afifah, University of Central FloridaShow Abstract
Zhaomiao Guo (firstname.lastname@example.org), University of Central Florida
We investigate the impacts of spatial pricing for ride-sourcing services in a Stackelberg framework considering traffic congestion. In the lower level, we use combined distribution and assignment approaches to explicitly capture the interactions between drivers' relocation, riders' mode choice, and all travelers' routing decisions. In the upper level, a single transportation network company (TNC) determines spatial pricing strategies to minimize imbalance in a two-sided market. We show the existence of the optimal pricing strategies for locational imbalance minimization, and propose effective algorithms with reliable convergence properties. Furthermore, the optimal pricing is unique and can be solved in a convex reformulation when matching time can be ignored. We conduct numerical experiments on different scales of transportation networks with different TNC objectives to generate policy insights on how spatial pricing could impact transportation systems.
ROBUST MATCHING-INTEGRATED VEHICLE REBALANCING IN RIDE-HAILING SYSTEM WITH UNCERTAIN DEMAND
Xiaotong Guo, Massachusetts Institute of Technology (MIT)Show Abstract
Nicholas Caros, Massachusetts Institute of Technology (MIT)
Jinhua Zhao (email@example.com), Massachusetts Institute of Technology (MIT)
With the rapid growth of the mobility-on-demand (MoD) market in recent years, ride-hailing companies have become an important component of the urban mobility system. There are two critical components in the operations of ride-hailing companies: driver-customer matching and vehicle rebalancing. In the previous literature, these two components are considered separately as two different problems, which could lead to potential efficiency loss for the ride-hailing system. In this paper, a novel approach, namely matching-integrated vehicle rebalancing (MIVR) model, is proposed to incorporate driver-customer matching into vehicle rebalancing problems. The MIVR model treats the diver-customer matching component at an aggregate level and minimizes a generalized cost including the total vehicle miles traveled (VMT) and the number of unsatisfied requests. To protect solutions against demand uncertainty, the robust MIVR model is proposed by introducing robust optimization (RO) techniques. Problem-specific uncertainty sets are designed for the robust MIVR model. The proposed MIVR model is tested against benchmark vehicle rebalancing models using real ride-hailing demand and travel time data from New York City (NYC). The MIVR model reduces wait times and the number of unsatisfied requests while increasing the total rebalancing distance compared to the benchmark model under most scenarios. In addition, a numerical approach is established to evaluate the robust MIVR model compared to the nominal one. The robust MIVR model produces better solutions against demand uncertainty.
An Analytical Model to Estimate Ride Pooling Traffic Impacts by Using the Macroscopic Fundamental Diagram
Aledia Bilali (firstname.lastname@example.org), Technical University of MunichShow Abstract
Ulrich Fastenrath, BMW AG
Klaus Bogenberger, Technische Universitat Munchen
Ride pooling services are considered as a customer-centric mode of transportation, but at the same time, an environmentally friendly one, due to the expected positive impacts on traffic congestion. This paper presents an analytical model that can estimate the traffic impacts of ride pooling on a city by using a previously developed shareability model, which captures the percentage of shared trips in an area, and the existence of a macroscopic fundamental diagram for the network of consideration. Moreover, the analytical model presented investigates also the impact that improving the average velocity of a city has on further increasing the percentage of shared trips in an operation area. The model is validated by means of microscopic traffic simulations for a ride pooling service operating in the city of Munich, where private vehicle trips are substituted with pooled vehicle trips for different penetration rates of the service. The results show that the average velocity in the city can be increased by up to 20% for the scenario when all the private vehicle trips are substituted with pooled vehicle trips, however the improvement is lower for smaller penetration rates of ride pooling. The operators and cities can use this study to quickly estimate the traffic impacts of introducing a ride pooling service in a certain area and for a certain set of service quality parameters.
Peak-Load Pricing and Demand Management for Ridesourcing Platforms
Cesar Yahia (email@example.com), University of Texas, AustinShow Abstract
Stephen Boyles, University of Texas, Austin
We investigate dynamic pricing mechanisms in ridesourcing systems where the platform offers users multiple trip alternatives. The offered alternatives consist of the trip cost at delayed departure times, and we seek to determine the cost associated with each offered departure time. The objective of the pricing strategy is to maximize revenue while limiting the anticipated (future) demand profile to the available driver supply. Thus, the pricing strategy depends on a probabilistic characterization of predicted spatial and temporal demand patterns. In contrast to equilibrium-based methods, we use transient analysis to evaluate state-dependent pricing policies. Simulation results using Lyft rides illustrate the trade-off between maximizing revenue and limiting future demand peaks to the available supply. In addition, we show that as the user's value of time increases, the ability of the pricing mechanism to minimize peaks in demand decreases.
A General Model of Demand-Responsive Transportation Services: From Taxi to Ridesharing to Dial-A-Ride
Carlos Daganzo, University of California, BerkeleyShow Abstract
Yanfeng Ouyang (firstname.lastname@example.org), University of Illinois, Urbana-Champaign
The paper presents a general analytic framework to model transit systems that provide door-to-door service. The model includes as special cases non-shared taxi and demand responsive transportation (DRT). In the latter we include both, paratransit services such as dial-a-ride (DAR), and the form of ridesharing (shared taxi) currently being used by crowd-sourced taxi companies like Lyft and Uber. The framework yields somewhat optimistic results because, among other things, it is deterministic and does not track vehicles across space. By virtue of its simplicity, however, the framework yields approximate closed form formulas for many cases of interest.
Optimality Conditions of the Single Bottleneck Model in the Morning Commute with Homogeneous Ridesharing Travelers and Time-varying Ridesharing Occupancy Ratio
Rui Ma (email@example.com), University of Alabama, HuntsvilleShow Abstract
This paper solves the system optimum for homogeneous ridesharing travelers on a single bottleneck corridor in the morning commute. Optimality conditions as the second-order partial derivatives of the system total cost are derived for various levels of ridesharing demand. The ridesharing occupancy ratios are time-varying and bounded with realistic consideration. The resulting system optimal dynamic ridesharing pattern helps to determine the best performance benchmark that the public agencies or the ridesharing platform can achieve by various means of system control, guidance and pricing designs.
Assessing the Effects of Limited Curbside Pickup Capacity in Meal Delivery Operations for Increased Safety during a Pandemic
Hossein Fotouhi, George Mason UniversityShow Abstract
Nicholas Mori, George Mason University
Elise Miller-Hooks, George Mason University
Vadim Sokolov, George Mason University
Sagar Sahasrabudhe, Grubhub
Meal delivery has become of increasing popularity in past years and of great importance in past months during the COVID-19 pandemic. Sustaining such services depends on maintaining provider profitability and reduced cost to consumers while continuing to support autonomy and independence for customers, restaurants, and delivery drivers (here crowdsourced drivers). This paper investigates the possible enactment of curbside regulations that limit the number of drivers simultaneously waiting at restaurants to pick up meals for delivery on both public safety and delivery efficiency. Curbside regulations would aim to increase safety by enabling social distancing between delivery personnel at pickup locations and have a secondary benefit of improving local traffic flows, which are sometimes impeded in busier, urban locations. Curbside space limits are studied in terms of their impacts on consumer-related performance measures: freshness of the food upon delivery and click-to-door time. This investigation is enabled through a proposed hybrid discrete-event and time-advanced simulation platform that replicates meal delivery service calls and pickup and delivery operations across a region built on data from a leading meal delivery company. Embedded within the simulation is an integer program that optimally assigns orders to drivers in a dynamically changing environment. Order assignments are constrained by imposed curbside capacity limits at the restaurants, and potential efficiencies and curbside violation reductions from bundling orders are assessed. Results of analyses from numerical experiments provide insights to state and local communities in designing curbside restrictions that reduce curbside crowding yet enable delivery companies to retain their profitability.
Optimal Routing of Multiple Vacant Taxis: A Policy Gradient Method with Endogenous State Transition Probabilities
Xinlian Yu (firstname.lastname@example.org), Southeast UniversityShow Abstract
Song Gao, University of Massachusetts, Amherst
This paper considers the optimal routing problem of a fleet of vacant taxis that operate under the rules set by a platform (such as Uber or Lyft), without knowledge of spatial and temporal order distribution until assigned to one by the platform. The problem is formulated as a Markov Decision Process where the state transition probabilities are determined endogenously, accounting for the dependence of taxi-passenger matching probabilities on taxi spatial distribution in the process of optimizing a stochastic policy that determines taxi spatial distribution. The stochastic policy is parameterized such that the probability of assigning taxis from a node to its adjacent links is a function of the demand rates along the links. The optimal policy parameter that maximizes the average reward is then obtained through a policy gradient method where the gradient is calculated from the differential value function. By applying the model and solution algorithm to a real network and taxi trip dataset in Shanghai, China, we show that the proposed approach is promising in terms of improving average reward over random walk. Besides, with a larger fleet size, the average reward tends to decrease due to competition among drivers.
Set Cover-based Formulation and Decomposition Solution Approach for the Crowdsourced Package Delivery Problem
Dingtong Yang, University of California, IrvineShow Abstract
Michael Hyland (email@example.com), University of California, Irvine
R. Jayakrishnan, University of California, Irvine
Motivated by the growth in e-commerce and the potential to crowdsource package delivery to people traveling in their own personal vehicles, this paper addresses the crowdsourced package delivery problem (CPDP). In the proposed crowdsourced delivery system, travelers provide their trip origin and destination locations to the system manager who assigns packages to vehicles while considering the detour (from the traveler’s original route) to deliver the packages. The paper presents a set cover-based formulation of the CPDP. Modeling the CPDP as a set cover problem enables a novel decomposition (heuristic) solution approach. The decomposition heuristic handles the packages assigned to shared personal vehicles (SPVs) and the packages assigned to dedicated vehicles (DVs) separately. For the packages assigned to SPVs, the solution approach enumerates possible SPV routes from the depot to the SPV driver’s destination. After enumerating the feasible routes for each SPV, packages are assigned to each SPV. To determine packages assigned to DVs, the paper conducts a DV cost analysis based on the estimation of vehicle routing problem (VRP) cost. The DV routes are computed using conventional VRP solvers. The paper includes a numerical case study, and the results show that the number of packages carried by SPVs has a linear relation with the total number of participating SPVs. The results also demonstrate that crowdsourced delivery has the potential to reduce delivery cost by 48% and VMT by 11%, compared to a delivery system with only DVs. The cost savings associated with using crowdsourcing delivery and SPVs mainly comes from reducing the fixed costs associated with DVs (e.g. purchasing, maintenance, insurance, added dedicated driver, etc.), rather than the gap in variable (i.e. mileage) costs between SPVs and DVs.
Dynamic Pricing in Free-Floating Carsharing Systems - A Model Predictive Control Approach
Cornelius Hardt, Technical University of MunichShow Abstract
Klaus Bogenberger, Technische Universitat Munchen
Mobility Sharing Systems (MSS) gained popularity throughout the last decade. Especially in one-way systems where users do not need to specify neither destination nor intended usage time, system operators regularly face system imbalances, where demand and vehicles are out of sync. There are two ways to encounter these situations: operator-based reallocation and user-based reallocation of vehicles. While the former utilizes paid staff, the latter tries to affect demand for vehicles to control the system towards a favorable distribution. In this paper, two approaches for user-base reallocation are presented. The myopic pricing policy only considers the current vehicle distribution as well as the demand expected in the current time-frame. The dynamic pricing policy incorporates the expected demand and the current and expected vehicle distribution within a prediction horizon. For this, a one-way MSS is modeled as Markov Decision Process featuring the vehicle distribution as states. The complexity of of the solution is reduced by applying an approximation to the state transition. Utilizing a Model Predictive Control-approach, optimal prices for the current state are determined. The impact of both proposed pricing policies is evaluated in a framework-based case study against a static pricing policy. Both dynamic policies yield an increase in profit by over 300%, while vehicle availability and average number of rentals increase by up to 8.15%and 45.8%. After all, the vehicle imbalance, measured as Root Mean Square Error, was reduced without staff-based reallocation by 11.9%.
Offline-Online Approximate Dynamic Programming for Stochastic Carsharing Systems with Relocation Incentives
Yang Liu (firstname.lastname@example.org), National University of SingaporeShow Abstract
Jiaohong Xie, National University of Singapore
Nan Chen, National University of Singapore
The carsharing service is an efficient and environmental-friendly mobility option. This study focuses on the real-time fleet management problem for one-way carsharing systems (CSS), including vehicle assignment and relocation problems, to achieve an optimal balance between demand and supply. Our modeling and solution framework integrates the offline value function approximation (VFA) policy and the online policy for dynamic decision making. The decision is made online with anticipation of uncertain future demand and travel time by learning the state value function. A novel user-based relocation strategy is integrated into the framework, in which customers are motivated to change their destinations by an incentive scheme, However, customers' behavior characteristics are unknown to the platform. Thus, we propose a Bayesian learning model to calibrate the behavior parameters online from users' responses. Numerical experiments in Singapore are carried out under different scenarios by varying the demand volume and travel time uncertainty. Our proposed offline-online policy provides solution outperforming the benchmark policies in terms of solution quality and run-time efficiency. It also overcomes the weakness of the pure VFA policy and reveals the necessity to incorporate travel time uncertainty. Our behavior learning scheme yields parameters converging to the actual values after a few online iterations. The user-based relocation strategy helps reduce the cost, and thus increase the profit.
Optimal Rebalancing and On-board Charging of Shared Electric Scooters
Jesus Javier Osorio Fuenmayor, University of Illinois, Urbana-ChampaignShow Abstract
Chao Lei, University of Illinois, Urbana-Champaign
Yanfeng Ouyang (email@example.com), University of Illinois, Urbana-Champaign
This paper presents a sequence of models for optimal charging and rebalancing of shared electric scooters (e-scooters) by allowing e-scooters to be charged while being transported on rebalancing vehicles. This problem is first modeled as a mixed-integer program for the multi-commodity inventory routing problem, where commodities represent e-scooters with different states of charge. To avoid prohibitive computation burden, continuous approximation techniques are proposed to estimate costs associated with the pickup and drop-off operations in small local neighborhoods, and the formulation turns into a discrete-continuous hybrid model for the integrated operations at both local and line-haul levels. A series of numerical experiments are conducted to demonstrate that, as compared to direct application of the discrete formulation, the proposed hybrid approach can produce good quality solutions for large-scale instances in a much shorter computation time.
Reliable Positioning and Operation of Standby Buses for Bunching Control
Antoine Petit, University of Illinois, Urbana-ChampaignShow Abstract
Yanfeng Ouyang (firstname.lastname@example.org), University of Illinois, Urbana-Champaign
Bus bunching can be mitigated by a dynamic vehicle substitution strategy in which standby buses are dispatched from predetermined locations to take over late or early buses so as to contain schedule deviations. Unlike traditional mitigation strategies such as speed control or stop skipping, this strategy requires the transit agency to make tactical location decisions as well as operational substitution decisions. This paper addresses the joint problem of finding the optimal parking locations as well as the optimal substitution policy to maximize efficiency of bunching control at the least costs for the transit agency. It also tackles the challenges associated with potentially unavailable parking locations and the possibility of using vehicles from farther backup locations that impose longer substitution lead times but allow better control over the entire service region. The optimal substitution policy under such unreliability issues is studied as an infinite-horizon stochastic dynamic program, while the expected needs for standby vehicles are used to obtain the optimal standby locations through an iterative solution process. Numerical examples show the benefits of the proposed joint decision models, and a series of sensitivity analyses are used to examine the impact of system parameters. A real-world case study is also presented to illustrate the applicability of the proposed model.
Review of Length Approximations for Tours with Few Stops
Youngmin Choi (email@example.com), University of Maryland, College ParkShow Abstract
Paul Schonfeld, University of Maryland, College Park
The shortest tour distance for visiting all points exactly once and returning to the origin is computed by solving the well-known Traveling Salesman Problem (TSP). Due to the large computational effort for optimizing TSP tours, researchers have developed approximations that relate the average length of TSP tours to the number of points n visited per tour. The existing approximations are used in transportation system planning and evaluation for estimating the distance for vehicles with a large capacity (e.g., delivery trucks) where n is relatively large. However, the approximations are derived from large instances are underestimating the TSP tour lengths for some recent delivery alternatives. The estimates of the approximation formula increase at a decreasing rate (i.e., with [[EQUATION]] ) as n increases. A comprehensive review is presented here of existing studies in approximating the TSP tour lengths for low n values, which have become important for some recently favored delivery alternatives (e.g., deliveries by bikes, drones, and robots).
Mobility Service Design via Joint Optimization of Transit Networks and Taxi Feeder Systems
Yining Liu, University of Illinois, Urbana-ChampaignShow Abstract
Yanfeng Ouyang (firstname.lastname@example.org), University of Illinois, Urbana-Champaign
This paper proposes a modeling framework to design an integrated mobility service system that is composed of local demand-responsive transportation (DRT) service and a fixed-route transit network to serve both local and long-distance trips. We select taxi fleet size and characteristics of a grid transit network structure to minimize the total agency and passenger costs. A new aspatial queuing network model is developed to capture the taxi operations when serving two types of passengers: those with randomly distributed O/D, and those with O/Ds concentrated at a set of fixed transit stations. The queuing model is integrated with the transit network design model to derive closed-form formulas for the system-wide cost, and to formulate a constrained non-linear program that optimizes the service region partition, local DRT service, and the transit network design. We apply the proposed model to a series of examples to demonstrate applicability and to show promising performance of the proposed system.
A Model and Heuristic for the Pickup and Delivery Problem with Dynamic Synchronized Transfers
Zhexi Fu, New York UniversityShow Abstract
Joseph Chow (email@example.com), New York University
Tai-Yu Ma, Luxembourg Institute of Socio-Economic Research
Microtransit and other flexible transit fleet services can reduce costs by incorporating transfers. However, transfers are costly to users if they have to get off a vehicle and wait at a stop for another pickup. A mixed integer linear programming (MILP) model is proposed to solve pickup and delivery problems with dynamic transfers, where the transfer location is determined by the MILP model rather than defined in advance and the transfer operation is strictly synchronized between vehicles within a hard time window. A heuristic algorithm is proposed to solve the problem with an acceptable solution in a much shorter computation time than commercial software. Two sets of synthetic numerical experiments are tested: 15 instances based on a 5x5 grid, and 24 different instances of varying grid sizes up to 250x250 grids to test scalability. The results show that adding dynamic transfers in microtransit can further reduce the total cost in more than 60% of scenarios. The heuristic on average has an optimality gap less than 10% while having a fraction of the run time and can scale up to 250x250 grids with run times within 5 minutes. We find the transfer strategy works better on grid-based networks with larger fleet size and higer request demands.
Planning Bus Systems for Mega-Cities: A Case Study for Beijing
Xuejie Liu, Beijing Jiaotong UniversityShow Abstract
Jiazheng Zhu, Beijing Transport Institute
Tengteng Ma, Beijing Transport Institute
Yanfeng Ouyang, University of Illinois, Urbana-Champaign
Carlos Daganzo, University of California, Berkeley
This paper presents and tests a method to design hierarchical bus networks for large-scale polycentric urban areas. The method produces conceptual plans based on geometric idealizations of regional networks intended to serve medium-distance trips, and then adapts such conceptual plans into implementable designs. Also considered are a supportive backbone system for long distance trips and a last-mile system for local trips. The focus is the medium distance system since this system is not well understood for megacities. Mathematical optimization is used to develop the regional plans. The objective function is composed of analytic formulae for a concept’s agency and user costs. These formulae include as decision variables each network’s total service distance, the total number of stops, and the service headway. The proposed method is applied to Beijing, China. The proposed solution includes 6531 km of directional bus service routes and 4825 stops, uses about 6243 vehicles and costs 1.43 million CNY/h to run, and yet the target passengers’ average door-to-door travel time is approximately 53.6 min. These numbers are considerable improvements. They are, respectively, about 53% of the agency cost currently used to provide bus service, and 79% of the current passenger travel time experienced in Beijing.
DISCLAIMER: All information shared in the TRB Annual Meeting Online Program is subject to change without notice. Changes, if necessary, will be updated in the Online Program and this page is the final authority on schedule information.