Large-scale optimization under uncertainty: applications to logistics and healthcare

Abstract

Many decision making problems in real life are affected by uncertainty. The area of optimization under uncertainty has been studied widely and deeply for over sixty years, and it continues to be an active area of research. The overall aim of this thesis is to contribute to the literature by developing (i) theoretical models that reflect problem settings closer to real life than previously considered in literature, as well as (ii) solution techniques that are scalable. The thesis focuses on two particular applications to this end, the vehicle routing problem and the problem of patient scheduling in a healthcare system. The first part of this thesis studies the vehicle routing problem, which asks for a cost-optimal delivery of goods to geographically dispersed customers. The probability distribution governing the customer demands is assumed to be unknown throughout this study. This assumption positions the study into the domain of distributionally robust optimization that has a well developed literature, but had so far not been extensively studied in the context of the capacitated vehicle routing problem. The study develops theoretical frameworks that allow for a tractable solution of such problems in the context of rise-averse optimization. The overall aim is to create a model that can be used by practitioners to solve problems specific to their requirements with minimal adaptations. The second part of this thesis focuses on the problem of scheduling elective patients within the available resources of a healthcare system so as to minimize overall years of lives lost. This problem has been well studied for a long time. The large scale of a healthcare system coupled with the inherent uncertainty affecting the evolution of a patient make this a particularly difficult problem. The aim of this study is to develop a scalable optimization model that allows for an efficient solution while at the same time enabling a flexible modelling of each patient in the system. This is achieved through a fluid approximation of the weakly-coupled counting dynamic program that arises out of modeling each patient in the healthcare system as a dynamic program with states, actions, transition probabilities and rewards reflecting the condition, treatment options and evolution of a given patient. A case-study for the National Health Service in England highlights the usefulness of the prioritization scheme obtained as a result of applying the methodology developed in this study.