A New Deep Reinforcement Learning Algorithm for the Online Stochastic Profitable Tour Problem

Abstract

This work presents an end-to-end framework for solving online stochastic optimization problems based on deep reinforcement learning. In particular, we focus on an online stochastic version of the profitable tour problem (PTP), which is a variant of the TSP with profits. The goal is to pick a subset of customers and maximize the total profits made from these customers, from which the total travel costs have to be subtracted. Profits are modeled through time-dependent random variables, whose realizations become available online. Most classical heuristic solution methods for combinatorial optimization problems require in-depth knowledge and expertise about the respective problem. In contrast to this, a deep reinforcement learning algorithm, called AlphaZero, has recently achieved state-of-the-art performance in combinatorial games, such as chess or Go, solely through self-play. We adapt this methodology to apply it to problems of online stochastic optimization, in particular a version of the PTP. Training is performed on a set of scenarios on a per-instance basis. First computational studies have shown promising results, improving the solution quality significantly through training.

Authors 1

1. Jonas Prünte Aachen INFORM Institute for Operations Research and Management GmbH

   Inform (Germany)

   Affiliation as printed

   INFORM Institute for Operations Research and Management GmbH