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

G-2016-110

Selective pricing in branch-price-and-cut algorithms for vehicle routing

, et

La méthode de branch-cut-and-price est la plus performante pour une grande panoplie de problèmes de tournées de véhicules (PTV). Pour plusieurs d'entre eux, le problème de "pricing" associé est hautement complexe. Pour alléger la résolution du problème de "pricing, il est normal de considérer une relaxation du problème. Dans cet article, nous introduisons un nouveau paradigme de résolution, notamment le "pricing sélectif" qui peut être utilisé afin de réduire l'effort de calcul associé. Pour illustrer ce nouveau cadre méthodologique, nous l'avons implémenté dans une méthode de branch-cut-and-price pour le PTV avec fenêtres de temps (PTVFT) dont le problème de pricing est une relaxation avec des voisinages (ng-routes). Nous développons une méthode d'étiquetage spécialement modifiée pour inclure le pricing sélectif, et l'avons testé sur des instances difficiles du PTVFT avec 200 clients. Nos expérimentations numériques montrent des réductions de jusqu'à un 32% du temps de calcul par rapport à l'approche classique de résolution. Nous introduisons aussi une heuristique capable de réduire les temps de calcul davantage.

, 16 pages