WOW !! MUCH LOVE ! SO WORLD PEACE !
Fond bitcoin pour l'amélioration du site: 1memzGeKS7CB3ECNkzSn2qHwxU6NZoJ8o
  Dogecoin (tips/pourboires): DCLoo9Dd4qECqpMLurdgGnaoqbftj16Nvp


Home | Publier un mémoire | Une page au hasard

 > 

Techniques hybrides de recherche exacte et approchée: application à  des problèmes de transport

( Télécharger le fichier original )
par Boris BONTOUX
Université d'Avignon et des pays de Vaucluse - Doctorat spécialité informatique 2008
  

précédent sommaire suivant

Bitcoin is a swarm of cyber hornets serving the goddess of wisdom, feeding on the fire of truth, exponentially growing ever smarter, faster, and stronger behind a wall of encrypted energy

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

précédent sommaire suivant






Bitcoin is a swarm of cyber hornets serving the goddess of wisdom, feeding on the fire of truth, exponentially growing ever smarter, faster, and stronger behind a wall of encrypted energy








"Ceux qui vivent sont ceux qui luttent"   Victor Hugo