13
Caixeiro viajante com seleção de hotéis

Caixeiro Viajante Com Seleção de Hotéis

Embed Size (px)

DESCRIPTION

Modelagem por subconjuntos do problema de Caixeiro Viajante com seleção de hotéis.

Citation preview

Page 1: Caixeiro Viajante Com Seleção de Hotéis

Caixeiro viajante com seleção de hotéis

Page 2: Caixeiro Viajante Com Seleção de Hotéis

TSPSH

• Dado um conjunto H de hotéis e um conjunto C de clientes o TSPSH é definido em um grafo completo G = (V, A) onde V = H C e A = {(i,j)| i, j V, i j}.

• Cada cliente demanda um serviço ou um tempo de visita i (com i = 0 , i H).

• O tempo cij necessário para viajar de um vértice i para um j, é conhecido para todos os pares de vértices.

Page 3: Caixeiro Viajante Com Seleção de Hotéis

Definições

• Entende-se por viagem, todo subtour que começa em um hotel disponível, visita clientes e termina também em um hotel.

• Tour é a soma de todas as viagens, sendo que deve começar em um hotel inicial e terminar nesse mesmo hotel.

Page 4: Caixeiro Viajante Com Seleção de Hotéis

Objetivo

• O primeiro objetivo é minimizar o número de viagens conectadas que são necessárias para visitar todos os clientes. Em segundo, minimizar o tempo total de viagem do tour.

Page 5: Caixeiro Viajante Com Seleção de Hotéis

Restrições

• Existe um hotel inicial i=0 , de onde o tour deve começar e terminar. Nada impede que esse hotel seja utilizado como hotel intermediário durante o tour.

• Cada viagem deve começar e terminar em um hotel disponível.

• O tempo total de uma viagem não deve exceder um tempo limite L.

Page 6: Caixeiro Viajante Com Seleção de Hotéis

Restrições

• Uma viagem deve começar exatamente do hotel onde a viagem anterior parou.

• O tempo total de uma viagem não deve exceder um tempo limite L.

• Não há limite de visitas a um hotel específico.

Page 7: Caixeiro Viajante Com Seleção de Hotéis

Modelo Matemático

• Dado xijd uma variável binária que assume valor 1

se, em uma viagem d a visita a um cliente ou a um hotel i é seguida por uma visita a um hotel ou cliente j , e valor 0 caso contrário.

• Assuma também a variável binária yd que assume valor 1 se em um dia pelo menos um cliente foi visitado. Será 0 se em um dia d não for requerida nenhuma viagem do dia d.

• Por último D representa o número máximo de viagens que pode ter a solução.

Page 8: Caixeiro Viajante Com Seleção de Hotéis

Função objetivo

• Min• Minimizar o número de viagens e o tempo total

do tour.• M é um número suficientemente grande, para

que é multiplicado na função objetivo, para que soluções com menor número de viagens sejam sempre melhores do que aquelas com maior número.

M σ 𝑦𝐷𝑑=1 d + σ ( σ 𝑐𝑖𝑗𝑥𝑖𝑗 )ሺ𝑖,𝑗ሻ∈𝐴𝐷𝑑=1

Page 9: Caixeiro Viajante Com Seleção de Hotéis

Sujeito a :

• 1 A restrição número 1 diz que cada cliente é visitado uma única vez durante todo o tour.

• 2 Restrição 2 garante a conectividade de cada viagem.

• 3 • 4

Restrições 3 e 4 dizem que toda viagem deve começar e terminar em um hotel.

σ σ 𝑥𝑖𝑗𝑑𝑖∈𝑉𝐷𝑑=1 = 1 ,𝑗 ∈𝐶

σ 𝑥𝑖𝑗𝑑𝑖∈𝑉 = σ 𝑥𝑗𝑖𝑑𝑖∈𝑉 ,𝑗 ∈𝐶 ,𝑑= 1,2,3…𝐷

σ σ 𝑥ℎ𝑗𝑑𝑗∈𝐶ℎ∈𝐻 = 𝑦𝑑 , d=1,2,3...D σ σ 𝑥𝑖ℎ𝑑𝑖∈𝐶ℎ∈𝐻 = 𝑦𝑑 , d=1,2,3...D

Page 10: Caixeiro Viajante Com Seleção de Hotéis

Sujeito a :

• (5)Restrição 5 impõe a máxima duração de cada viagem.

• 6

• (7) Restrições 6 e 7 dizem que o tour deve começar e terminar no hotel 0.

σ (𝑐𝑖𝑗+ 𝜏𝑖)(𝑖,𝑗)∈𝐴 𝑥𝑖𝑗𝑑 ≤ 𝐿 , d=1,2,...D

𝑥0𝑗 = 11𝑗∈𝑉/{0}

σ 𝑥𝑖0 1𝑖∈𝑉/{0} ≥ 𝑦𝑑 - 𝑦𝑑−1 , d=1,2, ..., D-1

Page 11: Caixeiro Viajante Com Seleção de Hotéis

Sujeito a :

• (8 )

• (9)

Restrições 8 e 9 dizem que se uma viagem termina em um hotel, a próxima deve começar no mesmo hotel.

σ 𝑥𝑖ℎ 𝑑𝑖∈𝑉 + 𝑦𝑑 ≥ σ 𝑥ℎ𝑖 𝑑+1𝑖∈𝑉 + 𝑦𝑑+1

h∈𝐻,𝑑= 1,….,𝐷

1− 𝑦𝑑+1 ≥ σ 𝑥𝑖ℎ 𝑑𝑖∈𝑉 − σ 𝑥ℎ𝑖 𝑑+1𝑖∈𝑉

h∈𝐻,𝑑= 1,….,𝐷

Page 12: Caixeiro Viajante Com Seleção de Hotéis

Sujeito a :

• (10)

Restrição 10 diz que uma viagem é marcada como iniciada, se pelo menos um cliente foi visitado em um dia d.

• (11) Restrição 11 afirma que as viagens ocorrem em dias

consecutivos. Começando no dia 1.

𝑥𝑖𝑗𝑑 ≤ 𝑦𝑑, (i,j)∈𝐴 , d=1,....,D

𝑦𝑑 ≥ 𝑦𝑑+1 , d=1,...., D-1

Page 13: Caixeiro Viajante Com Seleção de Hotéis

Sujeito a :

• (12)

Restrição 12 é para eliminação de sobtours, visto que uma solução viável do TSPSH pode conter ciclos começando e terminando no mesmo hotel.

(13) (14)

13 e 15 definem o domínio das variáveis de decisão.

σ σ 𝑥𝑖𝑗𝑑𝑗∈𝜅−{𝑖}𝑖∈𝜅 ≤ |𝜅| -1, 𝜅⊂ 𝐶 ,2 ≤ 𝜅 ≤ ȁ(𝐶ȁ(−1,𝑑= 1,….,𝐷

𝑥𝑖𝑗 𝑑 ∈ሼ0,1ሽ, ሺ𝑖,𝑗ሻ∈𝐴,𝑑= 1,….,𝐷 𝑦 𝑑 ∈ሼ0,1ሽ, 𝑑= 1,….,𝐷