Discussion :

[Wachter]

Bonjour,

Je souhaite modéliser puis résoudre le problème suivant. Chaque jour, un livreur/facteur part de la ville A, visite un certain nombre de villes, puis revient au point de départ A en fin de journée.

Le facteur reçoit un planning de 40 ou 50 villes à visiter. Il doit effectuer sa tournée en un nombre de jours minimal.

1. Le chemin le plus court entre les 50 villes n'est certainement pas optimal (le temps de calcul sera aussi coûteux), vu que le facteur va visiter une partie de ces villes et doit obligatoirement rentrer à la fin de sa tournée journalière.

2. Classer les villes par îlots (position géographique) et appliquer l'algorithme de résolution sur chaque îlot donnera-t-il la solution optimale ?

Fonction objectif 1 : minimiser la distance du parcours
Fonction objectif 2 : minimiser le nombre de jours de travail

Si vous avez des pistes, je suis preneur !

[CliffeCSTL]

Ce problème n'est pas le voyageur de commerce

Il faut définir un ordre de priorité. Quelle est la meilleure solution pour toi :

- 10 jours, 500 km
- 11 jours, 450 km

[DonQuiche]

Ce problème est en fait celui des tournées de véhicule (le voyageur de commerce est un cas particulier de ce problème).

Wikipédia formalise ce problème, en présente les nombreuses variantes, propose des approches algorithmique et fournit des liens vers des bibliothèques libres.

[Wachter]

Ce problème n'est pas le voyageur de commerce

Il faut définir un ordre de priorité. Quelle est la meilleure solution pour toi :

- 10 jours, 500 km
- 11 jours, 450 km

Pour moi, il s'agit d'une variante du voyageur de commerce. Je n'ai pas de priorités à définir : simplement faire des tournées en réduisant le nombre de jours (1 jour = 7 h).

Ce problème est en fait celui des tournées de véhicule (le voyageur de commerce est un cas particulier de ce problème).

Wikipédia formalise ce problème, en présente les nombreuses variantes, propose des approches algorithmique et fournit des liens vers des bibliothèques libres.

Je ne trouve pas ce que je cherche sur cette page. Le problème des tournées de véhicules traitent le cas de plusieurs véhicules à disposition ; dans mon cas, je dispose qu'un seul véhicule. Je dois simplement trouver un ensemble de villes à visiter (+ le trajet le plus court) chaque jour tout en réduisant la durée de travail.

[CliffeCSTL]

Je n'ai pas de priorités à définir : simplement faire des tournées en réduisant le nombre de jours (1 jour = 7 h).

Je dois simplement trouver un ensemble de villes à visiter (+ le trajet le plus court) chaque jour tout en réduisant la durée de travail.

Tu te contredis ...

Tu souhaite donc trouver l'ensemble des solutions qui minimisent le nombre de jours et parmi celles-ci les solutions qui minimisent la durée total de trajet.

[Wachter]

Je ne sais pas si je me contredis. En d'autres termes, le problème consiste à visiter toutes les villes en un temps minimum exprimé en jours.

[DonQuiche]

Le problème des tournées de véhicules traitent le cas de plusieurs véhicules à disposition ; dans mon cas, je dispose qu'un seul véhicule. Je dois simplement trouver un ensemble de villes à visiter (+ le trajet le plus court) chaque jour tout en réduisant la durée de travail.

Le problème ne précise pas si les trajets sont faits simultanément le même jour ou un jour après l'autre. Il te donne simplement N trajets pour parcourir l'ensemble des villes à parcourir.

[tbc92]

Pour moi, il s'agit d'une variante du voyageur de commerce. Je n'ai pas de priorités à définir : simplement faire des tournées en réduisant le nombre de jours (1 jour = 7 h).


Je ne trouve pas ce que je cherche sur cette page. Le problème des tournées de véhicules traitent le cas de plusieurs véhicules à disposition ; dans mon cas, je dispose qu'un seul véhicule. Je dois simplement trouver un ensemble de villes à visiter (+ le trajet le plus court) chaque jour tout en réduisant la durée de travail.

D'autres te l'ont dit, mais je répète : le problème est le même. Qu'il y ait 1 jour et plusieurs véhicules, ou 1 véhicule et plusieurs jours, ça ne change rien.