Article ID: | iaor20011928 |
Country: | Netherlands |
Volume: | 127 |
Issue: | 1 |
Start Page Number: | 69 |
End Page Number: | 77 |
Publication Date: | Nov 2000 |
Journal: | European Journal of Operational Research |
Authors: | Ladany Shaul P., Deitch Ray |
Keywords: | heuristics |
The one-period bus touring problem – also referred to as simply the bus touring problem (BTP) – objective is to maximize the total attractiveness of the tour by selecting a subset of sites to be visited and scenic routes to be traveled – both having associated non-negative attractivity values – given the geographic frame considerations and constraints on touring time, cost and/or total distance. The integer linear-programming model developed to derive an optimal bus touring solution for the BTP is not practical for such an NP-complete problem. A similar NP-hard problem is the orienteering tour problem (OTP) in which the identical start and end point is specified along with other locations having associated scores. Competitors seek to visit in a fixed amount of time, a subset of locations in order to maximize the total score. This paper presents a transformation from the BTP to the OTP and illustrates the use of an effective heuristic for the OTP together with an improvement process, aimed at generating a fast near-optimal BTP solution. The results of 11 bus touring problems are presented.