An Auxiliary Hybrid Heuristic Approach for Objective Function Design Evaluation-Using Train Unit Scheduling as an...

Area of Science:

• Operations Research
• Computer Science
• Applied Mathematics

Background:

• Real-world optimization problems are often NP-hard, necessitating near-optimal solutions.
• Differentiating between near-optimal solutions is crucial for practical applications.
• Incorporating numerous structural properties into objective functions is challenging.

Purpose of the Study:

• To propose and demonstrate a methodology for benchmarking objective function designs in hybrid heuristics.
• To assess the effectiveness of objective functions in differentiating solution quality and speeding up the solution process.
• To explore implicit satisfaction of unmodeled criteria through effective objective design.

Main Methods:

• Utilizing hybrid (meta-)heuristics that iteratively employ an exact solver on reduced problem instances.
• Developing a benchmarking methodology with structural similarity to exact solutions as the primary metric.
• Aggregating other solution features and evaluating alternative objective functions on a train unit scheduling problem.

Main Results:

• Two of the four tested objective functions proved significantly more effective than others.
• Effective objective functions enhanced solution differentiation and accelerated the solution process.
• Implicit satisfaction of certain criteria was observed with well-designed objective functions.

Conclusions:

• The proposed benchmarking methodology effectively evaluates objective function designs for hybrid heuristics.
• Objective function design is critical for avoiding poorly differentiated solution spaces.
• Effective objective functions can lead to better quality solutions and implicit satisfaction of practical constraints.