Discussion :

[laureat]

Bonjour,

J'espère que je poste dans la bonne rubrique. Dites-moi si je me trompe.

Je mène un projet sur le problème de tournées de véhicules avec ramassage et livraison (en anglais VRP with pick-up and delivery). Ce problème consiste à ramasser chez un ensemble d'expéditeur les produits et ensuite les transporter à fur et à mesure à un ensemble des clients.
L'objectif est de développer un outil d'aide à la décision qui permet de gérer en temps réel les tournées de véhicules en présence d'un évenement imprévu qui est le vol des produits.
La première tache consiste à proposer une formulation mathématique du problème. En deuxième lieu, c'est la résolution du problème par une métaheuristique ou une heuristique.
L'algorithme développé sera implémenté dans le serveur de l'entreprise du transport et l'ordinateur au bord du camion va afficher le nouveau itinéraire au chauffeur.

Pour l'instant, je fais que des lectures (ça fait deux mois d'ailleurs) et je n'ai pas tombé sur un article scientifique qui traite ce type du problème.

Je suis vraiment perdu.
Là, çe me reste que 4 mois pour le finaliser.

J'aimerais savoir quels sont les type de travaux de recherche surlesquels je peux m'appuyer. J'ai fait des recherches sur google en tapant des mots clés comme vol+ gestion tournée de véhicule; vol des produits+ gestion de en temps réel de tournées de véhicules; mais toujours je n'ai rien trouvé.
Il y a que des travaux qui traitent le problème du panne de camion, congestion.
Pourriez-vous m'aider à trouver des travaux qui porte sur mon sujet ou au moins dont je peux m'inspirer.

Par ailleurs, à votre avis quelle sera le fonction objectif dans ce cas?Quelle stratégie peut-on adopter pour résoudre le problème de re-routage du camion dans le cas où il y a un vol des produits du camion au moment de chargement chez l'expéditeur ou de déchargement chez le client?

J'espère que j'ai bien m'expliqué mon problème et que vous pourrez m'aider.

Merci d'avance de votre aide.

[seeme]

Bonjour!

Je pense qu'il faut d'abord laisser de côté l'aspect vol. Essaye de représenter le problème simplement. Si c'est simplement aller chercher des objets et les livrer, ça existe déjà, et ça se règle bien avec une meta heuristique.

Ensuite, je pense qu'il faut que tu définisses plus clairement le vol. Que se passe-t-il quand on vole de la marchandise? Le camion va au dépot? Il retourne chez le client?

Il faut absolument que tu formalises ton problème.

Je te donne une piste (après, il y a plusieurs approches possibles). Mais on peut dire que tu as une liste de clients qui sont en attente d'expédition ou de livraison. Ces clients sont séparés les uns des autres par une distance. Il faudrait aussi prendre en compte depuis combien de temps attend un client pour la levée/livraison. Il faut aussi réfléchir à la capacité du camion, au nombre d'heures du chauffeur avant un retour au dépot, compien de km il peut faire...

Pour le vol, ça dépend.. est-ce que tous les chemins se valent sur ce critère? Que se passe-t-il si on vole le camion?

Bref, tout ça pour dire qu'il manque plein d'info. Il faut absolument que tu listes de quoi tu as besoin, ce qui t'interesse. Une fois celà fait, réfléchis à ce qui a le plus d'importance, et aux relations entre tes informations (on va accepter de faire plus de km pour servir un client qui attend depuis longtemps, mais au passage, on peut peut-être ramasser quelques colis).

Après, mise en équation, définition de la fonction objectif, analyse mathématique. Et finalement, il faudra réfléchir à ce que tu veux (tu veux LA solution optimale, une solution, un ensemble de solution, si le chauffeur ne respecte pas le planning, que fais-tu...)

[laureat]

Bonjour,

Merci beaucoup seeme pour votre réponse.

En fait, le voulais résoudre le problème par une méthode exacte (programmation linéaire). Le problème ne tient pas compte de nombre d'heure de chauffeur. Les contraintes seront alors: capacité de véhicules et date de passage de camion et retour au dépot à la fin de la tournée.

S'il y a un vol de marchandises, j'ai pensé que le camion continue à servir les clients non encore servis existés dans sa tournée et envoyer un nouveau camion pour récupérer les marchandises du client dont les marchandises ont été volé au cours du transport et le livrer au client correspondant de façon à minimiser le temps total de voyage et le cout d'annulation de servir les clients dont les marchandises ont été volés.

Qu'en pensez-vous de cette piste?
Je me bloque au niveau de la modélisation (Quelles sont les variables de décisions? ). Bon on a un ensemble des noueds qui correspondent à des noeuds de enlévement ou de livraison, capacité des camions, ensemble des camions dans le dépot, les dates de passage à chaque noeud. Mais comment définir la stratégie adoptée?
J'attends votre réponse.
Merci encore.

[seeme]

Le problème de livraison est un cas d'école de la recherche opérationel, ça peut se résoudre à la main (avec un simplex si je me trompe pas).

Ce qu'il faut bien comprendre, c'est qu'une méthode déterministe va très vite bloquer... (bon c'est sûr, si il y a 3 clients et 2 camions, ça va aller...)

Si on liste ce dont tu as besoin:
* Distance (ou coût) pour aller d'un entrepôt i à un client j
* La capacité d'un camion
* Les entrepots en attente de levée
* Depuis combien de temps un client attend sa ou ses livraisons (c'est une idée, il y a d'autres moyens de le modéliser)

Une fonction objectif serait celle qui permettrait de minimiser la distance parcourue, le nombre de fois où le camion passe à l'entrepôt, et le temps d'attente des clients.

Une fois que tu arrives à représenter ça le plus simplement possible (vecteurs booléens, matrices triangulaires...) tu pourras chercher à trouver une fonction de calcul (tu peux aussi mettre en avant certains critères en les pondérant).

Si déjà tu arrives à faire ça, tu pourras t'intéresser au vol


Personnelement, je verrait bien un tabou ou un génétique.. mais bon...

[laureat]

Merci beaucoup seeme de votre réponse.

En fait, mon tuteur voulait modéliser le problème en un programme linéaire et le tester sur une instance réduite (10 clients, 2 camions).

[quoteUne fonction objectif serait celle qui permettrait de minimiser la distance parcourue][/quote]
Critèe classique

le nombre de fois où le camion passe à l'entrepôt

ça je n'ai pas compris.

le temps d'attente des clients.

ça c'est intéressant. Ca serait le temps d'arrivée chez le client moins le temps de début de service?

Merci de votre réponse

[seeme]

Pour le nombre d'aller retour du camion, c'est si le nombre de colis a livrer est superieur a la capacite du camion.

[laureat]

Bonjour,

Merci seeme de ta réponse.

J'ai modélisé le problème statique mais comment le modéfier ou le mettre à jour pour tenir compte de l'évenement de vol des produits au cours du transport?

[Acrim]

Je ne suis pas sur de comprendre vraiment ta question mais voici des pistes :

- Quel est la "réaction" attendu par rapport au vol ? Faut il les prévoir et générer les tournées les plus robustes ?

- Faut il s'adapter pour prendre en compte le vol ?

S'il s'agit "juste" d'adapter la tournée, ne suffirait il pas de faire retourner ton algo pour régénérer des nouvelles tournées (en ayant pris soin de fixer les parties déjà réalisées)

Par rapport aux mots clés (du cote de la programmation par contraintes puisque c'est plus mon domaine) :
- algorithme robuste (si il s'agit de générer des tournées résistantes)
- algorithme stochastique (si il s'agit de prendre en compte les stat. sur les vols)
- TSPPD (TSP with Pickup and Delivery)
- Dynamic CSP

[laureat]

Je ne suis pas sur de comprendre vraiment ta question mais voici des pistes :

- Quel est la "réaction" attendu par rapport au vol ? Faut il les prévoir et générer les tournées les plus robustes ?

- Faut il s'adapter pour prendre en compte le vol ?

S'il s'agit "juste" d'adapter la tournée, ne suffirait il pas de faire retourner ton algo pour régénérer des nouvelles tournées (en ayant pris soin de fixer les parties déjà réalisées)

Merci Acrim de ta réponse.
Oui ça c'est la stratégie "naive" .
En fait, je cherche à développer un modèle qui permet de tenir compte de l'évènement vol dans un temps plus court. Je pense utiliser le modèle de type partitionement ou multi-flots qui permet de générer tous les solutions possibles et de bien définir les ensembles ensuite de le résoudre par méthode génération de colone.Qu'en pensez-vous?

[Acrim]

D'accord, alors dans ce cas tu peux chercher du cote des "online algorithms" (et OLTSP : Online Traveling Salesman Problem).

Pour ce que j'en sais plusieurs stratégies sont utilisées : prècalculer les solutions (si il y a peu de possibilité), précalculer en limitant les possibilités (nombre de perturbations max par rapport a la solution initiale, stat. sur les perturbations passées). Quand ce n'est pas possible on peut aussi essayer de "réparer" la solution initiale (recherche locale, en fixant des parties de la solution et en relaxant les parties modifiées etc).

Est ce que la solution que tu proposes est la bonne ? Je ne sais pas mais je peux au moins te donner des pistes. Mais comme te l'a dit seeme, il faut que tu aies déjà une bonne idée du cas "normal" avant de te savoir quel sera la meilleure stratégie pour gérer le cas avec vol.

[laureat]

Est ce que la solution que tu proposes est la bonne ? Je ne sais pas mais je peux au moins te donner des pistes. Mais comme te l'a dit seeme, il faut que tu aies déjà une bonne idée du cas "normal" avant de te savoir quel sera la meilleure stratégie pour gérer le cas avec vol.

Oui je cherche à modéliser le problème pour implémenter dans un solveur commercial afin de déterminer la solution optimale en évitant la méthode ré-optimisation(c à d recalculer la nouvelle solution optimale en éliminant les clients déjà servis dans la tournée).

Une autre question, comment pense-tu intégrer la contrainte de rangement des produits dans le camion (elle signifie dernier produit ramassé premier livré
)?
J'attends ta réponse. Merci d'avance.

[Acrim]

Une autre question, comment pense-tu intégrer la contrainte de rangement des produits dans le camion (elle signifie dernier produit ramassé premier livré
)?
J'attends ta réponse. Merci d'avance.

Si tu fais du Pickup and Delivery tu devrais avoir des contraintes de précédences dans ton modèle. Donc éventuellement, les modifier pour prendre en compte l'ordre de visite des sites (mais bon ça t'oblige a dev ta propre contrainte). Sinon faut voir avec les contraintes dispo. dans ton solveur.

[laureat]

Si tu fais du Pickup and Delivery tu devrais avoir des contraintes de précédences dans ton modèle. Donc éventuellement, les modifier pour prendre en compte l'ordre de visite des sites (mais bon ça t'oblige a dev ta propre contrainte). Sinon faut voir avec les contraintes dispo. dans ton solveur.

J'ai modélisé la contraine de précédence comme suit:
Ti+pi+ ti,n+i<= Tn+i.
avec
i+n: le noeud de déchragement,
i= le noeud de chargement,
pi: le temps de service au noeud i
Ti+1: la date à laquelle le service sur le noeud i+1 commence.

Comment est ce que j'intégre le rangement des produits dans le camion?
Merci!