Groupe d’études et de recherche en analyse des décisions

G-2000-19

Transformations and Exact Node Routing Solutions by Column Generation

et

This article examines arc routing problems from the "dual" perspective of node routing. It first attempts to explain why and how an arc routing problem should be viewed as some version of a node routing problem, pending an appropriate transformation of the corresponding graph. The first part of the article addresses the issue of when such a transformation is necessary and the complementary question of when, or for what arc routing problems, from a computational point of view, a transformation to node routing is inappropriate. In addition, the first part attempt to provide some account of the different transformation schemes proposed over the years for arc routing problems into node routing setting. The second and the main part of the chapter focuses on providing a state-of-the-art survey of column generation methodology and its computational promise for solving node routing problems. The emphasis is on exact solutions to vehicle routing problems with time windows with and without split deliveries. The motivation stems from the fact that arc routing problems with time windows are very hard to model directly without an extensive graph modification and require transformation to node routing before an attempt of finding exact solutions can be made.

, 42 pages