{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,10]],"date-time":"2025-12-10T16:13:25Z","timestamp":1765383205088,"version":"3.46.0"},"reference-count":49,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2025,8,14]],"date-time":"2025-08-14T00:00:00Z","timestamp":1755129600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,8,14]],"date-time":"2025-08-14T00:00:00Z","timestamp":1755129600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/M007243\/1","EP\/M007243\/1","EP\/M007243\/1"],"award-info":[{"award-number":["EP\/M007243\/1","EP\/M007243\/1","EP\/M007243\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Oper. Res. Forum"],"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>Real-world combinatorial optimization problems are mostly NP-hard, and often only near-optimal solutions can be obtained practically. To differentiate as fine-grained as possible the near-optimal solutions is therefore desirable. Moreover, a real-world problem may have numerous possible structural properties of concern to the practitioners, too numerous to be all elicited and incorporated as optimization criteria in an objective function. In contrast with pure heuristics, we consider hybrid (meta-)heuristics that utilize an exact solver iteratively to solve a series of significantly reduced problem instances converging to near-optimal solutions within practical time. To avoid the hybrid heuristic being stranded in a \u201cpoorly differentiated\u201d solution space, an effective objective function design plays an important role. We propose a methodology to benchmark the effectiveness of alternative objective function designs. The main metric used is the structural similarity between the solutions obtained by the hybrid heuristic and by the exact solver. Several other solution features are also distilled and aggregated in the benchmark. This methodology is explained and demonstrated on a train unit scheduling problem tested with four alternative objective functions. The results show that two of them are significantly more effective than the others in differentiating solutions of different qualities and speeding up the solution process. Moreover, some criteria not modeled explicitly could also be satisfied implicitly in the effective objective designs.<\/jats:p>","DOI":"10.1007\/s43069-025-00529-7","type":"journal-article","created":{"date-parts":[[2025,8,14]],"date-time":"2025-08-14T13:59:54Z","timestamp":1755179994000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["An Auxiliary Hybrid Heuristic Approach for Objective Function Design Evaluation\u2014Using Train Unit Scheduling as an Example"],"prefix":"10.1007","volume":"6","author":[{"given":"Li","family":"Lei","sequence":"first","affiliation":[]},{"given":"Raymond","family":"Kwan","sequence":"additional","affiliation":[]},{"given":"Zhiyuan","family":"Lin","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,8,14]]},"reference":[{"issue":"1","key":"529_CR1","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1007\/s12469-013-0073-9","volume":"6","author":"Z Lin","year":"2014","unstructured":"Lin Z, Kwan RSK (2014) A two-phase approach for real-world train unit scheduling. Public Transp 6(1):35\u201365","journal-title":"Public Transp"},{"key":"529_CR2","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1016\/j.trb.2016.09.007","volume":"94","author":"Z Lin","year":"2016","unstructured":"Lin Z, Kwan RSK (2016) A branch-and-price approach for solving the train unit scheduling problem. Transp Res Part B: Methodol 94:97\u2013120","journal-title":"Transp Res Part B: Methodol"},{"issue":"3","key":"529_CR3","doi-asserted-by":"publisher","first-page":"881","DOI":"10.1007\/s10589-016-9831-3","volume":"64","author":"Z Lin","year":"2016","unstructured":"Lin Z, Kwan RS (2016) Local convex hulls for a special class of integer multicommodity flow problems. Comput Optim Appl 64(3):881\u2013919","journal-title":"Comput Optim Appl"},{"issue":"1\u20132","key":"529_CR4","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1007\/s12469-016-0138-7","volume":"9","author":"Z Lin","year":"2017","unstructured":"Lin Z, Barrena E, Kwan RSK (2017) Train unit scheduling guided by historic capacity provisions and passenger count surveys. Public Trans 9(1\u20132):137\u2013154","journal-title":"Public Trans"},{"key":"529_CR5","doi-asserted-by":"crossref","unstructured":"Lei L, Kwan R, Lin Z, Copado-Mendez PJ (2018) Resolution of station level constraints in train unit scheduling. In: 14th International conference on advanced systems in public transport and transitdata. Brisbane, Australia","DOI":"10.1007\/s12469-022-00295-3"},{"key":"529_CR6","unstructured":"Luo Y, Lin Z, Liu R (2025) Train unit scheduling optimization considering unit ordering. arxiv:2506.16329"},{"key":"529_CR7","doi-asserted-by":"publisher","first-page":"4135","DOI":"10.1016\/j.asoc.2011.02.032","volume":"11","author":"C Blum","year":"2011","unstructured":"Blum C, Puchinger J, Raidl G, Roli A (2011) Hybrid metaheuristics in combinatorial optimization: a survey. Appl Soft Comput 11:4135\u20134151","journal-title":"Appl Soft Comput"},{"key":"529_CR8","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1016\/j.cor.2015.10.014","volume":"68","author":"C Blum","year":"2016","unstructured":"Blum C, Pinacho P, L\u00f3pez-Ib\u00e1\u00f1ez M, Lozano JA (2016) Construct, merge, solve & adapt a new general algorithm for combinatorial optimization. Comput Oper Res 68:75\u201388","journal-title":"Comput Oper Res"},{"issue":"1","key":"529_CR9","first-page":"83","volume":"1","author":"TL Saaty","year":"2008","unstructured":"Saaty TL (2008) Decision making with the analytic hierarchy process. Int J Serv Sci 1(1):83\u201398","journal-title":"Int J Serv Sci"},{"key":"529_CR10","unstructured":"Ehrgott M (2005) Multicriteria optimization. Springer, vol 491"},{"key":"529_CR11","unstructured":"Cohon JL (2004) Multiobjective programming and planning. Courier Corporation, vol 140"},{"issue":"3","key":"529_CR12","first-page":"296","volume":"1","author":"Y Haimes","year":"1971","unstructured":"Haimes Y (1971) On a bicriterion formulation of the problems of integrated system identification and system optimization. IEEE Trans Syst Man Cybern 1(3):296\u2013297","journal-title":"IEEE Trans Syst Man Cybern"},{"issue":"6","key":"529_CR13","doi-asserted-by":"publisher","first-page":"853","DOI":"10.1007\/s00158-009-0460-7","volume":"41","author":"RT Marler","year":"2010","unstructured":"Marler RT, Arora JS (2010) The weighted sum method for multi-objective optimization: new insights. Struct Multidisc Optim 41(6):853\u2013862","journal-title":"Struct Multidisc Optim"},{"issue":"462\u2013474","key":"529_CR14","first-page":"3","volume":"18","author":"V Pareto","year":"1912","unstructured":"Pareto V (1912) Manuel d\u2019\u00e9conomie politique. Bull Amer Math Soc 18(462\u2013474):3","journal-title":"Bull Amer Math Soc"},{"issue":"12","key":"529_CR15","doi-asserted-by":"publisher","first-page":"2568","DOI":"10.1109\/TCYB.2014.2310651","volume":"44","author":"M Li","year":"2014","unstructured":"Li M, Yang S, Liu X (2014) Diversity comparison of pareto front approximations in many-objective optimization. IEEE Trans Cybern 44(12):2568\u20132584","journal-title":"IEEE Trans Cybern"},{"issue":"10","key":"529_CR16","doi-asserted-by":"publisher","first-page":"927","DOI":"10.1016\/j.trb.2004.02.004","volume":"38","author":"K Ghoseiri","year":"2004","unstructured":"Ghoseiri K, Szidarovszky F, Asgharpour MJ (2004) A multi-objective train scheduling model and solution. Transp Res Part B: Methodol 38(10):927\u2013952","journal-title":"Transp Res Part B: Methodol"},{"issue":"5","key":"529_CR17","doi-asserted-by":"publisher","first-page":"1913","DOI":"10.1109\/TITS.2014.2303146","volume":"15","author":"X Yang","year":"2014","unstructured":"Yang X, Ning B, Li X, Tang T (2014) A two-objective timetable optimization model in subway systems. IEEE Trans Intell Transp Syst 15(5):1913\u20131921","journal-title":"IEEE Trans Intell Transp Syst"},{"key":"529_CR18","first-page":"335","volume":"113","author":"AH Chow","year":"2018","unstructured":"Chow AH, Pavlides A (2018) Cost functions and multi-objective timetabling of mixed train services. Transp Res Part A: Pol Pract 113:335\u2013356","journal-title":"Transp Res Part A: Pol Pract"},{"key":"529_CR19","doi-asserted-by":"publisher","first-page":"108","DOI":"10.1016\/j.engappai.2018.09.001","volume":"76","author":"E Montero","year":"2018","unstructured":"Montero E, Riff M-C, Rojas-Morales N (2018) Tuners review: how crucial are set-up values to find effective parameter values? Eng Appl Artif Intell 76:108\u2013118","journal-title":"Eng Appl Artif Intell"},{"key":"529_CR20","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1613\/jair.2861","volume":"36","author":"F Hutter","year":"2009","unstructured":"Hutter F, Hoos HH, Leyton-Brown K, St\u00fctzle T (2009) ParamILS: an automatic algorithm configuration framework. J Artif Intell Res 36:267\u2013306","journal-title":"J Artif Intell Res"},{"issue":"1","key":"529_CR21","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1016\/j.swevo.2011.02.001","volume":"1","author":"AE Eiben","year":"2011","unstructured":"Eiben AE, Smit SK (2011) Parameter tuning for configuring and analyzing evolutionary algorithms. Swarm Evol Comput 1(1):19\u201331","journal-title":"Swarm Evol Comput"},{"issue":"1","key":"529_CR22","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1287\/opre.1050.0243","volume":"54","author":"B Adenso-Diaz","year":"2006","unstructured":"Adenso-Diaz B, Laguna M (2006) Fine-tuning of algorithms using fractional experimental designs and local search. Oper Res 54(1):99\u2013114","journal-title":"Oper Res"},{"key":"529_CR23","doi-asserted-by":"crossref","unstructured":"Hutter F, Hoos HH, Leyton-Brown K (2011) Sequential model-based optimization for general algorithm configuration. In: International conference on learning and intelligent optimization. Springer, pp 507\u2013523","DOI":"10.1007\/978-3-642-25566-3_40"},{"key":"529_CR24","unstructured":"Birattari M, St\u00fctzle T, Paquete L, Varrentrapp K (2002) A racing algorithm for configuring metaheuristics. In: Proceedings of the 4th annual conference on genetic and evolutionary computation. Morgan Kaufmann Publishers Inc, pp 11\u201318"},{"key":"529_CR25","doi-asserted-by":"crossref","unstructured":"Balaprakash P, Birattari M, St\u00fctzle T (2007) Improvement strategies for the f-race algorithm: sampling design and iterative refinement. In: International workshop on hybrid metaheuristics. Springer, pp 108\u2013122","DOI":"10.1007\/978-3-540-75514-2_9"},{"key":"529_CR26","unstructured":"Hutter F, Hoos HH, St\u00fctzle T (2007) Automatic algorithm configuration based on local search. In: AAAI, vol 7, pp 1152\u20131157"},{"key":"529_CR27","doi-asserted-by":"crossref","unstructured":"Blot A, Hoos HH, Jourdan L, Kessaci-Marmion M-\u00c9, Trautmann H (2016) MO-ParamILS: a multi-objective automatic algorithm configuration framework. In: International conference on learning and intelligent optimization. Springer, pp 32\u201347","DOI":"10.1007\/978-3-319-50349-3_3"},{"issue":"3","key":"529_CR28","doi-asserted-by":"publisher","first-page":"491","DOI":"10.1016\/S0305-0548(03)00249-1","volume":"32","author":"MN Azaiez","year":"2005","unstructured":"Azaiez MN, Al Sharif SS (2005) A 0\u20131 goal programming model for nurse scheduling. Comput Oper Res 32(3):491\u2013507","journal-title":"Comput Oper Res"},{"issue":"2","key":"529_CR29","doi-asserted-by":"publisher","first-page":"120","DOI":"10.1057\/hs.2015.12","volume":"5","author":"M Mihaylov","year":"2016","unstructured":"Mihaylov M, Smet P, Van Den Noortgate W, Vanden Berghe G (2016) Facilitating the transition from manual to automated nurse rostering. Health Syst 5(2):120\u2013131","journal-title":"Health Syst"},{"key":"529_CR30","doi-asserted-by":"crossref","unstructured":"Tsuji Y, Kuroda M, Kitagawa Y, Imoto Y (2012) Ant colony optimization approach for solving rolling stock planning for passenger trains. In: 2012 IEEE\/SICE international symposium on system integration (SII). IEEE, pp 716\u2013721","DOI":"10.1109\/SII.2012.6427319"},{"issue":"2","key":"529_CR31","doi-asserted-by":"publisher","first-page":"1281","DOI":"10.1016\/j.ejor.2005.03.032","volume":"174","author":"P-J Fioole","year":"2006","unstructured":"Fioole P-J, Kroon L, Mar\u00f3ti G, Schrijver A (2006) A rolling stock circulation model for combining and splitting of passenger trains. Euro J Oper Res 174(2):1281\u20131297","journal-title":"Euro J Oper Res"},{"key":"529_CR32","doi-asserted-by":"publisher","first-page":"541","DOI":"10.1023\/A:1016540724870","volume":"8","author":"E-G Talbi","year":"2002","unstructured":"Talbi E-G (2002) A taxonomy of hybrid metaheuristics. J Heuristics 8:541\u2013564","journal-title":"J Heuristics"},{"key":"529_CR33","unstructured":"Christian\u00a0Blum GR (2016) Hybrid metaheuristics: powerful tools for optimization. Springer"},{"key":"529_CR34","doi-asserted-by":"publisher","first-page":"417","DOI":"10.1007\/s10479-007-0203-3","volume":"155","author":"R Kwan","year":"2007","unstructured":"Kwan R, Kwan A (2007) Effective search space control for large and\/or complex driver scheduling problems. Ann Oper Res 155:417\u2013435","journal-title":"Ann Oper Res"},{"key":"529_CR35","unstructured":"Kwan R (2004) Bus and train driver scheduling. Handbook of scheduling: algorithms, models, and performance analysis, pp 51\u20131"},{"key":"529_CR36","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1007\/s10951-010-0212-y","volume":"14","author":"R Kwan","year":"2011","unstructured":"Kwan R (2011) Case studies of successful train crew scheduling optimisation. J Schedul 14:423\u2013434","journal-title":"J Schedul"},{"key":"529_CR37","unstructured":"Copado-Mendez P, Lin Z, Kwan R (2017) Size limited iterative method (SLIM) for train unit scheduling. In: Proceedings of the 12th metaheuristics international conference. Barcelona, Spain"},{"key":"529_CR38","doi-asserted-by":"crossref","unstructured":"Nepomuceno N, Pinheiro P, Coelho ALV (2008) In: Cotta C, Hemert J (eds) A hybrid optimization framework for cutting and packing problems. Springer, Berlin, Heidelberg, pp 87\u201399","DOI":"10.1007\/978-3-540-70807-0_6"},{"key":"529_CR39","first-page":"17","volume":"339","author":"MA Akbay","year":"2021","unstructured":"Akbay MA, Blum C (2021) Application of CMSA to the minimum positive influence dominating set problem 339:17\u201326","journal-title":"Application of CMSA to the minimum positive influence dominating set problem"},{"key":"529_CR40","doi-asserted-by":"crossref","unstructured":"Blum C, Ochoa G (2020) A comparative analysis of two matheuristics by means of merged local optima networks. Euro J Oper Res 290","DOI":"10.1016\/j.ejor.2020.08.008"},{"key":"529_CR41","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s10732-020-09462-w","volume":"27","author":"J Ferrer","year":"2021","unstructured":"Ferrer J, Chicano F, Ortega-Toro J (2021) CMSA algorithm for solving the prioritized pairwise test data generation problem in software product lines. J Heuristics 27:1\u201321","journal-title":"J Heuristics"},{"key":"529_CR42","doi-asserted-by":"publisher","first-page":"551","DOI":"10.1007\/s10732-017-9329-x","volume":"24","author":"C Blum","year":"2018","unstructured":"Blum C, Blesa MJ (2018) A comprehensive comparison of metaheuristics for the repetition-free longest common subsequence problem. J Heuristics 24:551\u2013579","journal-title":"J Heuristics"},{"key":"529_CR43","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1007\/s10732-020-09450-0","volume":"27","author":"N Dupin","year":"2021","unstructured":"Dupin N, Talbi E-G (2021) Matheuristics to optimize refueling and maintenance planning of nuclear power plants. J Heuristics 27:63\u2013105","journal-title":"J Heuristics"},{"issue":"3","key":"529_CR44","doi-asserted-by":"publisher","first-page":"379","DOI":"10.1002\/j.1538-7305.1948.tb01338.x","volume":"27","author":"CE Shannon","year":"1948","unstructured":"Shannon CE (1948) A mathematical theory of communication. Bell Syst Tech J 27(3):379\u2013423","journal-title":"Bell Syst Tech J"},{"key":"529_CR45","doi-asserted-by":"crossref","unstructured":"Saaty TL, Vargas LG (2012) Models, methods, concepts & applications of the analytic hierarchy process. Springer, vol 175","DOI":"10.1007\/978-1-4614-3597-6"},{"issue":"2","key":"529_CR46","doi-asserted-by":"publisher","first-page":"206","DOI":"10.1002\/net.21969","volume":"76","author":"Z Lin","year":"2020","unstructured":"Lin Z, Kwan RSK (2020) Avoiding unnecessary demerging and remerging of multi-commodity integer flows. Networks 76(2):206\u2013231","journal-title":"Networks"},{"key":"529_CR47","doi-asserted-by":"crossref","unstructured":"Stadler PF (2002) Fitness landscapes. Biol Evol Stat Phys 183\u2013204","DOI":"10.1007\/3-540-45692-9_10"},{"key":"529_CR48","doi-asserted-by":"publisher","first-page":"148","DOI":"10.1016\/j.ins.2013.04.015","volume":"241","author":"KM Malan","year":"2013","unstructured":"Malan KM, Engelbrecht AP (2013) A survey of techniques for characterising fitness landscapes and some possible ways forward. Inf Sci 241:148\u2013163","journal-title":"Inf Sci"},{"key":"529_CR49","unstructured":"Reidys CM, Stadler PF (1997) Combinatorial landscapes. Santa Fe Institute"}],"container-title":["Operations Research Forum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s43069-025-00529-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s43069-025-00529-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s43069-025-00529-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,12,10]],"date-time":"2025-12-10T16:08:24Z","timestamp":1765382904000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s43069-025-00529-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,8,14]]},"references-count":49,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2025,9]]}},"alternative-id":["529"],"URL":"https:\/\/doi.org\/10.1007\/s43069-025-00529-7","relation":{},"ISSN":["2662-2556"],"issn-type":[{"type":"electronic","value":"2662-2556"}],"subject":[],"published":{"date-parts":[[2025,8,14]]},"assertion":[{"value":"17 September 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 August 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 August 2025","order":3,"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 competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of Interest"}}],"article-number":"121"}}