AN INTEGER L-SHAPED ALGORITHM FOR TIME-CONSTRAINED TRAVELING SALESMAN PROBLEM WITH STOCHASTIC TRAVEL AND SERVICE TIMES

S. Y. Teng, H. L. Ong and H. C. Huang
Additional contact information
S. Y. Teng: Industrial and Systems Engineering Department, National University of Singapore, 10 Kent Ridge Crescent, Singapore 119260, Singapore
H. L. Ong: Industrial and Systems Engineering Department, National University of Singapore, 10 Kent Ridge Crescent, Singapore 119260, Singapore
H. C. Huang: Industrial and Systems Engineering Department, National University of Singapore, 10 Kent Ridge Crescent, Singapore 119260, Singapore

Asia-Pacific Journal of Operational Research (APJOR), 2004, vol. 21, issue 02, 241-257

Abstract: The time-constrained traveling salesman problem (TCTSP) is a variant of the classical traveling salesman problem, where only a subset of the customers can be visited due to the time limit constraint. In this paper, we consider the TCTSP with stochastic travel and service times. Given the normal working hoursTand a tolerance timeΔT, the total travel and service times of a route can exceedTas long as it is withinT+ΔT, though a penalty proportional to the amount in excess ofTwill be imposed. The problem consists of optimally selecting and sequencing a subset of customers to visit in the presence of random travel and service times to maximize the expected profit while satisfying the time limit constraint. We formulate the problem as a two-stage stochastic program with recourse, and propose an integer L-shaped solution method for solving it. Computational results show that the algorithm can solve problems with moderate size to optimality within reasonable time.

Keywords: Integer L-shaped method; time-constrained traveling salesman problem; stochastic program with recourse; Benders' decomposition (search for similar items in EconPapers)
Date: 2004
References: View complete reference list from CitEc
Citations: View citations in EconPapers (9)

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0217595904000229
Access to full text is restricted to subscribers

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wsi:apjorx:v:21:y:2004:i:02:n:s0217595904000229

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0217595904000229

Access Statistics for this article

Asia-Pacific Journal of Operational Research (APJOR) is currently edited by Gongyun Zhao

More articles in Asia-Pacific Journal of Operational Research (APJOR) from World Scientific Publishing Co. Pte. Ltd.
Bibliographic data for series maintained by Tai Tone Lim ().