Search

We study an integrated airline schedule design and fleet assignment model for constructing schedules by simultaneously selecting from a pool of optional flights and assigning fleet types to these scheduled flights. This is a crucial tactical decision which greatly influences airline profit. As passenger demand is often substitutable among available fare products between the same origin-destination pair, we study an optimization model that integrates within it a passenger choice model for fare product selections. To tackle the formidable computational challenge of solving this large-scale network design problem, we propose a decomposition approach based on partitioning the flight network into smaller subnetworks by exploiting weak dependency in the network structure. The decomposition relies on a series of approximation analyses and a novel fare split problem to reliably measure the approximation quality introduced by the partition by optimally allocating fares of products shared by flights in different subnetworks. We present several reformulations by representing fleet assignment and schedule decisions using composite variables and formally characterize the relationship of their strengths. This gives rise to a new reformulation that is able to flexibly trade off strength and size. We conduct detailed computational experiments using two realistically sized airline instances to demonstrate the effectiveness of our approach. Under a simulated passenger booking environment with both perfect and imperfect forecasts, we show that the fleeting and scheduling decisions informed by our approach deliver significant and robust profit improvement over benchmark implementations and previous models in the literature.

Motivated by growing applications in two-sided markets, we study a parallel matching queue with reneging. Demand and supply units arrive to the system and are matched in an FCFS manner according to a compatibility graph specified by an N-system. If they cannot be matched upon arrival, they queue and may abandon the system as time goes by. We derive explicit product forms of the steady state distributions of this system by identifying a partial balance condition.

Ride‐hailing platforms such as Uber, Lyft, and DiDi have achieved explosive growth and reshaped urban transportation. The theory and technologies behind these platforms have become one of the most active research topics in the fields of economics, operations research, computer science, and transportation engineering. In particular, advanced matching and dynamic pricing (DP) algorithms—the two key levers in ride‐hailing—have received tremendous attention from the research community and are continuously being designed and implemented at industrial scales by ride‐hailing platforms. We provide a review of matching and DP techniques in ride‐hailing, and show that they are critical for providing an experience with low waiting time for both riders and drivers. Then we link the two levers together by studying a pool‐matching mechanism called dynamic waiting (DW) that varies rider waiting and walking before dispatch, which is inspired by a recent carpooling product Express Pool from Uber. We show using data from Uber that by jointly optimizing DP and DW, price variability can be mitigated, while increasing capacity utilization, trip throughput, and welfare. We also highlight several key practical challenges and directions of future research from a practitioner's perspective.

We study the matching of jobs to workers in a queue, e.g. a ridesharing platform dispatching drivers to pick up riders at an airport. Under FIFO dispatching, the heterogeneity in trip earnings incentivizes drivers to cherry-pick, increasing riders' waiting time for a match and resulting in a loss of efficiency and reliability. We first present the direct FIFO mechanism, which offers lower-earning trips to drivers further down the queue. The option to skip the rest of the line incentivizes drivers to accept all dispatches, but the mechanism would be considered unfair since drivers closer to the head of the queue may have lower priority for trips to certain destinations. To avoid the use of unfair dispatch rules, we introduce a family of randomized FIFO mechanisms, which send declined trips gradually down the queue in a randomized manner. We prove that a randomized FIFO mechanism achieves the first best throughput and the second best revenue in equilibrium. Extensive counterfactual simulations using data from the City of Chicago demonstrate substantial improvements of revenue and throughput, highlighting the effectiveness of using waiting times to align incentives and reduce the variability in driver earnings.

Motivated in part by online marketplaces such as ridesharing and freelancing platforms, we study two-sided matching markets where agents are heterogeneous in their compatibility with different types of jobs: flexible agents can fulfill any job, whereas each specialized agent can only be matched to a specific subset of jobs. When the set of jobs compatible with each agent is known, the full-information first-best throughput (i.e. number of matches) can be achieved by prioritizing dispatch of specialized agents as much as possible. When agents are strategic, however, we show that such aggressive reservation of flexible capacity incentivizes flexible agents to pretend to be specialized. The resulting equilibrium throughput could be even lower than the outcome under a baseline policy, which does not reserve flexible capacity, and simply dispatches jobs to agents at random. To balance matching efficiency with agents' strategic considerations, we introduce a novel robust capacity reservation policy (RCR). The RCR policy retains a similar structure to the first best policy, but offers additional and seemingly incompatible edges along which jobs can be dispatched. We show a Braess' paradox-like result, that offering these additional edges could sometimes lead to worse equilibrium outcomes. Nevertheless, we prove that under any market conditions, and regardless of agents' strategies, the proposed RCR policy always achieves higher throughput than the baseline policy. Our work highlights the importance of considering the interplay between strategic behavior and capacity allocation policies in service systems.

Most voting methods can only deal with a finite number of candidates. In practice, there are important voting applications where the candidate space is continuous. We describe a new voting method by extending the Majority Judgment voting and ranking method to handle a continuous candidate space which is modeled as a convex set. We characterize the structure of the winner determination problem and present a practical iterative voting procedure for finding a (or the) winner when voter preferences are unknown.

In operating modern bike-sharing systems, understanding rider demand and behaviors is of significant importance. A key challenge in estimating demand is to account for the choice substitution effect, where a rider may substitute a trip for stations nearby when the first-choice location for picking up or returning a bike is not available. In this paper, we study and analyze a locational demand model to account for substitution behaviors that are determined by proximity. The model assumes that riders originate from a region in space, and each has a heterogeneous consideration radius to find stations with available bikes in the order of closeness to their locations. We study a natural parameterization of this model with distance rankings, each corresponding to a distance ordering of stations within the consideration radius of a rider from a particular origin. We characterize the conditions under which the model is identifiable and its parameters can be consistently estimated. By exploiting the locational structure and sparsity in stock-out patterns, which are inherent to bike-sharing systems, we find sparse representations of the model parameters and develop efficient first-order methods for estimating the parameters. Our approach is tractable on a city scale and has good empirical performance, which we demonstrate on a bike-sharing system in the Boston metropolitan area.

© 2018 Elsevier Ltd Three decades of research studies in ground delay program (GDP) decision-making, and air traffic flow management in general, have produced several analytical models and decision support tools to design GDPs with minimum delay costs. Most of these models are centralized, i.e., the central authority almost completely decides the GDP design by optimizing certain centralized objectives. In this paper, we assess the benefits of an airline-driven decentralized approach for designing GDPs. The motivation for an airline-driven approach is the ability to incorporate the inherent differences between airlines when prioritizing, and responding to, different GDP designs. Such differences arise from the airlines’ diverse business objectives and operational characteristics. We develop an integrated platform for simulating flight operations during GDPs, an airline recovery module for mimicking the recovery actions of each individual airline under a GDP, and an algorithm for fast solution of the recovery problems to optimality. While some of the individual analytical components of our framework, model and algorithm share certain similarities with those used by previous researchers, to the best of our knowledge, this paper presents the first comprehensive platform for simulating and optimizing airline operations under a GDP and is the most important technological contribution of this paper. Using this framework, we conduct detailed computational experiments based on actual schedule data at three of the busiest airports in the United States. We choose the recently developed Majority Judgment voting and grading method as our airline-driven decentralized approach for GDP design because of the superior theoretical and practical benefits afforded by this approach as shown by multiple recent studies. The results of our evaluation suggest that adopting this airline-driven approach in designing the GDPs consistently and significantly reduces airport-wide delay costs compared to the state-of-the-research centralized approaches. Moreover, the cost reduction benefits of the resultant airline-driven GDP designs are equitably distributed across different airlines.

Ride-hailing platforms such as Uber, Lyft and DiDi have achieved explosive growth and reshaped urban transportation. The theory and technologies behind these platforms have become one of the most active research topics in the fields of economics, operations research, computer science, and transportation engineering. In particular, advanced matching and dynamic pricing algorithms -- the two key levers in ride-hailing -- have received tremendous attention from the research community and are continuously being designed and implemented at industrial scales by ride-hailing platforms. We provide a review of matching and dynamic pricing techniques in ride-hailing, and show that they are critical for providing an experience with low waiting time for both riders and drivers. Then we link the two levers together by studying a pool-matching mechanism called dynamic waiting that varies rider waiting and walking before dispatch, which is inspired by a recent carpooling product Express Pool from Uber. We show using data from Uber that by jointly optimizing dynamic pricing and dynamic waiting, price variability can be mitigated, while increasing capacity utilization, trip throughput, and welfare. We also highlight several key practical challenges and directions of future research from a practitioner's perspective.

Most of the existing voting methods deal with a moderate (or at least finite) number of candidates. In practice, there are important voting applications where candidate space is huge or even of infinite size. We describe new methods in voting by extending the Majority Judgment voting and ranking method to handle a candidate space of infinite size. Specifically, the candidate space is modeled as a polyhedral set. Two approaches are developed. The first approach relies on multiple rounds of grading and iterative candidate generation. The candidate generation employs a novel mixed-integer programming model. The second approach employs a robust optimization framework and only takes as input each voters most preferred candidate. This results in an output vector which is the candidate that has the best worst-case guarantee in terms of majority grade. We demonstrate the effectiveness of our approaches through two case studies involving voting over polyhedral candidate space.

It is well recognized that the left turn reduces the intersection capacity significantly, because some of the traffic lanes cannot be used to discharge vehicles during its green phases. In this paper, we operationalize the phase swap sorting strategy (Xuan, 2011) to use most, if not all, traffic lanes to discharge vehicles at the intersection cross-section to increase its capacity. We explicitly take into consideration all through, left- and right-turning movements on all arms and formulate the capacity maximization problem as a Binary-Mixed-Integer-Linear-Programming (BMILP) model. The model is efficiently solved by standard branch-and-bound algorithms and outputs optimal signal timings, lane allocations, and other decisions. Numerical experiments show that substantially higher reserve capacity can be obtained under our approach.

In this paper, we analyze the effectiveness of the 2010 Tarmac Delay Rule from a passenger-centric point of view. The Tarmac Delay Rule stipulates that aircraft lift-off, or an opportunity for passengers to deplane, must occur no later than 3 h after the cabin door closure at the gate of the departure airport; and that an opportunity for passengers to deplane must occur no later than 3 h after the touchdown at the arrival airport. The Tarmac Delay Rule aims to protect enplaned passengers on commercial aircraft from excessively long delays on the tarmac upon taxi-out or taxi-in, and monetarily penalizes airlines that violate the stipulated 3-h tarmac time limit. Comparing the actual flight schedule and delay data after the Tarmac Delay Rule was in effect with that before, we find that the Rule has been highly effective in reducing the frequency of occurrence of long tarmac times. However, another significant effect of the rule has been the rise in flight cancellation rates. Cancellations result in passengers requiring rebooking, and often lead to extensive delay in reaching their final destinations. Using an algorithm to estimate passenger delay, we quantify delays to passengers in 2007, before the Tarmac Delay Rule was enacted, and compare these delays to those estimated for hypothetical scenarios with the Tarmac Delay Rule in effect for that same year. Our delay estimates are calculated using U.S. Department of Transportation data from 2007. Through our results and several sensitivity analyses, we show that the overall impact of the current Tarmac Delay Rule is a significant increase in passenger delays, especially for passengers scheduled to travel on the flights which are at risk of long tarmac delays. We evaluate the impacts on passengers of a number of rule variations, including changes to the maximum time on the tarmac, and variations in that maximum by time-of-day. Through extensive scenario analyses, we conclude that a better balance between the conflicting objectives of reducing the frequency of long tarmac times and reducing total passenger delays can be achieved through a modified version of the existing rule. This modified version involves increasing the tarmac time limit to 3.5 h and only applying the rule to flights with planned departure times before 5pm. Finally, in order to implement the Rule more effectively, we suggest the tarmac time limit to be defined in terms of the time when the aircraft begin returning to the gate instead of being defined in terms of the time when passengers are allowed to deplane. Keywords: Aviation, Tarmac Delay Rule, Passenger disruption and delay, National Center for Excellence for Aviation Operations Research (U.S.)

We propose a robust optimization approach to minimize total propagated delay in the aircraft routing problem. Instead of minimizing the expected total propagated delay by assuming that flight leg delays follow specific probability distributions, our model minimizes the maximal possible total propagated delay when flight leg delays lie in a prespecified uncertainty set. We develop exact and tractable solution approaches for our robust model. The major contribution of our model is that it allows us to explicitly model and handle correlation in flight leg delays (e.g., because of weather or various air traffic management initiatives) that existing approaches cannot efficiently incorporate. Using both historical delay data and simulated data, we evaluate the performance of our model and benchmark against the state-of-the-research stochastic approach. In most of the cases, we observe that our model outperforms the existing approach in lowering the mean, reducing volatility, and mitigating extreme values of total propagated delay. In the cases where a deficit in one of the three criteria exists, gains in the other two criteria usually offset this disadvantage. These results suggest that robust optimization approaches can provide promising results for the aircraft routing problem. The online appendix is available at https://doi.org/10.1287/trsc.2015.0657 .

It is well recognized that the left turn reduces the intersection capacity significantly, because some of the tra ffic lanes cannot be used to discharge vehicles during its green phases. In this paper, we operationalize the phase swap sorting strategy (Xuan, 2011) to use most, if not all, traffi c lanes to discharge vehicles at the intersection cross section to increase its capacity. We explicitly take into consideration all through, left- and right-turning movements on all arms and formulate the capacity maximization problem as a Binary-Mixed-Integer-Linear-Programming (BMILP) model. The model is e fficiently solved by standard branch-and-bound algorithms and outputs optimal signal timings, lane allocations, and other decisions. Numerical experiments show that substantially higher reserve capacity can be obtained under our approach.