We propose a consistent neighbourhood search (CNS) approach to solving the Two-Dimensional Vector Packing problem (2-DVPP). Given a set of items, each having a weight and a volume, the 2-DVPP consists of finding the minimum number of bins, with a weight and a volume capacity, necessary to pack all the items. The best results on the classical benchmark set for 2-DVPP are obtained by iterative local search algorithm presented in [5].

This Ph.D. thesis concerns algorithms for Combinatorial Optimization Problems. In Combinatorial Optimization Problems the set of feasible solutions is discrete or can be reduced to a discrete one, and the goal is to find the best possible solution. Specifically, in this research we consider three different problems in the field of Combinatorial Optimization including One-dimensional Bin Packing (and two similar problems), Machine Reassignment Problem and Rolling Stock Problem. The first one is a classical and well known optimization problem, while the other two are real world and very large scale problems arising in industry and have been recently proposed by Google and French Railways (SNCF) respectively. For each problem we propose a local search based heuristic algorithm and we compare our results with the best known results in the literature. Additionally, as an introduction to local search methods, two metaheuristic approaches, GRASP and Tabu Search are explained through a computational study on Set Covering Problem.

This paper presents a heuristic approach combining constraint satisfaction, local search and a constructive optimization algorithm for a large-scale energy management and maintenance scheduling problem. The methodology shows how to successfully combine and orchestrate different types of algorithms and to produce competitive results. We also propose an efficient way to scale the method for huge instances. A large part of the presented work was done to compete in the ROADEF/EURO Challenge 2010, organized jointly by the ROADEF, EURO and Electricite de France. The numerical results obtained on official competition instances testify about the quality of the approach. The method achieves 3 out of 15 possible best results.