Skip to content

Idées — Algorithme

Jump to bottom
Quentin RIBAC edited this page Apr 24, 2017 · 6 revisions

2017-04-22

Finalement, il semble trop hasardeux de vouloir fondre en une seule les deux variables temps total et coût de la distribution. Considérant également le nombre variable de facteurs, on peut donner un algorithme simple tel que :

  • On doit minimiser le coût ; le nombre de facteurs initial est minimal. La durée de la distribution, elle, ne sera pas minimisée mais limitée à une durée arbitraire, peut-être de 2h ou 3h.
//Valeurs initiales
final double DUREE_MAX = 2.0; //en heures
final int NB_COURRIERS; //une constante donnée
final Courrier[] courriers; //un tableau donné d’adresses et de type (lettre ou colis)
final Adresse centrePostal; //le point de départ et d’arrivée

//un facteur supplémentaire s’il y a au moins une lettre et un colis
int nbFacteurs = 0;
if ((courriers.nbColis() >= 1) && (courriers.nbLettres() >= 1)) {
    nbFacteurs++;
}

Circuits[] circuits;
double duree = 0;
double cout;
do {
    nbFacteurs++;
    cout = 0;
    for (int i = 0; i < nbFacteurs; i++) {
        circuits[i] = new Circuit(centrePostal);
        circuits[i].initNaive(); //TODO
        circuits[i].heuristique2opt(); //TODO
        cout += circuits[i].cout();
        if (circuits[i].duree() > duree) {
            duree = circuits[i].duree();
        }
    }
} while (duree > DUREE_MAX);

2017-04-19

Après davantage de réfléxion, j’ai réalisé que la question de la réduction du nombre de variables à optimiser soulevait une question sémantique : on ne peut pas simplement tout convertir dans la même unité par des formules arbitraires, mais l’unité des variables impose une unité sémantique.

Dans notre problème, nous pensions devoir limiter distance, coût et durée. Pour trouver une unité sémantique, il nous faut comprendre quels aspects d’un même concept ils recouvrent. Ce concept, à mon avis, est la dépense effectuée par La Poste pour la distribution.

C’est pourquoi dans l’estimation en temps, la valeur equivTemps(cout) devrait représenter le temps nécessaire à La Poste afin de rembourser ce coût. C’est pourquoi l’équation donnée en 2017-04-15 devrait être modifiée en :

equivTemps(cout) = cout / revenuDeLaPoste
tempsAMinimiser = tempsReelDistribution + cout / revenuDeLaPoste

Où le revenu de La Poste est le gain horaire du centre de distribution, que peut-être l’on estimera à deux fois la somme des salaires des employés.

(2) & (3) Problème des facteurs à pied ou en voiture, des lettres et des colis

En ce qui concerne uniquement le calcul des itinéraires et l’estimation des coûts, la solution sera je l’espère simple : dans le cas de l’existence d’une API Google Maps pour applications JavaSE, on pourra demander à Google les durées et coûts en carburant des déplacements entre les points de livraison, que l’on pourra demander au besoin en voiture ou à pied.

2017-04-15

Rappelons le but de l’algorithme : étant donné une liste de courriers (adresse & type (lettre ou colis)), calculer un chemin optimal de distribution.

Rappelons les contraintes et difficultés :

  • (1) nombre de facteurs variable ;
  • (2) colis devant être livrés par un facteur en voiture ;
  • (3) des rues à sens unique ou piétonnes ;
  • (4) il faut optimiser la distance, le coût et le temps de distribution, trois variables distinctes.

Réflexions sur les contraintes

(4) Réduction du nombre de variables à optimiser

La distance doit pouvoir être estimée en équivalent de temps de trajet et de coût en carburant pour le facteur motorisé. Autrement dit, les valeurs à optimiser sont coût et temps.

À présent, la question est de savoir si l’on peut estimer le temps en équivalent argent, dans le but de n’avoir qu’une variable à optimiser. Que veut-on dire par « optimiser le temps » ? Il s’agit de faire en sorte que la durée nécessaire à la distribution des courriers et au retour du ou des facteurs au centre de distribution soit minimale. Ceci dit, il se peut que pour deux instances du problème, on ait deux durées identiques, et deux coûts différents :

  • Cas 1 : 1 lettre à coût a, distance d, 1 facteur --> temps t, coût a
  • Cas 2 : 2 lettre à coûts a et b, toutes deux à distance d, 2 facteur --> temps t, coût a+b

On semble alors bloqué à un minimum de deux variables. Cependant, si l’on ne peut pas réduire le temps à un équivalent argent, peut-on réduire l’argent à un équivalent temps ?

On ferait alors :

tempsAMinimiser = tempsReelDistribution + equivTemps(cout)
cout = Σ(tempsParFacteur) × salaireHoraire + coutCarburant
equivTemps(cout) = cout/salaireHoraire = Σ(tempsParFacteur) + coutCarburant/salaireHoraire

Ce qui signifie qu’on cherche à minimiser la somme des temps réel de la distribution, somme des temps de tous les facteurs, équivalent temps du carburant. L’équivalent temps du carburant est calculé en €/(€/temps) = temps, donc la formule est homogène (dans la bonne unité).

Clone this wiki locally