Deep Reinforcement Learning for Traveling Salesman Problem with Time Windows and Rejections

Abstract

Recently deep reinforcement learning has shown success in solving NP-hard combinatorial optimization problems such as traveling salesman problems, vehicle routing problems, job-shop scheduling problems, as well as their variants. However, most of the problems being solved are still relatively simple compared to the real-world scenarios. For instance, feasibility constraints are rarely considered in the current frameworks. This paper investigates the possibility of applying deep reinforcement learning to tackle combinatorial optimization problems with feasibility constraints. We propose a framework to solve such problems by combining deep reinforcement learning with a greedy heuristic. We demonstrate this approach for the traveling salesman problem with time windows and rejection (TSPTWR). The results show that our approach outperforms a commonly employed tabu search heuristic, both in terms of the solution quality and the inference computation time. More specifically, the inference process is 100 to 1000 times faster than tabu search for different size TSPTWR. The proposed approach can be considered as a framework enhancing reinforcement learning with heuristics for solving more complex problems.