50 Years of Metaheuristics

In this talk, we review the milestones in the development of heuristic methods for optimization over the last 50 years. We propose a critical analysis of the main findings and contributions. Starting with the roots of the area that can be traced back to the classical philosophers, we follow the historical path of heuristics and metaheuristics in the field of operations research and list the main milestones, up to the latest proposals to hybridize metaheuristics. We distinguish between well-established methodologies in our community as opposed to nature inspired methods in terms of their contribution to the field. We also comment on the evolution of the methodologies in the MIC conferences, and finish with the next generation of heuristics in the context of machine learning and quantum computing.

Surveying the literature, one could be excused for thinking that there exist hundreds or even thousands of different metaheuristics. We classify those metaheuristics according to the way in which they manipulate the solutions. Constructive heuristics, build solutions from their constituting elements. Local search heuristics perform small changes to a single solution iteratively to improve it as much as possible. Finally, Population-based heuristics combine solutions into new ones. These categories provide a natural way to approach heuristics both from a theoretical and a historical perspective. We do not try to cover all existing metaheuristic methodologies, but we limit ourselves to those that changed our way of thinking in problem solving, and in that sense may be considered the most relevant ones. This talks summarizes the research project carried out with Profs. Marc Sevaux and Kenneth Sörensen recently published in the European Journal of Operations Research (EJOR).

Solving large-scale vehicle routing problems ... and beyond !

Vehicle routing problems (VRPs) are at the core of distribution logistics optimization and huge research efforts were devoted to the development of effective heuristics for their solution. 

In recent years, the explosion of urban logistics introduced new challenges in this domain, related to both the need of handling specific constraints and to a drastic increase in the size of the instances which characterise real world applications. Unfortunately, most of the existing heuristic methods for VRP are one the one hand very effective in achieving high quality solutions on many practically relevant variants of the VRP, but  on the other hand do not scale very well with the growth of the size of the problem to be solved. 

We developed a family of heuristics, originated by the FILO algorithm, that were designed to achieve a linear growth of the computing time with respect to the instance size while preserving state-of-the-art solution quality. The most recent implementations of FILO were capable of solving large-scale problems with additional constraints and classical variants with up to one million customers in a handful of minutes. 

Variable Neighborhood Search: Application in Cross-Docking Optimization

This talk outlines the main variants of the Variable Neighborhood Search (VNS) metaheuristic proposed over the past three decades, emphasizing its application in optimizing cross-docking operations. Cross-docking, a collaborative distribution strategy, involves consolidating and transferring goods between vehicles at an intermediate point before their final distribution. This work considers a critical problem within this strategy: the efficient door assignment and scheduling of trucks to minimize the total processing time (makespan). Instead of traditional two-phase approaches, we propose an integrated mixed-integer linear programming model to simultaneously address both stages in the considered version of the Cross-Dock Door Assignment and Scheduling Problem (CDASP). Furthermore, we design practical variants of a Variable Neighborhood Search metaheuristic with Strategic Oscillation, which obtain solutions with an average gap of less than 0.04% compared to the optimal solutions.

Meet in the "Compagnie des Indes" room on the ground floor.