Multiobjective Travelling Salesman Problem under Stochastic Environment

Abstract:

Travelling salesman problem is a fundamental combinatorial optimization model studied in the operations research community, and yet, there is surprisingly little literature that addresses stochastic uncertainties and multiple objectives in it simultaneously. This paper is devoted to a novel TSP variation called stochastic multiobjective TSP (SMOTSP) with random variables on the arc, and a new solution approach is proposed to obtain Pareto efficient route in it, whose validity is proved finally.

• Periodical: Applied Mechanics and Materials (Volumes 530-531)
• Pages: 512-516
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.530-531.512
• Online since: February 2014
• Authors: Qi Fang He, Tie Zhu Wang, Lu Pan, Zu Tong Wang
• Keywords: Genetic Algorithm (GA), Multiobjctive Optimization, Stochastic Modelling, Traveling Salesman Problem

References

[1] David L Applegate, Robert E Bixby, Vasek Chvatal, and William J Cook. The traveling salesman problem: a computational study. Princeton University Press, (2011).

DOI: 10.1145/1556154.1556162

[2] David Applegate, Robert Bixby, Vašek Chvátal, and William Cook. Finding cuts in the tsp (a preliminary report). Certer for Discrete Mathematics & Theoretical Computer Science, (1995).

[3] Adrian Dumitrescu. The traveling salesman problem for lines and rays in the plane. Discrete Mathematics, Algorithms and Applications, 4(04), (2012).

DOI: 10.1142/s1793830912500449

[4] Sing Liew. Introducing convex layers to the traveling salesman problem. arXiv preprint arXiv: 1204. 2348, (2012).

[5] P. Jaillet. Probabilistic Traveling Salesman Problems. PhD thesis, Massachusetts Institute of Technology, (1985).

[6] Dimitris J Bertsimas and David Simchi-Levi. A new generation of vehicle routing research: robust algorithms, addressing uncertainty. Operations Research, 44(2): 286–304, (1996).

DOI: 10.1287/opre.44.2.286

[7] E. Kao. A preference order dynamic program for a stochastic travelling salesman problem. Operations Research, 26: 1033–1045, (1978).

DOI: 10.1287/opre.26.6.1033

[8] Eleni Hadjiconstantinou and Daron Roberts. Routing under uncertainty: an application in the scheduling of field service engineers. The vehicle routing problem, pages 331–352, (2002).

DOI: 10.1137/1.9780898718515.ch13

[9] Luis Paquete and Thomas Stützle. A two-phase local search for the biobjective traveling salesman problem. In Evolutionary Multi-Criterion Optimization, pages 479–493. Springer, (2003).

DOI: 10.1007/3-540-36970-8_34

[10] Eric Angel, Evripidis Bampis, and Laurent Gourvès. Approximating the pareto curve with local search for the bicriteria tsp (1, 2) problem. Theoretical Computer Science, 310(1): 135–146, (2004).

DOI: 10.1016/s0304-3975(03)00376-1