Le problème de tournées de véhicules avec des demandes évidentielles

Ce papier porte sur deux modèles du problème de tournées de véhicules avec capacité (CVRP, en abrégé, pour Capacitated Vehicle Routing Problem) où les demandes des clients sont incertaines et représentées en utilisant la théorie de l'évidence. Le premier modèle, appelé CVRP Belief-Constrained Programming, est une extension de l'approche Chance-Constrained Programming en programmation stochastique, o`u la contrainte en probabilité est remplacée par deux contraintes évidentielles, i.e., nous imposons des bornes minimales pour la croyance et la plausibilité que la somme des demandes sur chaque route respecte la capacité. Le deuxième modèle, appelé CVRP with Evidential Recourses, étend l'approche dite de recours : si le véhicule arrive à un certain client et ne peut pas satisfaire sa demande, il doit retourner au dépôt et revenir au client. L'incertitude sur les recours possibles sur chaque route est représentée par une fonction de croyance et le coût d'une route est alors son coût classique (sans recours) additionné du pire coût espéré des recours. Des tests numériques sont présentés pour les deux modèles.