Campagne électorale : Vous avez dit 5.000 km ?

Optimisation d’une tournée politique électorale

 

Cela me semblait bizarre

de les entendre dire

qu’ils ont parcouru 5.000

km

 

La distance totale à parcourir étant minimale,

l’optimalité du chemin réduirait considérablement

les coûts, par exemple la consommation en carburant

du convoi de véhicules

De notre correspondant en France

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 à la candidature vont à la rencontre des populations dans les villes des 14 régions du Sénégal dans le but de récolter le plus grand nombre de voix possible.

Le coût de la campagne électorale est faramineux : tournées, meetings, distribution de tracts, collage d’affiches, etc. Ces dépenses sont difficilement pilotables en raison de paramètres de coût imprévisibles: 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.

Ce périple laborieux mobilise beaucoup de ressources. Certains candidats appellent leurs partisans et sympathisants au lancement d’une cagnotte, d’autres interrompent la tournée faute de carburant en suffisance. Ces problématiques diverses nous interpellent sur l’optimisation des ressources par la détermination du plus court chemin passant par toutes les régions. La distance totale à parcourir étant minimale, l’optimalité du chemin réduirait considérablement les coûts, par exemple la consommation en carburant du convoi de véhicules.
Dans ce qui suit, nous allons calculer la distance séparant les différentes villes puis appliquer 2 algorithmes mathématiques pour trouver ledit chemin.

Les données

Nous calculons la distance routière entre les villes du Sénégal avec le calculateur disponible via le lien suivant :
http://fr.distances-routieres.himmera.com/distance_routiere_entre_deux_villes- senegal/
Il est à préciser que cette distance n’est pas calculée en ligne droite. Selon l’ANSD, la distance entre Mbacké et Kabrousse est de 283,99 km à vol d’oiseau, alors que cela représente environ 420 km par la route.
Le calculateur fournit un résultat précis :

 

L’objectif revient à trouver un chemin passant par toutes les villes 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 villes augmente :

Supposons un ordinateur assez rapide pour évaluer un parcours en une demi-microseconde : le cas à 5 villes serait résolu en moins de 6 microsecondes, le cas à 10 villes en 0,09 seconde, mais, pour le cas à 20 villes, 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 ville de départ puis, à chaque étape, on sélectionne la prochaine ville la plus proche. Cette méthode ne garantit pas toujours l’optimalité de la solution obtenue mais elle donne un chemin très raisonnable.
L’approche du plus proche voisin donne le circuit rouge représenté sur le schéma ci- dessous. En partance de la ville de Dakar et reliant les 20 villes, sa longueur totale est de 4.598 km.

• 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 pour relier les 17 villes suivantes :

On obtient le circuit vert d’une longueur totale de 2.807 km.

Les circuits algorithmiques rouge et vert ne sont pas intuitifs. En comparant les 2 algorithmes, on voit que Little réduit drastiquement le chemin à parcourir. Un candidat peut donc percer les différentes villes prévues dans sa tournée en un temps record et au moindre coût.

Séga Fall MBODJI,

Paris