Maxime Chassaing

News instances :

LIMOS, UMR CNRS 6158 (Campus des Cézeaux, 63177 Aubière Cedex, France)

Sommaire :

DARP Instances Real Life

Auteurs:

	Maxime Chassaing maxime.chassaing [@] isima.fr	Laboratoire : LIMOS, UMR CNRS 6158 Campus des Cézeaux 63177 Aubière Cedex (France)
	Christophe Duhamel
	Philippe Lacomme
	Christian Laforest

Abstract

Nous proposons ici de télécharger des instances ultra-réalistes du DARP basées sur les positions GPS des villes Françaises. Elles respectent la définition du DARP proposée par Cordeau et Laporte 2003 [1] à deux exceptions :
1- la charge d’un client peut être supérieure à 1 (elle est comprise entre 1 et 4);
2- le temps maximum de transport d’un client varie en fonction des clients et de la distance que celui-ci veut parcourir
Enfin, dans cette page vous trouverez toutes les explications nécessaires pour manipuler ces instances ainsi que quelques outils pour la manipulation et pour l’affichage des solutions.

Download the DARP instances

small instances	medium instances	big instances	nightmare instances	All instances
Instance.zip	Instance.zip	Instance.zip	Instance.zip	instance.zip
solutionsR.zip	solutionsR.zip	solutionsR.zip	solutionsR.zip	solutionsR.zip
solutionsC.zip	solutionsC.zip	solutionsC.zip	solutionsC.zip	solutionsC.zip
solutionsF.zip	solutionsF.zip	solutionsF.zip	solutionsF.zip	solutionsF.zip
GPS_coordinate.zip	GPS_coordinate.zip	GPS_coordinate.zip	GPS_coordinate.zip	GPS_coordinate.zip

Les instances

Les instances sont très proches des instances classiques du DARP proposées par Cordeau et Laporte 2003 ou encore par Ropke et al 2007. Les principales caractéristiques sont les suivantes :

Les sommets ne sont plus repérés par des positions X et Y mais directement par les distances qui les séparent
Les clients sont répartis sur une superficie importante variant selon les instances, dépendant de la superficie des départements. Cette superficie varie de 100km² à plus de 8500 km².
Au véhicule est associé une vitesse moyenne que l'on suppose constante et d'environ 80km/h soit 1.33km/min.
Les distances séparant les différents sommets ne sont plus Géométriques mais se sont les distances réels (en mètre) parcourut par un véhicule pour rejoindre 2 villes. Plus de détails sur le calcul de ces distances sont disponibles à cette adresse : lien.
L’inégalité triangulaire n’est donc plus respectée.
Des fenêtres de temps .sont fixées à la fois sur le sommet de ramassage et sur celui de destination. Ces fenêtres de temps sont de tailles variantes selon les clients. Le temps de transport maximum (the maximum riding time) de chaque client dépend du client et de la distance qu’il a à parcourir.

Tableau 1 : détails sur les différentes instances.

post code	district name	Real Life Instances	N	M max	M used	BFS	res F	res R	res C	GPS coordinates client list
01000	Ain	RL_d01.txt	46	7	7	2396.55	DL	DL	DL	GPS_coordinates
02000	Aisne	RL_d02.txt	90	13	13	4025.16	DL	DL	DL	GPS_coordinates
03000	Allier	RL_d03.txt	62	10	8	3185.61	DL	DL	DL	GPS_coordinates
04000	Alpes de Haute Provence	RL_d04.txt	91	16	15	5972.08	DL	DL	DL	GPS_coordinates
05000	Hautes Alpes	RL_d05.txt	58	9	9	3393.09	DL	DL	DL	GPS_coordinates
06000	Alpes Maritimes	RL_d06.txt	60	10	10	3412.34	DL	DL	DL	GPS_coordinates
07000	Ardeche	RL_d07.txt	54	8	8	3082.8	DL	DL	DL	GPS_coordinates
08000	Ardennes	RL_d08.txt	42	7	7	1857.35	DL	DL	DL	GPS_coordinates
09000	Ariege	RL_d09.txt	83	12	11	3827.63	DL	DL	DL	GPS_coordinates
10000	Aube	RL_d10.txt	34	4	4	1341.02	DL	DL	DL	GPS_coordinates
11000	Aude	RL_d11.txt	47	7	6	2538.18	DL	DL	DL	GPS_coordinates
12000	Aveyron	RL_d12.txt	56	9	8	3614.27	DL	DL	DL	GPS_coordinates
13000	Bouches du Rhone	RL_d13.txt	59	9	8	3183.19	DL	DL	DL	GPS_coordinates
14000	Calvados	RL_d14.txt	88	12	13	3710.25	DL	DL	DL	GPS_coordinates
15000	Cantal	RL_d15.txt	94	14	14	5230.88	DL	DL	DL	GPS_coordinates
16000	Charentes	RL_d16.txt	64	10	9	2709.25	DL	DL	DL	GPS_coordinates
17000	Charentes Maritimes	RL_d17.txt	52	8	7	2861.93	DL	DL	DL	GPS_coordinates
18000	Cher	RL_d18.txt	128	20	16	6341.11	DL	DL	DL	GPS_coordinates
19000	Corrrèze	RL_d19.txt	112	15	14	5561.84	DL	DL	DL	GPS_coordinates
20000	Corse du Sud	RL_d20.txt	56	9	9	3567.32	DL	DL	DL	GPS_coordinates
21000	Cote d'Or	RL_d21.txt	63	9	9	3218.85	DL	DL	DL	GPS_coordinates
22000	Cote d'Armor	RL_d22.txt	119	18	16	6153.15	DL	DL	DL	GPS_coordinates
23000	Creuse	RL_d23.txt	101	13	14	4816.45	DL	DL	DL	GPS_coordinates
24000	Dordogne	RL_d24.txt	81	13	11	4643.65	DL	DL	DL	GPS_coordinates
25000	Doubs	RL_d25.txt	71	11	10	3693.55	DL	DL	DL	GPS_coordinates
26000	Drome	RL_d26.txt	63	9	7	2880.21	DL	DL	DL	GPS_coordinates
27000	Eure	RL_d27.txt	110	14	11	4664.12	DL	DL	DL	GPS_coordinates
28000	Eure et Loir	RL_d28.txt	70	10	8	3137.18	DL	DL	DL	GPS_coordinates
29000	Finistere	RL_d29.txt	82	13	12	4705.89	DL	DL	DL	GPS_coordinates
30000	Gard	RL_d30.txt	56	8	8	2678.58	DL	DL	DL	GPS_coordinates
31000	Haute Garonne	RL_d31.txt	65	9	8	3112.39	DL	DL	DL	GPS_coordinates
32000	Gers	RL_d32.txt	122	17	16	5824.23	DL	DL	DL	GPS_coordinates
33000	Gironde	RL_d33.txt	94	15	12	4880.13	DL	DL	DL	GPS_coordinates
34000	Herault	RL_d34.txt	68	11	10	3066.26	DL	DL	DL	GPS_coordinates
35000	Ille et Vilaine	RL_d35.txt	84	13	12	4142.25	DL	DL	DL	GPS_coordinates
36000	Indre	RL_d36.txt	42	6	6	2139.52	DL	DL	DL	GPS_coordinates
37000	Indre et Loire	RL_d37.txt	80	10	10	4164.12	DL	DL	DL	GPS_coordinates
38000	Isere	RL_d38.txt	102	16	14	5439.44	DL	DL	DL	GPS_coordinates
39000	Jura	RL_d39.txt	38	6	6	2030.44	DL	DL	DL	GPS_coordinates
40000	Landes	RL_d40.txt	66	10	9	3815.96	DL	DL	DL	GPS_coordinates
41000	Loir et Cher	RL_d41.txt	67	9	9	3198.74	DL	DL	DL	GPS_coordinates
42000	Loire	RL_d42.txt	89	13	11	4351.21	DL	DL	DL	GPS_coordinates
43000	Haute Loire	RL_d43.txt	43	6	6	2002.15	DL	DL	DL	GPS_coordinates
44000	Loire Atlantique	RL_d44.txt	86	11	11	4240.85	DL	DL	DL	GPS_coordinates
45000	Loiret	RL_d45.txt	85	12	11	4057.07	DL	DL	DL	GPS_coordinates
46000	Lot	RL_d46.txt	125	20	16	5637.37	DL	DL	DL	GPS_coordinates
47000	Lot et Garonne	RL_d47.txt	55	7	7	2636.07	DL	DL	DL	GPS_coordinates
48000	Lozere	RL_d48.txt	55	8	8	3083.19	DL	DL	DL	GPS_coordinates
49000	Maine et Loire	RL_d49.txt	123	18	16	5450.74	DL	DL	DL	GPS_coordinates
50000	Manche	RL_d50.txt	93	12	12	4650.02	DL	DL	DL	GPS_coordinates
51000	Marne	RL_d51.txt	64	10	9	3035.71	DL	DL	DL	GPS_coordinates
52000	Haute Marne	RL_d52.txt	29	4	4	1607.74	DL	DL	DL	GPS_coordinates
53000	Mayenne	RL_d53.txt	57	7	6	2484.6	DL	DL	DL	GPS_coordinates
54000	Meurthe et Mozelle	RL_d54.txt	86	15	12	3826.1	DL	DL	DL	GPS_coordinates
55000	Meuse	RL_d55.txt	28	5	4	1516.7	DL	DL	DL	GPS_coordinates
56000	Morbihan	RL_d56.txt	76	13	12	4287.3	DL	DL	DL	GPS_coordinates
57000	Moselle	RL_d57.txt	81	12	10	3758.09	DL	DL	DL	GPS_coordinates
58000	Nievre	RL_d58.txt	110	16	14	5127.06	DL	DL	DL	GPS_coordinates
59000	Nord	RL_d59.txt	96	13	13	5383.8	DL	DL	DL	GPS_coordinates
60000	Oise	RL_d60.txt	68	9	8	2816.27	DL	DL	DL	GPS_coordinates
61000	Orne	RL_d61.txt	55	8	8	2855.09	DL	DL	DL	GPS_coordinates
62000	Pas de Calais	RL_d62.txt	112	17	14	4458.1	DL	DL	DL	GPS_coordinates
63000	Puy de Dome	RL_d63.txt	87	12	11	3719.97	DL	DL	DL	GPS_coordinates
64000	Pyrennees Atlantiques	RL_d64.txt	80	12	11	4971.05	DL	DL	DL	GPS_coordinates
65000	Hautes Pyrennees	RL_d65.txt	111	15	13	4431.84	DL	DL	DL	GPS_coordinates
66000	Pyrennees Orientales	RL_d66.txt	75	11	11	3350.45	DL	DL	DL	GPS_coordinates
67000	Bas Rhin	RL_d67.txt	86	11	10	3615.08	DL	DL	DL	GPS_coordinates
68000	Haut Rhin	RL_d68.txt	62	10	8	2606.51	DL	DL	DL	GPS_coordinates
69000	Rhone	RL_d69.txt	76	10	9	2691.37	DL	DL	DL	GPS_coordinates
70000	Haute Saone	RL_d70.txt	39	6	6	2006.05	DL	DL	DL	GPS_coordinates
71000	Saone et Loire	RL_d71.txt	93	14	13	4820.43	DL	DL	DL	GPS_coordinates
72000	Sarthe	RL_d72.txt	93	13	12	3978.86	DL	DL	DL	GPS_coordinates
73000	Savoie	RL_d73.txt	68	10	10	4278.51	DL	DL	DL	GPS_coordinates
74000	Haute Savoie	RL_d74.txt	62	10	9	3335.58	DL	DL	DL	GPS_coordinates
75000	Paris	RL_d75.txt	10	2	2	150.91	DL	DL	DL	GPS_coordinates
76000	Seine Maritime	RL_d76.txt	76	11	9	3467.29	DL	DL	DL	GPS_coordinates
77000	Seine et Marne	RL_d77.txt	95	13	12	4099.4	DL	DL	DL	GPS_coordinates
78000	Yvelines	RL_d78.txt	95	13	12	2924.3	DL	DL	DL	GPS_coordinates
79000	Deux Sevres	RL_d79.txt	73	11	11	3206.91	DL	DL	DL	GPS_coordinates
80000	Somme	RL_d80.txt	85	11	11	4057.1	DL	DL	DL	GPS_coordinates
81000	Tarn	RL_d81.txt	53	7	7	2456.13	DL	DL	DL	GPS_coordinates
82000	Tarn et Garonne	RL_d82.txt	39	6	6	1842.84	DL	DL	DL	GPS_coordinates
83000	Var	RL_d83.txt	62	9	9	3275.42	DL	DL	DL	GPS_coordinates
84000	Vaucluse	RL_d84.txt	52	8	6	2368.34	DL	DL	DL	GPS_coordinates
85000	Vendee	RL_d85.txt	73	12	11	3785.93	DL	DL	DL	GPS_coordinates
86000	Vienne	RL_d86.txt	76	11	11	3624.95	DL	DL	DL	GPS_coordinates
87000	Haute Vienne	RL_d87.txt	54	8	7	2714.31	DL	DL	DL	GPS_coordinates
88000	Vosges	RL_d88.txt	63	10	9	3476.11	DL	DL	DL	GPS_coordinates
89000	Yonne	RL_d89.txt	67	10	10	3583.62	DL	DL	DL	GPS_coordinates
90000	Territoire de Belfort	RL_d90.txt	51	6	6	1133.45	DL	DL	DL	GPS_coordinates
91000	Essonne	RL_d91.txt	98	13	11	2846.48	DL	DL	DL	GPS_coordinates
92000	Haut de Seine	RL_d92.txt	17	2	2	347.01	DL	DL	DL	GPS_coordinates
93000	Seine Saint Denis	RL_d93.txt	19	3	2	418.76	DL	DL	DL	GPS_coordinates
94000	Val de Marne	RL_d94.txt	23	2	2	352.25	DL	DL	DL	GPS_coordinates
95000	Val d'Oise	RL_d95.txt	91	10	9	2453.72	DL	DL	DL	GPS_coordinates
20000	Haute Corse	RL_d96.txt	53	11	10	3593.6	DL	DL	DL	GPS_coordinates

Construction des instances

Dans le but d'obtenir des instances le plus proche possible de la réalité, la construction de ces instances repose sur plusieurs lois biaisées :

Concernant les tailles des trajets demandés par les clients
La position des fenêtres de temps
La taille des fenêtres de temps
Les contraintes de temps de transports maximums imposés aux clients

Lecture des instances

Une instance se découpe en 3 parties :

1 - Les données du problème

Cette partie concerne les données du problème et regroupe dans l’ordre :

m : le nombre de véhicule ;
2*n : 2* le nombre de clients, ce qui représente le nombre de sommets dans le graphe (sans compter le dépôt) ;
TRT : le temps maximum de trajet pour un véhicule (i.e. 8h de travail maximum pour un chauffeur soit 480 minutes) ;
C: la capacité maximale d’un véhicule ;
V: la vitesse en km/minute du véhicule.

Exemple : Partie 1

**************************************DATA
12 92 480 8 1.33

2 - La matrice des distances

Cette matrice carré est de taille (N+1)*(N+1).
La première ligne représente la distance en partant du sommet choisi pour être le dépôt vers les n autres sommets.
La valeur en position i,j correspond à la distance en mètre séparant le ième sommet et le jème.
Les valeurs sur la diagonale sont égales à 0.

ATTENTION : le même nœud peut être utilisé plusieurs fois, donc des distances de valeurs zéros peuvent apparaître.

Exemple : Partie 2

**************************************DISTANCE
0 64916 139561 1213 182080 ...
64916 0 115682 64384 157086 ...
139561 115682 0 140773 25871 ...
1213 64384 140773 0 183328 ...
182080 157086 25871 183328 0 ...
...
...
...

Matrice des distances réels en mètre parcourut par un véhicule entre deux sommets, avec en ligne le sommet d’origine et en colonne la destination.
Cette matrice est symétrique.

3 - Les données sur les clients

Dans cette 3ème partie sont regroupées les informations sur les clients.
Qui se compose dans l’ordre :

i : le numéro du véhicule ;
s[i] : le temps de chargement au sommet i.
c[i] : Le nombre de client à prendre(+) ou déposer(-) au sommet i ;
e[i] l[i] : les dates minimales et maximales pour traiter le sommet i (fenêtres de temps) ;
L[i] : la durée maximale pour effectuer le transport associées au client i.

La première ligne concerne le point 0, qui est le dépôt. Il a pour fenêtre de temps [0;1440] ce qui correspond à une journée de 24h (=1440min).
Les sommets numérotés de 1 à n suivantes sont les sommets de ramassages associés aux n clients.
Et les sommets numérotés de n+1 à 2*n suivants sont les sommets de destinations associés aux n clients.

Exemple : Partie 3

**************************************TimeWindows
0 0 0 0 1440 480
1 3 3 480 720 124
2 1 1 480 720 61
3 1 1 480 720 71
...
...
...
47 3 -3 605 785 124
48 1 -1 556 736 61
49 1 -1 533 773 71
...

Lecture des solutions

Dans ces pages vous trouverez 3 différentes formes de solutions.

1- Solutions réduites : forme simple

La première ligne donne le nombre de véhicules utilisés. La seconde, le nombre x de sommets dans le 1er véhicule, la suivante liste les x sommets dans l’ordre de traitement par le véhicule.

**************************************
2
16
0 10 3 20 1 13 2 11 4 14 6 12 16 7 17 21
8
0 5 8 15 18 9 19 21

2- Solutions traditionnelles :

Ces solutions sont construites sous la même forme que les solutions disponibles sur internet Pour les précédentes instances de la littérature. Ainsi les personnes ayant l’habitude de cette forme ou ayant déjà développé des fonctions utilisant ce formats peuvent continuer à les utiliser.

3- Solutions complètes

Ces solutions sont construites de manière à être réutilisable par la machine tout en restant au maximum compréhensible par l’homme. elles se présentent sous la forme de successions de "tableaux" ou chaque tableau correspondants à une tournée. Les premières lignes du tableau sont des informations générales sur la tournée puis chaque ligne correspond au passage du véhicule sur un sommet enfin les colonnes représentent les différentes variables utiles à la vérification des données :

S(i) : le sommet
C : la charge du véhicule au passage sur le sommet ;
TW0 : la borne inf. de la fenêtre de temps de ce sommet ;
TW1 : la borne sup. de la fenêtre de temps de ce sommet ;
VTW : différence entre la borne sup et le début du traitement du client ;
Min : différence entre la borne sup. et le début du traitement du client ;
A : date d'arrivée du véhicule sur le sommet ;
W : temps attendu par le véhicule avant de commencer le service ;
B : date de début du service ;
D : date de départ du véhicule ;
L : durée de transport du client ;
F : temps d'attente supplémentaire à ce sommet sans compromettre la solution.

Outils de visualisation

Pour visualiser les résultats sur une carte, à chaque instance est associée un fichier qui indique les coordonnées GPS correspondants à chaque sommet. Vous trouverez aussi un petit programme en C++ implémenté sous Visual studio 2010 qui utilise l'API google v3.
Pour l'utiliser vous devez fournir plusieurs éléments :

"1 - For generate the html file enter you google API key here:" Pour utiliser ce programme vous aller donc avoir besoin d’une clef Google API (qui est gratuite pour un usage privé). Si vous ne l’avez pas déjà vous pouvez la récupérer à cette adresse : https://developers.google.com/maps/documentation/javascript/tutorial?hl=FR#api_key

"2 - Enter file of coordinate AND solution file :
Puis de deux fichiers, 1 avec les coordonnées GPS des clients et une solution réduite correspondants à la même instance

le code source (fait sous Visual Studio 2010): TELECHARGER

ATTENTION : le même nœud peut être utilisé plusieurs fois, donc certains points se superposent parfois.

LEGENDE :
La ville en bleu point_depot est le dépôt;
les villes en verts point_pickup sont les sommets d’origine des clients ;
les villes en rouges point_delivery sont les sommets de destination des clients.

Licence

All the C#, C++ and Java programs are under the GNU General Public License
Warning : Please note these programs are provided for free without any guarantees.

Annexe : position GPS des villes de France

Dans l’archive suivantes vous trouverez les coordonnées GPS pour une grande partie des communes de France, certaines n’ayant pas été utilisées pour la création des instances. GPS_cities
Attention ces données ne sont pas fiables à 100%, certaines coordonnées ne correspondent pas aux villes associées (la cause est due aux accents et aux homonymes qui ont perturbé la recherche effectuée sur API Google MAP).

Research topics with Maxime Chassaing