Grant: Discovery Grants Program - Individual

Column generation (CG) technique of linear programming may be used to solve to optimality linear programs with a very large number of variables. The main objective of this project is to develop and implement CG algorithms for clustering and vehicule routing problems.Clustering addresses the following general problem: given a set of entities, find subsets, or clusters, which are homogeneous and/or well separated. Homogeneity means that entities in the same cluster must be similar and separation that entities in different clusters must differ one from another. In this program, we work on the development and implementation of CG algorithms for finding optimal partition of the set of entities. During the last years, I have worked, together with Gilles Caporossi and Pierre Hansen, on the development of the first generic system for exact clustering by CG. The main objectives of this research program consist on the improvement and the extension of this system.Routing problems often are the very core of transportation systems in logistics. The Vehicle Routing Problem (VRP) is the most prominent as it consists in building a set of routes of minimal cost to visit a set of clients with known demands. The time-dependant Vehicle Routing Problem (TDVRP) is an extension of the VRP where the travel time between two clients can vary over the time. This is especially important in areas where there is a strong variation in terms of traffic (urban areas or cities main access points). The main goal of this research program is to develop an exact method based CG for solving the TDVRP.