Premium
Efficient neighborhood search for the Probabilistic Pickup and Delivery Travelling Salesman Problem
Author(s) -
Beraldi Patrizia,
Ghiani Gianpaolo,
Laporte Gilbert,
Musmanno Roberto
Publication year - 2005
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20063
Subject(s) - travelling salesman problem , pickup , probabilistic logic , computation , computer science , mathematical optimization , traveling purchaser problem , mathematics , bottleneck traveling salesman problem , algorithm , artificial intelligence , image (mathematics)
In this article the probabilistic Pickup and Delivery Travelling Salesman Problem is studied and an efficient neighborhood search procedure is developed. This procedure requires O ( n 3 ) computations for the evaluation of the neighborhood of a given solution while the straightforward approach has an O ( n 5 )complexity. © 2005 Wiley Periodicals, Inc. NETWORKS, Vol. 45(4), 195–198 2005