Premium
The maximum collection problem with time‐dependent rewards
Author(s) -
Erkut E.,
Zhang J.
Publication year - 1996
Publication title -
naval research logistics (nrl)
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.665
H-Index - 68
eISSN - 1520-6750
pISSN - 0894-069X
DOI - 10.1002/(sici)1520-6750(199608)43:5<749::aid-nav10>3.0.co;2-j
Subject(s) - mathematical optimization , heuristic , node (physics) , greedy algorithm , branch and bound , computer science , routing (electronic design automation) , upper and lower bounds , mathematics , algorithm , computer network , mathematical analysis , structural engineering , engineering
We consider a routing problem where the objective is to maximize the sum of the rewards collected at the nodes visited. Node rewards are decreasing linear functions of time. Time is spent when traveling between pairs of nodes, and while visiting the nodes. We propose a penalty‐based greedy (heuristic) algorithm and a branch‐and‐bound (optimal) algorithm for this problem. The heuristic is very effective in obtaining good solutions. We can solve problems with up to 20 nodes optimally on a microcomputer using the branch‐and‐bound algorithm. We report our computational experience with this problem. © 1996 John Wiley & Sons, Inc.