Bin Packing/Covering with Delivery, solved with the evolution of algorithms
Attila Benkő, György Dósa, Źsolt Tuza · 2010
We deal with a new problem that we call Bin Packing/Covering with Delivery. Mainly we mean under this expression that we look for not only a good, but a “good and fast” packing or covering. In a recent manuscript defined several ways to treat such a problem, and investigate here one of them. We design polynomial-time algorithms finding exact offline solutions on a large class of problem instances, prove non-approximability in general, and also propose a new method that we call the “Evolution of Algorithms” for the online setting, to solve this (algorithmically very hard) problem. In case of such methods a neighborhood structure is defined among algorithms, and using a metaheuristic (simulated annealing in this paper) in some sense the best algorithm is chosen to solve the problem. We show the efficiency of the proposed method by several computer tests.