Tailoring Optimization Approaches with Domain Knowledge in Industry Process for Meta-heuristic Development
Organizations: Wrocław University of Science and Technology, Faculty of Information and Communication Technology, ul. Ignacego Łukasiewicza 5, 50-371 Wrocław, Poland · University of Zagreb, Faculty of Electrical Engineering and Computing, Unska ul. 3, 10000 Zagreb, Croatia · Melbourne, Victoria, Australia
Abstract
The paper presents an Industry Process for Meta-heuristic Development (IPMD) schema, a systematic methodology for applying meta- and hyper-heuristic applications to optimization problems. In this context, we present a case study of Balancing Non-dominated Tournament Genetic Programming (BNTGP) applied to solve two NP-hard multi-objective optimization problems: routing (Capacitated Vehicle Routing Problem with Time Windows) and scheduling (Multi-Skill Resource Constrained Project Scheduling Problem). The BNTGP method is based on a metaheuristic design. Its genetic programming-based representation makes BNTGP a hyper-heuristic, as it enables the exploration of a search space of heuristics for solving problems in general. The resulting heuristic can then be applied across a set of problem instances.
Figures & tables
| Aspect | CVRPTW | MS-RCPSP |
|---|---|---|
| Type | Routing problem | Scheduling problem |
| Decision variable | Customer | Activity–resource pair |
| Decoder | Route builder | Schedule builder |
| Constraints | Capacity, time windows | Skills, task precedence |
| Basic features | Distance, demand | Duration, skills, costs |
| Domain features | Regional descriptors | Pairwise descriptors |
Metaheuristic Optimization
Metaheuristic optimization develops flexible search strategies for finding strong solutions to difficult problems when exact methods are too costly.
See all 122 papers