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

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...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Majed G. Alharbi, Ahmed Stohy, Mohammed Elhenawy, Mahmoud Masoud, Hamiden Abd El-Wahed Khalifa
Formato:	article
Lenguaje:	EN
Publicado:	MDPI AG 2021
Materias:	traveling salesman problem with time window deep neural network reinforcement learning Environmental effects of industries and plants TD194-195 Renewable energy sources TJ807-830 Environmental sciences GE1-350
Acceso en línea:	https://doaj.org/article/aa734ea2fec849eaab75df411fadffd1
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:aa734ea2fec849eaab75df411fadffd1
record_format	dspace
spelling	oai:doaj.org-article:aa734ea2fec849eaab75df411fadffd12021-11-25T19:05:25ZSolving Traveling Salesman Problem with Time Windows Using Hybrid Pointer Networks with Time Features10.3390/su1322129062071-1050https://doaj.org/article/aa734ea2fec849eaab75df411fadffd12021-11-01T00:00:00Zhttps://www.mdpi.com/2071-1050/13/22/12906https://doaj.org/toc/2071-1050This 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.Majed G. AlharbiAhmed StohyMohammed ElhenawyMahmoud MasoudHamiden Abd El-Wahed KhalifaMDPI AGarticletraveling salesman problem with time windowdeep neural networkreinforcement learningEnvironmental effects of industries and plantsTD194-195Renewable energy sourcesTJ807-830Environmental sciencesGE1-350ENSustainability, Vol 13, Iss 12906, p 12906 (2021)
institution	DOAJ
collection	DOAJ
language	EN
topic	traveling salesman problem with time window deep neural network reinforcement learning Environmental effects of industries and plants TD194-195 Renewable energy sources TJ807-830 Environmental sciences GE1-350
spellingShingle	traveling salesman problem with time window deep neural network reinforcement learning Environmental effects of industries and plants TD194-195 Renewable energy sources TJ807-830 Environmental sciences GE1-350 Majed G. Alharbi Ahmed Stohy Mohammed Elhenawy Mahmoud Masoud Hamiden Abd El-Wahed Khalifa Solving Traveling Salesman Problem with Time Windows Using Hybrid Pointer Networks with Time Features
description	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.
format	article
author	Majed G. Alharbi Ahmed Stohy Mohammed Elhenawy Mahmoud Masoud Hamiden Abd El-Wahed Khalifa
author_facet	Majed G. Alharbi Ahmed Stohy Mohammed Elhenawy Mahmoud Masoud Hamiden Abd El-Wahed Khalifa
author_sort	Majed G. Alharbi
title	Solving Traveling Salesman Problem with Time Windows Using Hybrid Pointer Networks with Time Features
title_short	Solving Traveling Salesman Problem with Time Windows Using Hybrid Pointer Networks with Time Features
title_full	Solving Traveling Salesman Problem with Time Windows Using Hybrid Pointer Networks with Time Features
title_fullStr	Solving Traveling Salesman Problem with Time Windows Using Hybrid Pointer Networks with Time Features
title_full_unstemmed	Solving Traveling Salesman Problem with Time Windows Using Hybrid Pointer Networks with Time Features
title_sort	solving traveling salesman problem with time windows using hybrid pointer networks with time features
publisher	MDPI AG
publishDate	2021
url	https://doaj.org/article/aa734ea2fec849eaab75df411fadffd1
work_keys_str_mv	AT majedgalharbi solvingtravelingsalesmanproblemwithtimewindowsusinghybridpointernetworkswithtimefeatures AT ahmedstohy solvingtravelingsalesmanproblemwithtimewindowsusinghybridpointernetworkswithtimefeatures AT mohammedelhenawy solvingtravelingsalesmanproblemwithtimewindowsusinghybridpointernetworkswithtimefeatures AT mahmoudmasoud solvingtravelingsalesmanproblemwithtimewindowsusinghybridpointernetworkswithtimefeatures AT hamidenabdelwahedkhalifa solvingtravelingsalesmanproblemwithtimewindowsusinghybridpointernetworkswithtimefeatures
_version_	1718410357246001152

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

Ejemplares similares