Campagne : D’Est en Ouest, du Nord au Sud

Tournée politique électorale

 

D’Est en Ouest, du Nord au Sud

De notre correspondant en France

Séga Fall MBODJI

A l’aube de l’élection présidentielle, la campagne électorale anime le pays de la téranga, d’Est en Ouest, du Nord au Sud. Pour faire leur promotion, les candidats vont à la rencontre des populations dans les différentes régions du Sénégal et éventuellement la Diaspora, dans le but de récolter le plus grand nombre de voix possible. Cette exploration territoriale nécessite des ressources financières faramineuses : financement des tournées, meetings, distributions de tract, impressions et collages d’affiche, etc. Sans cadrage a priori d’une campagne électorale, l’estimation du budget s’avère compliquée car les dépenses inattendues deviennent vite exorbitantes.

Sillonner le pays est loin d’être une évidence pour tous les candidats, même si cette étape demeure primordiale pour un prétendant à la magistrature suprême. Certains candidats ont la chance de pouvoir appeler leurs partisans et sympathisants au lancement d’une cagnotte tandis que d’autres peinent à dénicher un financement suffisant. Ces problématiques diverses nous interpellent sur l’optimisation des ressources par la détermination du plus court chemin passant une unique fois par chaque région. Cette minimisation distancielle du trajet réduirait considérablement les coûts, par exemple la consommation en carburant du convoi de véhicules.

L’objectif de cette étude est de déterminer mathématiquement le meilleur itinéraire reliant les 14 régions du Sénégal qu’un candidat doit parcourir dans sa tournée politique. Le candidat passe une unique fois dans chacune des régions ; d’où l’optimalité de cet itinéraire.

Les données

Nous considérons les 14 régions suivantes du Sénégal :

                                 

Pour calculer la distance routière entre ces régions, nous utiliserons le calculateur en ligne disponible via le lien suivant : http://fr.distances-routieres.himmera.com/distance_routiere_entre_deux_villessenegal/ Précision du calculateur : Selon l’ANSD, la distance entre Mbacké et Kabrousse est de 283,99 km en vol d’oiseau, alors que cela représente environ 420 km par la route.
Pour cette même distance entre Mbacké et Kabrousse, le calculateur en ligne trouve 285 km en vol d’oiseau et 426 km par la route :

Ces résultats confirment la robustesse du calculateur.
Sachant qu’un candidat mobilise son convoi par la voie routière, nous allons calculer la distance routière qui se distingue de la distance à vol d’oiseau entre les régions.
Grâce au calculateur, nous déduisons la matrice des distances suivante :

Algorithmes

L’objectif consiste à trouver un chemin passant par toutes les régions une unique fois et qui soit de longueur minimale. Une approche de résolution naïve, mais qui donne un résultat exact, est de balayer tous les chemins possibles par recherche exhaustive. Cette méthode devient très vite impraticable lorsque le nombre de régions augmente :

                       
Supposons un ordinateur assez rapide pour évaluer un parcours en une demi-microseconde : le cas à 5 régions serait résolu en moins de 6 microsecondes, le cas à 10 régions en 0,09 seconde, mais pour le cas à 20 régions, il faudrait 964 ans pour balayer toutes les solutions possibles. Il est donc indispensable de recourir à des techniques de résolution plus performantes.

• Algorithme du plus proche voisin

La technique est simple et consiste à choisir une région de départ puis à chaque étape on sélectionne la prochaine région la plus proche. Cette méthode ne garantit pas  toujours l’optimalité de la solution obtenue mais elle donne un chemin raisonnable. L’approche du plus proche voisin donne le circuit rouge représenté sur le schéma ci-dessous. En partance de la région de Dakar pour l’exploration des 13 autres régions, la dernière région à visiter est Kédougou. Le parcours s’étend sur 3.185 km avec un retour à Dakar du candidat.

• Algorithme de Little

C’est un algorithme de résolution par Branch and Bound (Séparation et Evaluation). La séparation consiste à considérer l’inclusion ou l’exclusion d’un trajet (𝑖,𝑗) dans une tournée. Elle produit 2 branches dans un arbre de recherche binaire.
L’Evaluation fournit une borne inférieure de la distance de la tournée par des opérations sur le tableau des distances. Autrement dit, dans l’arbre de recherche binaire, on inclut à chaque étape le trajet dont l’exclusion cause le plus grand regret.
On applique l’algorithme de Little sur les 14 régions du Sénégal pour déterminer le circuit optimal pour une tournée politique d’un candidat. On obtient le circuit vert d’une longueur totale de 2.509 km.

Contrairement au circuit du plus proche voisin qui dépend de la région de partance, celui de Little reste inchangé quelle que soit la région de départ. C’est un circuit optimisé non orienté et constitue un itinéraire idéal pour un candidat qui souhaite battre campagne dans chacune des 14 régions.

Considérons le poids électoral régional qui représente la part d’électeurs de chaque région par rapport au nombre d’électeurs inscrits dans le fichier électoral.

On constate que le groupement des régions de Dakar, Thiès, Diourbel, Saint-Louis, Kaolack, Louga et Fatick concentre plus de 75% de l’électorat. Donc un candidat aux ressources limitées pourrait parcourir seulement ces 7 régions dont le circuit optimal de Little (en vert) s’étend sur 1.148 km, 2 fois moins de régions et 2 fois moins de distance.