Troisième partie
Tronquer les méthodes exactes :
méthode de Branch & Price
heuristique
5 Application au problème de Tournées de
Véhicules avec Contraintes de Chargement 125
5.1 Préambule : Intérêt du problème
126
5.2 Problèmes de calcul de tournées de
véhicules 127
5.2.1 Du problème du Voyageur de Commerce au
problème de Tour-
nées de Véhicules 127
5.2.2 Le 2L-VRP parmi les problèmes de Tournées de
Véhicules . . . 128
5.3 État de l'art 128
5.3.1 Résolution du 2L-VRP 128
5.3.2 Algorithmes de chargement 131
5.4 Modèle classique du problème du 2|RO|L-VRP
132
5.5 Génération de colonnes 134
5.5.1 Modélisation d'un ESPPRC 138
5.5.2 Résolution par programmation dynamique 139
5.6 Notre approche : un schéma de Branch & Price
141
5.6.1 Méthode de séparation 142
5.6.2 Initialisation de 1 pour la génération de
colonnes 143
5.6.3 Remontées de colonnes 143
5.6.4 Problème esclave : ESPPRC 144
5.6.5 Problème de chargement séquentiel à
deux dimensions 147
5.7 Deux approches différentes pour la
réalisabilité du chargement 153
5.7.1 Vérification de la réalisabilité a
posteriori 153
5.7.2 Construction de routes réalisables dans le
sous-problème 155
5.8 Branch & Price heuristique 159
5.8.1 Problème esclave heuristique 159
5.8.2 Gestion des colonnes 160
5.8.3 Méthode de séparation 160
5.9 Résultats expérimentaux 161
5.9.1 Paramètres retenus 161
5.9.2 Classes d'instances 161
5.9.3 Analyses des résultats 162
5.10 Conclusions et perspectives 165
Chapitre 5
Application au problème de
Tournées de Véhicules avec
Contraintes de Chargement
Chapitre 5. Application au problème de Tournées de
Véhicules avec Contraintes de Chargement
5.1 Préambule : Intérêt du
problème
Le problème tel qu'il nous a été
présenté par l'entreprise Daumas, Autheman et Associés,
est le suivant. Un service de traiteur avec livraisons de repas à
domicile, situé en région parisienne, a fait une étude de
marché afin d'optimiser les trajets des livraisons, ainsi que
l'agencement du chargement des livraisons.
La problèmatique se compose de plusieurs
problèmes. Le premier est un problème de chargement. Les
commandes de repas et de matériel à livrer sont
préparées dans des entrepôts. Pour le chargement de ce
matériel, les livreurs doivent remplir les surfaces de livraison des
véhicules sans plan de chargement. Un temps important est donc perdu
dans l'essai de configurations afin de remplir les surfaces de livraison. Le
nombre d'objets à charger est, de plus, calculé au plus juste par
rapport à la capacité de la surface de livraison. Les repas
à livrer sont posés sur des chariots dont les dimensions sont
connues. Les objets à livrer sont des produits fragiles. Ainsi, dans la
plupart des cas, il n'y a pas d'empilage possible, les plats étant trop
fragiles pour pouvoir résister aux poids d'autres objets posés
au-dessus. Pour chaque véhicule, la taille de la surface de chargement
est connue et cette taille est identique pour tous les véhicules. Les
déchargements des livraisons ne peuvent se faire que par les portes
arrières. Pour accélérer le temps de livraison, il est
préférable de pouvoir facilement décharger les produits
à livrer, lors de la livraison pour chaque client.
Le deuxième problème concerne l'optimisation des
livraisons. Tous les départs des livraisons se font à partir d'un
dépôt central. Les distances entre les différents points de
livraisons sont connues, ainsi que les distances entre les points de livraisons
et le dépôt central. L'entreprise dispose d'une flotte fixe de
véhicules homogènes.
Ce problème, dans une version simplifiée, est
similaire à un problème connu dans la littérature sous le
nom de problème de Tournées de Véhicules avec Contraintes
de Chargement en Deux Dimensions (Vehicule Routing Problem with
Two-Dimensional Loading Constrains ou 2L-VRP).
La section 5.2 expose un bref historique des problèmes
de Tournées de Véhicules. La section 5.3 présente un
état de l'art sur le problème de Tournées de
Véhicules avec Contraintes de Chargement. Un modèle classique du
2L-VRP est décrit dans la section 5.4, puis nous présentons le
fonctionnement de la méthode de résolution par
génération de colonnes dans la section 5.5. Les
différentes méthodes de résolution que nous proposons sont
introduites dans les sections 5.6, 5.7 et 5.8. Enfin, l'efficacité de
nos méthodes est évaluée à travers des
résultats expérimentaux proposés dans la section 5.9.
5.2. Problèmes de calcul de tournées de
véhicules
| 
