Hybrid Metaheuristics

Research in metaheuristics for combinatorial optimization problems has lately experienced a noteworthy shift towards the hybridization of metaheuristics with other techniques for optimization. At the same time, the focus of research has changed from being rather algorithm-oriented to being more problem-oriented. Nowadays the focus is on solving a problem at hand in the best way possible, rather than promoting a certain metaheuristic. This has led to an enormously fruitful cross-fertilization of different areas of optimization, algorithmics, mathematical modeling, operations research, statistics, simulation, and other fields. This cross-fertilization has resulted in a multitude of powerful hybrid algorithms that were obtained by combining components or concepts from different optimization techniques. Hereby, hybridization is not restricted to different variants of metaheuristics but includes, for example, the combination of mathematical programming, dynamic programming, constraint programming or statistical modeling with metaheuristics.

Logistics and transportation are some areas that use mathematical programming and heuristic methods to solve many of their problems. In practice, Mixed-Integer Programming (MIP) is very popular for addressing combinatorial optimization problems in these areas, since a mathematical model holds true for a given problem. The success of MIP lies mainly in the powerful MIP solvers that exist today, such as: GUROBI, CPLEX Optimizer, GLPK, SCIP or XPRESS.  Con un modelo adecuado, estos solucionadores a menudo son capaces de resolver instancias de problemas difíciles en un tiempo razonable, y si la optimización se cancela antes, aún pueden dar soluciones aproximadas útiles junto con garantías de calidad de un umbral.

 

This investigation tries to apply several prominent hybridization techniques that have proven to be successful on a large variety of applications to Traveling Car Renter Salesman Problem. The Traveling Car Renter Salesman Problem or simply Traveling Car Renter Problem (CaRS), is a generalization of the Traveling Salesman Problem (TSP) where the tour can be decomposed into contiguous sub-tours that are travelled by di erent rented cars. The objective is to construct a minimal cost Hamiltonian circuit, considering the penalty paid for changing cars for another on the tour, this penalty is the cost of returning a car to the city where it was rented. CaRS is classi ed as a NP-hard problem. This work studies the CaRS version classi ed as: complete, total, unrestricted, with no repetition, free and symmetric. This research is focused on hybrid procedures that combine metaheuristics and linear programming (LP) based on the branch-and-bound algorithm. Metaheuristics and procedures based on exact methods are hybridized, such as: Scienti c algorithms (ScA), Evolutionary algorithms (EA), Adaptive Local Search Procedure (ASLP) and a new variant of ALSP called Iterated Adaptive Local Search Procedure (IALSP). The following techniques are proposed to deal with CaRS: ScA+ALSP, EA+IALSP e ScA+IALSP. A mixed integer programming model proposed for CaRS is corrected and then used by ALSP and IALSP. Non-parametric tests are used to compare the algorithms within a set of instances from the literature.

Figura 1. Status of the variables among the ALSP and IALSP sets.

Variables in the ALSP and IALSP can be classified as: fixed (S), test (T ) and non-fixed ( S̄ ).  We refer to the collection of variables (those with the same status) as a set instead of a group. Fig. 1 shows the process of changing variables among sets S, T and S̄ to ALSP and IALSP. Initially, all variables are in S. Both T and S̄ are empty. Subsequently, a subset of variables from S is randomly chosen and assigned to T with |T| = size. S is updated with the difference between S and T . Finally, there are two cases in which variables from T change sets. First, if maxLRgap is large or the optimization is finished due to processing time limit, variables from T are added to S and T becomes empty, the process is repeated. In the second case, if the solution found for a sub-problem is equal to or better than the incumbent solution, the variables from T are added to S̄ and T becomes empty. In this case, the process is repeated with S = S − T . This process continues until S becomes empty or the runtime for the ALSP is exceeded. 

Algorithm 1 presents a pseudo-code for the ScA+ALSP for a minimization problem. First, ScA provides a solution, sol, which is transformed into an incumbent solution, solInc, for the proposed model (proposed formulation). Solution sol can be the minimal set of variables, which represents unambiguously a single solution. Second, the strategy used in ALSP was 10-stages, i.e. 10 consecutive executions, where the final solution of an execution was given as the initial solution of the next execution (10 times). If the MIP solver finds an optimal solution, optSolInc, in the extended formulation, solInc becomes optSolInc. Finally, once the execution of the ALSP algorithm is complete, solInc (best solution found by ALSP) is returned. This same idea is applied to algorithms 2.
 
For more details about the research visit the next articles:

• A hybrid metaheuristic using a corrected formulation for the Traveling Car Renter Salesman Problem.
• A Hybrid Metaheuristic for the Traveling Car Renter Salesman Problem.