Premium
Time‐dependent traveling salesman problem–the deliveryman case
Author(s) -
Lucena Abilio
Publication year - 1990
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.3230200605
Subject(s) - travelling salesman problem , bounding overwatch , scheme (mathematics) , bottleneck traveling salesman problem , mathematics , upper and lower bounds , 2 opt , traveling purchaser problem , mathematical optimization , combinatorics , computer science , mathematical analysis , artificial intelligence
We consider a scheme to derive lower bounds for the time‐dependent traveling salesman problem. It involves splitting lower bounds into a number of components and optimizing each of these components. The lower bounds thus derived are shown to be at least as sharp as the ones previously suggested for the problem. We describe a branch‐and‐bound algorithm based on our lower bounding scheme and computationally test it for an instance of the problem known as the traveling deliveryman problem.