Méthodes à deux phases pour le problème de tournées de véhicule avec contraintes d’accessibilité

30/09/2017
Publication e-STA e-STA 2005-2
OAI : oai:www.see.asso.fr:545:2005-2:20017
DOI :

Résumé

Méthodes à deux phases pour le problème de tournées de véhicule avec contraintes d’accessibilité

Métriques

12
4
203.42 Ko
 application/pdf
bitcache://90dc17bdcbc2ce55e8bcae8acc830fe98c2c9ff6

Licence

Creative Commons Aucune (Tous droits réservés)
<resource  xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
                xmlns="http://datacite.org/schema/kernel-4"
                xsi:schemaLocation="http://datacite.org/schema/kernel-4 http://schema.datacite.org/meta/kernel-4/metadata.xsd">
        <identifier identifierType="DOI">10.23723/545:2005-2/20017</identifier><creators><creator><creatorName>Mahdi Souid</creatorName></creator><creator><creatorName>Saïd Hanafi</creatorName></creator><creator><creatorName>Frédéric Semet</creatorName></creator></creators><titles>
            <title>Méthodes à deux phases pour le problème de tournées de véhicule avec contraintes d’accessibilité</title></titles>
        <publisher>SEE</publisher>
        <publicationYear>2017</publicationYear>
        <resourceType resourceTypeGeneral="Text">Text</resourceType><dates>
	    <date dateType="Created">Sat 30 Sep 2017</date>
	    <date dateType="Updated">Sat 30 Sep 2017</date>
            <date dateType="Submitted">Tue 13 Nov 2018</date>
	</dates>
        <alternateIdentifiers>
	    <alternateIdentifier alternateIdentifierType="bitstream">90dc17bdcbc2ce55e8bcae8acc830fe98c2c9ff6</alternateIdentifier>
	</alternateIdentifiers>
        <formats>
	    <format>application/pdf</format>
	</formats>
	<version>34032</version>
        <descriptions>
            <description descriptionType="Abstract"></description>
        </descriptions>
    </resource>
.

é é— Le problème de tournées de véhicules possède de nombreuses applications dans des domaines tels que la logistique, la planification des réseaux de distribution et leur gestion. Dans cet article, on traite le problème de tournées de véhicules avec contraintes d'accessibilité. On propose une stratégie de résolution heuristique à deux phases. La première phase correspond à la résolution d'un problème de localisation à l'aide d'une méthode de séparation-évaluation. La seconde phase correspond à la résolution de problèmes de routage. Des tests sont faits afin de comparer trois approches basées sur des modélisations différentes du problème de localisation. é — Tournées de véhicules, localisation, heuristique, relaxation Lagrangienne, Séparation-évaluation. Les Problèmes de Tournées de Véhicules (PTV) consistent à affecter des commandes de clients à des véhicules et à construire la tournée de chaque véhicule à travers les sites de livraison de ces commandes en satisfaisant certaines contraintes et en optimisant un objectif donné. La version de base des PTV est le problème de tournées de véhicules avec contraintes de capacité (PTVC). Dans ce cas, tous les clients sont connus à l’avance et chaque client est desservi en un seul passage. Les véhicules sont identiques et basés dans un seul dépôt, et seules les contraintes de capacité pour les véhicules sont imposées. L’objectif consiste à minimiser le coût total de la desserte des clients. Le PTVC est un problème NP-difficile [11]. La résolution exacte se restreint à des instances de taille relativement réduite. Vu que les problèmes de transport posés dans la pratique sont, en général, de taille importante différentes heuristiques ont été développées pour la résolution du PTVC permettant une résolution approchée en un temps raisonnable. Le cas particulier d’une seule tournée nous ramène au problème du voyageur de commerce (PVC) [15]. Dans cet article, nous nous intéressons à un problème de localisation et transport appelé problème de tournées de véhicule avec des contraintes d’accessibilité (PTVA). Le PTVA est défini sur un graphe G=(V,E) où V est l’ensemble des sommets représentant le dépôt et les clients : V={0,1,…,n} et E l’ensemble des arêtes. Pour toute arête (i,j) ∈ E, on définit également un coût cij. L’ensemble de clients est desservi à l’aide d’un camion et d’une remorque qui forment un train- routier. L’ensemble V est partitionné en deux sous-ensembles : l’ensemble des sommets {1,…,p} correspond aux clients- remorque qui sont accessibles par le train-routier et le camion seul. L’ensemble des sommets {p+1,…,n} correspond aux clients-camion qui ne sont accessibles que par le camion seul. On suppose que les quantités contenues dans le train-routier suffisent pour desservir tous les clients. L’existence de la contrainte d’accessibilité a comme conséquence que la tournée du véhicule n’est pas un simple cycle ou circuit, comme c’est le cas pour le PVC. La tournée du train-routier (Figure 1) est composée d’un tour principal réalisé par le train-routier et de sous-tours effectués par le camion seul [13][14]. Le train- routier débute son tour principal en partant du dépôt en direction d’un premier client accessible qui est donc nécessairement un client-remorque. Une fois la marchandise livrée, deux cas de figures se présentent : soit on décroche la remorque pour effectuer un ou plusieurs sous-tours avec le camion seul, soit on se déplace vers un autre client accessible par le train routier. Plusieurs sous-tours peuvent donc être accomplis à partir d’un client-remorque situé sur le tour principal. Un tel client est appelé racine. Un sous-tour peut inclure des clients-camion et des clients-remorque. La quantité totale livrée sur un sous-tour ne peut dépasser la capacité du camion. La multiplicité des sous-tours correspond à des chargements successifs, dans le camion, de marchandises stockées dans la remorque. Suite à la réalisation de sous-tours, la remorque est raccrochée au camion et le train-routier se dirige vers le client suivant du tour principal qui s’achève au dépôt. Dépôt Tour principal Sous-Tour Client-camion Client-Remorque Client-remorque racine Figure 1. Schéma d’une solution du PTVA L' objectif du PTVA consiste à minimiser le coût total de la tournée du train-routier. Le coût total est la somme des coûts du tour principal et des sous-tours. De nombreuses heuristiques utilisées pour le PTVC font partie d’une classe appelée par Christofides [3] : méthodes à deux phases. La résolution du PTVC avec une méthode à deux phases consiste à décomposer la résolution en deux étapes : une étape de groupement de clients en routes réalisables et une étape de construction des routes. L’ordre d’exécution de ceux MAHDI SOUID, SAÏD HANAFIET FREDERIC SEMET Laboratoire d’Automatique, de Mécanique et d’Informatique Industrielles et Humaines UMR 8530 UNIVERSITE DE VALENCIENNES ET DU HAINAUT CAMBRESIS LE MONT HOUY 59313, VALENCIENNES CEDEX 9, FRANCE Méthodes à deux phases pour le problème de tournées de véhicule avec contraintes d’accessibilité deux étapes, permet de distinguer deux types de méthodes à deux phases : routage d’abord groupement en second [1][12], groupement d’abord routage en second [6]. La méthode de résolution à deux phases adaptée dans cet article est de type groupement d’abord routage en second. Elle consiste à résoudre, en premier, un problème de localisation et un problème d’élaboration de tournées ensuite. La première phase consiste à déterminer les clients présents sur le tour principal et à grouper les clients restant en classes. Trois modèles de localisation sont proposés suivant le type de groupement effectué. On distingue un premier modèle avec groupement de clients en sous-tours. Les groupes obtenus correspondent alors à des sous-tours réalisables respectant la contrainte de capacité du camion. Un second modèle, agrégation du premier par relaxation des contraintes de capacité, et un troisième modèle, agrégation du second modèle par relaxation des coûts d’ouverture des sous tours, consistent à effectuer des groupements autour des clients-remorques. La deuxième phase consiste à résoudre un problème de routage pour chaque classe. Une heuristique de post-optimisation est ensuite appliquée. Elle consiste à procéder à des déplacements ou à des échanges de clients entre sous-tours [14]. La suite de cet article s’organise comme suit. Dans la section 2, nous détaillons la première phase de résolution du PTVA à travers la description des trois modèles de localisation et de leurs résolutions. Dans la section 3, nous présentons les résolutions des problèmes de routage associés à chaque modèle. Dans la section 4, nos approches sont comparées sur la base des résultats obtenus sur différentes instances tests. Enfin, les conclusions sont formulées dans la section 5. ! " # $ % & $ # ' ( ) ' $ * $ $ ' " ' # " La première phase de résolution du PTVA consiste à localiser les clients-remorque présents sur le tour principal et à partitionner les clients restant en groupes. A. Modèles de localisation 1) Modèle de localisation avec regroupement en sous-tour Dans cette première modélisation, les groupes formés respectent la contrainte de capacité du camion, c' est-à-dire que le volume distribué dans chaque groupement ne dépasse pas la charge du camion. La fonction objectif du modèle de localisation fait intervenir les coûts suivants : • Le coût 1 i c de placement d’un client-remorque i sur le tour principal est estimé par le coût d’un aller-retour du dépôt au client-remorque, c’est-à-dire i 0 0 i 1 i c c c + = . • Le coût 2 ik c d’ouverture du kème sous-tour à partir de la racine i est approximé par le coût d’un aller retour de la racine i à un point germe gik déterminé suite à l’application d’une heuristique de balayage [8], c' est-à- dire i g g i 2 ik ik ik c c c , , + = . • Le coût k 3 ij c d’insertion d’un client j dans le kème sous- tour issu de la racine i est approximé comme le coût d’insertion du client j entre la racine i et le point germe gik. Il s’exprime par : ik ik g i g j ij k 3 ij c c c c , , − + = Dans la suite, notons par m le nombre maximal de sous-tours ouverts. Les variables binaires utilisées dans le premier modèle de localisation (L1) sont définies pour i=1,…,p ; j=1,…,n et k=1,…,m : • xij k = 1 si j est desservi depuis i lors du parcours du kème sous-tour, 0 sinon. • yi = 1 si i est sur le tour principal, 0 sinon. • zik = 1 si le kème sous-tours issu du client-remorque i est ouvert, 0 sinon. On obtient le modèle suivant (L1) : = = = ≠ = = = + + p 1 i m 1 k p 1 i n i j 1 j k ij k 3 ij m 1 k p 1 i ik 2 ik i 1 i x c z c y c Min Sous les contraintes : La contrainte (1) signifie que chaque client-remorque est affecté soit au tour principal soit à exactement un des sous tours. La contrainte (2) spécifie que chaque client-camion est affecté à exactement un seul sous tour. La contrainte (3) indique que la quantité des biens livrée, lors du parcours d’un sous tour, ne doit pas dépasser la charge du camion. La contrainte (4) traduit qu’un sous tour n’existe que si le client remorque duquel il est issu est racine. 2) Modèle de localisation avec distinction de sous-tours D’un point de vue modélisation, la différence entre ce deuxième modèle de localisation (L2) et le modèle (L1) se situe au niveau de la contrainte de capacité (3) qui devient [14] : Dans le modèle (L1), chaque groupement correspond à un sous-tour, le groupement des clients est fait autour des points germes alors que pour le second modèle (L2) le groupement est fait autour des clients-remorque racines. Algébriquement, cela correspond à une agrégation des contraintes (3) pour chaque = ≠ = = + m 1 k p i j 1 j k ji i 1 x y ,..., p 1 i = (1) 1 = = ≠ = m 1 k p j i 1 i k ij x ,...,n 1 p j + = (2) ik n i j 1 j k ij j z Q x q ≤ ≠ = ... ; .. ,m , 1 k ,p ,. 1 i = = (3) i ik y z ≤ ... ; ,m , 1 k ,...,p 1 i = = (4) ou 1 0 xk ij = ,..., ; ..., ; m 1 k n , 1 j ,...,p 1 i = = = (5) ou 1 0 yi = ,..., p 1 i = (6) ou 1 0 zik = ... ; ,m , 1 k ,...,p 1 i = = (7) = = ≠ = ≤ m 1 k ik m 1 k n i j 1 j k ij j z Q x q p 1 i ,..., = (8) client-remorque. En deuxième phase, on résout un PVC au niveau de chaque groupe de clients pour le premier modèle alors qu’on résout un PTV pour le deuxième modèle. 3) Modèle de localisation sans distinction de sous-tours Pour ce troisième modèle (L3) le regroupement de clients est fait, comme pour le modèle précédent, autour des clients- remorque, la seule différence est que l’on ne distingue pas les sous-tours. Pour le modèle sans distinction de sous-tours on obtient des groupements autour des clients-remorque pour lesquels on résout un PTV en seconde phase de résolution du PTVA. L’avantage de ce modèle par rapport au précédent est qu’il ne requiert pas la définition de coût pour chaque sous- tour potentiel, ces coûts pouvant être difficiles à estimer. B. Résolution exacte des modèles de localisation Pour résoudre de façon exacte le problème de localisation on utilise une méthode de séparation-évaluation [4][10]. Le calcul des bornes inférieures est fait par relaxation Lagrangienne des contraintes de capacité. Les bornes supérieures sont calculées par des heuristiques Lagrangiennes. 1) Relaxation Lagrangienne La relaxation Lagrangienne [5] permet de déterminer pour chaque sous-problème (au niveau de chaque nœud) une borne inférieure. La structure du problème de localisation (L1) permet différentes relaxations. On distingue, en particulier, deux possibilités de relaxation. Une première consiste à dualiser les contraintes d’affectation (1) et (2). Une deuxième consiste à dualiser les contraintes de capacité (3). On a choisi la première possibilité de relaxation vu que pour la seconde la propriété d’intégrité est satisfaite. On détaille la relaxation retenue dans ce qui suit. Soit λ ∈ Rn un vecteur de multiplicateurs de Lagrange. En dualisant les contraintes (1) et (2) dans la fonction objectif on obtient : = = = = ≠ = + − = m 1 k p 1 i m 1 k p 1 i ik 2 ik n i j 1 j k ij j k 3 ij z c x c Min L ) ( ( ) ( λ λ + ) ) ( = = + − n 1 j j p 1 i i i 1 i y c λ λ sous les contraintes (3), (4), (5), (6) et (7). Pour λ fixé, la relaxation Lagrangienne ) (λ L est séparable en p sous-problèmes, un par client-remorque. Ainsi pour un client-remorque i donné on a le problème suivant : ) ) ( ) ( ( ) ( i i 1 i m 1 k ik 2 ik m 1 k n i j 1 j k ij j k 3 ij i y c z c x c Min L λ λ λ − + + − = = = ≠ = sous les contraintes : Dans le cas où yi = 0, on a ) (λ i L = 0. Dans le cas où yi = 1, ce qui correspond à l’affectation du client i sur le tour principal, on obtient le problème de sac à dos binaire suivant : ) ) ( ( ) ( ik 2 ik n i j 1 j k ij j k 3 ij ik z c x c Min L + − = ≠ = λ λ sous les contraintes : En notant ) ( ˆ λ i L comme la valeur optimale du problème ) (λ i L , la valeur optimale de la relaxation Lagrangienne est donc : = = + = n 1 j j p 1 i i 0 L L λ λ λ )) , ) ( ˆ (min( ) ( . Le dual Lagrangien (D) consiste à trouver la meilleure borne fournie par les différentes relaxations : (D) )) ( ( max λ λ L n R ∈ Le problème (D) est résolu par une méthode de sous-gradient modifié [2]. A chaque itération h, la direction de recherche dh est calculée en fonction du sous-gradient courant gh de ) ( h L λ et la direction dh-1 . Plus formellement, 1 1 g d = 1 h h h h d g d − + = θ où gh est un sous-gradient de la fonction Lagrangienne L au point λh et < = − − sinon si 0 0 d g d g 1 h h 1 h h h θ Rappelons que le sous-gradient est calculé à partir d’une solution optimale de la relaxation Lagrangienne [9]. Plus précisément, pour le modèle L1, à l’itération h, un sous- gradient gh de ) ( h L λ est calculé comme suit : + = − = − − = = = = = n , ... 1, p j p , ,... 1 j m 1 k p 1 i k ij m 1 k p 1 i k ij j h j x 1 x y 1 g ik n i j 1 j k ij j z Q x q ≤ ≠ = ,...,m 1 k = (9) i ik y z ≤ ,...,m 1 k = (10) ou 1 0 xk ij = ,...,m 1 k ,...,n; 1 j = = (11) ou 1 0 yi = (12) ou 1 0 zik = ,...,m 1 k = (13) ik n i j 1 j k ij j z Q x q ≤ ≠ = (14) ou 1 0 xk ij = ...,n , 1 j = (15) ou 1 0 zik = (16) où (y, x) est une solution optimale de la relaxation Lagrangienne ) ( h L λ . Le multiplicateur initial est calculé comme suit : { } + = = = = n , ... 1, p j ,..., , min p , ,... 1 j p 1 i c c 3 ij 1 j 0 j λ A chaque itération h, le multiplicateur courant λh est déterminé par la relation de récurrence suivante : h h 1 h h d t − = − λ λ où th est le pas de déplacement calculé comme suit : h h h g L( Z t ) − = β où Z est une borne supérieure de la valeur optimale de (D) et β est un paramètre initialisé à 2 et est divisé par 2 lorsque la valeur de la solution n’a pas évolué après un certain nombre d’itérations. 2) Heuristiques Lagrangiennes Une borne supérieure de la valeur optimale du problème de localisation est utilisée dans la recherche arborescente afin de permettre l’élagage des branches non prometteuses. Cette borne supérieure est calculée par une heuristique Lagrangienne spécifique au modèle utilisé. L’algorithme suivant décrit l’heuristique utilisée par le modèle de localisation (L2) : Algorithme. Heuristique Lagrangienne pour le modèle (L2) Soit (x,y,z) une solution optimale de la relaxation Lagrangienne L(λ). La solution n’étant pas primale réalisable (donc certaines contraintes relaxées dans la fonction objectif sont violées). Posons 2 ik j k 3 ij k ij c Q q c ) / ( + = δ . Nous distinguons deux cas d’irréalisabilité : • Cas d’ un client-remorque j∈{1,…,p} Si yj = 1 alors 0 xk ij = pour tout i=1,…,p ; k=1,…,m ; Sinon Si = = = m 1 k p 1 i k ij 0 x alors yj = 1 ; Sinon { } m 1 k p 1 i k ij k j i ,..., ; ,..., : min * * = = = δ δ 0 xk ij = pour tout i=1,…,p ;k=1,…,m 1 xk j i = * * ; • Cas d’ un client-camion j∈{p+1,…,n} Si = = = m 1 k p 1 i k ij 0 x alors { } m 1 k p 1 i k ij k j i ,..., ; ,..., : min * * = = = δ δ 0 xk ij = pour tout i=1,…,p ; k=1,…,m 1 xk j i = * * ; Les heuristiques Lagrangiennes utilisées pour les modèles de localisation (L1) et (L3) utilisent la même stratégie que celle utilisée pour le modèle (L2) [14]. Les trois heuristiques sont basées sur le même principe de " réparation " de la solution obtenue. Il s’agit de déterminer pour chaque client non affecté, l’affectation la moins coûteuse et de supprimer pour un client trop affecté toutes les affectations sauf celle qui coûte le moins cher. On utilise le terme 2 ik j k 3 ij k ij c Q q c ) / ( + = δ pour évaluer l’insertion du client j dans le kème sous-tour issu de la racine i. ! " # $ + & $ # ' $ ) ' $ * $ # $ $ $ # La première phase de la méthode à deux phases a permis de constituer les groupes de clients et de les affecter aux clients- remorque présents sur le tour principal. La seconde phase consiste à résoudre un problème de routage pour chaque groupe. On distingue, suivant la manière de groupement, deux types de problèmes de routage. Dans le cas où la répartition de clients permet de former des sous-tours ce qui est le cas pour le modèle de localisation (L1). Dans ce cas on résout un PVC pour chaque groupe. Dans le cas où, les groupes ont été formés autour de clients-remorque (L2) et (L3), on résout un PTVC pour chaque groupe. Pour la résolution du PTVC on utilise également une méthode à deux phases de type groupement d’abord routage en second. La première phase consiste en une méthode de balayage [8]. Pour chaque sous-tour, l’heuristique GENIUS [7] est appliquée pour résoudre le PVC associé. L’heuristique GENIUS consiste en deux phases : une première phase de construction de tournée par insertion des clients un par un dans une tournée comportant initialement trois clients, et une seconde phase de post-optimisation de la tournée construite. La solution obtenue avec la méthode à deux phases peut être améliorée par une série de transformations locales. On applique une procédure de post-optimisation qui consiste en l’application d’une descente qui utilise deux structures de voisinages. Un premier voisinage V1 consiste en des mouvements de déplacements de clients entre sous-tours issus d’une même racine. Un deuxième voisinage V2 est utilisé suite à la descente avec le premier voisinage. Il consiste à effectuer des échanges de clients entre sous-tours issus d’une même racine. , $ # ' " # * $ - $ # Les expériences numériques sont réalisées dans un environnement UNIX, sous une plateforme Sun OS 5.9. Les programmes sont écrits en langage C en utilisant le compilateur gcc. L’évaluation de la performance des méthodes à deux phases est effectuée sur un ensemble d’instances générées aléatoirement. Chaque instance est caractérisée par trois paramètres : n le nombre de clients, p le nombre de clients- remorques et α un paramètre pour modifier la charge de camion. La capacité de chaque camion est calculée comme suit : Q = + = ) / .( p q n 1 p i i α . Les quantités desservies qj, pour j=1,…,n, sont générées suivant une distribution uniforme dans l’intervalle [1,100]. L’ensemble des jeux de données est constitué de 120 instances du PTVA. Ces instances sont obtenues en faisant varier n=100,300, p=10%,30% de n et α=1,2 ; 1,0 et 0,8. Pour chaque problème 10 instances aléatoires sont générées. D’abord on présente les résultats numériques obtenus pour les modèles de localisation (L2) et (L3). Ensuite, on présente une étude comparative des solutions données par les deux approches basées sur les modèles (L2) et (L3). A. Résolution des modèles de localisation Les tableaux 1 et 2 présentent les résultats obtenus pour la résolution des deux modèles de localisation (L2) et L3). La résolution implémentée est une méthode de séparation- évaluation utilisant la méthode de sous-gradient et l’heuristique Lagrangienne décrits dans la section 2. Chaque ligne des tableaux 1 et 2 correspond à une moyenne sur 10 instances résolues. La colonne Zh/Z* représente le ratio entre la valeur de la meilleure solution réalisable trouvée à la racine de l’arborescence et la valeur de la solution optimale. La colonne Noeud représente le nombre de nœuds de l’arborescence explorés. La colonne t représente le temps de calcul en secondes. n p a Zh/Z* Noeud t 100 10 1,2 1,209 124,2 28,1 1,0 1,189 316,8 94,4 0,8 1,195 188,3 38,0 30 1,2 1,382 129,7 71,8 1,0 1,194 88,3 43,9 0,8 1,065 53,2 67,0 300 30 1,2 1,176 225,9 81,7 1,0 1,110 33,6 111,9 0,8 1,012 176,6 78,8 90 1,2 1,115 133,2 128,5 1,0 1,019 86,7 233,1 0,8 1,017 123,7 300,2 Tableau 1. Modèle de localisation (L2) n p α Zh/Z* Noeud t 100 10 1,2 1,005 17,8 2,1 1,0 1,002 5,2 1,7 0,8 1,000 18,0 2,3 30 1,2 1,012 53,9 9,4 1,0 1,006 31,6 9,5 0,8 1,004 38,2 9,2 300 30 1,2 1,007 47,9 32,4 1,0 1,001 48,6 22,2 0,8 1,003 52,6 19,8 90 1,2 1,010 127,6 28,5 1,0 1,012 171,2 134,1 0,8 1,011 134,7 129,0 Tableau 2. Modèle de localisation (L3) Ces résultats nous conduisent à faire les observations suivantes. Pour les deux modèles les solutions sur les 10 instances générées ont pu être obtenues. Les solutions ne peuvent toutefois pas être comparées à ce stade. Par contre il apparaît que le modèle sans distinction de sous-tours (L3) requiert pour sa résolution des temps de calcul plus faibles que le modèle avec distinction de sous-tours (L2). Le temps de calcul varie dans les deux cas selon le nombre total de clients mais également selon le nombre de clients-remorques présents. Les problèmes plus contraints en termes de capacité (α petit) sont également plus difficiles à résoudre. Dans le cas du modèle (L3), la solution générée à la racine avec l’heuristique Lagrangienne est de bonne qualité. Ceci n’est pas le cas avec l’heuristique Lagrangienne associée au modèle (L2) qui génère des résultats de qualité moyenne variant entre 1,2% et 38,2% par rapport à la valeur optimale. B. Méthodes à deux phases Le tableau 3 décrit les résultats obtenus par la méthode à deux phases en utilisant les deux modèles de localisation (L2) et (L3). Chaque ligne de ce tableau correspond, également, à une moyenne sur 10 instances résolues. La colonne H2 (resp. H3) rapporte les résultats obtenus par la méthode à deux phases pour laquelle la première phase résout le modèle L2 (resp. L3). La colonne HP2 (resp. HP3) correspond aux résultats fournis par la méthode à deux phases avec le modèle L2 (resp. L3) suivi d’une phase de post-optimisation. Pour toutes les colonnes la valeur du rapport entre la valeur obtenue et la meilleure solution connue, est rapportée. n p α H2 HP2 H3 HP3 100 10 1,2 1,170 1,062 1,059 1,000 1,0 1,166 1,038 1,059 1,000 0,8 1,080 1,000 1,073 1,000 30 1,2 1,429 1,000 1,186 1,000 1,0 1,217 1,028 1,094 1,000 0,8 1,059 1,000 1,062 1,022 300 30 1,2 1,095 1,025 1,061 1,000 1,0 1,077 1,000 1,090 1,010 0,8 1,097 1,039 1,075 1,000 90 1,2 1,070 1,030 1,044 1,000 1,0 1,059 1,000 1,068 1,005 0,8 1,028 1,000 1,007 1,007 Tableau 3. Comparaison des méthodes à deux phases Les résultats présentés dans le tableau 3 nous permettent de faire les observations suivantes. La résolution du PTVA à l’aide de l’heuristique H3 basée sur la modélisation sans distinction de sous-tours (L3) fournit des meilleurs résultats que celles trouvées par l’heuristique H2 basée sur la modélisation avec distinction de sous-tours (L2). Une justification de ce fait est que pour le modèle sans distinction de sous-tours (L3) la composition des sous-tours est faite en seconde phase donc elle est moins affectée par les approximations faites lors de la première phase de résolution. On note aussi l’amélioration apportée par la procédure de post- optimisation aux solutions obtenues par les deux heuristiques H2, H3. Notons que la phase de post-optimisation appliquée après H2 et H3 permet de réduire l’écart entre les heuristiques H2 et H3. Les heuristiques HP2 et HP3 fournissent donc des résultats homogènes. Les temps d’exécution de la deuxième phase de routage et de la phases de post-optimisation sont relativement petit (1 à 4 secondes) comparé au temps total de résolution. , ' # Nous avons proposé des méthodes approchées à deux phases (localisation et routage) pour résoudre le problème de tournées de véhicule avec contraintes d’accessibilité. Trois modèles de localisation ont été proposés. Ils se distinguent par le type de groupement de clients. Un groupement conduit à la résolution d’une série de problèmes de voyageurs de commerce en phase de routage. Un autre groupement conduit à la résolution d’une série de problèmes de tournées de véhicules en seconde phase. Les problèmes de localisation, de la première phase, sont résolus par une méthode de séparation-évaluation. Les problèmes de routage, PVC et PTVC, sont résolus d’une manière approchée par des méthodes de recherche locale. Une phase de post-optimisation est appliquée pour améliorer la solution trouvée. D’autres méthodes approchées telles que des métaheuristiques peuvent être utilisées pour la résolution du problème de tournées de véhicules avec contraintes d’accessibilité [14]. , E.E $ $ # [1] J.E. Beasley, "Route-first cluster-second methods for vehicle routing", Omega 11, pp. 403-408, 1983. [2] P. Camerini, L. Fratta et F. Maffioli, "On improving relaxation methods by modified gradient techniques", Mathematical Programming Study 3, pp. 26-34, 1975. [3] N. Christofides, A. Mingozzi et P. Toth, "The vehicle routing problem", dans Combinatorial Optimization, N. Christofides, A. Mingozzi, P. Toth et C. Sandi, éditeurs, Wiley, Chichester, pp. 315-338, 1979. [4] M. Fischetti, P. Toth et D. Vigo, "A branch-and-bound algorithm for the capacitated vehicle routing problem on directed graphs", Operations Research 42, pp. 846-859, 1994. [5] M. L. Fisher, "The Lagrangian relaxation method of solving integer programming problems", Management Science 27, pp. 1-18, 1981. [6] M. L. Fisher et R. Jaikumar, "A generalized assignment heuristic for vehicle routing", Networks 11, pp. 109-124, 1981. [7] M. Gendreau, A. Hertz et G. Laporte, "New insertion and postoptimization procedures for the traveling salesman", Operations Research 40, pp. 1086-1094, 1992. [8] B. E. Gillett et L. R. Miller, "A heuristic algorithm for the vehicle dispatch problem", Operations Research 22, pp. 340-349, 1974. [9] M. Held, P. Wolfe et M.P. Crowder, "Validation of the subgradient optimization", Mathematical Programming 6, pp. 62-88, 1974. [10] E. K. Lee et J. E. Mitchell, "Integer programming : branch and bound methods", dans Encyclopedia of Optimization, C.A. Floudas et P.M. Pardalos, éditeurs, Kluwer academic publishers, volume 2, pp. 509-519, 2001. [11] J.K. Lenstra et A.H.G. Rinnooy Kan, "Complexity of vehicle routing and scheduling problems", Networks 11, pp. 221-227, 1981. [12] C. Prins, "A simple and effective evolutionary algorithm for the vehicle routing problem", à paraître dans Computers and Operations research. /%0 1 F. Semet, "A two-phase algorithm for the partial accessibility constrained vehicle routing problem", Annals of Operations Research 61, pp. 45-65, 1995. /%2 1 M. Souid, "Résolution approchée d’un problème de tournées de véhicule avec contraintes d’accessibilité", Thèse de doctorat, Valenciennes, France, 2003. [15] P. Toth et D. Vigo, "The Vehicle Routing Prolem", Editions SIAM, Philadelphie, 2001.