Abstract
In this work we study the potential of cloud computing in the context of optimization. For this purpose we perform a case study on the Probabilistic Traveling Salesman Problem with Deadlines, an extremely difficult stochastic combinatorial optimization problem. By using a large amount of computational resources in parallel, it is possible to obtain significantly better solutions for the Probabilistic Traveling Salesman Problem with Deadlines in the same amount of time. For many different applications this advantage clearly outweighs the requirement for additional computational resources, in particular considering the convenience of modern cloud infrastructures.
D. Weyland—This work has been supported by the Swiss National Science Foundation as part of the Early Postdoc.Mobility grant 152293.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Campbell, A.M., Thomas, B.W.: Probabilistic traveling salesman problem with deadlines. Transp. Sci. 42(1), 1–21 (2008)
Campbell, A.M., Thomas, B.W.: Runtime reduction techniques for the probabilistic traveling salesman problem with deadlines. Comput. Oper. Res. 36(4), 1231–1248 (2009)
Dumas, Y., Desrosiers, J., Gelinas, E., Solomon, M.M.: An optimal algorithm for the traveling salesman problem with time windows. Oper. Res. 43(2), 367–371 (1995)
Jaillet, P.: Probabilistic traveling salesman problems. PhD thesis, MIT, Department of Civil Engineering (1985)
Jaillet, P.: A priori solution of a traveling salesman problem in which a random subset of the customers are visited. Oper. Res. 36(6), 929–936 (1988)
Johnson, D.S., McGeoch, L.A.: The traveling salesman problem: a case study in local optimization. Local Search Comb. Optim. 1, 215–310 (1997)
Weyland, D.: On the computational complexity of the probabilistic traveling salesman problem with deadlines. Theor. Comput. Sci. 540, 156–168 (2014)
Weyland, D., Montemanni, R., Gambardella, L.M.: A metaheuristic framework for stochastic combinatorial optimization problems based on GPGPU with a case study on the probabilistic traveling salesman problem with deadlines. J. Parallel Distrib. Comput. 73, 74–85 (2012)
Weyland, D., Montemanni, R., Gambardella, L.M.: Hardness results for the probabilistic traveling salesman problem with deadlines. In: Mahjoub, A.R., Markakis, V., Milis, I., Paschos, V.T. (eds.) ISCO 2012. LNCS, vol. 7422, pp. 392–403. Springer, Heidelberg (2012)
Weyland, D., Montemanni, R., Gambardella, L.M.: Heuristics for the probabilistic traveling salesman problem with deadlines based on quasi-parallel monte carlo sampling. Comput. Oper. Res. 40(7), 1661–1670 (2013)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Weyland, D. (2015). Metaheuristics and Cloud Computing: A Case Study on the Probabilistic Traveling Salesman Problem with Deadlines. In: Moreno-Díaz, R., Pichler, F., Quesada-Arencibia, A. (eds) Computer Aided Systems Theory – EUROCAST 2015. EUROCAST 2015. Lecture Notes in Computer Science(), vol 9520. Springer, Cham. https://doi.org/10.1007/978-3-319-27340-2_35
Download citation
DOI: https://doi.org/10.1007/978-3-319-27340-2_35
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-27339-6
Online ISBN: 978-3-319-27340-2
eBook Packages: Computer ScienceComputer Science (R0)