In several vehicle routing and crew scheduling problems solved by column generation, the objective has two levels: minimize first the number of vehicles/crews used and second the operational costs. In this case, the objective function of the proposed model often combines both levels by using large fixed costs for the first level. These large values slow down the column generation solution process. In this talk, we present an exact dynamic fixed costs strategy that can substantially reduce solution times.

Dynamic aggregation concepts will be discussed. We associate the set of tasks with an equivalence relation. Each equivalence class is then represented by one set partitioning constraint only. In order to obtain optimality, we update the partition dynamically. Results show that this strategy reduces significantly, in most test cases, the size of the restricted master problem as well as the solution times especially for large instances.

MDVSP problems are usually solved by a column generation method embedded in a branch-and-cut algorithm. When the horizon of tours is long (2 days to 1 week), the problem becomes very difficult to solve. Even its linear relaxation may not be solved in a reasonable time. We use a stabilized column generation algorithm in order to solve the linear relaxation efficiently. Tests are performed over a set of randomly generated long-horizon MDVSP instances.