A Deep Reinforcement Learning Approach for Solving the Traveling
  Salesman Problem with Drone
  Reinforcement learning has recently shown promise in learning quality
solutions in many combinatorial optimization problems. In particular, the
attention-based encoder-decoder models show high effectiveness on various
routing problems, including the Traveling Salesman Problem (TSP).
Unfortunately, they perform poorly for the TSP with Drone (TSP-D), requiring
routing a heterogeneous fleet of vehicles in coordination -- a truck and a
drone. In TSP-D, the two vehicles are moving in tandem and may need to wait at
a node for the other vehicle to join. State-less attention-based decoder fails
to make such coordination between vehicles. We propose an attention
encoder-LSTM decoder hybrid model, in which the decoder's hidden state can
represent the sequence of actions made. We empirically demonstrate that such a
hybrid model improves upon a purely attention-based model for both solution
quality and computational efficiency. Our experiments on the min-max
Capacitated Vehicle Routing Problem (mmCVRP) also confirm that the hybrid model
is more suitable for coordinated routing of multiple vehicles than the
attention-based model.
