×

zbMATH — the first resource for mathematics

Efficiently solving the traveling thief problem using hill climbing and simulated annealing. (English) Zbl 1436.90121
Summary: Many real-world problems are composed of multiple interacting sub-problems. However, few investigations have been carried out to look into tackling problems from a metaheuristics perspective. The Traveling Thief Problem (TTP) is a new NP-hard problem with two interdependent components that aim to provide a benchmark model to better represent this category of problems. In this paper, TTP is investigated theoretically and empirically. Two algorithms based on a 2-OPT steepest ascent hill climbing algorithm and the simulated annealing metaheuristic named CS2SA* and CS2SA-R are proposed to solve the problem. The obtained results show that the proposed algorithms are efficient for many TTP instances of different sizes and properties and are very competitive in comparison with two of the best-known state-of-the-art algorithms.
MSC:
90C27 Combinatorial optimization
90C06 Large-scale problems in mathematical programming
90C59 Approximation methods and heuristics in mathematical programming
Software:
Genocop; irace; SPOT; TSPLIB
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Aarts, E.; Korst, J., Simulated Annealing and Boltzmann Machines: A Stochastic Approach to Combinatorial Optimization and Neural Computing (1989), John Wiley & Sons, Inc.: John Wiley & Sons, Inc. New York, NY, USA · Zbl 0674.90059
[2] Applegate, D.; Cook, W.; Rohe, A., Chained Lin-Kernighan for large traveling salesman problems, INFORMS J. Comput., 15, 1, 82-92 (2003) · Zbl 1238.90125
[3] Birattari, M.; Yuan, Z.; Balaprakash, P.; Stützle, T., F-race and iterated F-race: an overview, Experimental Methods for the Analysis of Optimization Algorithms, 311-336 (2010), Springer · Zbl 1204.68280
[4] Bonyadi, M. R.; Michalewicz, Z.; Barone, L., The travelling thief problem: the first step in the transition from theoretical problems to realistic problems, Proceedings of the IEEE Congress on Evolutionary Computation (CEC), 1037-1044 (2013), IEEE
[6] Bonyadi, M. R.; Michalewicz, Z.; Roman Przybyŏek, M.; Wierzbicki, A., Socially inspired algorithms for the Travelling Thief Problem, Proceedings of the Conference on Genetic and Evolutionary Computation, 421-428 (2014), ACM
[7] Chand, S.; Wagner, M., Fast heuristics for the multiple traveling thieves problem, Proceedings of the Conference on Genetic and Evolutionary Computation, 293-300 (2016), ACM
[8] Croes, G., A method for solving traveling-salesman problems, Oper. Res., 6, 6, 791-812 (1958) · Zbl 1414.90303
[9] Delaunay, B., Sur la sphere vide, Izv. Akad. Nauk SSSR, Otdelenie Matematicheskii i Estestvennyka Nauk, 7, 793-800, 1-2 (1934) · JFM 60.0946.06
[10] Dorigo, M.; Gambardella, L. M., Ant colonies for the travelling salesman problem, BioSystems, 43, 2, 73-81 (1997)
[11] Dror, M., Arc Routing: Theory, Solutions and Applications (2012), Springer Science & Business Media
[12] Dueck, G.; Scheuer, T., Threshold accepting: a general purpose optimization algorithm appearing superior to simulated annealing, J. Comput. Phys., 90, 1, 161-175 (1990) · Zbl 0707.65039
[13] El Yafrani, M.; Ahiod, B., Cosolver2b: an efficient local search heuristic for the travelling thief problem, Proceedings of the IEEE/ACS Twelfth International Conference on Computer Systems and Applications (AICCSA), 1-5 (2015), IEEE
[14] El Yafrani, M.; Ahiod, B., Population-based vs. single-solution heuristics for the Travelling Thief Problem, Proceedings of the Conference on Genetic and Evolutionary Computation. Proceedings of the Conference on Genetic and Evolutionary Computation, GECCO’16 (2016), ACM: ACM Denver, CO, USA
[15] El Yafrani, M.; Ahiod, B., A local search based approach for solving the Travelling Thief Problem: the pros and cons, Appl. Soft Comput., 52, 795-804 (2017)
[16] Faulkner, H.; Polyakovskiy, S.; Schultz, T.; Wagner, M., Approximate approaches to the Traveling Thief Problem, Proceedings of the Conference on Genetic and Evolutionary Computation. Proceedings of the Conference on Genetic and Evolutionary Computation, GECCO’16 (2016), ACM: ACM Denver, CO, USA
[17] Glover, F., Tabu search-part i, ORSA J. Comput., 1, 3, 190-206 (1989) · Zbl 0753.90054
[18] Glover, F., Tabu search-part ii, ORSA J. Comput., 2, 1, 4-32 (1990) · Zbl 0771.90084
[19] Goldberg, D. E.; Lingle, R., Alleles, loci, and the traveling salesman problem, Proceedings of the First International Conference on Genetic Algorithms and Their Applications, 154-159 (1985), Lawrence Erlbaum Associates, Publishers
[20] Guibas, L.; Stolfi, J., Primitives for the manipulation of general subdivisions and the computation of Voronoi, ACM Trans. Gr. (TOG), 4, 2, 74-123 (1985) · Zbl 0586.68059
[21] Hu, J.-Q.; Leida, B., Traffic grooming, routing, and wavelength assignment in optical WDM mesh networks, Proceedings of the INFOCOM Twenty-Third Annual Joint Conference of the IEEE Computer and Communications Societies, 1 (2004), IEEE
[22] Ibrahimov, M.; Mohais, A.; Schellenberg, S.; Michalewicz, Z., Evolutionary approaches for supply chain optimisation: part I: single and two-component supply chains, Int. J. Intell. Comput. Cybern., 5, 4, 444-472 (2012)
[23] Ibrahimov, M.; Mohais, A.; Schellenberg, S.; Michalewicz, Z., Evolutionary approaches for supply chain optimisation. part II: multi-silo supply chains, Int. J. Intell. Comput. Cybern., 5, 4, 473-499 (2012)
[24] Iori, M.; Martello, S., Routing problems with loading constraints, Top, 18, 1, 4-27 (2010) · Zbl 1279.90146
[25] Lin, S., Computer solutions of the traveling salesman problem, Bell Syst. Tech. J., 44, 10, 2245-2269 (1965) · Zbl 0136.14705
[26] Lin, S.; Kernighan, B. W., An effective heuristic algorithm for the traveling-salesman problem, Oper. Res., 21, 2, 498-516 (1973) · Zbl 0256.90038
[27] López-Ibánez, M.; Dubois-Lacoste, J.; Stützle, T.; Birattari, M., The irace package, iterated race for automatic algorithm configuration, Technical Report (2011), Citeseer
[28] Martello, S.; Toth, P., Knapsack Problems: Algorithms and Computer Implementations (1990), John Wiley & Sons, Inc. · Zbl 0708.68002
[29] Mei, Y.; Li, X.; Yao, X., Improving efficiency of heuristics for the large scale Traveling Thief Problem, Simulated Evolution and Learning, 631-643 (2014), Springer
[30] Mei, Y.; Li, X.; Yao, X., On investigation of interdependence between sub-problems of the travelling thief problem, Soft Comput., 1-16 (2014)
[31] Michalewicz, Z., Genetic Algorithms+ Data Structures= Evolution Programs (2013), Springer Science & Business Media
[32] Neumann, F.; Polyakovskiy, S.; Skutella, M.; Stougie, L.; Wu, J., A fully polynomial time approximation scheme for packing while traveling, CoRR, abs/1606.06818 (2017)
[33] Papadimitriou, C. H., The euclidean travelling salesman problem is np-complete, Theor. Comput. Sci., 4, 3, 237-244 (1977) · Zbl 0386.90057
[34] Polyakovskiy, S.; Neumann, F., Packing while traveling: mixed integer programming for a class of nonlinear knapsack problems, Integration of AI and OR Techniques in Constraint Programming, 332-346 (2015), Springer · Zbl 06605766
[35] Polyakovskiy, S.; Neumann, F., The packing while traveling problem, Eur. J. Oper. Res., 258, 2, 424-439 (2017) · Zbl 1394.90494
[36] Polyakovskiy, S.; Reza, M.; Wagner, M.; Michalewicz, Z.; Neumann, F., A comprehensive benchmark set and heuristics for the Traveling Thief Problem, Proceedings of the Genetic and Evolutionary Computation Conference (GECCO) (2014), Vancouver, Canada
[37] Reinelt, G., TSPLIB - A traveling salesman problem library, ORSA J. Comput., 3, 4, 376-384 (1991) · Zbl 0775.90293
[38] Stolk, J.; Mann, I.; Mohais, A.; Michalewicz, Z., Combining vehicle routing and packing for optimal delivery schedules of water tanks, OR Insight, 26, 3, 167-190 (2013)
[39] Vargha, A.; Delaney, H. D., A critique and improvement of the CL common language effect size statistics of Mcgraw and Wong, J. Edu. Behav. Stat., 25, 2, 101-132 (2000)
[40] Wagner, M., Stealing items more efficiently with ants: a swarm intelligence approach to the Travelling Thief Problem, Proceedings of the tenth International Conference on Swarm Intelligence, ANTS 2016, 273-281 (2016), Springer International Publishing: Springer International Publishing Brussels, Belgium
[41] Wagner, M.; Lindauer, M.; Misir, M.; Nallaperuma, S.; Hutter, F., A case study of algorithm selection for the Traveling Thief Problem, J. Heuristics (2017)
[42] Weiszer, M.; Chen, J.; Ravizza, S.; Atkin, J.; Stewart, P., A heuristic approach to greener airport ground movement, Proceedings of the IEEE Congress on Evolutionary Computation (CEC), 3280-3286 (2014), IEEE
[43] Wu, J.; Polyakovskiy, S.; Neumann, F., On the impact of the renting rate for the unconstrained nonlinear knapsack problem, Proceedings of the Conference on Genetic and Evolutionary Computation. Proceedings of the Conference on Genetic and Evolutionary Computation, GECCO’16 (2016), ACM: ACM Denver, CO, USA
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.