A Meta-Heuristic Factory for Vehicle Routing Problems

摘要: This paper presents a generic technique for improving constraint-based heuristics through the discovery of meta-heuristics. The idea is to represent family “push/pull” algorithms, based on inserting and removing tasks in current solution, with an algebra let learning algorithm search best possible algebraic term (which represents hybrid algorithm), given set problems optimization criterion. describes application this using vehicle routing time windows (VRPTW) as domain example, although approach can be applied many other which seen assignment resources (generalized assignments). We suppose that domain-dependent (constraint-based) has been built, able insert remove handle domain-specific constraints. Our goal improve such techniques like LDS (Limited Discrepancy Search), LNS (Large Neighborhood ejection trees or chains, described manner insertion deletion operations. show automatic tuning combination yields better solution than hand-tuning, considerably less effort. contribution thus twofold: we demonstrate meta-heuristics new best-known results Solomon benchmarks, provide method automatically adjust different sizes, complexity objectives.