Vehicle routing problems with alternative paths: an application to on-demand transportation

Thierry Garaix (1, 2) , Christian Artigues (3) , Dominique Feillet (4) , Didier Josselin (2)

1 LIA - Laboratoire Informatique d'Avignon
2 ESPACE - Études des Structures, des Processus d’Adaptation et des Changements de l’Espace
3 LAAS-MOGISA
4 SFL-ENSMSE - Département Sciences de la Fabrication et Logistique

The class of vehicle routing problems involves the optimization of freight or passenger transportation activities. These problems are generally treated via the representation of the road network as a weighted complete graph. Each arc of the graph represents the shortest route for a possible origin-destination connection. Several attributes can be defined for one arc (travel time, travel cost . . . ), but the shortest route modelled by this arc is computed according to one single criterion, generally travel time. Consequently, some alternative routes proposing a different compromise between the attributes of the arcs are discarded from the solution space. In this work, we propose to represent the road network with a multigraph, so that these alternative routes are considered, and to evaluate how it impacts on solution algorithms and solution values. A simple insertion algorithm is proposed and illustrated in the context of a on-demand transportation system developed in a French area. Computational experiments on academic and realistic data underline the potential cost savings brought by the multigraph model.

Mots clés: vehicle routing; on-demand transportation; multigraph; shortest path problem with resource constraints; dial-a-ride problem

Domaines: Recherche opérationnelle [math.OC]

Thierry Garaix, Christian Artigues, Dominique Feillet, Didier Josselin. Vehicle routing problems with alternative paths: an application to on-demand transportation. European Journal of Operational Research, 2010, 204 (1), pp.62-75. ⟨10.1016/j.ejor.2009.10.002⟩. ⟨hal-00109003v3⟩