WHIR PROBIRER I NORSK BOMPOIRIKK
utkommer 25. april med artikler av blant andre:
A natureza combinatória do Dial-a-Ride Problem leva a que o volume da árvore de pesquisa seja muito elevado, pelo que todas as técnicas que possam reduzi-lo poderão ser um contribu- to importante para alcançar soluções neste contexto (Rossi et al., 2006). No nosso contexto e dada a utilização da Programação com Restrições, foram aplicadas algumas técnicas basea- das nas formulações acima e nos conceitos presentes na literatura (Berbeglia et al., 2010; Cordeau & Laporte, 2003; Cordeau, 2006; Melachrinoudis et al., 2007; Parragh, 2011).
Uma das técnicas mais usadas para reduzir o espaço de pesquisa consiste na identificação de simetrias (Rossi et al., 2006) que possam ser quebradas de modo a não serem geradas soluções equivalentes, isto é, cuja utilidade e resultados nada acrescentam por serem iguais aos de outras soluções. Este tipo de situações ocorre particularmente com os veículos pois, ao existirem veículos idênticos e sendo a utilização de qualquer um deles válida, é esperado que se obtenham soluções simétricas. Assim, e de modo a obter tal redução, impõe-
se que os tempos de saída dos depósitos iniciais são todos crescentes (para veículos do mesmo tipo), isto é, o primeiro veículo sairá primeiro que o segundo, o segundo que o terceiro, etc… Formalmente, e assumindo uma frota homogénea por uma questão de simplicidade, esta restrição pode ser expressa, para o modelo de domínios finitos, da seguinte forma:
k Depósitos k mj k 1,...,m Esperas j Esperas k
Numa frota heterogénea esta restrição poderá também ser aplicada de forma idêntica para veículos do mesmo tipo. Assumindo tipo V como uma função que devolve o tipo do veículo
VVeículos, a restrição pode formalizar-se como:
V V Veículos k lk,l tipoVk tipoVl Esperas k Esperas l
Como alternativa, para modelações que não contemplem os tempos de espera, poderá optar-se por estabelecer, mediante uma ordenação dos veículos que compõem a frota, que a cardinalidade das rotas dos k-ésimos veículos são superiores ao dos seguintes. Contemplando a situação em que a cardinalidade de duas rotas distintas é igual, poderá cortar-se simetrias obrigando a que o primeiro vértice servido (não considerando o ponto de partida) terá que ter uma codificação inferior, por exemplo, que o correspondente vértice da rota seguinte.
Por outro lado, e como já foi referido no decorrer deste capítulo, existem ligações que não fazem sentido do ponto de vista do problema, por questões de timing do serviço ou mesmo devido à carga do veículo. Tendo presentes alguns conceitos e variáveis apresentados na Secção 7.1 como a duração do serviço no vértice i, di, a janela temporal
L U associada a i, i
esse mesmo vértice e também o tempo de viagem T i j entre os vértices i e j, é intuitivo
, perceber que os seguintes arcos devem ser eliminados do espaço de pesquisa:
k d , com , kDepósitos k m e d Destinos , pois nenhum veículo terá comoprimeira paragem um local onde se deixam passageiros.
De forma idêntica todos os arcos do tipo
o k , com , kDepósitos k m eoOrigens, e do tipo
ni i,
, com iOrigens e n sendo o número total depedidos de transporte.
As janelas temporais associadas a cada vértice podem também levar a arcos do tipo
,i j , com ,i j Vértices , sejam removidos se Ui di T i j
, Lj. Ainda baseado nos timings do serviço e nas janelas temporais, os arcos
,i j e
,jn i , com
iOrigens, jVértices e n como o número de pedidos de88
, j
,
T i j d T j n i Tempo Máximo de Viagem
Ainda neste âmbito, será interessante apresentar o conceito de caminho não admissível. Este define-se como uma sequência de vértices que violam alguma das restrições, tipicamente ligadas aos timings ou à capacidade do veículo. Com base neste conceito é também possível excluir os arcos:
,in j
se o caminho , ,j i nj n, não for admissível. i
ni j,
se o caminho ,i ni j n, , j não for admissível.
,i j se os caminhos , ,i j ni n, j e , ,i j nj n, não forem admissíveis. i
ni n, j
se os caminhos i j n, , i n, j e j i n, , i n, j não foremadmissíveis.
Além de permitir eliminar os arcos referidos acima, o conceito de caminho não admissível permite também descobrir pares de pedidos incompatíveis, ou seja, pares de pedidos que não podem ser servidos pelo mesmo veículo devido aos timings do serviço. Os pedidos i e j são considerados incompatíveis caso nenhum dos caminhos entre eles seja admissível. Caso os caminhos: , ,i j ni n, j , , ,i j nj n, , , ,i j i ni n, j , j i n, , j n, , ,i i ni j n, , j e
, , ,
j nj i n sejam não admissíveis, os oito arcos entre i, j, n + i e n + j podem também ser i
removidos do espaço de pesquisa.
Verificar se um dado caminho é admissível não é uma tarefa propriamente trivial dado o número de restrições, janelas temporais e tempos de espera pelo que deve basear-se no conceito de Forward Time Slack proposto por Savelsbergh (1992) e generalizado por Cordeau (2006). Este conceito diz que, para o caminho , ,i j ni n, j , por exemplo, será necessário
verificar se cada troço cumpre as restrições temporais e de carga do veículo. Para as primeiras, terão que se verificar as seguintes condições:
i
, j, jTempos i d Esperas i T i j L U (7.4.28)
com di sendo a duração do serviço no vértice i e L Uj, j a janela temporal associada ao
vértice j. Validado este primeiro troço, torna-se necessário validar o seguinte tendo em conta o anterior, ou seja:
, , , i n i n i j Tempos i D Esperas i T i j L U D Esperas j T j n i (7.4.29)Este tipo de condições acaba por traduzir os tempos de chegada aos diversos vértices que devem pertencer ao intervalo
L U que representa o intervalo de tempo em que é permitido , chegar a um dado local. Por fim, a condição para o último troço do caminho é dada por:
, , , , i j n j n j n i Tempos i D Esperas i T i j D Esperas j T j n i L U D Esperas n i T n i n j (7.4.30)Adicionalmente, as restrições relativas à capacidade dos veículos poderão apenas invalidar caminhos em que os “vértices origem” sejam consecutivos, como é o caso do caminho exemplificado acima, , ,i j ni n, j .