Integrated Vehicle Routing and Service Scheduling under Time and Cancellation Uncertainties with Application in Non-Emergency Medical Transportation

In this paper, we consider an integrated vehicle routing and service scheduling problem for serving customers in distributed locations who need pick-up, drop-off or delivery services. We take into account the random trip time, non-negligible service time and possible customer cancellations, under which an ill-designed schedule may lead to undesirable vehicle idleness and customer waiting. … Read more

On the Value of Multistage Risk-Averse Stochastic Facility Location With or Without Prioritization

We consider a multiperiod stochastic capacitated facility location problem under uncertain demand and budget in each period. Using a scenario tree representation of the uncertainties, we formulate a multistage stochastic integer program to dynamically locate facilities in each period and compare it with a two-stage approach that determines the facility locations up front. In the … Read more

Improving Column-Generation for Vehicle Routing Problems via Random Coloring and Parallelization

We consider a variant of the Vehicle Routing Problem (VRP) where each customer has a unit demand and the goal is to minimize the total cost of routing a fleet of capacitated vehicles from one or multiple depots to visit all customers. We propose two parallel algorithms to efficiently solve the column-generation based linear-programming relaxation … Read more

Sequential Competitive Facility Location: Exact and Approximate Algorithms

We study a competitive facility location problem (CFLP), where two firms sequentially open new facilities within their budgets, in order to maximize their market shares of demand that follows a probabilistic choice model. This process is a Stackelberg game and admits a bilevel mixed-integer nonlinear program (MINLP) formulation. We derive an equivalent, single-level MINLP reformulation … Read more

A Shared Mobility Based Framework for Evacuation Planning and Operations under Forecast Uncertainty

To meet evacuation needs from carless populations who may require personalized assistance to evacuate safely, we propose a ridesharing-based evacuation program that recruits volunteer drivers before a disaster strikes, and then matches volunteers with evacuees who need assistance once demand is realized. We optimize resource planning and evacuation operations under uncertain spatiotemporal demand, and construct … Read more

Multistage Distributionally Robust Mixed-Integer Programming with Decision-Dependent Moment-Based Ambiguity Sets

We study multistage distributionally robust mixed-integer programs under endogenous uncertainty, where the probability distribution of stage-wise uncertainty depends on the decisions made in previous stages. We first consider two ambiguity sets defined by decision-dependent bounds on the first and second moments of uncertain parameters and by mean and covariance matrix that exactly match decision-dependent empirical … Read more

Distributionally Robust Facility Location Problem under Decision-dependent Stochastic Demand

Facility location decisions significantly impact customer behavior and consequently the resulting demand in a wide range of businesses. Furthermore, sequentially realized uncertain demand enforces strategically determining locations under partial information. To address these issues, we study a facility location problem where the distribution of customer demand is dependent on location decisions. We represent moment information … Read more

Distributionally Robust Partially Observable Markov Decision Process with Moment-based Ambiguity

We consider a distributionally robust Partially Observable Markov Decision Process (DR-POMDP), where the distribution of the transition-observation probabilities is unknown at the beginning of each decision period, but their realizations can be inferred using side information at the end of each period after an action being taken. We build an ambiguity set of the joint … Read more

Benders Cut Classification via Support Vector Machines for Solving Two-stage Stochastic Programs

We consider Benders decomposition for solving two-stage stochastic programs with complete recourse based on finite samples of the uncertain parameters. We define the Benders cuts binding at the final optimal solution or the ones significantly improving bounds over iterations as valuable cuts. We propose a learning-enhanced Benders decomposition (LearnBD) algorithm, which adds a cut classification … Read more

An Approximation Algorithm for Vehicle Routing with Compatibility Constraints

We study a multiple-vehicle routing problem with a minimum makespan objective and compatibility constraints. We provide an approximation algorithm and a nearly-matching hardness of approximation result. We also provide computational results on benchmark instances with diverse sizes showing that the proposed algorithm (i) has a good empirical approximation factor, (ii) runs in a short amount … Read more