Voyageur de commerce avec deux fonctions objectif

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 !

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

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

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

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.

Citation:

---

Envoyé par CliffeCSTL

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

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).

Citation:

---

Envoyé par 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.

---

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.

Citation:

---

Envoyé par Wachter

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).

---

Citation:

---

Envoyé par Wachter

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.

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.

Très bien, il ne te reste plus qu'à modéliser sous forme de programme linéaire en nombre entier 8-)

C'est là que tu bloques ?

Voilà comment je modéliserai le problème :

Données :
- Soit le graphe orienté et pondéré https://latex.codecogs.com/gif.latex?G%3D%28V%2CE%29 où https://latex.codecogs.com/gif.latex...C%20%5Ccup%20D est l'ensemble des sommets représentant les villes, avec https://latex.codecogs.com/gif.latex...right%20%5C%7D respectivement les villes de départ et d'arrivée, et https://latex.codecogs.com/gif.latex?C l'ensemble des villes à visiter. https://latex.codecogs.com/gif.latex?E représente l'ensemble des arcs tel que https://latex.codecogs.com/gif.latex...e%20j%20%5C%7D. On pose alors https://latex.codecogs.com/gif.latex...%5Cright%20%7C.
- On note https://latex.codecogs.com/gif.latex?d_%7Bij%7D la distance entre deux villes https://latex.codecogs.com/gif.latex...0%5Cin%20V%5E2.
- On note https://latex.codecogs.com/gif.latex?%5Clambda la durée maximale d'une tournée. On suppose alors que https://latex.codecogs.com/gif.latex...le%20%5Clambda.

Variables de décisions :
- La variable binaire https://latex.codecogs.com/gif.latex?y_t pour https://latex.codecogs.com/gif.latex?t%3D1..n vaut 1 si une tournée existe le jour https://latex.codecogs.com/gif.latex?t, 0 sinon.
- La variable binaire https://latex.codecogs.com/gif.latex?x_%7Bij%7D%5Et pour https://latex.codecogs.com/gif.latex?t%3D1..n, https://latex.codecogs.com/gif.latex...29%20%5Cin%20E, vaut 1 si l'arc https://latex.codecogs.com/gif.latex...%5Cright%20%29 est utilisé le jour https://latex.codecogs.com/gif.latex?t.

Programme linéaire en nombre entier :

Fonction objectif : on minimise le nombre de jours consommés :

https://latex.codecogs.com/gif.latex..._{t=1}^{n} y_t

On s'assure que toutes les villes sont visitées exactement une fois :

https://latex.codecogs.com/gif.latex...0j%20%5Cin%20C

Contrainte de connectivité :

https://latex.codecogs.com/gif.latex...t%20%3D%201..n

Contrainte sur l'utilisation des jours :

https://latex.codecogs.com/gif.latex...t%20%3D%201..n

Respect de la contrainte de durée pour chaque tournée :

https://latex.codecogs.com/gif.latex...D%201%20..%20n

On s'assure que les variables sont bien entières :

https://latex.codecogs.com/gif.latex...0%3D%201%20..n

https://latex.codecogs.com/gif.latex...0%3D%201%20..n

N'hésitez pas à me corriger si il y a des erreurs.

Citation:

---

Envoyé par Wachter

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.

Citation:

---

Envoyé par Wachter

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.

Citation:

---

Envoyé par CliffeCSTL

N'hésitez pas à me corriger si il y a des erreurs.

---

A priori, il manque une élimination de sous-tours, sinon ta tournée pourrait être composée de sous-tours disjoints (deuxième figure de http://www.math.uwaterloo.ca/tsp/met...pt/subtour.htm). Pas à implémenter naïvement pour que ça marche en pratique niveau performance.

Citation:

---

Envoyé par dourouc05

A priori, il manque une élimination de sous-tours, sinon ta tournée pourrait être composée de sous-tours disjoints (deuxième figure de http://www.math.uwaterloo.ca/tsp/met...pt/subtour.htm). Pas à implémenter naïvement pour que ça marche en pratique niveau performance.

---

Exact, bien vu :

https://latex.codecogs.com/gif.latex...t%20%3D%201..n

Merci beaucoup pour vos contributions. :zoubi:

Je reviendrai vers vous dès que j'aurai fini d'analyser les solutions proposées.

Bonjour,

Tu peux t'inspirer de la discution sur ce sous-forums : " Voyageur de commerce avec horaires d'ouvertures"