We consider chance-constrained binary programs, where each row of the inequalities that involve uncertainty needs to be satisfied probabilistically. Only the information of the mean and covariance matrix is available, and we solve distributionally robust chance-constrained binary programs (DCBP). Using two different ambiguity sets, we equivalently reformulate the DCBPs as 0-1 second-order cone (SOC) programs. We further exploit the submodularity of 0-1 SOC constraints under special and general covariance matrices, and we utilize the submodularity as well as lifting to derive extended polymatroid inequalities to strengthen the 0-1 SOC formulations. We incorporate the valid inequalities in a branch-and-cut algorithm for efficiently solving DCBPs. We demonstrate the computational efficacy and solution performance using diverse instances of a chance-constrained bin packing problem.

We consider a single-server scheduling problem given a fixed sequence of appointment arrivals with random no-shows and service durations. The probability distribution of the uncertain parameters is assumed to be ambiguous, and only the support and first moments are known. We formulate a class of distributionally robust (DR) optimization models that incorporate the worst-case expectation/conditional value-at-risk penalty cost of appointment waiting, server idleness, and overtime into the objective or constraints. Our models flexibly adapt to different prior beliefs of no-show uncertainty. We obtain exact mixed-integer nonlinear programming reformulations and derive valid inequalities to strengthen the reformulations that are solved by decomposition algorithms. In particular, we derive convex hulls for special cases of no-show beliefs, yielding polynomial-sized linear programming models for the least and the most conservative supports of no-shows. We test various instances to demonstrate the computational efficacy of our approaches and to compare the results of various DR models given perfect or ambiguous distributional information. The e-companion is available at https://doi.org/10.1287/opre.2017.1656 .

Carsharing has been considered as an effective means to increase mobility and reduce personal vehicle usage and related carbon emissions. In this paper, we consider problems of allocating a carshare fleet to service zones under uncertain one-way and round-trip rental demand. We employ a two-stage stochastic integer programming model, in the first stage of which we allocate shared vehicle fleet and purchase parking lots or permits in reservation-based or free-floating systems. In the second stage, we generate a finite set of samples to represent demand uncertainty and construct a spatial–temporal network for each sample to model vehicle movement and the corresponding rental revenue, operating cost, and penalties from unserved demand. We minimize the expected total costs minus profit and develop branch-and-cut algorithms with mixed-integer, rounding-enhanced Benders cuts, which can significantly improve computation efficiency when implemented in parallel computing. We apply our model to a data set of Zipcar in the Boston–Cambridge, Massachusetts, area to demonstrate the efficacy of our approaches and draw insights on carshare management. Our results show that exogenously given one-way demand can increase carshare profitability under given one-way and round-trip price differences and vehicle relocation cost whereas endogenously generated one-way demand as a result of pricing and strategic customer behavior may decrease carshare profitability. Our model can also be applied in a rolling-horizon framework to deliver optimized vehicle relocation decisions and achieve significant improvement over an intuitive fleet-rebalancing policy. The online appendix is available at https://doi.org/10.1287/msom.2017.0644 .

Through smartphone apps, drivers and passengers can dynamically enter and leave ride-hailing platforms. As a result, ride-pooling is challenging due to complex system dynamics and different objectives of multiple stakeholders. In this paper, we study ride-pooling with no more than two passenger groups who can share rides in the same vehicle. We dynamically match available drivers to randomly arriving passengers and also decide pick-up and drop-off routes. The goal is to minimize a weighted sum of passengers' waiting time and trip delay time. A spatial-and-temporal decomposition heuristic is applied and each subproblem is solved using Approximate Dynamic Programming (ADP), for which we show properties of the approximated value function at each stage. Our model is benchmarked with the one that optimizes vehicle dispatch without ride-pooling and the one that matches current drivers and passengers without demand forecasting. Using test instances generated based on the New York City taxi data during one peak hour, we conduct computational studies and sensitivity analysis to show (i) empirical convergence of ADP, (ii) benefit of ride-pooling, and (iii) value of future supply-demand information.