Modeling and strategy for production planning problem and spatial ride-hailing system

Abstract

This thesis focuses on two fundamental problems in modern industry: Production Planning problem in Supply Chain System and Optimal Matching Problem in Ride-hailing System. In the first part, we propose an efficient and flexible decomposition framework for solving large-scale production planning and scheduling problem, which essentially is a huge mixed-integer programming problem. We focus on several levels of decomposition: from the model perspective, we filter necessary and valid variables and constraints out of the original problem before construction; for items with similar BOM structures, we divide them into groups based on spectral clustering analysis and generate a series of subproblems; we calculate the priority order for these problems and progressively denote two subproblems with current highest priority as Master problem and Auxiliary problem, which are solved in a parallel fashion; to decompose the Master Problem from the time perspective, we combine LP relaxation and rolling horizon strategy output a near-optimal solution. The freedom to choose filtration intensity, subproblems numbers, and the truncated time window length makes our decomposition algorithm flexible and adaptive. Numerically, the gap between the optimal solution to the original problem and the one to our decomposition algorithm is small, and the overall construction and solving time is significantly shortened. In the second part, we study the optimal threshold matching policy in a three-stage flexible queueing model for a spatial ride-hailing system with two types of passengers and drivers, aiming to maximize the throughput and profit for the system. We first get accurate performance evaluations from a fluid approximation and obtain optimal solutions based on the unique equilibrium of the fluid process. Furthermore, we design an adaptive profit maximization algorithm based on the optimality condition to solve problems with time-varying arrival rates. Simulations provide convincing verification of the near-optimality of our threshold matching policy and algorithm.

Date of Award	2021
Original language	English
Awarding Institution	The Hong Kong University of Science and Technology
Supervisor	Jiheng ZHANG (Supervisor)