Approche ELS pour résoudre le problème du DARP

Auteurs : M. CHASSAING, P. LACOMME, C. LAFOREST

Laboratoire : LIMOS (Laboratoire d’Informatique, de Modélisation et d’Optimisation des Systèmes

Contact : maxime.chassaing@isima.fr

Plan de la présentation

Introduction et contexte

1. Présentation du problème

Dial-a-ride Problem (DARP)

2. Démarche de résolution

Principe et fonctionnement de l’approche ELS

3. Les résultats

4. Création de nouvelles instances

Conclusion

RO

AD

EF 2

01

4 à

Bo

rdea

ux

2

Pla

n

1. Présentation du problème

RO

AD

EF 2

01

4 à

Bo

rdea

ux

3

One-to-Many-to-One (1-M-1)

General pickup and delivery porblem(GPDP)

One-to-One

(1-1)a

-a

b-b

c

-c

c

a

b

d

e -e

-d

d

d

d,e

Dépôt

6

2

1

-946

4

10

6

9

8

-10

5

-1

-4

45

DépôtMany-

to-Many (M-M)

-6

-2

1

9-4

-2

139

7 2 8

1

90

-7

9

1

4

00

10

14

9

Dépôt

Anily et al. (2006)Frederickson et

Guan (1992)

Stacker Crane Problem

(SCP)

Cordeau et al (2003)Chevrier et al (2012)

Dial-a-Ride Problem(DARP)

Bronmo et al. (2007)Chevrier et al (2012)

Vehicule Routing Problem with Pickups and Deliveries

(VRPPD)

Sexton et Bodin (1985)Dumas et al. (1990)

VRPPD with Time Windows

(VRPPDTW)

m =1, Q = 1

Qualité du transport

P/D

Fenêtres de temps

Stein (1978)Lubbecke (2004)

Single vehicule routing problem with PD

(SVRPPD)

T≠ Ø m = 1

Sexton (1985)Psaraftis (1980)

Single vehicule Dial-a-ride Problem

(SVDARP)

m =1

Cortés et al. (2007)Mitrovic-Minic et Cordeau (2006)

VRP and with Transshipments

(VRPPDT)

Par

tie

1/4

: P

rése

nta

tio

n d

u

pro

blè

me

1. Ensemble de N véhicules

2. Ensemble de M clients1. Une origine :

2. Une destination:

3. 4 règles à respecter :1. Charge maximum du véhicule

2. Fenêtres de temps

3. Temps de trajet maximum pour chaque véhicule

4. Temps de trajet maximum pour chaque client

4. Objectif : transporter tous les clients à leur destination en minimisant la distance parcourue.

RO

AD

EF 2

01

4 à

Bo

rdea

ux

4

Par

tie

1/4

: P

rése

nta

tio

n d

u

pro

blè

me

Fenêtre de temps imposéepour le passage du véhicule sur au moins l’un des deux sommets

Définition du problème

Dial a ride dans la littératures

RO

AD

EF 2

01

4 à

Bo

rdea

ux

5

Les articles comparés ici

1. Cordeau, J.-F., Laporte, G., 2003. A tabu search heuristic for the static multi-vehicle dial-a-ride problem. Transportation Research Part B 37 (6), 579–594.

2. Parragh, S.N., Doerner, K.F., Hartl, R.F., 2010. Variable neighborhood search for the dial-a-ride problem. Lecture Notes in computer science vol. 6876., 1129-1138.

3. Jain, S., Van Hentenryck P., 2011. Large neighborhood search for dial-a-ride problems. In: Principles and practice of constraint programming. Computers & Operations Research 40 (1), Springer.

4. Parragh, S.N., Schmid, V., 2012. Hybrid column generation and large neighborhood search for the dial-a-ride problem. Computers & Operations Research 40 (1), 490–497.

Des articles récents

1. Kirchlera, D., Wolfler Calvo, R., 2013. A Granular Tabu Search algorithm for the Dial-a-Ride Problem. Transportation Research Part B: Methodological 56, 120–135.

2. Masson, R., Lehuédé, F., Péton, O., 2014. The Dial-A-Ride Problem with Transfers. Computers & Operations Research 41, 12-23.

Par

tie

1/4

: P

rése

nta

tio

n d

u

pro

blè

me

Les instances du DARP de la littérature

1. Deux grands jeux d’instances

RO

AD

EF 2

01

4 à

Bo

rdea

ux

6

Par

tie

1/4

: P

rése

nta

tio

n d

u

pro

blè

me

Cordeau J-F et Laporte G. 200320 instances

Ropke S. et al. 200742 instances

Les points communs :

Nœuds disposés dans un carré 20x20Les temps maximums de trajet identiques pour tous les clients

Les différences :

Charge de chaque client = 1Service time = 10

Entre 3 et 11 véhicules Entre 24 et 144 clients

Charge des clients entre 1 et 6Services time dépendant de la charge

Entre 2 et 8 véhicules Entre 16 et 96 clients

Les solutions optimales sont connues

2. Démarche de résolution

Approche ELS (Evolutionary local Search)

Metaheuristique

• Repose sur des points clefs :

• Une fonction d’évaluation

• Générer une solution initiale

• Recherche locale efficace

• Parcourir l’espace (l’approche ELS)

• Diversité (éviter d’explorer x fois la même zone)

RO

AD

EF 2

01

4 à

Bo

rdea

ux

7

Par

tie

2/4

: D

ém

arc

he

de

ré

solu

tio

n

Evaluation

RO

AD

EF 2

01

4 à

Bo

rdea

ux

8

Par

tie

2/4

: D

ém

arc

he

de

ré

solu

tio

n

Quand un tour est connu:

• L’évaluation proposée par Cordeau et Laporte en 2003

• Algorithme répond si la tournée est possible ou pas

• avec une solution

1. Repris dans les articles suivants S.N. Parragh 2010 et 2013

“eight step evaluation”

Dépôtdébut

1 2 3 40

5

10

15

20 W[2

]=2

Temps

W[3

]=0

W[4

]=0

Dépôt fin

TRT

= 1

0

W[1

]=0

Dépôtdébut

1 2 3 40

5

10

15

20 W[2

]=0

Temps

W[3

]=0

W[4

]=0

Dépôt fin

TRT

= 8

W[1

]=0

Distance entre les sommetsDistance entre les sommets

Générer une solution initiale

• Etape 1 : choisir un ordre pour les clients :

• Etape 2 : affecter les clients à un tour :

RO

AD

EF 2

01

4 à

Bo

rdea

ux

9

4 5 2 3 1 9 6 8 7 10Liste ordonnée

des clients :

2- 3+

3-6+

6-

9+

9-Dépôt

7+

8+

4+5+

1+

4-5-

7-8-

2+

1-

4 5 2 3 9 6 8 7 101

dépôt 4+ dépôt5+ 5- 4-

dépôt 2+ dépôt2- 3+ 3-

dépôt dépôt

1+ 1-1+ 1-

1+ 1-1+ 1-

RO

AD

EF 2

01

4 à

Bo

rdea

ux

10

Par

tie

2/4

: D

ém

arc

he

de

ré

solu

tio

n

Recherche locale

Plusieurs mouvements rapides s’alternent (4 différents)

• déplacer à une meilleur place

• déplacer un client gênant

• détruire une partie d’une tournée

• réorganiser une tournée

• Ces mouvements sont

fortement randomiséssolution courante initiale

Valeurs des

solutions

solution possible après recherche locale

Si

S1 S2 S3 Sp-1 Sp

Si’

S1’ S2’ S3’ Sp-1’ Sp’

S1 S2 S3 Sp-1 Sp

S1’ S2’ S3’ Sp-1’ Sp’

Générer p voisins

Solution initiale

Solution après recherche locale

Nombre d’itérations

de ELS

Sx’

Meilleur résultat parmi

les p voisins

Parcourir l’espace des solutions

RO

AD

EF 2

01

4 à

Bo

rdea

ux

11

Par

tie

2/4

: D

ém

arc

he

de

ré

solu

tio

nSchéma de l’approche ELS :

Remarque: à chaque itération de ELS

Meilleur des p voisins devient le

nouveau père pour l’itération suivante

Même si

Valeur (Solution père)

meilleure que

Valeur (Solution meilleur voisin)

B- Parcourir l’espace des solutions

RO

AD

EF 2

01

4 à

Bo

rdea

ux

12

S pere

Sfils

1Sfils

2Sfils

3Sfils

p-1Sfils

p

S1’ S2’ S3’ Sp-1’ Sp’

S pere

Sfils’2<

Par

tie

2/4

: D

ém

arc

he

de

ré

solu

tio

n

RO

AD

EF 2

01

4 à

Bo

rdea

ux

13

Par

tie

2/4

: D

ém

arc

he

de

ré

solu

tio

n

Solution courante

Solution optimale

Valeurs des

solutions

L’ensemble des solutions

Voisinage de la solution courante

Solution courante

Solution optimale

Valeurs des

solutions

L’ensemble des solutions

Meilleur voisin

+ Table de hachage

Sortir des minimum locaux

Une solution Clef unique

Idée de génération de clefs : -> Coût solution * 10000

-> + Dates de passage sur les clients situés en début, milieu et fin des tours

Ne pas explorer plus de X fois les mêmes solutions.

Diversité

3- Les résultats

RO

AD

EF 2

01

4 à

Bo

rdea

ux

14

Par

tie

3/4

: L

es

Ré

sult

ats

• 5 exécutions

• 2 jeux d’instances de la littérature

• Comparaisons avec des temps normalisés :

Cordeau and

Laporte [2003]

S.N. Parragh et al

[2010]

S.N. Parragh et

al [2013]nous [2013]

Methode utilisée

Tabu

Search

(TS)

Variable

Neighborgood

Search

(VNS)

Large

Neighborhood

Search

(LNS)

Evolutionary

Local

Search

(ELS)

Computer Pentium 4, 2 GHz Pentium D Intel Xenon Core™ i7-3770 CPU

GHz 2.00 3.20 2.67 3.40

Language N/C C++ C++ C++

Operating System N/C N/C N/CWindows 7

Professionnel

Closest computer in

benchmark

produced by Jack

Dongarra

Pentium 4 1.9GHz

computer

Pentium 4E, 3.0

GHz computer

Estimation

méthode VNSPar expérimentation

Mflop 533.93 630.30 1141.61 2526.33

Speed factor 4.73 4.01 2.21 1.00

Tableau de résultats 1/2

RO

AD

EF 2

01

4 à

Bo

rdea

ux

15

m n Best

(%)CPUn Avg

(%)

Best

(%)CPUn Avg

(%)

Best

(%)CPUn Avg

(%)

Best

(%)CPUT2B CPUTT

R1a 3 24 0.00 4.02 0.00 0.00 2.24 0.00 0.00 0.24 0.00 0.00 0.01 1.73

R2a 5 48 0.25 17.04 0.15 0.00 4.99 0.39 0.00 1.25 0.00 0.00 0.77 3.77

R3a 7 72 0.02 36.32 0.77 0.19 8.28 1.17 0.62 2.31 0.17 0.08 4.58 8.93

R4a 9 96 0.44 60.82 1.40 0.64 15.89 1.05 0.15 7.37 0.73 0.27 10.40 18.73

R5a 11 120 1.48 97.76 1.60 1.45 38.52 1.58 0.29 12.08 0.54 -0.33 26.47 36.21

R6a 13 144 2.06 113.89 3.06 2.15 57.37 1.92 0.46 21.94 1.43 1.13 53.59 66.74

R7a 4 36 0.00 9.28 0.87 0.00 2.40 0.29 0.00 0.46 0.17 0.00 0.80 2.47

R8a 6 72 1.45 43.21 1.61 0.56 13.20 1.51 0.84 2.68 1.28 0.00 2.46 7.70

R9a 8 108 2.15 106.79 2.26 1.31 35.68 2.70 0.48 11.26 4.41 2.75 13.19 23.38

R10a 10 144 2.76 185.05 2.10 1.38 88.52 2.78 2.01 21.34 0.85 0.07 44.91 49.78

R1b 3 24 0.00 4.08 0.00 0.00 3.21 0.97 0.00 0.28 0.00 0.00 0.20 1.16

R2b 5 48 0.14 17.53 1.19 0.33 6.46 1.09 0.10 1.36 0.26 0.00 2.09 3.40

R3b 7 72 1.75 39.20 1.94 1.10 11.05 1.33 0.00 3.71 0.93 0.72 6.26 9.24

R4b 9 96 1.24 65.92 2.11 0.72 31.78 2.24 1.04 10.22 0.85 0.33 16.82 21.58

R5b 11 120 2.03 114.86 1.82 0.89 68.33 2.12 1.68 19.95 0.41 -0.14 28.87 41.98

R6b 13 144 0.80 155.81 1.88 0.62 85.04 0.81 0.04 32.35 0.40 -0.09 65.01 72.76

R7b 4 36 0.00 8.94 0.00 0.00 4.19 0.00 0.00 0.59 0.00 0.00 0.36 2.15

R8b 6 72 0.28 48.33 1.64 0.24 14.20 1.92 0.49 4.32 0.73 0.02 2.97 7.65

R9b 8 108 1.43 108.41 2.43 1.13 38.05 2.15 0.00 12.44 0.84 0.40 16.14 22.26

R10b 10 144 0.68 195.37 1.60 0.47 135.42 2.47 1.39 31.48 2.26 -0.18 39.41 54.18

Moyenne : 0.95 71.63 1.42 0.66 33.24 1.42 0.48 9.88 0.81 0.25 16.77 22.79

S.N. Parragh et al

[2013]. Hybrid LNS (5

runs)

proposed ELS (5 runs)Cordeau and

Laporte [2003].

TS

S.N. Parragh et al

[2010]. VNS (5 runs)

Par

tie

3/4

: L

es

Ré

sult

ats

Résultats après 2,25 minutes

RO

AD

EF 2

01

4 à

Bo

rdea

ux

16

BKS* : Best known solution

Jain

et al

[2011]

Parragh

et al

[2010]

Parragh

et al

[2013]

Parragh

et al

[2013]

Masso

n et al

[2014]

Instance m n BKS* LNS-

FFPA

VNS LNS HLNS ALNS ELS

R1a 3 24 190.02 X X X X X

R2a 5 48 301.34 X

R3a 7 72 532.00 X

R4a 9 96 570.25 X

R5a 11 120 627.68 X

R6a 13 144 785.26 X

R7a 4 36 291.71 X

R8a 6 72 487.84 X

R9a 8 108 658.31 X

R10a 10 144 855.15 X

R1b 3 24 164.46 X X X X

R2b 5 48 295.66 X

R3b 7 72 484.83 X

R4b 9 96 529.33 X

R5b 11 120 577.98 X

R6b 13 144 737.69 X

R7b 4 36 248.21 X X X X

R8b 6 72 461.39 X

R9b 8 108 593.49 X

R10b 10 144 793.21 X

Total 1 1 2 6 6 14

X = Meilleure solution en moyenne sur les 5 exécutions, pour un temps comparable

Par

tie

3/4

: L

es

Ré

sult

ats

Tableau des résultats 2

RO

AD

EF 2

01

4 à

Bo

rdea

ux

17

NAME OPT Avg

(%)

Best

(%)CPUd Avg

(%)

Best

(%)CPUe

T2B CPUeTT

NAME OPT Avg

(%)

Best

(%)CPUd Avg

(%)

Best

(%)CPUe

T2B CPUeTT

a2-16 294.25 0.00 0.00 0.12 0.00 0.00 0.00 0.00 b2-16 309.41 0.00 0.00 0.15 0.00 0.00 0.01 0.01

a2-20 344.83 0.00 0.00 0.28 0.00 0.00 0.00 0.51 b2-20 332.64 0.00 0.00 0.21 0.00 0.00 0.00 0.00

a2-24 431.12 0.00 0.00 0.35 0.00 0.00 0.01 0.01 b2-24 444.71 0.03 0.00 0.40 0.00 0.00 0.01 0.01

a3-24 344.83 0.00 0.00 0.29 0.00 0.00 0.14 0.87 b3-24 394.51 0.00 0.00 0.31 0.38 0.00 0.06 0.40

a3-30 494.85 0.08 0.00 0.50 0.25 0.00 0.43 0.81 b3-30 531.44 0.00 0.00 0.48 0.00 0.00 0.04 1.08

a3-36 583.19 0.01 0.00 0.83 0.00 0.00 0.06 0.06 b3-36 603.79 0.06 0.00 0.74 0.00 0.00 0.55 0.55

a4-32 485.50 0.04 0.00 0.55 0.00 0.00 0.36 0.36 b4-32 494.82 0.00 0.00 0.43 0.00 0.00 0.03 1.47

a4-40 557.69 0.00 0.00 0.78 0.00 0.00 0.30 0.30 b4-40 656.63 0.00 0.00 1.00 0.00 0.00 0.18 1.99

a4-48 668.82 0.03 0.00 1.62 0.11 0.00 0.08 1.04 b4-48 673.81 0.17 0.00 1.73 0.15 0.00 0.16 2.18

a5-40 498.41 0.00 0.00 0.85 0.00 0.00 0.14 0.14 b5-40 613.72 0.00 0.00 0.78 0.00 0.00 0.24 0.24

a5-50 686.62 0.04 0.00 1.60 0.02 0.00 0.97 3.12 b5-50 761.40 0.09 0.00 1.49 0.04 0.00 1.18 3.20

a5-60 808.42 0.11 0.01 2.51 0.00 0.00 0.25 4.23 b5-60 902.04 0.16 0.05 3.00 0.00 0.00 1.33 1.33

a6-48 604.12 0.07 0.00 1.14 0.00 0.00 0.26 3.81 b6-48 714.83 0.00 0.00 1.07 0.00 0.00 2.11 2.11

a6-60 819.25 0.32 0.13 2.29 0.02 0.00 1.69 2.46 b6-60 860.07 0.01 0.00 2.07 0.00 0.00 0.71 0.71

a6-72 916.05 0.41 0.07 4.43 0.13 0.00 4.26 5.56 b6-72 978.47 0.18 0.12 4.43 0.03 0.00 3.15 6.37

a7-56 724.04 0.00 0.00 1.67 0.05 0.00 1.83 1.83 b7-56 823.97 0.02 0.00 1.82 0.19 0.00 2.84 5.15

a7-70 889.12 0.49 0.05 2.88 0.09 0.00 2.93 6.43 b7-70 912.62 0.26 0.05 3.70 0.00 0.00 3.65 3.66

a7-84 1033.37 0.68 0.27 7.04 0.20 0.01 4.63 9.65 b7-84 1203.37 0.85 0.66 6.72 0.08 0.00 6.71 9.39

a8-64 747.46 0.07 0.00 2.14 0.06 0.00 4.14 8.27 b8-64 839.89 0.09 0.09 2.56 0.12 0.07 4.75 7.79

a8-80 945.73 0.60 0.31 5.73 0.14 0.00 4.74 10.29 b8-80 1036.34 0.19 0.03 3.84 0.01 0.00 7.78 10.26

a8-96 1229.70 0.53 0.41 9.92 0.24 0.17 6.91 8.84 b8-96 1185.55 0.44 0.19 10.32 0.13 0.03 4.59 12.35

Total 0.17 0.06 2.26 0.06 0.01 1.63 3.27 0.12 0.06 2.25 0.05 0.01 1.91 3.35

Proposed ELS (5 runs)Parragh et al [2013]

Hybrid LNS (5 runs)

Proposed ELS (5 runs) Parragh et al [2013]

Hybrid LNS (5 runs)

Par

tie

3/4

: L

es

Ré

sult

ats

Limites des instances typesCarrée 20 x 20 -> 30 unités de temps pour que le véhicule le traverse

• Dans les instances classiques on constate que :

RO

AD

EF 2

01

4 à

Bo

rdea

ux

18

Par

tie

4/4

:p

rop

osi

tio

n d

e

no

uve

lles

inst

ance

s

• Le temps de chargement des clients

(Cordeau et Laporte 2003 )

• 10 unités de temps

• Le temps maximum des clients dans le véhicule.

(Cordeau et Laporte 2003 )

• 90 unités de temps (quelque soit la distance qu’ils souhaitent parcourir)

donc environ 3x la distance max

Proposition de nouvelles instances

RO

AD

EF 2

01

4 à

Bo

rdea

ux

19

• 96 instances –> 96 départements français

• Générer aléatoirement (des lois biaisées)

• Pour la distances à parcourir

• Les positions des fenêtres de temps dans la journée

• Les tailles des fenêtres de temps

10%

75%

10% 5%

Distance entre sommet d’origine et le sommet de destination du client

% desclients

[<10km] [10-30km] [70-100km][30-70km] [>100km]0%

36%16%

Répartition des fenêtres de temps des clients

% desclients

3h-7h1%

7h-11h 11h-15h 19h-23h 23h-3h

36%

15h-19h10% 1%

Par

tie

4/4

:p

rop

osi

tio

n d

e

no

uve

lles

inst

ance

s

RO

AD

EF 2

01

4 à

Bo

rdea

ux

20

Création d’instance

Par

tie

4/4

:p

rop

osi

tio

n d

e

no

uve

lles

inst

ance

s

• Propose un ensemble de BKS obtenues après 10 min de notre méthode

http://fc.isima.fr/~chassain/Phd/Real_life_instances.php

Nouvelles instances96 instances

Les points communs :

*Correspond à la définition du DARP proposé par Cordeau et Laporte 2003

Les différences :

Nœuds disposés dans des superficies qui varient : 100km² à 8500km²Ne respecte plus l’inégalité triangulaire (distance réelle)

Les temps de trajet maximums varient en fonction des clientsCharge des clients varie de 1 à 4

Services time dépendant de la chargeEntre 2 et 20 véhicules Entre 10 et 128 clients

Outil de visualisation

• Comme on travaille avec des villes

-> très visuelles.

• Exemple une petite application disponible sur le site web pour afficher une tournée d’un véhicule R

OA

DEF

20

14

à B

ord

eau

x

21

Par

tie

4/4

:p

rop

osi

tio

n d

e

no

uve

lles

inst

ance

s

Conclusions• Dial a ride problem

• ELS : un schéma algorithmique simple

• Des résultats intéressants :

• sur les 2 jeux d’instances classiques de la littérature.

http://fc.isima.fr/~chassain/Phd/ELSapproachDARP.php

• Un nouveau jeu d’instances proposé:

• Instances disponibles sur le site :

http://fc.isima.fr/~chassain/Phd/Real_life_instances.php

RO

AD

EF 2

01

4 à

Bo

rdea

ux

22

Co

ncl

usi

on