Abstract
Many evolutionary and constructive heuristic approaches have been introduced in order to solve the Travelling Thief Problem (TTP). However, the accuracy of such approaches is unknown due to their inability to find global optima. In this paper, we propose three exact algorithms and a hybrid approach to the TTP. We compare these with state-of-the-art approaches to gather a comprehensive overview on the accuracy of heuristic methods for solving small TTP instances.
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
Notes
- 1.
All instances are available online: http://cs.adelaide.edu.au/~optlog/research/ttp.php.
- 2.
They are fitted polynomials of degree six used only for visualisation purposes.
References
Applegate, D., Bixby, R., Chvatal, V., Cook, W.: Concorde TSP solver (2006). http://www.math.uwaterloo.ca/tsp/concorde.html
Benchimol, P., Van Hoeve, W.-J., Régin, J.-C., Rousseau, L.-M., Rueher, M.: Improved filtering for weighted circuit constraints. Constraints 17(3), 205–233 (2012). doi:10.1007/s10601-012-9119-x. ISSN 1572-9354
Bonyadi, M., Michalewicz, Z., Barone, L.: The travelling thief problem: the first step in the transition from theoretical problems to realistic problems. In: 2013 IEEE Congress on Evolutionary Computation (CEC), pp. 1037–1044 (2013)
Bonyadi, M.R., Michalewicz, Z., Przybylek, M.R., Wierzbicki, A.: Socially inspired algorithms for the travelling thief problem. In: Proceedings of the 2014 Annual Conference on Genetic and Evolutionary Computation, GECCO 2014, pp. 421–428. ACM (2014)
El Yafrani, M., Ahiod, B.: Cosolver2B: an efficient local search heuristic for the travelling thief problem. In: 2015 IEEE/ACS 12th International Conference of Computer Systems and Applications (AICCSA), pp. 1–5. IEEE (2015)
El Yafrani, M., Ahiod, B.: Population-based vs. single-solution heuristics for the travelling thief problem. In: Proceedings of the Genetic and Evolutionary Computation Conference 2016, GECCO 2016, pp. 317–324. ACM (2016)
Faulkner, H., Polyakovskiy, S., Schultz, T., Wagner, M.: Approximate approaches to the traveling thief problem. In: Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation, GECCO 2015, pp. 385–392. ACM (2015)
Held, M., Karp, R.M.: A dynamic programming approach to sequencing problems. In: Proceedings of the 1961 16th ACM National Meeting, ACM 1961, pp. 71.201-71.204. ACM (1961)
Hooker, J.N.: Logic, optimization, and constraint programming. INFORMS J. Comput. 14(4), 295–321 (2002)
Lin, S., Kernighan, B.W.: An effective heuristic algorithm for the traveling-salesman problem. Oper. Res. 21(2), 498–516 (1973)
Mei, Y., Li, X., Yao, X.: Improving efficiency of heuristics for the large scale traveling thief problem. In: Dick, G., et al. (eds.) SEAL 2014. LNCS, vol. 8886, pp. 631–643. Springer, Cham (2014). doi:10.1007/978-3-319-13563-2_53. ISBN 978-3-319-13563-2
Mei, Y., Li, X., Salim, F., Yao, X.: Heuristic evolution with genetic programming for traveling thief problem. In: 2015 IEEE Congress on Evolutionary Computation (CEC), pp. 2753–2760, May 2015. doi:10.1109/CEC.2015.7257230
Mei, Y., Li, X., Yao, X.: On investigation of interdependence between sub-problems of the travelling thief problem. Soft Comput. 20(1), 157–172 (2016)
Neumann, F., Polyakovskiy, S., Skutella, M., Stougie, L., Wu, J.: A Fully Polynomial Time Approximation Scheme for Packing While Traveling. ArXiv e-prints (2017)
Pisinger, D.: Advanced Generator for 0–1 Knapsack Problem. http://www.diku.dk/~pisinger/codes.html
Pisinger, D.: Where are the hard knapsack problems? Comput. Oper. Res. 32(9), 2271–2284 (2005). doi:10.1016/j.cor.2004.03.002. ISSN 0305-0548
Polyakovskiy, S., Neumann, F.: The packing while traveling problem. Eur. J. Oper. Res. 258(2), 424–439 (2017)
Polyakovskiy, S., Bonyadi, M.R., Wagner, M., Michalewicz, Z., Neumann, F.: A comprehensive benchmark set and heuristics for the traveling thief problem. In: Proceedings of the 2014 Annual Conference on Genetic and Evolutionary Computation, GECCO 2014, pp. 477–484. ACM (2014)
Refalo, P.: Impact-based search strategies for constraint programming. In: Wallace, M. (ed.) CP 2004. LNCS, vol. 3258, pp. 557–571. Springer, Heidelberg (2004). doi:10.1007/978-3-540-30201-8_41
Reinelt, G.: TSPLIB—a traveling salesman problem library. ORSA J. Comput. 3(4), 376–384 (1991)
Stützle, T., Hoos, H.H.: MAX MIN ant system. Future Gener. Comput. Syst. 16(8), 889–914 (2000)
Wagner, M.: Stealing items more efficiently with ants: a swarm intelligence approach to the travelling thief problem. In: Dorigo, M., Birattari, M., Li, X., López-Ibáñez, M., Ohkura, K., Pinciroli, C., Stützle, T. (eds.) ANTS 2016. LNCS, vol. 9882, pp. 273–281. Springer, Cham (2016). doi:10.1007/978-3-319-44427-7_25
Wagner, M., Lindauer, M., Mısır, M., Nallaperuma, S., Hutter, F.: A case study of algorithm selection for the traveling thief problem. J. Heuristics pp. 1–26 (2017)
Acknowledgements
This work was supported by the Australian Research councils through grants DP130104395 and DE160100850, and by the supercomputing resources provided by the Phoenix HPC service at the University of Adelaide.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
Wu, J., Wagner, M., Polyakovskiy, S., Neumann, F. (2017). Exact Approaches for the Travelling Thief Problem. In: Shi, Y., et al. Simulated Evolution and Learning. SEAL 2017. Lecture Notes in Computer Science(), vol 10593. Springer, Cham. https://doi.org/10.1007/978-3-319-68759-9_10
Download citation
DOI: https://doi.org/10.1007/978-3-319-68759-9_10
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-68758-2
Online ISBN: 978-3-319-68759-9
eBook Packages: Computer ScienceComputer Science (R0)