تقرير
A Deep Reinforcement Learning Approach for Solving the Traveling Salesman Problem with Drone
| العنوان: | A Deep Reinforcement Learning Approach for Solving the Traveling Salesman Problem with Drone |
|---|---|
| المؤلفون: | Bogyrbayeva, Aigerim, Yoon, Taehyun, Ko, Hanbum, Lim, Sungbin, Yun, Hyokun, Kwon, Changhyun |
| سنة النشر: | 2021 |
| المجموعة: | Computer Science Mathematics |
| مصطلحات موضوعية: | Mathematics - Optimization and Control, Computer Science - Artificial Intelligence, Computer Science - Machine Learning |
| الوصف: | 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. |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2112.12545 |
| رقم الأكسشن: | edsarx.2112.12545 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |