{
  "id": "2112.12545",
  "version": "v3",
  "published": "2021-12-22T04:59:44.000Z",
  "updated": "2022-12-05T13:21:50.000Z",
  "title": "A Deep Reinforcement Learning Approach for Solving the Traveling Salesman Problem with Drone",
  "authors": [
    "Aigerim Bogyrbayeva",
    "Taehyun Yoon",
    "Hanbum Ko",
    "Sungbin Lim",
    "Hyokun Yun",
    "Changhyun Kwon"
  ],
  "categories": [
    "math.OC",
    "cs.AI",
    "cs.LG"
  ],
  "abstract": "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 a hybrid model that uses an attention encoder and a Long Short-Term Memory (LSTM) network decoder, 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 the coordinated routing of multiple vehicles than the attention-based model. The proposed model demonstrates comparable results as the operations research baseline methods.",
  "revisions": [
    {
      "version": "v3",
      "updated": "2022-12-05T13:21:50.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "deep reinforcement learning approach",
      "traveling salesman problem",
      "hybrid model",
      "capacitated vehicle routing problem",
      "operations research baseline methods"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}