logo IMB
Retour

Séminaire Optimisation Mathématique Modèle Aléatoire et Statistique

New Results on Vehicle Routing Problems with Special Demand Structures

Artur Pessoa

( Universidade Federal Fluminense (Brasil) )

Salle 2, IMB

le 25 janvier 2024 à 11:00

In this work, we present new results of the ongoing work performed with two postgraduate students in UFF, Brazil. Both consider variants of the vehicle routing problem with special demand structures. The first is a new family of capacity-like cuts for a variant where visited points (facilities) differ from the demand points. In this variant, called m-CTP, each facility has an associated subset of demand points that can be attended by it. Experiments show that the proposed cut family allows for reducing the time required to solve some literature instances by more than one order of magnitude. The second result considers the vehicle routing problem with split deliveries. For this variant, we present a polynomial algorithm to recognise whether a set of graph edge multiplicities corresponds to a feasible solution or not. The new algorithm relies on a special property of the edge multiplicities that can be easily enforced by cuts in an MIP formulation. For general edge multiplicities, the recognition problem has been known as NP-hard for several years.