An auxiliary hybrid heuristic approach for objective function design evaluation
Authors:
Preprint
- 19 April 2023
- preprint
- Published by Springer Nature in Research Square
Abstract
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 utilise 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 “poorly differentiated” 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.Keywords
All Related Versions
This publication has 25 references indexed in Scilit:
- CMSA algorithm for solving the prioritized pairwise test data generation problem in software product linesJournal of Heuristics, 2020
- Matheuristics to optimize refueling and maintenance planning of nuclear power plantsJournal of Heuristics, 2020
- A comprehensive comparison of metaheuristics for the repetition-free longest common subsequence problemJournal of Heuristics, 2017
- Train unit scheduling guided by historic capacity provisions and passenger count surveysPublic Transport, 2016
- Local convex hulls for a special class of integer multicommodity flow problemsComputational Optimization and Applications, 2016
- A two-phase approach for real-world train unit schedulingPublic Transport, 2013
- Hybrid metaheuristics in combinatorial optimization: A surveyApplied Soft Computing, 2011
- Case studies of successful train crew scheduling optimisationJournal of Scheduling, 2010
- A Hybrid Optimization Framework for Cutting and Packing Problems2008
- Effective search space control for large and/or complex driver scheduling problemsAnnals of Operations Research, 2007