AN ADDITIVE APPROACH FOR THE OPTIMAL SOLUTION OF THE PRIZE-COLLECTING TRAVELLING SALESMAN PROBLEM. VEHICLE ROUTING: METHODS AND STUDIES. STUDIES IN MANAGEMENT SCIENCE AND SYSTEMS - VOLUME 16
Consider the following generalization of the well-known travelling salesman problem. The prize-collecting travelling salesman problem (pc-tsp) is to find a minimum-cost route for the vehicle, visiting each city at most once and collecting a total prize not less than a given goal g. Such a problem arises in several routing and scheduling applications and belongs to the class of np-hard problems. In this paper, we introduce several mathematical models of the problem and point out its main substructures. Additive bounding procedures are then designed yielding sequences of increasing lower bound on the optimum value of the problem. Extensive computational results on randomly generated test problems are reported, comparing the performance of the proposed bounding procedures. A branch and bound algorithm for the optimal solution of pc-tsp is finally described and computationally analyzed. (Author/TRRL)
-
Availability:
- Find a library where document is available. Order URL: http://worldcat.org/isbn/0444704078
-
Corporate Authors:
Elsevier
Radarweg 29
Amsterdam, Netherlands 1043 NX -
Authors:
- Fischetti, M
- Toth, P
- Publication Date: 1988
Media Info
- Features: References;
- Pagination: p. 319-343
-
Serial:
- Publication of: Dalctraf
- Publisher: Dalctraf
Subject/Index Terms
- TRT Terms: Calculation; Itinerary; Mathematical models; Methodology; Operations research; Planning; Routing; Theory; Vehicles
- ITRD Terms: 6464: Calculation; 699: Itinerary; 6473: Mathematical model; 9102: Method; 9055: Operational research; 143: Planning; 9078: Theory; 1255: Vehicle
- Subject Areas: Highways; Planning and Forecasting; Vehicles and Equipment;
Filing Info
- Accession Number: 00491696
- Record Type: Publication
- Source Agency: Transport Research Laboratory
- ISBN: 0-444-70407-8
- Files: ITRD, TRIS
- Created Date: Mar 31 1990 12:00AM