tournér de véhicules

[kader1]

Bonjour
En naviguant sur internet, j'ai vu que le problème de l'optimisation de tournée de véhicules est l'un des problèmes NP-difficiles. Mais ils expliquent les algorithmes d'une façon savante et je ne comprends pas; ils ne donnent pas un exemple concrêt c'est à dire un exemple à faire à la main.
Y'a t-il quelqu'un qui peut m'expliquer comment on fait à la main pour optimiser les distances et le nombre de véhicules sur un exemple de ce genre:

A,B,C,D,E,F,G,...sont les centres à livrer, chaque centre tant de palettes, le nombre de camions entre 4 et 8 par exemple, capacité d'un camion de tant de palettes, distances entre centres connues; je vous laisse le choix des données
( si ce n'est pas clair je peux fournir des données)
Merci pour votre aide.

 

[thomlau]

Re : tournér de véhicules

Bonsoir kader, le forum;

Je suis sur que pas mal de gens peuvent t'aider, mais il faut un fichier de départ, avec des données bidons, lieu de livraison A à G, camion 1 à 8 par exemple, contenance de chaque camion en équivalent palettes (32 ou 33 pour un semi complet si je ne m'abuse), de plus (mais je n'en suis pas sur), Google peut être utile dans la conception de ton fichier.

Donc un conseil, envoie un début de fichier...

bonne soirée à tous.

@+

 

[kader1]

Re : tournér de véhicules

Bonjour Thomlau

Voici les données que tu m'as demandées pour optimiser la tournée des véhicules en distance et en nombre de de véhicules

Tonnages à livrer à chaque centre
A 5
B 1
C 2.5
D 1
E 3
F 1.5
G 5
H 4
I 1
J 5
K 6
L 2
M 1
N 4
P 1

O est la plate-forme d’ou les véhicules partent et y reviennent
On dispose de 4 véhicules de capacité 15 tonnes chacun
Ci joint le distancier

On peut modifier le nombre de centres à livrer, des données, car ce n'est qu'un exemple à titre pédagogique.

 

[CBernardT]

Re : tournér de véhicules

Bonjour Kader1, thomlau et le forum,

Etant donné un ensemble de villes séparées par des distances connues, définir une tournée idéale consiste à trouver le plus court chemin qui relie toutes les villes.

1- Une logique empirique consiste à se rendre depuis la ville départ à la ville la plus proche. Puis, de proche en proche, revenir à la ville départ. En additionnant les distances entre villes on obtient la longueur de la tournée.

2- Si cette solution n’est pas optimum elle permet d’organiser et de réduire notablement la longueur du circuit de la tournée.

3- Une extension de cette solution consiste à définir toutes les tournées possibles en partant de toutes les villes constituant la tournée. On retiendra la tournée dont la distance est la plus courte.

4- Généralement, la définition du circuit de la tournée de véhicules n’est qu’un aspect du problème. En effet, des contraintes de capacité de chargement des véhicules, des contraintes liées aux horaires, etc. interagissent entre elles et viennent compliquer la résolution du problème.

5- Si le poids des colis à livrer dépasse la capacité d’un véhicule, le premier véhicules sera chargé d’un poids de colis inférieur à sa capacité qui corresponde aux premières étapes du circuit, le second véhicules sera chargé des colis des étapes suivantes et ainsi de suite jusqu’à la dernière livraison à effectuer.

Dans le fichier joint le détail du processus empirique comme défini au point 3 avec l’utilisation du distancier fourni.

 

[kader1]

Re : tournér de véhicules

Bonjour Bernard
Merci pour l'explication, ça a dû te couter du temps.
1°) On est pas sûr que la tournée retenue est optimale mais c'est mieux que rien...
2°) Cette tournée sera décomposée en 4 tournées car il faut 4 véhicules pour livrer et voici les circuits obtenus en suivant la tournée dans l'ordre ou' elle a été déterminée:
1er véhicule: OLMPNCHO 14.5 tonnes à livrer
2 ième véhicule: OGBAFO 12.5 tonnes à livrer
3 ième véhicule: OEDIJO 10 tonnes à livrer
4 ième véhicule: OKO 6 tonnes à livrer

Je pense que c'est ça...
Merci

 

[CBernardT]

Re : tournér de véhicules

Bonjour Kader1, thomlau et le forum,

Je vois que la solution proposée a retenu ton attention et que tu l'as parfaitement assimilée.

Contrairement aux solutions combinatoires, cette solution est facilement programmable sur Excel. Un exemple de programme en fichier joint :

Dans la feuille "DISTANCIER" :

1- Le tableau permet de saisir 40 destinations différentes. Mettre à jour les cellules vertes. Les cellules rouges sont protégées et mises à jour par formules.

2- A gauche des destinations saisir le tonnage de livraison.

Dans la feuille "TOURNEE" :

1- Dans la cellule F2 choisir le point de départ.

2- Dans le tableau de la flotte de véhicules (6 camions sont possibles mais plus si nécessaire) placer les capacités de chargement dans les cellules sous les camions.

3- Lancer la recherche de la tournée optimale par le bouton "TOURNEE OPTIMALE".

4- Les circuits des véhicules s'affichent dans le tableau sous chacun d’eux.

 

[kader1]

Re : tournér de véhicules

Bonjour Bernard
Merci pour la programmation sous excel
Mais il y a un petit problème:
1°) quelque soit la tournée, le total est toujours 1075 km
2°) pour la tournée commenant par le centre K, ça s'arrête au premier camion avec livraison 14.5 tonnes
Merci

 

[CBernardT]

Re : tournér de véhicules

Bonjour Kader1 et le forum,

Bonjour Bernard
Merci pour la programmation sous excel
Mais il y a un petit problème:
1°) quelque soit la tournée, le total est toujours 1075 km
2°) pour la tournée commenant par le centre K, ça s'arrête au premier camion avec livraison 14.5 tonnes
Merci

Ton retour me laisse perplexe

Quand je dis facilement à programmer il faut relativiser et l'utilisation du classeur demande une certaine logique :

1- Il est normal que quelque soit la ville de départ on trouve la même distance égale à 1075 kms sinon, cela voudrait dire que le circuit le plus court n'est peut-être pas celui retenu. Le résultat du programme correspond au processus présenté au point trois du post explicatif de la méthode.
Il est possible que la distance et/ou le circuit diffèrent, après modification du distancier bien sûr !

2- Si tu changes le point de départ. Pourquoi pas ! Cependant, cela sous-entend qu'il faut changer les tonnages à livrer car un point de départ ne peut avoir de tonnage à livrer et le point de départ précédent doit lui au contraire recevoir un tonnage.

3- Si l’on veut retirer une destination sans livraison, il faut modifier le distancier tout comme pour en ajouter une nouvelle.

 

[alaoui.]

Re : tournér de véhicules

bonjour chers membres
je suis débutant en excel et j'ai une tournée de ramassage à optimiser est ce vous pouvez m'aider vous touvez les information distancier avec tt ce qui vas avec déjà j'ai fais une essai mais je vous une application qui donne l'ordre de ramassage
BN contrainte de capacité nn posé
un seul camion pour un seul secteur