We present a hybrid solver (called GELATO) that exploits the potentiality of a Constraint Programming (CP) environment (Gecode) and of a Local Search (LS) framework (EasyLocal++). GELATO allows the user to easily develop and use hybrid meta-heuristic combining CP and LS phases (in particular Large Neighborhood Search). We tested some hybrid algorithms on different instances of the Asymmetric Traveling Salesman Problem: even if only naive LS strategies have been used, our meta-heuristics improve the standard CP and LS methods, in terms of both quality of the solution reached and execution time. GELATO will be integrated into a more general tool to solve Constraint Satisfaction/ Optimization Problems. Moreover, it can be seen as a new library for approximate and efficient searching in Gecode.
A Hybrid Solver for Large Neighborhood Search: Mixing Gecode and EasyLocal++
CIPRIANO, Raffaele;DI GASPERO, Luca;DOVIER, Agostino
2009-01-01
Abstract
We present a hybrid solver (called GELATO) that exploits the potentiality of a Constraint Programming (CP) environment (Gecode) and of a Local Search (LS) framework (EasyLocal++). GELATO allows the user to easily develop and use hybrid meta-heuristic combining CP and LS phases (in particular Large Neighborhood Search). We tested some hybrid algorithms on different instances of the Asymmetric Traveling Salesman Problem: even if only naive LS strategies have been used, our meta-heuristics improve the standard CP and LS methods, in terms of both quality of the solution reached and execution time. GELATO will be integrated into a more general tool to solve Constraint Satisfaction/ Optimization Problems. Moreover, it can be seen as a new library for approximate and efficient searching in Gecode.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.