Scientific Program > Talks by Speaker > Glize Estèle

We propose an extension of the single objective exact algorithm of Baldacci et al. (2008) to generate the complete Pareto front of a bi-objective VRP. The resulting algorithm combines the column generation and the branch-and-bound methods.

The algorithm requires the set of non-dominated points of the LP-relaxation to define a lower bound of the problem. Each point is combined with a direction in which the solution optimizes the problem. The algorithm also needs an upper bound representing feasible solutions of the initial problem. For each direction, the associated gap between the corresponding lower bound point and the closest upper bound point is computed. Then, all routes having their parametrized cost within this gap are generated and solving the resulting VRP provides a Pareto optimal solution.

Afterwards, every pair of consecutive Pareto optimal solutions previously found defines a reduced area where other optimal solutions could be. Those are generated successively by calculating their most efficient direction, lower bound and gap.

The algorithm is applied to a bi-objective VRP with time-windows to minimize two different costs on each route. Computational results will be compared with a classical bi-objective technique.