# Hybridation entre recherche incomplète et apprentissage de conflits pour un problème de routage avec sélection de clients

Trong-Hieu Tran, Cédric Pralet, Hélène Fargier

► To cite this version:

Trong-Hieu Tran, Cédric Pralet, Hélène Fargier. Hybridation entre recherche incomplète et apprentissage de conflits pour un problème de routage avec sélection de clients. 22ème congrès annuel de la société Française de Recherche Opérationnelle et d'Aide à la Décision (ROADEF 2021), Société Française de Recherche Opérationnelle et d'Aide à la Décision (ROADEF); Laboratoire IRIMAS de l'Université de Haute-Alsace, Apr 2021, Mulhouse, France. pp.1-2. hal-03311839

HAL Id: hal-03311839

https://hal.science/hal-03311839v1

Submitted on 2 Aug 2021

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
Hybridation entre recherche incomplète et apprentissage de
conflits pour un problème de routage avec sélection de clients

Trong-Hieu Tran¹, Cédric Pralet², Hélène Fargier¹

¹ IRIT-CNRS, Université de Toulouse, Toulouse, France
{trong-hieu.tran,helene.fargier}@irit.fr

² ONERA/DTIS, Université de Toulouse, F-31055 Toulouse, France
cedric.pralet@onera.fr

Mots-clés: recherche incomplète, apprentissage de conflits, OBDD, OPTW.

# 1 Problématique

Les méthodes de recherche dites incomplètes sont souvent utilisées en pratique pour traiter
en temps contraint des problèmes d'optimisation difficiles, en s'appuyant par exemple sur des
métaheuristiques type recherche tabou pour s'échapper des optima locaux. Nous nous inté-
ressons ici au développement d'une nouvelle stratégie de recherche permettant d'améliorer la
qualité des solutions produites ou de produire ces solutions plus rapidement. L'idée poursui-
vie consiste à réaliser une *recherche incomplète guidée par les conflits* rencontrés lors de la
résolution, un conflit correspondant dans notre cas à une instanciation d'un sous-ensemble des
variables de décision qui conduit à une violation des contraintes du problème ou à une sous-
optimalité de la solution. L'objectif est de mémoriser ces conflits *sur le long terme* et de les
utiliser pour d'une part éviter de revisiter inutilement certaines zones de l'espace de recherche
et d'autre part tenter d'orienter la recherche vers les solutions les plus prometteuses. Cette idée
de recherche guidée par les conflits est à rapprocher de la méthode CDCL (*Conflict Driven
Clause Learning*) travaillant sur des problèmes SAT [1, 2].

La nouvelle méthode proposée est appliquée au problème de routage connu sous le nom d'OPTW (Orienteering Problem with Time Windows [4]), dans lequel un véhicule doit maximiser le profit collecté en visitant un sous-ensemble de clients candidats, sachant (1) qu'il existe pour chaque client une fenêtre temporelle autorisée pour la visite, une durée de visite et un profit associé, et (2) qu'un temps de transition est requis pour passer d'un client à un autre.

# 2 Techniques mises en œuvre

Nous considérons comme point de départ une méthode de recherche basique qui part d'un
plan vide pour le véhicule et qui tente d'insérer à chaque étape un nouveau client dans le plan.
Cette phase d'insertion est itérée jusqu'à ce que tous les clients aient été considérés. Une phase
de perturbation est ensuite appliquée, en retirant x% des clients du plan, suite à quoi des inser-
tions itératives de clients sont à nouveau tentées. L'algorithme s'arrête lorsque la meilleure so-
lution connue n'a pas été améliorée depuis un nombre fixé de phases de perturbation-insertion.

Au sein de cette méthode élémentaire, nous ajoutons des techniques d'apprentissage de
conflits ainsi qu'une heuristique de choix du prochain client à insérer basée sur ces conflits :

- Lorsqu'une tentative d'insertion d'un client c échoue, nous calculons très rapidement une
explication de cet échec d'insertion. Cette explication prend la forme d'un sous-ensemble
de clients {$c_1, \dots, c_k$} minimal pour l'inclusion et qui contient des clients pour lesquels
aucun ordre de visite réalisable n'a été trouvé dans le temps imparti pour raisonner.
— Pour l'heuristique de sélection d'un nouveau client à insérer à chaque étape, nous tentons de choisir un client *c* de manière à maximiser une évaluation de la récompense globale qu'il serait possible d'obtenir en sélectionnant *c*, étant donné tous les clients déjà sélectionnés et tous les conflits de sélection déjà mémorisés.

Plusieurs obstacles doivent toutefois être surmontés pour obtenir une approche efficace, avec (1) la question de la taille mémoire requise pour stocker tous les conflits rencontrés, (2) la question de la rapidité de la requête d'extraction d'un meilleur client en prenant en compte les conflits, (3) la question de la rapidité des opérations de modification de la base de conflits.

Pour surmonter ces obstacles, la sélection d'un client *c* est exprimée par une variable boo-
léenne $x_c$, un conflit $\{c_1, \dots, c_k\}$ est vu comme une clause $\neg x_{c_1} \lor \dots \lor \neg x_{c_k}$, et l'ensemble
des conflits est stocké sous la forme d'un OBDD (*Ordered Binary Decision Diagram* [3]), qui
correspond à une structure de données pouvant être exponentiellement plus compacte qu'une
table listant tous les conflits et qui nous permet de sélectionner en temps linéaire en la taille
de l'OBDD un client "optimal" étant donné les conflits mémorisés et les profits associés aux
clients. Par ailleurs, pour limiter l'impact d'opérations standards de réoptimisation de la taille
d'un OBDD, les conflits trouvés par l'algorithme sont ajoutés par *batch* et non un par un.

3 Résultats obtenus

La méthode proposée a été implémentée en langage Python, avec pour la partie gestion des OBDD une utilisation de la librarie PyCUDD. Des expérimentations ont été réalisées sur des instances classiques d'OPTW (https://www.mech.kuleuven.be/en/cib/op). Beaucoup de meilleures bornes connues ainsi que des améliorations par rapport à la méthode d'ILS [5] ont été retrouvées, avec des temps de calcul compétitifs avec l'état de l'art (cf. table 1).

<table><caption>TAB. 1 – Quelques résultats obtenus sur des instances classiques d'OPTW (tests réalisés sur un
processeur Intel Core i5-10210U, 1.6 GHz, 16 GB de RAM)</caption>
   <thead>
    <tr>
     <td>
      Instance
     </td>
     <td>
      ILS+GRASP [4]
     </td>
     <td>
      ILS [5]
     </td>
     <td>
      Notre résultat
     </td>
     <td>
      #conflits
     </td>
     <td>
      #OBDD (noeuds)
     </td>
     <td>
      CPU(s)
     </td>
    </tr>
   </thead>
   <tbody>
    <tr>
     <td>
      c107
     </td>
     <td>
      <strong>
       370
      </strong>
     </td>
     <td>
      360
     </td>
     <td>
      <strong>
       370
      </strong>
     </td>
     <td>
      7350
     </td>
     <td>
      1789
     </td>
     <td>
      5.59
     </td>
    </tr>
    <tr>
     <td>
      r101
     </td>
     <td>
      <strong>
       198
      </strong>
     </td>
     <td>
      182
     </td>
     <td>
      <strong>
       198
      </strong>
     </td>
     <td>
      5720
     </td>
     <td>
      1708
     </td>
     <td>
      3.38
     </td>
    </tr>
    <tr>
     <td>
      r104
     </td>
     <td>
      <strong>
       303
      </strong>
     </td>
     <td>
      297
     </td>
     <td>
      299
     </td>
     <td>
      15936
     </td>
     <td>
      2129
     </td>
     <td>
      9.72
     </td>
    </tr>
    <tr>
     <td>
      r107
     </td>
     <td>
      <strong>
       299
      </strong>
     </td>
     <td>
      288
     </td>
     <td>
      294
     </td>
     <td>
      11661
     </td>
     <td>
      2347
     </td>
     <td>
      7.94
     </td>
    </tr>
    <tr>
     <td>
      r109
     </td>
     <td>
      <strong>
       277
      </strong>
     </td>
     <td>
      276
     </td>
     <td>
      <strong>
       277
      </strong>
     </td>
     <td>
      15118
     </td>
     <td>
      4645
     </td>
     <td>
      9.55
     </td>
    </tr>
   </tbody>
  </table>

Divers travaux futurs sont envisagés, notamment la réduction de la taille de la base de conflits
via l'utilisation de langages de compilation autres que les OBDD ou l'approximation de la
forme compilée. Un autre point concerne le traitement des incertitudes, avec comme motivation
applicative des problèmes de sélection d'observations pour un satellite où des informations
météo de dernière minute peuvent modifier les profits associés aux observations.

Références

[1] G. Audemard, J.-M. Lagniez, B. Mazure, and L. Sais. Integrating conflict driven clause learning to local search. In *Int. Workshop on Local Search Techniques in Constraint Satisfaction*, 2009.

[2] A. Biere, M. Heule, H. van Maaren, and T. Walsh, editors. *Handbook of Satisfiability*, chapter 4 : Conflict Driven Clause Learning. IOS Press, 2009.

[3] R. Bryant. Graph-based algorithms for boolean function manipulation. *IEEE Transactions on Computers*, C-35(8) :677–691, 1986.

[4] W. Souffriau, P. Vansteenwegen, G. V. Berghe, and D. Van Oudheusden. The multi-constraint team orienteering problem with multiple time windows. *Transportation Science*, 47 :53–63, 2013.

[5] P. Vansteenwegen, W. Souffriau, G. V. Berghe, and D. Van Oudheusden. Iterated local search for the team orienteering problem with time windows. *Computers & Operations Research*, 36(12) :3281–3290, 2009.