Stochastic travelling salesperson and shortest route models with safety time. (5th January 2015)

• Record Type: Journal Article
• Authors: Mazmanyan, Lilit; Trietsch, Dan
• Is Part Of: International journal of planning and scheduling. Volume 2:Number 1(2014)
• Page Start: 53
• Page End: 76
• Publication Date: 2015-01-05
• Subjects: travelling salesperson problem -- TSP -- shortest route problem -- stochastic scheduling -- safe scheduling -- lognormal scheduling -- safety time; Production scheduling -- Periodicals; Mathematical statistics -- Periodicals; Operations research -- Periodicals; 658.53
• Languages: English
• ISSNs: 2044-494X

Abstract

We address the stochastic traveling salesperson problem (TSP) with distances measured by travel time. As a by-product, we obtain comparable results for the shortest route problem. We study how to select the best path and due date to minimise fundamental safe scheduling objectives. Model 1 requires minimising the due date subject to a service level constraint. Model 2 addresses a weighted trade-off between the due date and the expected tardiness. In alternate formulations, the due date is given and we maximise the service level for Model 1, or minimise the expected tardiness for Model 2. We show that Alternate 1 is equivalent to Model 1, but Alternate 2 is different to Model 2. For normal and lognormal travel times, we proceed by solving few deterministic TSP derived instances. This approach provides optimal solutions for some models. For all other models, it becomes an effective heuristic with tight performance guarantee certificates.