AN ALGORITHM FOR SINGLE CONSTRAINT MAXIMUM COLLECTION PROBLEM

Abstract

There are many studies which consider an optimal tour on a given graph including the well-known Traveling Salesman Problem (TSP) and Vehicle Routing Problem (VRP). Most of these studies, however, assume that "all" nodes on a given graph should be visited exactly once or at least once. In this paper, we relax this assumption and consider the following problem: "Given items with known values located at nodes of network, one wants to collect items so that their total value is maximized, under the assumption that a tour starting from the "center" node and returning to the center node is completed within a predetermined time limit." Because of the added (time) constraint, one may not visit all nodes. The addition of this simple-looking constraint makes the problem difficult as it introduces an added dimention of selecting nodes to visit. After a brief introduction, Section 2 presents two formulations of the problem, a native formulation and an improved one based on the introduction of self-loops to the graph corresponding to the problem. The latter formulation allows us to utilize solution strategies developed for the standard TSP. A branch and bound solution strategies together with a solution method of a relaxation problem is described in Section 3. A relaxation problem is generally an assignment problem with an added constraint for which an efficient branch and bound procedure is proposed. In particular, a recommended strategy for the selection of the branching variable is identified, and also an efficient procedure to transmit information from a branching problem to its sub-problems is proposed. Section 4 presents results of computational time requirements and basic characteristics of the proposed algorithm are clarified.