Reprise du message précédent :
Salut à tous,
 
J'ai un petit problème, dont voici l'intitulé
 
Je dispose d'une liste de clients situés en France, chacun générant pour moi un Chiffre d'affaire unique.
 
Mon but est de créer des tournées (coursiers) de livraison à ces client (pour leur faire parvenir les produits que je leur vends)
 
J'ai 2 contraintes:
- Je veux que mes coursiers fassent le moins de km possible
- Je veux desservir les gros clients en termes de chiffre d'affaires en premier
 
Les coursiers partent d'un point donné et reviennent à ce même point une fois la livraison effectuée
 
Quelqu'un a une idée du modèle/algorithme à mettre en place pour optimiser au maximum mes tournées?  
 
Merci

ça ressemble pas mal à un problème de voyageur de commerce, mais avec une contrainte supplémentaire vu que tu veux servir ceux qui font le plus de chiffre en premier.
 
par contre, faudrait préciser un peu tes contraintes. tu disposes de combien de coursiers ? tu veux créer plusieurs tournées différentes, ou alors une seule tournée qui passe par tous tes clients ? est-ce que tu peux préciser "desservir les plus gros en premier" ? parce que j'imagine qu'un modèle où tu dessers tes clients par chiffre d'affaire décroissant ne t'intéresse pas, si c'est pas efficace en termes de kilométrage...

J'ai 3 coursiers
Plusieurs tournées différentes
Effectivement, pour cela j'ai calculé un score (ratio CA/distance du point de départ), mais j'avoue que je trouve son utilité limitée

En fait il faut trouver un modèle dans lequel les conditions "clients aux plus gros CA" et "distance kilométrique faible" seraient validées, la meilleure configuration possible en gros. Je ne vois qu'un algorithme pour faire ça

Merci pour ta réponse

Pas mieux que double clic : c'est un problème NP Complet, donc il n'existe aucun PC assez puissant pour trouver la solution en un temps raisonnable (genre, t'as pas mille milliards de milliards de siècles devant toi ).
Les seules solutions sont les trucs genre algorithmes génétiques, recuit simulé, programmation par contrainte ... Bref, tout ce qui est méta heuristiques, ou heuristiques adaptés à ton problème (bien que dans ton cas, je ne pense pas que tu puisses faire d'optimisations personnalisés)

Edith : par contre, t'as combien de clients ?

216 clients
le calcul intégral serait si long que ça?  

Bah en gros, t'es dans un calcul factoriel :
Premier coup, t'as 216 possibilités (de choisir le premier client), second, t'as 215, etc etc, donc, t'as 216! possibilités.
Donc, t'as 10^412 chemins à calculer. En admettant que tu puisses calculer 10^20, voire 10^50 trucs par secondes, combien de secondes te faut-il pour tout calculer ? ^^

Edith, c'est pour ça que je demandais le nombre de clients : si t'en as qu'une 20aine, tu peux faire le calcul. Mais quand ça devient trop gros => méta heuristiques.

j'imagine que pour rendre les choses plus drôles la liste des clients qui doivent être livrés change à chaque départ de tournée ?

Ok merci
Et si je découpe ma clientèle par tranches (ex: ca faible/moyen/élevé et distance faible/moyenne/élevée) dans un tableau bête, je peux traiter chaque cas séparément et donc réduire les chemins possibles?

edit: d'ailleurs si ton CA min = 1000 €  et CA max = 65000 €, comment fais tu pour déterminer au mieux 3 tranches? (élevé/moyen/faible), comment faire une répartition optimale?

non

ok une première chose à faire, ça pourrait être de regrouper les clients qui sont proches géographiquement (s'il y en a), de manière à diminuer le nombre de cas à prendre en compte. la manière d'attaquer le problème dépend pas mal de la manière dont il se présente en fait

mal
 
Sinon j'ai ajouté une question  

drapal    
 
je n'ai fait qu'un Bac S (spé SVT), mais j'aime bien les maths, et j'vais devoir m'y remettre pour mes concours cette année

Bien évidemment, tu gagneras un max de temps.
En gros, 216! >>>>>>>>>>>>>>>>>>>>>>>>>>>>> (216/3)! * 3
Par contre, faut voir si 6.10^103 est un nombre viable.

Mais bon, dans tous les cas, faut passer par un programme informatique, la main, t'oublies. Et après, si c'est programmé, regarde quand même du côté d'un algo de méta heuristique (je dis pas ce mot pour rien depuis tout à l'heure j'espère) : c'est TA solution. Disons qu'une méta heuristique te trouve au mieux LA solution, et au pire, une bonne solution.

J'ai un trou de mémoire sur un nom d'algo.
Une idée : tu divises tes CA en trois groupes égaux (ie : pauvres < moyens < riches). Tu calcules pour chacun la moyenne et l'écart type. Après, le but sera de changer les points dans les groupes afin de réduire la somme des écarts type. Concrètement, t'as tes valeurs triées, et t'as A qui est la plus grosse valeur des pauvres. Bin tu connais la somme des Ep + Em + Er (E comme écart type), tu déplaces A dans les moyens, tu recalcules Mp, Mm, Ep et Em, et tu compares Ep + Em + Er nouveau à l'ancien. Donc au final, tes groupes n'auront plus la même taille.
Par contre attention :
1) j'ai pas l'impression que cet algo soit parfait. Mais je pense qu'il peut donner de bons résultats.
2) ne pas oublier que la moyenne d'un groupe + ou - un élément se calcule très facilement à partir de la moyenne précédente : M = (a + b + c + d) / n = S / n. Si tu rajoutes e, ça devient (S + e) / n + 1
3) même chose pour l'écart type.

 
Bon, je confirme, cet algo n'est pas parfait du tout
L'autre solution plus bourrin, c'est de calculer tous les ensembles possibles (genre {1, 1, 214}; {1, 2, 213}...), et tu cherches l'endroit où la somme Mp + Mm + Mr est minimum. On en profite, t'as pas des masses de points, et c'est un algo en n2 (à la louche) (donc un algo très très raisonnable).

Ok merci je vais tenter
SInon, existe-t-il un soft capable de donner toutes les distances par rapport à un point donné sur une carte? (sans rentrer les adresses manuellement une à une)

Typiquement je rentre mes 100 destinations sous excel et j'obtiens tous mes distanciers par rapport à un point?

euh, tu veux dire tu rentres l'adresse de ton point de départ et tu veux la distance à ton point d'arrivée ? à la limite, on peut bidouiller un truc en php qui fait une requête sur un site d'itinéraires et qui parse la page de réponse pour en extraire la distance, m'enfin c'est pas super orthodoxe

Non en gros c'est avoir un tableau en double entrée avec mes mêmes addresses sur les lignes et colonnes
A chaque croisement de ligne et de colonne, ben t'as une distance

oui, donc il faut bien un truc qui calcule la distance entre deux adresses pour remplir ton tableau

Une fois qu'on a cette data, je ne pense pas que l'algorithme soit difficile à mettre en place

Pt de départ ---> D1 (choisit le meilleur score,càd CA D1/distance pt de départ-D1 le plus élevé= ---> D2 (choisit le meilleur score, çad CA D2/distance D1-D2 le plus élevé), ---> Dx

Vi mais il me faudrait un truc en auto pour calculer la distance de 100 point par rapport à 100 autres, un par un dans Yahoo Maps je vais pleurer
Et MapPoint ne le fait pas

Un truc comme ça
 
http://www.migdal.org/israel/utilitaires/distance.php

ben alors ce que j'ai dit, un truc qui envoie automatiquement des requêtes à un site d'itinéraires et qui extrait le résultat mais ça demande un peu de connaissances en programmation...

jconnais rien
sinon ya ça : http://fr.wikipedia.org/wiki/Algorithme_de_Dijkstra
 

euh, oui, mais ça fonctionne pas avec des adresses réelles ça

Bonjour,
 
je viends là parce que presque certain que j'aurais la meilleur solution à mon problème.
 
Comment un convertie un entier base 10 en base 2.
 
(pas taper)  
 
Merci

Commence avec ton nombre base 10, et divise par 2 avec reste successivement.
 
Par exemple: prenons 22.
22 = 2 * 11 + 0
donc le chiffre des unités est 0
11 = 2 * 5 + 1
donc le prochain chiffre est 1
5 = 2*2 + 1
2 = 2*1 + 0
1 = 2*0 + 1
 
22 base 10 = 10110 base 2

Je n'ai pas compris.  

Comment choisis -tu 11, 5, 2, ... ?

- Tu prends la puissance de 2 la plus grande qui soit inférieure ou égale à ton nombre. Ca sera ton premier chiffre en binaire ( toujours 1 )
- Pour chaque puissance inférieure, si la somme dépasse ton nombre moins la puissance en décimal, ca sera un 0. Sinon, ca sera un 1.
- Tu refais la meme chose jusqu'a 0

c'est pas très clair, on va illustrer :

pour 11 : la puissance la plus grande ne dépassant pas 11 est 2^3 = 8
l'écriture en binaire est donc : 1 _ _ _

8 + 2 ^2 = 12, ca dépasse, donc 0 : 1 0 _ _

8 + 2^1 = 10, c'est bon, donc 1 : 1 0 1 _

et 10 + 2^0 = 11, le compte est bon : 1 0 1 1

Ah merci Leroi14, j'ai fait ceci, je vais jeter un coup d'œil, mais je crois que c'est bon.

Ah merci Leroi14, j'ai fait ceci, je vais jeter un coup d'œil, mais je crois que c'est bon.

function To_bbyte(The_Byte : in byte) return T_Byte is
      Last : Positive := 8;
      Value : integer := Integer(The_Byte);
      Bbyte : T_Byte := (others => False);
      Rest : Integer;
   begin
      loop
         rest := (value rem 2);
         value := (Value/2);
         Bbyte(Last) := boolean'Val(Rest);
         exit when Value = 0;
         Last := Last - 1;
      end loop;
      return Bbyte;
   end To_Bbyte;

tain j'avais fait une erreur dans ma derniere ligne

Je trouve plus intuitif l'utilisation de la division euclidienne par 2.

C'est pas parce que tu as été banni de la section programmation que ça t'autorise a poster ici ce que tu ne peux dorénavant poster la-bas, hein...  
A+,
 

 
Djikstra peut fonctionner avec des adresses réelles, mais faut se le recoder (faut se refaire un graph avec le temps entre les destinations).
 
Par contre, on passe d'un algo en N² (pour calculer les moyennes), à un algo en N5 (algo pour calculer les moyennes + algo de djikstra). Donc ça commence à prendre du temps (enfin, c'est très très inférieur au temps de N!, ça c'est clair).

Bonjour gilou,
Je suis toujours bannie ce matin en tout cas.  
 
Arff, laisse tompbé, j'ai raté, un "ne" dans "ce que tu ne peux dorénavant"  
OK !

En fait il est pas très intelligent jovalise, je suis déçu

Bonjour,
 
Pouvez-vous expliquer comment 0**0 = 1;
 
Merci.  

0^0 est ce qu'on appelle une forme indéterminée en maths, ce qui signifie que l'on ne peut y attribuer un sens absolu. Dans le même genre on peut citer 0/0 ou 1^INF.
 
Elles sont traitées dans le cadre de la théorie des limites. Par exemple l'expression lim x^x est de type 0^0 mais sa limite vaut 1 quand x--> 0. Cela ne signifie pas que 0^0 = 1. En guise de contre exemple, l'expression 2*x^x est aussi du type 0^0 mais sa limite vaut 2.

 
C'est une convention ?