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. 0 1996 John Wiley & Sons. Inc.
1. Introduction
Perhaps the most popular problem in the network optimization literature is the traveling-salesman problem (TSP). Recently, a number of network problems that are closely related to the TSP have been suggested by different authors. One of these related problems is the maximum collection problem with time-dependent rewards ( MCPTDR ), which was recently introduced by Brideau and Cavalier ( BC) [ 21. They suggested an integer programming formulation and a heuristic algorithm for this problem. In this article we describe an alternative heuristic, and an implicit enumeration algorithm for MCPTDR. We also report our computational experience with the solution algorithms.
The MCPTDR is defined on a graph G ( N , A ) with node set N = { 0, 1,2, . . . , n } , and arc set A = { ( i , j ) , z , J β¬ N } . The travel time on arc ( i , j ) is given by d!,. The reward at node i is given by r, ( t ) = max { 6, -sit, 0 } for t 2 0, and the time required to collect the reward is denoted by u, . It is assumed that the reward at node i is collected at the arrival instance.
However, u, units of time must pass before node i can be departed. Point 0 is assumed to be the depot with ro = 0 for all t > 0 and vo = 0. A solution to MCPTDR consists of a sequence of nodes in G . The objective is to find the sequence that maximizes the total reward collected.
The MCPTDR is closely related to another routing problem, namely, the orienteering problem, for which a number of applications, such as vehicle routing and production planning problems, have been suggested in the literature [ 101. The MCPTDR problem may be relevant in a competitive environment. BC suggest that the rewards may correspond to sales made. The sales potentials may be declining over time, because other salespeople are operating in the same area. Given the initial sales potential, and the decline rates, the ob-