Les fenêtres de temps vont t’amener à supprimer des arcs dans ton graphe. Si je modélise le VRPtw :
Données :
Soit le graphe où est l'ensemble des sommets représentants les clients (notés ) et les dépôts (notés , où représente le dépôt de départ et le dépôt d'arrivé) et l'ensemble des arcs, avec la fenêtre de temps de l'élément . Soit la demande du client . Soit le nombre de véhicules qui compose la flotte et la capacité d'un véhicule. On note la durée du trajet de vers , .
Variable de décisions :
- est une variable binaire de décision indiquant si l'arc est emprunté par le -ième véhicule.
- La variable binaire indique si le client est visité par le n-ième véhicule.
- On pose , avec l'instant d'arrivée du n-ième véhicule sur le sommet et le temps d'attente.
Programme linéaire en nombre entier :
On minimise la distance totale parcouru par les véhicules
Sous contraintes :
Partager