3L-CVRP

3L-CVRP (three dimensional)

Authors:


Ch. Duhamel	P. Lacomme	H. Toussaint

Last Update: 21/04/2011.

This web page provide a full description of the results introduced in:

Duhamel C., P. Lacomme, A. Quilliot, H. Toussaint, "A GRASPxELS approach for the VRP with three dimensional loading constraints", submitted to Computers and Operations Research.

Comparative study:

Tables below provide a comparative study using the previous published articles:

(Gendreau et al., 2006)	Gendreau M., M. Iori and S. Martello. "A tabu search algorithm for a routing and contrainer loading problem". Transportation Science, 40(3):342-350, 2006.
(Fuellerer et al., 2010)	Fuellerer G., K.F. Doener, R.F. Hartl and M. Iori. "Meta-Heuristics for Vehicle Routing with three dimensional loading constraints". European Journal of Operational Research, 201(3):751-759, 2010.

A new software for 3LCVRP solution representation

We propose for free a software for Windows plateform which allow graphical represetation of solution.

This software has been achieved by H. Toussaint and it is under the GNU licence.

File format

The software accept file where :

- the first line gives the truck characteristics (lenght, width, heigh)

- the second line gives the number of items to pack

- the lines gives the item dimensions (lenght, width, heigh) and the item position in the truck (x, y, z)

The file 80_SOMME_T_2.txt gives :
- truck of length 68 - 39 - 34
- 33 it the total number of items to pack
- the first item has dimension 21-15-19 and it's located at 0-0-15
- the second item has dimension 14-32-5 and it's located at 17-0-0
....

Executable files is available here

For example, a double click on visu3D.exe lauch the MSDOS console :

Enter des.txt on the prompt.

How to change the scene representation ?

CTRL : lock/unlock the scene
SHIFT : lock/unlock camera rotation

mouse : rotations on x-axe, y-axe and z-axe

mouse button wheel : zoom in/ou

Source code file is available here

You must include OpenGL et the SDL library.

Details of solutions for the 3L-CVRP "classical instances"

Instances used by (Gendreau et al., 2006) and (Fuellerer et al., 2010) are available here.

Results with rotations here

Results without rotations here

3L-CVRP solutions (rotations allowed)

instance	(Gendreau et al., 2006)		(Fuellerer et al., 2010)		GRASPELS

01	297.65	3.40	297.65	1.00	297.65	3.53	297.65	0
02	334.96	0.60	334.96	0.10	335.67	0.06	334.96	0
03	362.27	448.1	362.27	16.20	362.27	13.99	362.27	0.2
04	430.89	11.1	430.89	0.50	430.88	0.4	430.88	0
05	395.64	0.50	406.50	9.60	379.43	8.16	379.43	0.1
06	495.85	14.7	495.85	1.20	495.85	0.3	495.85	0
07	742.23	1.80	732.52	18.10	725.43	237.39	725.43	4.9
08	735.14	104.90	735.14	13.30	735.14	36.63	735.14	1.1
09	630.13	977.80	630.13	3.70	630.13	2.18	630.13	0.1
10	717.90	410.70	711.45	92.60	687.57	589.11	687.57	32.1
11	718.24	208.10	718.25	81.90	718.24	1453.35	718.24	1.8
12	614.60	1 302.70	612.63	7.50	610.05	19.66	610	2
13	2 316.56	2 317.30	2391.77	174.50	2306.04	1242.44	2306.04	86.9
14	1 276.60	2 121.30	1222.17	425.90	1186.96	2423.64	1184.44	3600.2
15	1 196.55	2 916.14	1182.86	645.00	1161.2	2144.72	1161.11	689.3
16	698.61	863.00	698.61	2.80	698.61	2.87	698.61	0
17	906.42	753.20	862.18	3.10	861.8	8.58	861.79	1.2
18	1 124.33	2198.90	1112.18	1484.60	1084.26	1893.69	1078.41	2030.8
19	680.29	1 390.30	671.60	414.40	670.44	3322.67	658.34	3429.6
20	529.00	7 007.50	515.39	1436.70	510.95	2892.97	503.3	1469.7
21	1 004.40	6 262.50	951.87	2105.70	943.05	4173.74	921.25	4697.4
22	1 068.96	2 078.70	1030.12	1218.40	1029.87	3561.8	1009.45	3348.3
23	1 012.51	4 314.10	971.05	1231.70	987.06	3120.66	976.46	1889.1
24	1 063.61	1 052.50	1057.39	184.70	1056.33	2610.2	1047.75	682.8
25	1 371.32	500.90	1207.97	3986.10	1232.73	4489.01	1219.77	4658.4
26	1 557.12	1 075.00	1453.39	2843.60	1415.15	3484.63	1393.76	3066.6
27	1 378.52	3 983.20	1333.16	2208.30	1317.38	3372.87	1304.82	2422.3
Avg. Cost	876.31		856.67		847.04		841.96
Avg. Time		1 567.40		689.3		1522.56		1189.44
Avg. Norm. Time

3L-CVRP solutions (comparative study with and without rotations)

instance	GRASPELS				GRASPELS

	Rotations allowed				Rotations forbidden
01	297.65	3.53	297.65	0	297.65	1.01	297.65	0
02	335.67	0.06	334.96	0	335.67	0.06	334.96	0
03	362.27	13.99	362.27	0.2	362.27	5.31	362.27	0.2
04	430.88	0.4	430.88	0	430.88	0.19	430.88	0
05	379.43	8.16	379.43	0.1	379.43	1.56	379.43	0
06	495.85	0.3	495.85	0	495.85	0.34	495.85	0
07	725.43	237.39	725.43	4.9	732.51	104.85	732.51	0.1
08	735.14	36.63	735.14	1.1	730.66	115.78	730.66	0.1
09	630.13	2.18	630.13	0.1	633.72	2.52	633.72	0.1
10	687.57	589.11	687.57	32.1	704.97	1009.19	704.64	34.2
11	718.24	1453.35	718.24	1.8	718.24	225.1	718.24	13.6
12	610.05	19.66	610	2	610	11.62	610	2.7
13	2306.04	1242.44	2306.04	86.9	2299.05	111.17	2299.05	3.9
14	1186.96	2423.64	1184.44	3600.2	1194.57	2966.97	1192.29	612
15	1161.2	2144.72	1161.11	689.3	1163.34	1975.9	1163.23	1050.3
16	698.61	2.87	698.61	0	700.8	1.2	700.8	0.1
17	861.8	8.58	861.79	1.2	861.79	7.69	861.79	2.2
18	1084.26	1893.69	1078.41	2030.8	1091.61	2502.66	1091.28	4137.8
19	670.44	3322.67	658.34	3429.6	665.45	2489.16	662.96	1810.9
20	510.95	2892.97	503.3	1469.7	515.95	2340.49	513.28	3166.3
21	943.05	4173.74	921.25	4697.4	947.3	2503.9	940.72	2945.8
22	1029.87	3561.8	1009.45	3348.3	1039.64	2249.58	1021.02	3552.4
23	987.06	3120.66	976.46	1889.1	980.63	2194.71	972.12	3146.3
24	1056.33	2610.2	1047.75	682.8	1053.6	3964.98	1048.55	3697.1
25	1232.73	4489.01	1219.77	4658.4	1224.56	2898.75	1209.81	2564.6
26	1415.15	3484.63	1393.76	3066.6	1427.58	3053.36	1421.35	4711.4
27	1317.38	3372.87	1304.82	2422.3	1322.02	2449.77	1298.84	3617.4
Avg. Cost	847.04		841.96		848.88		845.48
Avg. Time		1522.56		1189.44		1229.18		1298.87
Avg. Norm. Time

Instances 08 : presentation of the solution

The solution is composed of 5 trips :

Trip 1 : Depot, 14 , 17, 22, 20, 19, Depot

Trip 2 : Depot, 11, 13, 9, 5, 4, 7, Depot

Trip 3 : Depot, 16, 15, 3, 2, 1, 6, 12, Depot

Trip 4 : Depot, 21, 8, 10, Depot

Trip 5 : Depot, 18, Depot

Trips details :

Trip number	Trip weight	Trip volume	Trip cost
1	1925	32861	212.611
2	2725	34932	142.299
3	994	26906	160.881
4	4425	21017	170.821
5	120	11628	44.045
Total solution :			730.657

New set of instances

Main characteristics:

- true distance between french cities
- 96 instances (with 20 to 300 serviced nodes) corresponding to the French districts
- created using an improved version of the software introduced by Vianney Bajart and Christophe Charles
- No linear dependence between vehicles capacity and fixed cost
- Include nightmare instances with up to 250 nodes

DLTQ's instances

download

n : the number of node including the depot

nt : the number of trucks available

nc : the number of items to pack

Capa : truck capacity

H - W - L: truck dimensions

Instance name	District name	District cities name list	n	nt	nc	Capa	H	W	L	Instances to download
DLT_01.txt	Ain		92	9	213	61	34	35	60
DLT_02.txt	Aisne		181	27	418	68	32	25	61
DLT_03.txt	Allier		124	25	248	63	33	33	63
DLT_04.txt	Alpes de Haute Provence		183	40	401	58	30	32	63
DLT_05.txt	Hautes Alpes		116	25	247	67	33	31	60
DLT_06.txt	Alpes Maritimes		121	28	277	67	32	25	60
DLT_07.txt	Ardeche		108	25	235	57	34	25	66
DLT_08.txt	Ardennes		84	12	171	63	31	25	60
DLT_09.txt	Ariege		167	17	363	67	30	39	63
DLT_10.txt	Aube		69	10	161	57	32	27	66
DLT_11.txt	Aude		95	12	214	66	33	25	67
DLT_12.txt	Aveyron		112	14	223	69	30	25	66
DLT_13.txt	Bouches du Rhone		119	15	251	67	30	25	69
DLT_14.txt	Calvados		176	18	389	57	34	37	60
DLT_15.txt	Cantal		188	33	399	55	30	25	60
DLT_16.txt	Charentes		129	15	271	55	30	30	67
DLT_17.txt	Charentes Maritimes		105	13	216	56	34	25	65
DLT_18.txt	Cher		256	31	533	62	32	25	67
DLT_19.txt	Corrrèze		224	36	506	61	30	25	61
DLT_2A.txt	Corse du Sud		113	15	239	59	31	25	69
DLT_2B.txt	Haute Corse		107	18	235	64	30	25	60
DLT_21.txt	Cote d'Or		126	15	292	64	32	25	60
DLT_22.txt	Cote d'Armor		239	23	493	63	31	32	69
DLT_23.txt	Creuse		203	28	468	57	30	28	66
DLT_24.txt	Dordogne		163	18	362	68	30	34	63
DLT_25.txt	Doubs		143	17	311	67	30	25	69
DLT_26.txt	Drome		126	14	276	62	33	25	69
DLT_27.txt	Eure		220	23	468	57	31	32	68
DLT_28.txt	Eure et Loir		141	19	300	68	31	25	67
DLT_29.txt	Finistere		164	21	358	58	31	25	67
DLT_30.txt	Gard		112	16	255	60	30	30	60
DLT_31.txt	Haute Garonne		131	18	297	56	30	25	65
DLT_32.txt	Gers		244	28	549	59	31	33	62
DLT_33.txt	Gironde		189	20	419	64	30	37	63
DLT_34.txt	Herault		136	21	290	55	34	25	62
DLT_35.txt	Ille et Vilaine		168	19	359	59	33	30	69
DLT_36.txt	Indre		85	12	184	69	31	25	66
DLT_37.txt	Indre et Loire		161	17	340	57	30	34	69
DLT_38.txt	Isere		205	21	453	60	30	33	64
DLT_39.txt	Jura		77	10	172	68	34	26	60
DLT_40.txt	Landes		132	19	305	60	30	27	62
DLT_41.txt	Loir et Cher		135	20	281	62	32	25	60
DLT_42.txt	Loire		178	20	392	67	31	32	63
DLT_43.txt	Haute Loire		86	11	176	56	30	25	68
DLT_44.txt	Loire Atlantique		172	22	385	56	34	25	68
DLT_45.txt	Loiret		170	23	358	59	31	25	68
DLT_46.txt	Lot		250	32	564	63	30	30	66
DLT_47.txt	Lot et Garonne		111	12	259	62	34	35	60
DLT_48.txt	Lozere		111	15	242	57	32	26	60
DLT_49.txt	Maine et Loire		246	29	544	66	30	32	63
DLT_50.txt	Manche		187	31	419	55	30	25	60
DLT_51.txt	Marne		129	17	294	60	32	26	69
DLT_52.txt	Haute Marne		59	7	123	66	34	25	61
DLT_53.txt	Mayenne		115	11	249	69	34	37	66
DLT_54.txt	Meurthe et Mozelle		172	28	383	67	30	25	60
DLT_55.txt	Meuse		56	7	109	68	30	25	61
DLT_56.txt	Morbihan		153	33	339	59	31	25	61
DLT_57.txt	Moselle		163	15	368	69	31	36	65
DLT_58.txt	Nievre		220	27	500	68	30	33	60
DLT_59.txt	Nord		193	19	418	64	33	37	61
DLT_60.txt	Oise		137	23	316	65	31	25	60
DLT_61.txt	Orne		111	12	231	57	32	36	65
DLT_62.txt	Pas de Calais		225	32	510	68	34	25	60
DLT_63.txt	Puy de Dome		174	26	362	59	30	25	60
DLT_64.txt	Pyrennees Atlantiques		161	26	369	66	30	25	60
DLT_65.txt	Hautes Pyrennees		223	23	516	59	33	33	64
DLT_66.txt	Pyrennees Orientales		150	19	318	65	30	31	60
DLT_67.txt	Bas Rhin		172	18	381	57	32	37	68
DLT_68.txt	Haut Rhin		125	18	251	65	30	25	62
DLT_69.txt	Rhone		152	23	340	61	30	25	60
DLT_70.txt	Haute Saone		78	7	149	66	32	35	66
DLT_71.txt	Saone et Loire		186	17	416	64	30	37	69
DLT_72.txt	Sarthe		186	20	388	55	32	34	67
DLT_73.txt	Savoie		137	16	281	55	30	32	67
DLT_74.txt	Haute Savoie		125	17	272	60	32	25	68
DLT_75.txt	Paris		20	3	37	59	34	25	63
DLT_76.txt	Seine Maritime		152	24	322	58	30	25	61
DLT_77.txt	Seine et Marne		190	20	409	56	32	33	67
DLT_78.txt	Yvelines		190	20	401	69	32	34	66
DLT_79.txt	Deux Sevres		147	21	324	63	30	25	60
DLT_80.txt	Somme		171	38	387	67	34	39	68
DLT_81.txt	Tarn		106	15	237	57	34	25	60
DLT_82.txt	Tarn et Garonne		79	10	173	59	33	34	67
DLT_83.txt	Var		124	12	277	69	32	38	65
DLT_84.txt	Vaucluse		105	15	238	66	31	25	64
DLT_85.txt	Vendee		146	14	310	67	30	37	65
DLT_86.txt	Vienne		153	27	341	68	30	25	62
DLT_87.txt	Haute Vienne		108	11	224	69	30	35	61
DLT_88.txt	Vosges		127	19	276	64	30	25	60
DLT_89.txt	Yonne		134	18	298	62	30	25	69
DLT_90.txt	Territoire de Belfort		102	13	209	65	30	28	68
DLT_91.txt	Essonne		196	20	459	57	34	34	65
DLT_92.txt	Haut de Seine		35	6	78	61	32	25	69
DLT_93.txt	Seine Saint Denis		39	6	79	59	30	25	60
DLT_94.txt	Val de Marne		46	5	101	65	31	38	65
DLT_95.txt	Val d'Oise		183	29	402	55	30	25	67

Solutions for the new set of instances

Theses instances can be divided into 4 subsets:

- DLT_3LCVRP_1: set of 13 small scale instances with less than 100 nodes;

- DLT_3LCVRP _2: set of 40 medium scale instances with a number of nodes varying from 100 to 150;

- DLT_3LCVRP _3: set of 33 large scale instances with a number of nodes varying from 150 to 200;

- DLT_3LCVRP _4: set of 11 nightmare instances with a number of nodes greater than 200.

DLT's solutions

less than 100 nodes

Rotations allowed

Instance name	Number of cities (nodes)	Solution cost	Solution time
DLT_01.dat	92	1388,27	5418,4
DLT08.dat	84	1041,54	2461
DLT10LP.dat	69	1200,33	2580,6
DLT_11.dat	95	1517,85	4854,3
DLT_36.dat	85	2042,01	5324
DLT_39.dat	77	1758,5	5076,3
DLT_43.dat	86	1317,93	5301
DLT_52.dat	59	1146,78	2618
DLT_55.dat	56	1078,8	1526,2
DLT_70.dat	78	1289,68	5052,7
DLT_75.dat	20	71,6	1,3
DLT_82.dat	79	1006,8	5135,5
DLT_92.dat	35	254,56	133,4
DLT_93.dat	39	216,35	4722,1
DLT_94.dat	46	242,04	2581,4

DLP's solutions

from 100 to 150 nodes

Rotations allowed

Instance name	Number of cities (nodes)	Solution cost	Solution time
DLT_03.dat	124	2052,27	5330,8
DLT_05.dat	116	2026,35	5430,4
DLT_06.dat	121	3444,2	4476,5
DLT_07.dat	108	2434,31	4389
DLT_12.dat	112	2268,78	4844,2
DLT_13.dat	119	2296,61	4062,9
DLT_16.dat	129	1872,63	5180,4
DLT_17.dat	105	1929,74	4671,5
DLT_2A.dat	113	2821,78	4917,4
DLT_2B.dat	107	3665,83	4552,5
DLT_21.dat	126	1885,21	5375,1
DLT_25.dat	143	3159,12	5429,8
DLT_26.dat	126	2648,82	5409,2
DLT_28.dat	141	2832,9	5414,4
DLT_30.dat	112	3436,54	5424,6
DLT_31.dat	131	1776,06	4792,8
DLT_34.dat	136	2736,49	5347,4
DLT_40.dat	132	3912,77	5438,5
DLT_41.dat	135	2759,98	5400,7
DLT_47.dat	111	1778,14	5402,5
DLT_48.dat	111	2875,28	5407,1
DLT_51.dat	129	2217,5	5400,4
DLT_53.dat	115	1528,12	5440,7
DLT_60.dat	137	2231,22	5300
DLT_61.dat	111	1954,09	5309,2
DLT_66.dat	150	2872,76	5470,1
DLT_68.dat	125	2042,68	5038,4
DLT_73.dat	137	3085,56	5188,6
DLT_74.dat	125	3442,3	5427,2
DLT_79.dat	147	3077,39	4672,8
DLT_81.dat	106	2097,33	5390,7
DLT_83.dat	124	2811,55	4558,9
DLT_84.dat	105	1662,31	5384,2
DLT_85.dat	146	2361,79	5557,1
DLT_87.dat	108	1498,54	5404,8
DLT_88.dat	127	2919,94	5317,4
DLT_89.dat	134	2314,52	5400
DLT_90.dat	102	642,05	4674,6

DLP's solutions

from 150 to 200 nodes

Rotations allowed

Instance name	Number of cities (nodes)	Solution cost	Solution time
DLT_02.dat	181	3411,68	5407,4
DLT_04.dat	183	3898,77	5479,7
DLT_09.dat	167	3457,07	5416,9
DLT_14.dat	176	3341,09	5535,1
DLT_15.dat	188	4597,8	5426
DLT_24.dat	163	5261,64	5274,6
DLT_29.dat	164	5249,17	5425,4
DLT_33.dat	189	4112,79	5700,6
DLT_35.dat	168	2680,55	5404,7
DLT_37.dat	161	3178,33	5232,7
DLT_42.dat	178	4007,88	5598
DLT_44.dat	172	3513,68	5484,1
DLT_45.dat	170	3208,11	5552,8
DLT_50.dat	187	6084,57	5458,6
DLT_54.dat	172	3810,19	5476,1
DLT_56.dat	153	4347,93	5405,4
DLT_57.dat	163	4599,94	5535,2
DLT_59.dat	193	3069,32	5422,7
DLT_63.dat	174	3569,56	5430,4
DLT_64.dat	161	4077,55	5044,2
DLT_67.dat	172	2201,15	4696,7
DLT_69.dat	152	2031,52	4472,4
DLT_71.dat	186	4093,28	5378,3
DLT_72.dat	186	2548,62	5456,2
DLT_76.dat	152	2977,96	5159,4
DLT_77.dat	190	2705,95	5424,8
DLT_78.dat	190	2671,51	5244,6
DLT_80.dat	171	2407,48	5555,6
DLT_86.dat	153	3962,59	5418,2
DLT_91.dat	196	2181,66	5231,5
DLT_95.dat	183	1868,38	5319,8

DLP's solutions

more than 200 nodes (nighmare instances :) )

Rotations allowed

Instance name	Number of cities (nodes)	Solution cost	Solution time
DLT_18.dat	256	4557,44	5463,3
DLT_19.dat	224	5081,43	5485,2
DLT_22.dat	239	4522,52	5666,8
DLT_23.dat	203	3161,36	5403,6
DLT_27.dat	220	3652,64	5450
DLT_32.dat	244	4414,94	5477,3
DLT_38.dat	205	5313,02	5598,1
DLT_46.dat	250	5170,43	5532,8
DLT_49.dat	246	5832,03	5619,2
DLT_58.dat	220	3905,81	5791,7
DLT_62.dat	225	4484,43	5336,7
DLT_65.dat	223	2992,35	5570,3

Solutions with rotations

download

Solutions with no rotations

download