Voyageur de commerce avec deux fonctions objectif

**Wachter** · 05/02/2016, 15h12

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** · 05/02/2016, 19h22

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** · 05/02/2016, 20h52

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** · 05/02/2016, 21h55

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

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

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.

**CliffeCSTL** · 06/02/2016, 04h46

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

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.

**Wachter** · 06/02/2016, 05h01

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.

**CliffeCSTL** · 06/02/2016, 11h40

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

C'est là que tu bloques ?

**CliffeCSTL** · 06/02/2016, 12h16

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

Données :
- Soit le graphe orienté et pondéré $G=(V,E)$ où $V = C \cup D$ est l'ensemble des sommets représentant les villes, avec $D = \left \{ d_e, d_s \right \}$ respectivement les villes de départ et d'arrivée, et $C$ l'ensemble des villes à visiter. $E$ représente l'ensemble des arcs tel que $E=\left \{ \left ( i,j \right ) \right | i \in C \cup \left \{ d_e \right \}, j \in C \cup \left \{ d_s \right \}, i \ne j \}$ . On pose alors $n = \left | V \right |$ .
- On note $d_{ij}$ la distance entre deux villes $\left ( i,j \right ) \in V^2$ .
- On note $\lambda$ la durée maximale d'une tournée. On suppose alors que $\forall i \in C, d_{d_ei}+d_{id_s}\le \lambda$ .

Variables de décisions :
- La variable binaire $y_t$ pour $t=1..n$ vaut 1 si une tournée existe le jour $t$ , 0 sinon.
- La variable binaire $x_{ij}^t$ pour $t=1..n$ , $\left ( i,j \right ) \in E$ , vaut 1 si l'arc $\left ( i,j \right )$ est utilisé le jour $t$ .

Programme linéaire en nombre entier :

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

$min \sum_{t=1}^{n} y_t$

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

$\sum_{i \in C \cup d_e} \sum_{t=1}^{n} x_{ij}^t = 1 \ \ \ \ \forall j \in C$

Contrainte de connectivité :

$\sum_{j \in C \cup d_e} x_{ji}^t = \sum_{j \in C \cup d_s} x_{ij}^t \ \ \ \ \forall i \in C \ \ \ \ \forall t = 1..n$

Contrainte sur l'utilisation des jours :

$y_t \ge \sum_{\left ( i,j \right ) \in E} x_{ij}^t \ \ \ \ \forall t = 1..n$

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

$\sum_{\left ( i,j \right ) \in E} d_{ij} x_{ji}^t \le \lambda \ \ \ \ \forall t = 1 .. n$

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

$x_{ij}^t \in \left \{ 0,1 \right \} \ \ \ \ \forall (i,j) \in E, \ \ \ \ \forall t = 1 ..n$

$y_t \in \left \{ 0,1 \right \} \ \ \ \ \forall t = 1 ..n$

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

**DonQuiche** · 06/02/2016, 13h25

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.

**tbc92** · 06/02/2016, 13h36

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.

**dourouc05** · 07/02/2016, 22h21

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.

**CliffeCSTL** · 07/02/2016, 23h23

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 :

$\sum_{i \in S} \sum_{j \in V \setminus S} x_{ij}^t = 2 y_t \ \ \ \ \forall S \subseteq C, S \ne \emptyset, \ \ \ \ \forall t = 1..n$