{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,8]],"date-time":"2025-07-08T16:43:50Z","timestamp":1751993030179,"version":"3.37.3"},"reference-count":45,"publisher":"Springer Science and Business Media LLC","issue":"4-6","license":[{"start":{"date-parts":[[2023,10,9]],"date-time":"2023-10-09T00:00:00Z","timestamp":1696809600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,10,9]],"date-time":"2023-10-09T00:00:00Z","timestamp":1696809600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Data61","award":["scholarships"],"award-info":[{"award-number":["scholarships"]}]},{"DOI":"10.13039\/501100001791","name":"Griffith University","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100001791","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Heuristics"],"published-print":{"date-parts":[[2023,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>A travelling thief problem (TTP) is a proxy to real-life problems such as postal collection. TTP comprises an entanglement of a travelling salesman problem (TSP) and a knapsack problem (KP) since items of KP are scattered over cities of TSP, and a thief has to visit cities to collect items. In TTP, city selection and item selection decisions need close coordination since the thief\u2019s travelling speed depends on the knapsack\u2019s weight and the order of visiting cities affects the order of item collection. Existing TTP solvers deal with city selection and item selection separately, keeping decisions for one type unchanged while dealing with the other type. This separation essentially means very poor coordination between two types of decision. In this paper, we first show that a simple local search based coordination approach does not work in TTP. Then, to address the aforementioned problems, we propose a human designed coordination heuristic that makes changes to collection plans during exploration of cyclic tours. We further propose another human designed coordination heuristic that explicitly exploits the cyclic tours in item selections during collection plan exploration. Lastly, we propose a machine learning based coordination heuristic that captures characteristics of the two human designed coordination heuristics. Our proposed coordination based approaches help our TTP solver significantly outperform existing state-of-the-art TTP solvers on a set of benchmark problems. Our solver is named Cooperation Coordination (CoCo) and its source code is available from<jats:ext-link xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" ext-link-type=\"uri\" xlink:href=\"https:\/\/github.com\/majid75\/CoCo\">https:\/\/github.com\/majid75\/CoCo<\/jats:ext-link>.<\/jats:p>","DOI":"10.1007\/s10732-023-09518-7","type":"journal-article","created":{"date-parts":[[2023,10,9]],"date-time":"2023-10-09T08:59:07Z","timestamp":1696841947000},"page":"487-544","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Solving travelling thief problems using coordination based methods"],"prefix":"10.1007","volume":"29","author":[{"given":"Majid","family":"Namazi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5655-0683","authenticated-orcid":false,"given":"M. A. Hakim","family":"Newton","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Conrad","family":"Sanderson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Abdul","family":"Sattar","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,10,9]]},"reference":[{"key":"9518_CR1","doi-asserted-by":"crossref","unstructured":"Ali, F., Mohamedkhair, M.: Hyper-heuristic approaches for the travelling thief problem. In: International Conference on Computer, Control, Electrical, and Electronics Engineering (ICCCEEE), pp. 1\u20136 (2020)","DOI":"10.1109\/ICCCEEE49695.2021.9429559"},{"issue":"1","key":"9518_CR2","doi-asserted-by":"publisher","first-page":"82","DOI":"10.1287\/ijoc.15.1.82.15157","volume":"15","author":"D Applegate","year":"2003","unstructured":"Applegate, D., Cook, W., Rohe, A.: Chained Lin\u2013Kernighan for large traveling salesman problems. INFORMS J. Comput. 15(1), 82\u201392 (2003)","journal-title":"INFORMS J. Comput."},{"key":"9518_CR3","doi-asserted-by":"crossref","unstructured":"Balas, E.: The prize collecting traveling salesman problem and its applications. The traveling salesman problem and its variations, pp. 663\u2013695. Springer, Berlin (2007)","DOI":"10.1007\/0-306-48213-4_14"},{"issue":"11","key":"9518_CR4","doi-asserted-by":"publisher","first-page":"1844","DOI":"10.1016\/j.cor.2009.05.004","volume":"37","author":"B Bontoux","year":"2010","unstructured":"Bontoux, B., Artigues, C., Feillet, D.: A memetic algorithm with a large neighborhood crossover operator for the generalized traveling salesman problem. Comput. Oper. Res. 37(11), 1844\u20131852 (2010)","journal-title":"Comput. Oper. Res."},{"key":"9518_CR5","doi-asserted-by":"crossref","unstructured":"Bonyadi, M.R., Michalewicz, Z., Barone, L.: The travelling thief problem: The first step in the transition from theoretical problems to realistic problems. In: IEEE Congress on Evolutionary Computation (CEC), pp. 1037\u20131044 (2013)","DOI":"10.1109\/CEC.2013.6557681"},{"key":"9518_CR6","doi-asserted-by":"crossref","unstructured":"Bonyadi, M.R., Michalewicz, Z., Przybylek, M.R., Wierzbicki, A.: Socially inspired algorithms for the travelling thief problem. In: Annual Conference on Genetic and Evolutionary Computation, pp. 421\u2013428 (2014)","DOI":"10.1145\/2576768.2598367"},{"key":"9518_CR7","doi-asserted-by":"crossref","unstructured":"Bonyadi, M.R., Michalewicz, Z., Wagner, M., Neumann, F.: Evolutionary computation for multicomponent problems: opportunities and future directions. In: Optimization in Industry, pp. 13\u201330. Springer, Berlin (2019)","DOI":"10.1007\/978-3-030-01641-8_2"},{"issue":"6","key":"9518_CR8","doi-asserted-by":"publisher","first-page":"791","DOI":"10.1287\/opre.6.6.791","volume":"6","author":"GA Croes","year":"1958","unstructured":"Croes, G.A.: A method for solving traveling-salesman problems. Oper. Res. 6(6), 791\u2013812 (1958)","journal-title":"Oper. Res."},{"issue":"82","key":"9518_CR9","doi-asserted-by":"publisher","first-page":"5026","DOI":"10.21105\/joss.05026","volume":"8","author":"RR Curtin","year":"2023","unstructured":"Curtin, R.R., Edel, M., Shrit, O., Agrawal, S., Basak, S., Balamuta, J.J., Sanderson, C.: mlpack 4: a fast, header-only C++ machine learning library. J. Open Source Softw. 8(82), 5026 (2023)","journal-title":"J. Open Source Softw."},{"key":"9518_CR10","first-page":"793","volume":"7","author":"B Delaunay","year":"1934","unstructured":"Delaunay, B.: Sur la sph\u00e8re vide. Izvestia Akademii Nauk SSSR, Otdelenie Matematicheskikh i Estestvennykh Nauk 7, 793\u2013800 (1934)","journal-title":"Izvestia Akademii Nauk SSSR, Otdelenie Matematicheskikh i Estestvennykh Nauk"},{"issue":"1","key":"9518_CR11","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1006\/jcph.1993.1010","volume":"104","author":"G Dueck","year":"1993","unstructured":"Dueck, G.: New optimization heuristics: the great deluge algorithm and the record-to-record travel. J. Comput. Phys. 104(1), 86\u201392 (1993)","journal-title":"J. Comput. Phys."},{"key":"9518_CR12","doi-asserted-by":"crossref","unstructured":"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, pp. 317\u2013324 (2016)","DOI":"10.1145\/2908812.2908847"},{"key":"9518_CR13","doi-asserted-by":"publisher","first-page":"795","DOI":"10.1016\/j.asoc.2016.09.047","volume":"52","author":"M El Yafrani","year":"2017","unstructured":"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\u2013804 (2017)","journal-title":"Appl. Soft Comput."},{"key":"9518_CR14","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1016\/j.ins.2017.12.011","volume":"432","author":"M El Yafrani","year":"2018","unstructured":"El Yafrani, M., Ahiod, B.: Efficiently solving the Traveling Thief Problem using hill climbing and simulated annealing. Inf. Sci. 432, 231\u2013244 (2018)","journal-title":"Inf. Sci."},{"issue":"1\u20132","key":"9518_CR15","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1007\/s10710-017-9308-x","volume":"19","author":"M El Yafrani","year":"2018","unstructured":"El Yafrani, M., Martins, M., Wagner, M., Ahiod, B., Delgado, M., L\u00fcders, R.: A hyperheuristic approach based on low-level heuristics for the travelling thief problem. Genet. Program Evolvable Mach. 19(1\u20132), 121\u2013150 (2018)","journal-title":"Genet. Program Evolvable Mach."},{"key":"9518_CR16","doi-asserted-by":"crossref","unstructured":"Faulkner, H., Polyakovskiy, S., Schultz, T., Wagner, M.: Approximate approaches to the traveling thief problem. In: Annual Conference on Genetic and Evolutionary Computation, pp. 385\u2013392 (2015)","DOI":"10.1145\/2739480.2754716"},{"key":"9518_CR17","volume-title":"The Traveling Salesman Problem and Its Variations","author":"G Gutin","year":"2006","unstructured":"Gutin, G., Punnen, A.P.: The Traveling Salesman Problem and Its Variations. Springer, Berlin (2006)"},{"key":"9518_CR18","doi-asserted-by":"publisher","DOI":"10.1016\/j.scs.2020.102393","volume":"62","author":"M Hannan","year":"2020","unstructured":"Hannan, M., Begum, R., Al-Shetwi, A.Q., Ker, P., Al Mamun, M., Hussain, A., Mahlia, T.: Waste collection route optimisation model for linking cost saving and emission reduction to achieve sustainable development goals. Sustain. Cities Soc. 62, 102393 (2020)","journal-title":"Sustain. Cities Soc."},{"key":"9518_CR19","doi-asserted-by":"crossref","unstructured":"Kellerer, H., Pferschy, U., Pisinger, D.: Introduction to NP-completeness of knapsack problems. Knapsack problems, pp. 483\u2013493. Springer, Berlin (2004)","DOI":"10.1007\/978-3-540-24777-7_16"},{"issue":"9","key":"9518_CR20","doi-asserted-by":"publisher","first-page":"857","DOI":"10.1016\/0305-0548(95)00079-8","volume":"23","author":"J-U Kim","year":"1996","unstructured":"Kim, J.-U., Kim, Y.-D.: Simulated annealing and genetic algorithms for scheduling products with multi-level product structure. Comput. Oper. Res. 23(9), 857\u2013868 (1996)","journal-title":"Comput. Oper. Res."},{"issue":"2\u20133","key":"9518_CR21","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1016\/0166-218X(90)90100-Q","volume":"26","author":"G Laporte","year":"1990","unstructured":"Laporte, G., Martello, S.: The selective travelling salesman problem. Discrete Appl. Math. 26(2\u20133), 193\u2013207 (1990)","journal-title":"Discrete Appl. Math."},{"key":"9518_CR22","doi-asserted-by":"publisher","DOI":"10.1016\/j.asoc.2020.106284","volume":"93","author":"A Maity","year":"2020","unstructured":"Maity, A., Das, S.: Efficient hybrid local search heuristics for solving the travelling thief problem. Appl. Soft Comput. 93, 106284 (2020)","journal-title":"Appl. Soft Comput."},{"key":"9518_CR23","doi-asserted-by":"crossref","unstructured":"Martins, M.S., El Yafrani, M., Delgado, M.R., Wagner, M., Ahiod, B., L\u00fcders, R.: HSEDA: A heuristic selection approach based on estimation of distribution algorithm for the travelling thief problem. In: Proceedings of the Genetic and Evolutionary Computation Conference, pp. 361\u2013368 (2017)","DOI":"10.1145\/3071178.3071235"},{"key":"9518_CR24","doi-asserted-by":"crossref","unstructured":"Mei, Y., Li, X., Yao, X.: Improving efficiency of heuristics for the large scale traveling thief problem. Simulated evolution and learning. Lecture Notes in Computer Science (LNCS), vol. 8886, pp. 631\u2013643 (2014)","DOI":"10.1007\/978-3-319-13563-2_53"},{"key":"9518_CR25","doi-asserted-by":"crossref","unstructured":"Mei, Y., Li, X., Salim, F., Yao, X.: Heuristic evolution with genetic programming for traveling thief problem. In: IEEE Congress on Evolutionary Computation (CEC), pp. 2753\u20132760 (2015)","DOI":"10.1109\/CEC.2015.7257230"},{"issue":"1","key":"9518_CR26","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1007\/s00500-014-1487-2","volume":"20","author":"Y Mei","year":"2016","unstructured":"Mei, Y., Li, X., Yao, X.: On investigation of interdependence between subproblems of the travelling thief problem. Soft. Comput. 20(1), 157\u2013172 (2016)","journal-title":"Soft. Comput."},{"key":"9518_CR27","doi-asserted-by":"crossref","unstructured":"Michalewicz, Z.: Quo vadis, evolutionary computation? In: IEEE World Congress on Computational Intelligence, pp. 98\u2013121 (2012)","DOI":"10.1007\/978-3-642-30687-7_6"},{"key":"9518_CR28","doi-asserted-by":"crossref","unstructured":"Nagata, Y.: New EAX crossover for large TSP instances. Parallel problem solving from nature\u2014PPSN IX, pp. 372-381. Springer, Berlin (2006)","DOI":"10.1007\/11844297_38"},{"key":"9518_CR29","doi-asserted-by":"crossref","unstructured":"Namazi, M., Newton, M.A., Sattar, A., Sanderson, C.: A profit guided coordination heuristic for travelling thief problems. In: Proceedings of the International Symposium on Combinatorial Search, vol. 10, pp. 140\u2013144 (2019)","DOI":"10.1609\/socs.v10i1.18513"},{"key":"9518_CR30","doi-asserted-by":"crossref","unstructured":"Namazi, M., Sanderson, C., Newton, M.A., Sattar, A.: Surrogate assisted optimisation for travelling thief problems. In: Proceedings of the International Symposium on Combinatorial Search, vol. 11, pp. 111\u2013115 (2020)","DOI":"10.1609\/socs.v11i1.18542"},{"issue":"11","key":"9518_CR31","doi-asserted-by":"publisher","first-page":"1877","DOI":"10.1016\/j.cor.2009.06.014","volume":"37","author":"SU Ngueveu","year":"2010","unstructured":"Ngueveu, S.U., Prins, C., Calvo, R.W.: An effective memetic algorithm for the cumulative capacitated vehicle routing problem. Comput. Oper. Res. 37(11), 1877\u20131885 (2010)","journal-title":"Comput. Oper. Res."},{"key":"9518_CR32","doi-asserted-by":"crossref","unstructured":"Nikfarjam, A., Neumann, A., Neumann, F.: On the use of quality diversity algorithms for the traveling thief problem. In: Proceedings of the Genetic and Evolutionary Computation Conference, pp. 260\u2013268 (2022)","DOI":"10.1145\/3512290.3528752"},{"issue":"2","key":"9518_CR33","doi-asserted-by":"publisher","first-page":"424","DOI":"10.1016\/j.ejor.2016.09.035","volume":"258","author":"S Polyakovskiy","year":"2017","unstructured":"Polyakovskiy, S., Neumann, F.: The packing while traveling problem. Eur. J. Oper. Res. 258(2), 424\u2013439 (2017)","journal-title":"Eur. J. Oper. Res."},{"key":"9518_CR34","doi-asserted-by":"crossref","unstructured":"Polyakovskiy, S., Bonyadi, M.R.,Wagner, M., Michalewicz, Z., Neumann, F.: A comprehensive benchmark set and heuristics for the traveling thief problem. In: Annual Conference on Genetic and Evolutionary Computation, pp. 477\u2013484 (2014)","DOI":"10.1145\/2576768.2598249"},{"key":"9518_CR35","doi-asserted-by":"crossref","unstructured":"Potter, M.A., De Jong, K.A.: A cooperative coevolutionary approach to function optimization. In: International Conference on Parallel Problem Solving from Nature, pp. 249\u2013257 (1994)","DOI":"10.1007\/3-540-58484-6_269"},{"issue":"4","key":"9518_CR36","doi-asserted-by":"publisher","first-page":"376","DOI":"10.1287\/ijoc.3.4.376","volume":"3","author":"G Reinelt","year":"1991","unstructured":"Reinelt, G.: TSPLIB-A traveling salesman problem library. ORSA J. Comput. 3(4), 376\u2013384 (1991)","journal-title":"ORSA J. Comput."},{"key":"9518_CR37","doi-asserted-by":"crossref","unstructured":"Sachdeva, R., Neumann, F., Wagner, M.: The dynamic travelling thief problem: benchmarks and performance of evolutionary algorithms. In: International Conference on Neural Information Processing, pp. 220\u2013228 (2020)","DOI":"10.1007\/978-3-030-63823-8_27"},{"issue":"8","key":"9518_CR38","doi-asserted-by":"publisher","first-page":"889","DOI":"10.1016\/S0167-739X(00)00043-1","volume":"16","author":"T St\u00fctzle","year":"2000","unstructured":"St\u00fctzle, T., Hoos, H.H.: MAX-MIN ant system. Future Gen. Comput. Syst. 16(8), 889\u2013914 (2000)","journal-title":"Future Gen. Comput. Syst."},{"issue":"1","key":"9518_CR39","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.ejor.2010.03.045","volume":"209","author":"P Vansteenwegen","year":"2011","unstructured":"Vansteenwegen, P., Souffriau, W., Van Oudheusden, D.: The orienteering problem: a survey. Eur. J. Oper. Res. 209(1), 1\u201310 (2011)","journal-title":"Eur. J. Oper. Res."},{"issue":"2","key":"9518_CR40","doi-asserted-by":"publisher","first-page":"720","DOI":"10.1287\/trsc.2015.0584","volume":"50","author":"T Vidal","year":"2016","unstructured":"Vidal, T., Maculan, N., Ochi, L.S., Vaz Penna, P.H.: Large neighborhoods with implicit customer selection for vehicle routing problems with profits. Transp. Sci. 50(2), 720\u2013734 (2016)","journal-title":"Transp. Sci."},{"key":"9518_CR41","doi-asserted-by":"crossref","unstructured":"Wagner, M.: Stealing items more efficiently with ants: a swarm intelligence approach to the travelling thief problem. Swarm intelligence. Lecture Notes in Computer Science (LNCS), vol. 9882, pp. 273\u2013281 (2016)","DOI":"10.1007\/978-3-319-44427-7_25"},{"issue":"3","key":"9518_CR42","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1007\/s10732-017-9328-y","volume":"24","author":"M Wagner","year":"2018","unstructured":"Wagner, M., Lindauer, M., M\u00fds\u00fdr, M., Nallaperuma, S., Hutter, F.: A case study of algorithm selection for the traveling thief problem. J. Heurist. 24(3), 295\u2013320 (2018)","journal-title":"J. Heurist."},{"key":"9518_CR43","doi-asserted-by":"crossref","unstructured":"Wu, J.,Wagner, M., Polyakovskiy, S., Neumann, F.: Exact approaches for the travelling thief problem. In: Asia-Pacific Conference on Simulated Evolution and Learning, pp. 110\u2013121 (2017)","DOI":"10.1007\/978-3-319-68759-9_10"},{"key":"9518_CR44","doi-asserted-by":"crossref","unstructured":"Wuijts, R.H., Thierens, D.: Investigation of the traveling thief problem. In: Proceedings of the Genetic and Evolutionary Computation Conference, pp. 329\u2013337 (2019)","DOI":"10.1145\/3321707.3321766"},{"key":"9518_CR45","doi-asserted-by":"publisher","first-page":"54056","DOI":"10.1109\/ACCESS.2021.3070204","volume":"9","author":"Z Zhang","year":"2021","unstructured":"Zhang, Z., Yang, L., Kang, P., Jia, X., Zhang, W.: Solving the traveling thief problem based on item selection weight and reverse-order allocation. IEEE Access 9, 54056\u201354066 (2021)","journal-title":"IEEE Access"}],"container-title":["Journal of Heuristics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10732-023-09518-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10732-023-09518-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10732-023-09518-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,30]],"date-time":"2024-10-30T10:38:44Z","timestamp":1730284724000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10732-023-09518-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,10,9]]},"references-count":45,"journal-issue":{"issue":"4-6","published-print":{"date-parts":[[2023,12]]}},"alternative-id":["9518"],"URL":"https:\/\/doi.org\/10.1007\/s10732-023-09518-7","relation":{},"ISSN":["1381-1231","1572-9397"],"issn-type":[{"type":"print","value":"1381-1231"},{"type":"electronic","value":"1572-9397"}],"subject":[],"published":{"date-parts":[[2023,10,9]]},"assertion":[{"value":"7 July 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 May 2023","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 September 2023","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 October 2023","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no conflicting or competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}},{"value":"This research does not involve any ethical issues.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethics approval"}},{"value":"All authors give consent for publication.","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent for publication"}}]}}