×

Learning hybrid algorithms for vehicle routing problems. (English) Zbl 1066.68536

Summary: This paper presents a generic technique for improving hybrid algorithms through the discovery of and tuning of meta-heuristics. The idea is to represent a family of ‘push/pull’ heuristics that are based upon inserting and removing tasks in a current solution, with an algebra. We then let a learning algorithm search for the best possible algebraic term, which represents a hybrid algorithm for a given set of problems and an optimization criterion.
In a previous paper, we described this algebra in detail and provided a set of preliminary results demonstrating the utility of this approach, using vehicle routing with time windows as a domain example. In this paper we expand upon our results providing a more robust experimental framework and learning algorithms, and report on some new results using the standard Solomon benchmarks. In particular, we show that our learning algorithm is able to achieve results similar to the best-published algorithms using only a fraction of the CPU time. We also show that the automatic tuning of the best hybrid combination of such techniques yields a better solution than hand tuning, with considerably less effort.

MSC:

68T05 Learning and adaptive systems in artificial intelligence
68N19 Other programming paradigms (object-oriented, sequential, concurrent, automatic, etc.)
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
90C27 Combinatorial optimization
PDFBibTeX XMLCite