Journées de l'optimisation 2009 Optimizations days

Meta-heuristics are essential in addressing hard, combinatorial optimization problems. Co-operative parallel strategies provide the means to enhance the efficiency of the search and improve the quality of the solutions found. We present an overview of the topic, using vehicle routing and network design problems as illustrations and conclude with perspectives on addressing complex, multi-attribute combinatorial problems.

The real-world problems reflect the complexity and the heterogeneity of our modern society. Here we present the Integrative Cooperative Search framework that can simultaneously deal with multiple dimensions of a rich, complex problem. This approach uses the decomposition along the set of problem's attributes and the guided cooperation between the solving modules.

In real world applications, VRP problems have a great number of characteristics difficult to handle comprehensively through traditional methods. We address a rich VRP application which considers basic duration and capacity constraints with additional dimensions such as time windows, multiple periods and multiple depots. We propose an effective solution approach based on a new multi-thread cooperative optimization framework.

In this case study, we have considered the Hours-of-Service regulations during long-haul trips (Part 395 of the Federal Motor Carrier Safety Regulations) and other constraints in a vehicle routing problem. The main modelling aspects of this problem are introduced and we propose a tabu search heuristic using dynamic programming in the evaluation of route feasibility and quality.