Title: Stochastic travelling salesperson and shortest route models with safety time

Authors: Lilit Mazmanyan; Dan Trietsch

Addresses: College of Engineering, American University of Armenia, Yerevan, Armenia ' College of Engineering, American University of Armenia, Yerevan, Armenia

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.

Keywords: travelling salesman problem; TSP; shortest route; stochastic scheduling; safe scheduling; lognormal scheduling; safety time.

DOI: 10.1504/IJPS.2014.066707

International Journal of Planning and Scheduling, 2014 Vol.2 No.1, pp.53 - 76

Received: 26 Apr 2014
Accepted: 31 Aug 2014
Published online: 14 Jan 2015 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article