A new branch-cut-and-price algorithm for the split delivery vehicle routing with time windows

Isaac Balster (1) , Teobaldo Bulhões (2) , Pedro Munari (3) , Ruslan Sadykov (1)

1 EDGE - Formulations étendues et méthodes de décomposition pour des problèmes génériques d'optimisation
2 UFPB - Universidade Federal da Paraiba / Federal University of Paraiba
3 UFSCar - Universidade Federal de São Carlos [São Carlos]

We present a new branch-cut-and-price algorithm for the split delivery vehicle routing problem with time windows. We devise a novel property of optimal solutions and take advantage from this information throughout the modelling. Our algorithm also uses several state-of-the-art techniques from the literature, known and new families of valid inequalities. Our algorithm establishes new start-of-the-art results for the problem.

Mots clés: split delivery vehicle routing problem with time windows.; Branch-cut-and-price

Domaines: Recherche opérationnelle [math.OC]; Combinatoire [math.CO]

Isaac Balster, Teobaldo Bulhões, Pedro Munari, Ruslan Sadykov. A new branch-cut-and-price algorithm for the split delivery vehicle routing with time windows. 23ème congrès annuel de la Société Française de Recherche Opérationnelle et d'Aide à la Décision, INSA Lyon, Feb 2022, Villeurbanne - Lyon, France. ⟨hal-03595220⟩