A formulação anterior considera implicitamente a modelação de uma frota homogénea constitu- ída por um ou mais veículos. No entanto, muitas instâncias do Dial-a-Ride Problem são com- postas por frotas não homogéneas. Para contemplar esta situação diversos parâmetros têm que ser redefinidos, sendo que, a título de exemplo, o facto de se contemplar uma frota onde os veículos têm diferentes características obriga a que se considere um novo índice k K , que permite identificar cada um dos veículos que compõem a frota. Por outro lado o custo da via- gem associada ao arco
,i j também será redefinido para kij
c , permitindo reflectir a heteroge-
neidade da frota. Além dos parâmetros, todas as variáveis da versão base do problema terão que sofrer alterações para contemplar a frota, agora, heterogénea (Parragh, 2011).
Esta heterogeneidade da rota pode não ser apenas ao nível dos consumos de combustível, da potência e, consequentemente, velocidade de ponta dos veículos, mas também relativamente ao tipo de lugares disponíveis para transporte dos clientes do problema em causa. Como já referido neste documento, estes poderão ter necessidade especiais de transporte, como por exemplo, transporte de cadeiras de rodas, em macas, em cadeiras apropriadas para crianças, entre outros. Assim a variável Qi que modela o número de
passageiro a bordo do veículo após o vértice i ser servido, deverá ser reformulada de modo a ser possível diferenciar não só o veículo como também os diferentes tipos de lugar: r k
i
Q , com k e r sendo o índice relacionado com as diferentes necessidades especiais contempladas K
pelo veículo em causa, e.g., r = 0 pode simbolizar lugares sentados, r = 1, lugares em cadeiras de rodas e r = 2 em maca.
Por fim, mas não menos importante, pode ter-se uma preocupação acrescida com a qualidade do serviço muitas vezes modelada por um factor de penalização na função objectivo (Paquette et al., 2009). Neste modelo em particular tal factor poderia ser aplicado através da
criação de uma nova variável k i
W que representa o custo do tempo de espera do veículo k,
com passageiros a bordo, no vértice i. Assim a função a minimizar passaria a ser representada da seguinte forma:
k k k
ij ij i
k K i V j V c x k K i P D W
(5.2.15)Ao modelo apresentado teriam que ser adicionadas algumas restrições e uma variável que indicasse o tempo de chegada de um dado veículo a um local já que agora este tempo pode não corresponder ao tempo de início do serviço devido ao possível tempo de espera. Deste modo considere-se a variável k
i
A a variável que indica tal momento, com i e k KV , que
iria dar origem a restrições como:
0 , , k k k k i i i i W W B A i V kK (5.2.16) , , k k i i B A i V kK (5.2.17) 1 , , , k k k k ij j i i ij x A B d t i jV k K (5.2.18)
De notar que a primeira restrição traduz o tempo de espera como o intervalo de tempo entre o início do serviço num dado vértice e o tempo a que a viatura chegou ao local, sendo o primeiro sempre superior ou igual ao segundo, como referido na segunda restrição. A última restrição mapeia o tempo de chegada a um dado vértice como a soma do tempo de início do serviço no seu antecessor, mais a duração do serviço nesse mesmo local e o tempo de viagem entre os locais em causa. Apesar da restrição apresentada não ser linear, é possível a sua linearização com recurso a variáveis binárias.
6. Programação com Restrições
A Programação com Restrições (Lauriere, 1978) é um poderoso paradigma para a resolução de problemas de pesquisa e de combinatória que recorre a técnicas de diversas áreas, das quais se destacam, a Inteligência Artificial, as Bases de Dados, as Linguagens de Programa- ção, a Ciência da Computação, bem como Investigação Operacional. A sua aplicação está cada vez mais difundida, sendo que actualmente domínios como o planeamento, agendamen- to, definição de rotas para veículos, redes e bioinformática são provas do sucesso deste para- digma (Rossi et al., 2006).
A base desta abordagem passa pela modelação de um dado problema através da definição das restrições que lhe estão associadas, sendo estas definidas através das relações entre as variáveis do problema. O modelo obtido é inserido num resolvedor que, por sua vez, irá explorar o espaço de soluções do problema de modo a encontrar valores para todas as variáveis que satisfaçam as restrições impostas.
Deste modo é comum referir-se que a Programação com Restrições é um paradigma que mistura as abordagens matemática e computacional já que são declaradas variáveis, domínios e restrições que o resolvedor terá que satisfazer. No entanto, para que o processo de resolução não se torne ineficiente, é também necessário delinear estratégias de pesquisa.
Classicamente um Problema de Satisfação de Restrições, em inglês Constraint
Satisfaction Problem (CSP), é definido por um triplo
X D C onde X é um tuplo de n variáveis, , ,
1, 2,..., nX X X X , D é o tuplo dos domínios correspondentes D D D1, ,...,2 Dn tal que
i i
X D . Por fim C é um tuplo de restrições C C C1, ,...,2 Cm , no qual cada restrição C pode j
ser vista como um par ,
j
S j
R S onde
j
S
R representa a relação entre as variáveis presentes em
j
S , sendo este último o escopo da restrição C . Por outras palavras, j Rié um subconjunto do
44
produto cartesiano dos domínios das variáveis presentes em Si. Uma solução deste CSP é um
tuplo A A A1, ,...,2 An onde AiDi e cada restrição C é satisfeita de modo a que j RSj
mantenha a projecção de A para o escopo de S . Se o conjunto de soluções for vazio, o j
problema não é satisfazível (Marriott & Stuckey, 1998; Rossi et al., 2006).
Caso a dimensão do escopo de cada restrição seja limitada a 1 ou 2, então as restrições dizem-se unárias ou binárias, respectivamente, podendo, deste modo, representar o CSP através de um grafo de restrições onde os vértices simbolizam as variáveis e os arcos, as restrições. Por outro lado, se as restrições forem n-árias, com n > 2, o problema pode ser representado através de um hipergrafo.
Ainda que este framework seja simples e tenha uma grande abrangência, pode ser especializado ou generalizado de diversas formas. Em particular, se o problema a resolver não é apenas de satisfação mas também de optimização, acrescentar-se-á a minimização/maximização de uma ou mais funções objectivo.
Rossi et al. (2006) consideram que os algoritmos para resolução de CSP’s se inserem numa de duas categorias: inferência e pesquisa, sendo que por diversas vezes se combinam ambas as abordagens. Dados os domínios das diversas variáveis do problema, o espaço de soluções poderia ser “facilmente” enumerado e cada combinação seria testada para determinar se constitui ou não uma solução. No entanto, esta abordagem pode tornar-se demasiado pesada, pelo que a inferência e a pesquisa pretendem melhorar a procura de soluções. Inevitavelmente a combinação de ambas as técnicas tem um trade-off associado pois nem sempre o custo computacional gasto na redução do problema é proporcional à redução conseguida no tempo total de resolução do problema, ainda que quanto mais reduzido estiver um problema, mais fácil este será de resolver. Esta correlação entre a pesquisa e a inferência pode ser expressa através do gráfico que se apresenta na Figura 6.1.
Figura 6.1 - Trade-off entre a Pesquisa e a Redução.