Please use this identifier to cite or link to this item: https://doi.org/10.1142/S0217595904000229
Title: An integer L-shaped algorithm for time-constrained traveling salesman problem with stochastic travel and service times
Authors: Teng, S.Y. 
Ong, H.L. 
Huang, H.C. 
Keywords: Benders' decomposition
Integer L-shaped method
Stochastic program with recourse
Time-constrained traveling salesman problem
Issue Date: Jun-2004
Source: Teng, S.Y., Ong, H.L., Huang, H.C. (2004-06). An integer L-shaped algorithm for time-constrained traveling salesman problem with stochastic travel and service times. Asia-Pacific Journal of Operational Research 21 (2) : 241-257. ScholarBank@NUS Repository. https://doi.org/10.1142/S0217595904000229
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 hours T and a tolerance time ΔT, the total travel and service times of a route can exceed T as long as it is within T + ΔT, though a penalty proportional to the amount in excess of T will 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.
Source Title: Asia-Pacific Journal of Operational Research
URI: http://scholarbank.nus.edu.sg/handle/10635/63010
ISSN: 02175959
DOI: 10.1142/S0217595904000229
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

SCOPUSTM   
Citations

13
checked on Dec 6, 2017

WEB OF SCIENCETM
Citations

11
checked on Nov 22, 2017

Page view(s)

79
checked on Dec 10, 2017

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.