Solution methods for the dynamic and probabilistic profitable tour problem

Abstract Sequential decision-making under uncertainty plays a fundamental role in domains such as finance, healthcare, and supply chain management. Multistage stochastic programming and stochastic dynamic programming provide powerful mathematical frameworks for optimizing multistage decisions, but their practicality is often limited by the curse of dimensionality. To overcome this limitation, scalable approximate methods, such as reinforcement learning, have gained prominence. A central area of application is revenue management, historically used in the airline industry and now increasingly relevant in digital commerce, where demand management and logistics are closely intertwined. Motivated by these challenges, this paper studies the Dynamic and Probabilistic Profitable Tour Problem (DPPTP), a sequential decision-making problem involving two interdependent phases: an online phase, in which requests arrive dynamically and must be accepted or rejected in real-time, and an offline phase, in which accepted requests must be fulfilled by solving a Traveling Salesman Problem. We formulate the DPPTP as a Markov Decision Process and derive a stochastically optimal decision-making policy. Given the computational intractability of computing optimal policies for larger instances, we investigate heuristic and approximate solution methods, with a particular focus on Proximal Policy Optimization (PPO), a reinforcement learning algorithm. Our computational study provides a comprehensive evaluation of PPO’s performance relative to optimal and heuristic benchmarks, demonstrating that it achieves near-optimal performance while scaling effectively to problem instances with up to 96 distinct requests.