[PDF] [PDF] Une approche Branch-Cut-and-Price pour la résolution du problème

Une approche Branch-Cut-and-Price pour la résolution du problème de voyageur de commerce suffisamment proche avec contraintes de couverture sur les arcs Soukaina Semami1, Mohamed Bouchoum1, Brahim Aghezzaf1 Université Hassan II, Faculté des Sciences Ain Choc (FSAC) Laboratoire d'Informatique et Aide à la Décision (LIAD), Département de Mathématiques et Informatique B.P 5366 Maârif Casablanca 20100, (Maroc) {soukaina.sema@gmail.com, m.bouchoum@fsac.ac.ma, b.aghezzaf@fsac.ac.ma} Mots-clés : RFID, CEARP, Branch-Cut-and-Price, SCIP, Voyageur de commerce suffisamment proche. 1 Introduction Le problème du voyageur de commerce suffisamment proche avec contraintes de couverture sur les arcs, mieux connu par Close Enough Ar c Routing Problem (CEARP) est une nouvelle variante du fameux Traveling Salesman Problem (TSP). Cette variante est principalement conçue pour le secteur de distribution d'énergie : ea u, gaz, électricité . Certaines inf ormations, notamment les qu antités consom mées, sont communiquées à distance par des entreprises de ce secteur et ce, en utilisant la lecture automatisée des compteurs (AMR) avec l'identification par radio fréquence (RFID). Ainsi la visite de certains clients dans leur propre localisation n'est plus obligatoire. Un état de l'art ainsi que d'autres contextes d'application sur le problème CEARP sont détaillés dans [2, 3]. Nous proposons une formulation du CEARP pour le cas orienté sous la forme d'un programme non linéaire d'un entier mixte non convexe. Cette formulation a la propriété que la fixation de toutes les variables entières à n'importe quelle valeur entière donne un problème convexe non linéaire. Soit G = (V, A) un graphe complet où V= {v0 ... vn-1} est l'ensemble des noeuds et A= {(vi, vj) : vi,vj ∈ V} est l'ensemble des arcs. Chaque noeud vi ∈ V est entouré d'un disque du rayon de couverture r, à l'exception du dépôt v0. Soit (xi,yi) les coordonnées cartésiennes d'un point sur le tour qui est "le plus proche» du noeud vi, ce point est dit point représentatif du noeud i (détails dans [3]). Définissons W= {w1,w2...wl}, un ensemble des clients qui doivent être couverts. Soit λlij des coefficients binaires égaux à 1 si le client wl ∈ W peut être couvert par l'arc (vi,vj) ∈ A, 0 sinon. Soit ξij la variable binaire égale à 1 si l'arc (vi,vj) est sélectionné par le tour, 0 sinon. Le but du CEARP est de chercher la tournée la plus courte commençant et terminant au dépôt de manière à ce que chaque client soit couvert par le tour. Un client est couvert par le tour si la distance minimale entre le client et un arc du tour est inférieure au rayon de couverture r. Le CEARP peut être formulé comme suit : Minimiser ξ!"!!!!!!!! x!-x!!+y!-y!² (1) Sujet à: ξ!"=1 ∀ j ∈ V (2) ξ!"=1!!!!, pour tout j (3) ξ!"=1!!!!, pour tout i (4)