Marvin Caspar

• This cumulative dissertation is composed of five individual research papers that focus on request acceptance and scheduling decisions in different operations research environments. Fundamentally, this work studies the Capacitated Profitable Tour Problem (CPTP), a routing optimization problem in which a subset of requests is selected to maximize total profit while respecting vehicle capacity constraints and visiting their associated locations. In this background, coordinated scheduling of accepted requests can induce nonlinear cost effects, as routing costs generally do not scale proportionally with the distances between locations. On the one hand, the CPTP is studied in dynamic and stochastic sequential decision-making environments, where decisions are made over time under uncertainty. On the other hand, static and deterministic variants of the CPTP are considered to provide insights into optimal policies and ex-post solutions derived under full information. Furthermore, different subtour elimination constraints are analyzed for their computational efficiency in solving the CPTP. Regarding problem extensions, the impact of allowing split deliveries and incomplete services in the CPTP is investigated in detail. In addition to studying the CPTP, this dissertation introduces the dynamic and stochastic multidimensional knapsack problem with a generalized upper bound, in which item classes arrive sequentially under uncertainty, and at most one item from each arriving class may be accepted to schedule resource consumption. Methodologically, this dissertation develops Markov decision process formulations and mixed-integer linear programming formulations for various request acceptance and scheduling problems. Based on these formulations, optimal, approximate, and heuristic policies are derived to solve the corresponding problems. Building on recent advances in machine learning, extensive computational experiments on well-established benchmark datasets demonstrate the strong potential of reinforcement learning and value function approximation methods for dynamic and stochastic decision-making in request acceptance and scheduling environments. In addition to advancing the academic literature through the development of new models, solution methods, applications, and results, this dissertation makes a practical contribution by releasing open-source software implementations of model formulations and proposed solution methods.