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.

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.

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.

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.