Reinforcement Learning Applied to the Dynamic Capacitated Profitable Tour Problem with Stochastic Requests

This paper investigates the Dynamic Capacitated Profitable Tour Problem with Stochastic Requests (DCPTPSR), a variant of the Traveling Salesman Problem (TSP) with profits. In the DCPTPSR, online decisions must be made for accepting and scheduling requests over a finite number of periods. Requests follow a discrete-time stochastic process, and each request is characterized by a location, demand, and prize. Accepted requests must be served on a TSP tour such that the collected prize minus the transportation costs becomes maximal. The DCPTPSR has practical applications in food delivery and less-than-truckload transportation, where requests arrive in an online fashion and immediate decisions about acceptance and scheduling must be made. We model the DCPTPSR by a Markov Decision Process (MDP) and propose a Stochastic Dynamic Programming (SDP) algorithm for solving the problem to optimality. Addressing the computational challenges involved in SDP, we present a framework that integrates Reinforcement Learning (RL) as an alternative solution method. We perform an extensive numerical study where instances with up to incoming 25 requests can be solved by SDP while our RL approach can be used to adequately solve instances with even up to 100 incoming requests. Particularly, the performance of the RL approach is very close to the optimal policy by SDP and outperforms both the first come first serve heuristic and the first accept traveling salesman algorithm. The latter algorithm accepts requests if the available capacity enables it and fulfills these demands in an optimal TSP tour afterward. Especially instances with scarce capacity show considerable potential for savings in request acceptance and transportation scheduling decisions if both decisions are made simultaneously.