Solving Traveling Salesman Problem with Time Windows Using Hybrid Pointer Networks with Time Features

Majed G. Alharbi, Ahmed Stohy, Mohammed Elhenawy, Mahmoud Masoud and Hamiden Abd El-Wahed Khalifa
Additional contact information
Majed G. Alharbi: Department of Mathematics, College of Science and Arts, Qassim University, Al Mithnab 56648, Saudi Arabia
Ahmed Stohy: Department of Computer and Systems Engineering, Minya University, Minya 61512, Egypt
Mohammed Elhenawy: Centre for Accident Research and Road Safety, Queensland University of Technology, Brisbane 4059, Australia
Mahmoud Masoud: Centre for Accident Research and Road Safety, Queensland University of Technology, Brisbane 4059, Australia
Hamiden Abd El-Wahed Khalifa: Department of Mathematics, College of Science and Arts, Qassim University, Al-Badaya 51951, Saudi Arabia

Sustainability, 2021, vol. 13, issue 22, 1-12

Abstract: This paper introduces a time efficient deep learning-based solution to the traveling salesman problem with time window (TSPTW). Our goal is to reduce the total tour length traveled by -*the agent without violating any time limitations. This will aid in decreasing the time required to supply any type of service, as well as lowering the emissions produced by automobiles, allowing our planet to recover from air pollution emissions. The proposed model is a variation of the pointer networks that has a better ability to encode the TSPTW problems. The model proposed in this paper is inspired from our previous work that introduces a hybrid context encoder and a multi attention decoder. The hybrid encoder primarily comprises the transformer encoder and the graph encoder; these encoders encode the feature vector before passing it to the attention decoder layer. The decoder consists of transformer context and graph context as well. The output attentions from the two decoders are aggregated and used to select the following step in the trip. To the best of our knowledge, our network is the first neural model that will be able to solve medium-size TSPTW problems. Moreover, we conducted sensitivity analysis to explore how the model performance changes as the time window width in the training and testing data changes. The experimental work shows that our proposed model outperforms the state-of-the-art model for TSPTW of sizes 20, 50 and 100 nodes/cities. We expect that our model will become state-of-the-art methodology for solving the TSPTW problems.

Keywords: traveling salesman problem with time window; deep neural network; reinforcement learning (search for similar items in EconPapers)
JEL-codes: O13 Q Q0 Q2 Q3 Q5 Q56 (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://www.mdpi.com/2071-1050/13/22/12906/pdf (application/pdf)
https://www.mdpi.com/2071-1050/13/22/12906/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jsusta:v:13:y:2021:i:22:p:12906-:d:684832

Access Statistics for this article

Sustainability is currently edited by Ms. Alexandra Wu

More articles in Sustainability from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().