An algorithm for single constraint maximum collection problem

An algorithm for single constraint maximum collection problem

0.00 Avg rating0 Votes
Article ID: iaor1988562
Country: Japan
Volume: 31
Issue: 4
Start Page Number: 515
End Page Number: 530
Publication Date: Dec 1988
Journal: Journal of the Operations Research Society of Japan
Authors: ,
Keywords: networks, optimization, programming: integer
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, the authors 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 dimension 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.

Reviews

Required fields are marked *. Your email address will not be published.