( PDF ) Algoritmo para o problema de roteamento dinâmico de veículos com janelas de tempo e tempos de viagem variáveis

ads:

Livros Grátis

http://www.livrosgratis.com.br

Milhares de livros grátis para download.

• K

•

Q

• i [e

i

, l

i

]

•

K V

k

V

k

v ∈ V k

•

G = (V, E) V = v

0

, v

1

, ..., v

n

E = e

0

, e

1

, ..., e

m

v

0

i j c

ij

c

ij

= c

ji

∀(i, j) ∈ E Q

i q

i

0 < q

i

≤ Q

x

ij

i j

x

ij

x

ji

V

c

= V 0

V

S ⊆ V

c

q(S)

S δ(S)

S

min Σ

e∈E

c

e

x

e

Subject to : Σ

e∈δ(i)

x

e

= 2 ∀i ∈ V

Σ

e∈δ(0)

x

e

= 2K

Σ

e∈δ(S)

x

e

= 2K(S) ∀S ⊆ V

x

e

≤ 1 ∀e ∈ E δ(0)

x

e

≥ 0 ∀e ∈ E

K

S K(S) S

V

K(S)

e ∈ E

e

•

•
•

α

i j i j

n

i

n

i

n

i

RouteSet

min Σ

r∈RouteSet

c

r

x

r

Σ

r∈RouteSet

σ

ir

x

r

= 1 ∀i ∈ C

x

r

∈ 0, 1

• C

• c

r

• x

r

• σ

ir

r

i r

• RouteSet

RouteSet

n

i

• id

• registrationT ime

• q

i

• (x, y)

• [e

,

l

i

]

•

G(V, E) V

E

•

i j d

ij

i j

j

F uncaoCusto = nv ∗ cv + dt ∗ cd + pa ∗ ta + pe ∗ te

• F uncaoCusto

• nv

• cv

• dt

• cd

• pa

• ta

• pe

• te

Algoritmo

←−

≤

= ∅

()

←− ( , )

←− ( )

( , )

( )

depot

requests time V RP Solution

time

←−

i

=

←−

( , )

•

F itness = 1/FuncaoCusto

F uncaoCusto

i

←− ∗

←−

population rate

rate

Competition

• n

•

n

•

←−

i

←−

IndivRate

mutationRate

•

• route

•

route

• route

i

j

i i

i j

T = l

0

− e

0

e

0

l

0

(λ)

i j T

λ λ

i j

(V

m

) λ

λ i j

i

j i j V

(i, j) i

j

T

ij

= d

ij

/(M ∗V

m

)

• T

ij

i j

• M (i, j)

• V

m

• d

ij

(i, j)

0

200

0 50 100 150 200 250

Tempo de Viagem

Tempo de partida

Tempo de Partida X Tempo de Viagem - Origem(35,35), Destino (55,45), Distancia: 14,14

n −1

n

0

10

20

30

40

50

60

70

80

0 10 20 30 40 50 60 70

Eixo das ordenadas

Eixo das abcissas

Arquivo R101 - Solomon (1987)

0

10

20

30

40

50

60

70

80

0 10 20 30 40 50 60 70

Eixo das ordenadas

Eixo das abcissas

Arquivo R201 - Solomon (1987)

RC1 RC2

R1 C1 RC1

0

10

20

30

40

50

60

70

80

90

0 10 20 30 40 50 60 70 80 90 100

Eixo das ordenadas

Eixo das abcissas

Arquivo C101 - Solomon (1987)

0

10

20

30

40

50

60

70

80

90

0 10 20 30 40 50 60 70 80 90 100

Eixo das ordenadas

Eixo das abcissas

Arquivo C201 - Solomon (1987)

R2 C2 RC2

0

10

20

30

40

50

60

70

80

90

0 10 20 30 40 50 60 70 80 90 100

Eixo das ordenadas

Eixo das abcissas

Arquivo RC101 - Solomon (1987)

0

10

20

30

40

50

60

70

80

90

0 10 20 30 40 50 60 70 80 90 100

Eixo das ordenadas

Eixo das abcissas

Arquivo RC201 - Solomon (1987)

•

0

200

400

600

800

1000

1200

0 20 40 60 80 100

Tempo de Registro

Identificadores de Demanda

Identificadores de Demanda X Tempo de Registro - (R101)

time = 0

0

200

400

600

800

1000

1200

0 20 40 60 80 100

Tempo de Registro

Identificadores de Demanda

Identificadores de Demanda X Tempo de Registro - (R101)

competition

n

u u

tempo

iteracao

tempo

execucao

tempo

execucao

= tempo

iteracao

∗periodo/u

µ σ

√

n n

µ

(x − z

1−α/2

.S/



(n), x + z

1−α/2

.S/



(n))

z

1−α/2

S

n

0

500000

1e+06

1.5e+06

2e+06

2.5e+06

3e+06

3.5e+06

RC201RC101C201C101R201R101

OBJETIVO

INSTANCIA

ONLINE

Grau 0.2

Grau 0.4

Grau 0.6

Grau 0.8

0

500000

1e+06

1.5e+06

2e+06

2.5e+06

3e+06

3.5e+06

RC201RC101C201C101R201R101

OBJETIVO

INSTANCIA

ONLINE

Grau 0.2

Grau 0.8

0

500000

1e+06

1.5e+06

2e+06

2.5e+06

3e+06

RC201RC101C201C101R201R101

OBJETIVO

INSTANCIA

DEMANDA

Grau 0.2

Grau 0.4

Grau 0.6

Grau 0.8

0

500000

1e+06

1.5e+06

2e+06

2.5e+06

3e+06

RC201RC101C201C101R201R101

OBJETIVO

INSTANCIA

DEMANDA

Grau 0.2

Grau 0.8

0

500000

1e+06

1.5e+06

2e+06

2.5e+06

3e+06

3.5e+06

RC201RC101C201C101R201R101

OBJETIVO

INSTANCIA

PERIODICA

Grau 0.2

Grau 0.4

Grau 0.6

Grau 0.8

0

500000

1e+06

1.5e+06

2e+06

2.5e+06

3e+06

3.5e+06

RC201RC101C201C101R201R101

OBJETIVO

INSTANCIA

PERIODICA

Grau 0.2

Grau 0.8

0

500

1000

1500

2000

2500

RC201RC101C201C101R201R101

DISTANCIA

INSTANCIA

ONLINE

Grau 0.2

Grau 0.4

Grau 0.6

Grau 0.8

0

500

1000

1500

2000

2500

RC201RC101C201C101R201R101

DISTANCIA

INSTANCIA

ONLINE

Grau 0.2

Grau 0.8

0

500

1000

1500

2000

2500

3000

3500

RC201RC101C201C101R201R101

DISTANCIA

INSTANCIA

DEMANDA

Grau 0.2

Grau 0.4

Grau 0.6

Grau 0.8

0

500

1000

1500

2000

2500

3000

3500

RC201RC101C201C101R201R101

DISTANCIA

INSTANCIA

DEMANDA

Grau 0.2

Grau 0.8

0

500

1000

1500

2000

2500

3000

3500

4000

RC201RC101C201C101R201R101

DISTANCIA

INSTANCIA

PERIODICA

Grau 0.2

Grau 0.4

Grau 0.6

Grau 0.8

0

500

1000

1500

2000

2500

3000

3500

4000

RC201RC101C201C101R201R101

DISTANCIA

INSTANCIA

PERIODICA

Grau 0.2

Grau 0.8

0

1

2

3

4

5

6

7

8

9

RC201RC101C201C101R201R101

VEICULOS

INSTANCIA

ONLINE

Grau 0.2

Grau 0.4

Grau 0.6

Grau 0.8

0

1

2

3

4

5

6

7

8

9

RC201RC101C201C101R201R101

VEICULOS

INSTANCIA

ONLINE

Grau 0.2

Grau 0.8

0

5

10

15

20

25

30

35

40

RC201RC101C201C101R201R101

VEICULOS

INSTANCIA

DEMANDA

Grau 0.2

Grau 0.4

Grau 0.6

Grau 0.8

0

5

10

15

20

25

30

35

40

RC201RC101C201C101R201R101

VEICULOS

INSTANCIA

DEMANDA

Grau 0.2

Grau 0.8

0

5

10

15

20

25

RC201RC101C201C101R201R101

VEICULOS

INSTANCIA

PERIODICA

Grau 0.2

Grau 0.4

Grau 0.6

Grau 0.8

0

5

10

15

20

25

RC201RC101C201C101R201R101

VEICULOS

INSTANCIA

PERIODICA

Grau 0.2

Grau 0.8

Livros Grátis
( http://www.livrosgratis.com.br )
 
Milhares de Livros para Download:
 
Baixar livros de Administração
Baixar livros de Agronomia
Baixar livros de Arquitetura
Baixar livros de Artes
Baixar livros de Astronomia
Baixar livros de Biologia Geral
Baixar livros de Ciência da Computação
Baixar livros de Ciência da Informação
Baixar livros de Ciência Política
Baixar livros de Ciências da Saúde
Baixar livros de Comunicação
Baixar livros do Conselho Nacional de Educação - CNE
Baixar livros de Defesa civil
Baixar livros de Direito
Baixar livros de Direitos humanos
Baixar livros de Economia
Baixar livros de Economia Doméstica
Baixar livros de Educação
Baixar livros de Educação - Trânsito
Baixar livros de Educação Física
Baixar livros de Engenharia Aeroespacial
Baixar livros de Farmácia
Baixar livros de Filosofia
Baixar livros de Física
Baixar livros de Geociências
Baixar livros de Geografia
Baixar livros de História
Baixar livros de Línguas

Baixar livros de Literatura
Baixar livros de Literatura de Cordel
Baixar livros de Literatura Infantil
Baixar livros de Matemática
Baixar livros de Medicina
Baixar livros de Medicina Veterinária
Baixar livros de Meio Ambiente
Baixar livros de Meteorologia
Baixar Monografias e TCC
Baixar livros Multidisciplinar
Baixar livros de Música
Baixar livros de Psicologia
Baixar livros de Química
Baixar livros de Saúde Coletiva
Baixar livros de Serviço Social
Baixar livros de Sociologia
Baixar livros de Teologia
Baixar livros de Trabalho
Baixar livros de Turismo
 
 