Search for: All records

We study the mean-standard deviation minimum cost flow (MSDMCF) problem, where the objective is minimizing a linear combination of the mean and standard deviation of flow costs. Due to the nonlinearity and nonseparability of the objective, the problem is not amenable to the standard algorithms developed for network flow problems. We prove that the solution for the MSDMCF problem coincides with the solution for a particular mean-variance minimum cost flow (MVMCF) problem. Leveraging this result, we propose bisection (BSC), Newton–Raphson (NR), and a hybrid (NR-BSC)—method seeking to find the specific MVMCF problem whose optimal solution coincides with the optimal solution for the given MSDMCF problem. We further show that this approach can be extended to solve more generalized nonseparable parametric minimum cost flow problems under certain conditions. Computational experiments show that the NR algorithm is about twice as fast as the CPLEX solver on benchmark networks generated with NETGEN. 

This study proposes a multi-period facility location formulation to maximize coverage while meeting a coverage reliability constraint. The coverage reliability constraint is a chance constraint limiting the probability of failure to maintain the desired service standard, commonly followed by emergency medical services and fire departments. Further, uncertainties in the failure probabilities are incorporated by utilizing robust optimization using polyhedral uncertainty sets, which results in a compact mixed-integer linear program. A case study in the Portland, OR metropolitan area is analyzed for employing unmanned aerial vehicles (UAVs) or drones to deliver defibrillators in the region to combat out-of-hospital cardiac arrests. In the context of this study, multiple periods represent periods with different wind speed and direction distributions. The results show that extending to a multi-period formulation, rather than using average information in a single period, is particularly beneficial when either response time is short or uncertainty in failure probabilities is not accounted for. Accounting for uncertainty in decision-making improves coverage significantly while also reducing variability in simulated coverage, especially when response times are longer. Going from a single-period deterministic formulation to a multi-period robust formulation boosts the simulated coverage values by 57%, on average. The effect of considering a distance-based equity metric in decision-making is also explored. 

Increasing e-commerce activity, competition for shorter delivery times, and innovations in transportation technologies have pushed the industry toward instant delivery logistics. This paper studies a facility location and online demand allocation problem applicable to a logistics company expanding to offer instant delivery service using unmanned aerial vehicles or drones. The problem is decomposed into two stages. During the planning stage, the facilities are located, and product and battery capacity are allocated. During the operational stage, customers place orders dynamically and real-time demand allocation decisions are made. The paper explores a multi-armed bandit framework for maximizing the cumulative reward realized by the logistics company subject to various capacity constraints and compares it with other strategies. The multi-armed bandit framework provides about 7% more rewards than the second-best strategy when tested on standard test instances. A case study based in Portland Metro Area showed that multi-armed bandits can outperform the second-best strategy by more than 20%. 

Given a set of a spatially distributed demand for a specific commodity, potential facility locations, and drones, an agency is tasked with locating a pre-specified number of facilities and assigning drones to them to serve the demand while respecting drone range constraints. The agency seeks to maximize the demand served while considering uncertainties in initial battery availability and battery consumption. The facilities have a limited supply of the commodity being distributed and also act as a launching site for drones. Drones undertake one-to-one trips (from located facility to demand location and back) until their available battery energy is exhausted. This paper extends the work done by Chauhan et al. and presents an integer linear programming formulation to maximize coverage using a robust optimization framework. The uncertainty in initial battery availability and battery consumption is modeled using a penalty-based approach and gamma robustness, respectively. A novel robust three-stage heuristic (R3SH) is developed which provides objective values which are within 7% of the average solution reported by MIP solver with a median reduction in computational time of 97% on average. Monte Carlo simulation based testing is performed to assess the value of adding robustness to the deterministic problem. The robust model provides higher and more reliable estimates of actual coverage under uncertainty. The average maximum coverage difference between the robust optimization solution and the deterministic solution is 8.1% across all scenarios.