Markov Chain Anticipation for the Online Traveling Salesman Problem by Simulated Annealing Algorithm

Authors

Department of Mathematics, Faculty of Basic Science, University of Qom, Qom, Iran

Abstract

The arc costs are assumed to be online parameters of the network and decisions should be made while the costs of arcs are not known. The policies determine the permitted nodes and arcs to traverse and they are generally defined according to the departure nodes of the current policy nodes. In on-line created tours arc costs are not available for decision makers. The on-line traversed nodes are fixed and unchangeable for the next times. A discrete time Markov chain is established in on-line policy times. Then, the best state is selected to traverse the next node by a simulated annealing heuristic.

Keywords

References

1. G. Ausiello, V. Bonifaci, L. Laura, The on-line asymmetric traveling salesman problem, J. Discrete Algorithms, 6, 290-298 (2008).
2. G. Ausiello, M. Demange, L. Laura, V. Paschos, Algorithms for the on-line quota traveling salesman problem, Inf. Processing Letters, 92, 89-94 (2004).
3. N. Christo_des, Worst-case analysis of a new heuristic for the travelling salesman problem, Carnegie Mellon University, Technical Report, CS-93-13 (1976).
4. G. Gutin, A.P. Punnen, The traveling salesman problem and its variations, Kluwer Academic Publishers, Boston (2004).
5. O.C. Ibe, Markov Processes for Stochastic Modeling, Academic Press, Boston (2009).
6. P. Jaillet, X. Lu, Online traveling salesman problems with service exibility, Networks, 58, 137-146 (2011).
7. M.W. Park, Y.D. Kim, A systematic procedure for setting parameters in simulated annealing algorithms, Computers and Operations Res., 25, 207-217 (1998).
8. C.H. Papadimitriouc, J.N. Tsitsiklis, The complexity of Markov chain decision processes, Mathematics of Operation Res., 12, 441-450 (1987).
9. A. Ptrowski, J. Dro, E.P.S. Taillard, Metaheuristics for Hard Optimization, Springer, Heidelberg (2006).
10. G.H. Polychronopoulos, J.N. Tsitsiklis, Stochastic shortest path problems with recourse, Networks, 27, 133-143 (1996).
11. X. Wen, Y. Xu, H. Zhang, Online traveling salesman problem with deadline and advanced information, Computers and Industrial Engineering, 63, 1048-1053 (2012).
12. W. Yu, Z. Liu, X. Bao, Optimal deterministic algorithms for some variants of online quota traveling salesman problem, European J. Operational Res., 238, 735-740 (2014).
13. H. Zhang, W. Tong, Y. Xu, G. Lin, The steiner traveling salesman problem with online edge blockages, European J. Operational Res., 243, 30-40 (2015).
14. Ruprecht-Karls-Universitt Heidelberg, http://comopt.ifi.uniheidelberg.de/software/TSPLIB95/index.html
Global Analysis and Discrete Mathematics
Volume 2, Issue 1
May 2017
Pages 33-38

Files

History

  • Receive Date: 17 February 2016
  • Revise Date: 03 May 2017
  • Accept Date: 18 November 2016

Share

How to cite

Statistics