Tackling car-sharing service design problems at scale with high-resolution data : discrete simulation-based optimization approaches

Abstract

This thesis considers the design of two-way (i.e., round-trip) car-sharing services. The optimization problems are formulated as high-dimensional discrete simulation-based optimization (DSO) problems. Existing DSO algorithms cannot tackle these problems at scale. Moreover, they are designed based on asymptotic performance guarantees, but lack computational efficiency, i.e., they tend to not perform well under tight computational or simulation budgets. The main contribution of this thesis is to show how mixed-integer programming (MIP) models can be used to enable general-purpose DSO algorithms to become: (i) scalable: the car-sharing problems can now be tackled at scale; and (ii) computationally efficient: solutions with good performance can be identified given tight computational budgets.

More generally, the methods proposed in this thesis contribute to bridging the gap between these two mostly disconnected research communities of analytical optimization and simulation-based optimization. This thesis formulates MIP models and proposes two approaches to embed the MIP information within the DSO algorithms. First, we use a MIP to formulate a metamodel, which is an analytical approximation of the simulation-based objective function. The information from the MIP is used at every iteration of a DSO algorithm by solving an analytical metamodel optimization problem. Second, we use a MIP to enhance the partitioning step of an existing globally convergent DSO algorithm. The MIP is used to identify low-dimensional subregions of the feasible region, where more exhaustive simulation is to be carried out.

We then compare the performance of methods that either: (i) use the MIP information for metamodeling, (ii) use the MIP information for partitioning, or (iii) use the MIP information for both metamodeling and partitioning. We study how the MIP's accuracy impacts the performance of these methods. Based on both small synthetic problems and a Boston area case study, we show how the scalability and the computational efficiency of both a general-purpose locally convergent DSO algorithm and a general-purpose globally convergent DSO algorithm are enhanced. We also present results from a New York City case study. The case studies use detailed car-sharing reservation data from a major car-sharing operator. We benchmark the methods versus several algorithms, including stochastic programming. The combination of MIPs with DSO algorithms leads to methods with both asymptotic performance guarantees as well as good short-term performance.