[2H4-GS-13] AI application: Data analysis and search

[2H4-GS-13-05] Reinforcement learning for solving time-dependent traveling salesman problem

〇Kensuke Nakanishi¹, Yuichi Miyamura¹, Shunsuke Hirose¹, Tomotake Kozu¹ (1. Deloitte Touche Tohmatsu LLC)

Keywords:Reinforcement learning, Combinatorial optimization problem, Traveling salesman problem, Seq2Seq

Incorporated into sequence to sequence (seq2seq) model, reinforcement learning (RL) successfully sets up a solver for combinatorial optimization problems, where some pioneering works have proposed frameworks to solve problems such as traveling salesman problems (TSP) and vehicle routing problems (VRP). This article aims to enhance the applicability of the RL scheme for real-world problems, and tackles to apply it to time-dependent TSP (TDTSP). Since the TDTSP is a kind of the TSP where traveling cost between cities changes according to time, it can be used for modelling problems such as routing problems and scheduling problems in reality. Defining a seq2seq model for the TDTSP, we evaluate the RL scheme performance, and show the applicability to the TDTSP.