HPI-akse respons

X i=1 xij = 1 ∀j ∈ V (2.6) n X j=1 xij = 1 ∀i ∈ V (2.7) X i,j∈S xij ≤ |S| − 1 ∀S ⊂ G, S 6= ∅ (2.8) xij ∈ {0, 1} ∀i, j ∈ V (2.9) em que:

xij é uma variável binária que assume valor 1, se aresta eij pertence à

solução do problema e 0, caso contrário;

cij é um valor que representa o custo de viagem da cidade i para a cidade j;

S é um subgrafo de G, em que |S| corresponde ao número de vértices nesse subgrafo.

A solução ótima do PCV é dada pelo conjunto de arestas que fazem parte da rota cujo custo é o menor possível. Essas arestas minimizam a função objetivo f (2.5) e não violam as restrições previamente definidas. As restrições (2.6) e (2.7) garantem que todas as cidades na solução gerada são conectadas somente a uma cidade antecessora e a uma sucessora, respectivamente. No entanto, essas duas restrições não são suficientes para garantir que a solu- ção gerada seja um ciclo hamiltoniano, uma vez que podem existir sub-rotas desconexas da origem, conforme mostra o exemplo ilustrado na Figura 2.4a. Para evitar a formação de ciclos ou circuitos desconexos da origem, as res- trições (2.8) devem ser observadas ao gerar uma solução. Essas restrições garantem que o número de arestas em um subgrafo é sempre menor que o número de vértices contidos nesse subgrafo. Desse modo, evita-se o uso da aresta que forma um ciclo no subgrafo (Figura 2.4b).

2.2.3 Variações do PCV

Apesar da definição do PCV ser bastante simples — tendo basicamente três elementos essenciais: vértices, arestas e custos — existem muitas variações para esse tipo de problema. A variação mais simples do PCV é a simétrica fortemente conectada. Uma instância de PCV é simétrica quando o custo de viagem entre duas cidades adjacentes é o mesmo independente da cidade inicial. E a instância é fortemente conectada se existe uma conexão para qual- quer par de cidades. No entanto, existem outras características que também têm sido consideradas por causa da tentativa de obter modelos mais próximos do mundo real, tais como: múltiplos caixeiros, variação do custo ao longo do tempo, custo de entrega e coleta, ganho de bônus e janela de tempo (Arenales et al., 2007; Goldbarg e Luna, 2005).

Algumas variações do PCV são brevemente descritas a seguir:

• Simétrico. A viagem entre duas cidades adjacentes têm o mesmo custo, independente da cidade em que se inicia a viagem. Matematicamente, esta propriedade corresponde à cij = cji ∀ eij ∈ E.

• Assimétrico. O sentido de deslocamento entre as cidades é relevante, tanto que o grafo que modela essa variação de PCV possui arestas orien- tadas. Em notação matemática, a assimetria é identificada por: ∃ eij ∈ E

tal que cij 6= cji.

• Fortemente conectado. Todos os vértices são adjacentes a qualquer outro vértice. ∀vi, vj ∈ V , ∃eij ∈ E.

• Fracamente conectado. Caracterizado pela ausência de uma ou mais arestas. Existe, pelo menos, um par de vértices não adjacentes. ∃vi, vj ∈ V

tal que eij ∈ E./

• Múltiplos caixeiros. Para esse tipo de PCV, vários caixeiros são consi- derados para uma mesma instância do problema. Os caixeiros devem realizar rotas diferentes visitando cidades diferentes. Em uma situação prática, considere uma empresa distribuidora de refrigerantes que possui vários veículos (caixeiros) para realizar a entrega em diferentes clientes (cidades). Todos os veículos iniciam suas rotas a partir do depósito da empresa (cidade inicial). Em seguida, cada um segue uma rota para vi- sitar um subconjunto diferente de clientes e, ao final, todos retornam ao depósito (Bektas, 2006).

• Variação de custo. Para facilitar o uso de algoritmos para resolver as instâncias de PCV, normalmente, os custos de viagem entre as cidades são pré-determinadas. No entanto, a variação de custo ao longo do tempo

2.2. NOTAÇÃO MATEMÁTICA PARA PROBLEMAS DE OTIMIZAÇÃO 43

pode ser considerada nos modelos dos problemas do mundo real, em que a mobilidade nas vias públicas das cidades depende de vários fatores como: horário do tráfego, interdição de vias, acidentes de trânsito, dentre outros (Patvichaichod, 2011).

• PCV com Bônus. Um bônus representa um valor de benefício que o caixeiro deve receber em cada cidade visitada. Nesse caso, o caixeiro deve visitar um subconjunto de cidades com o objetivo de minimizar o custo total e maximizar os bônus recolhidos. Na prática, essa variação de PCV pode ser usada para modelar a rota que uma empresa precisa fazer para receber pagamentos de seus clientes (Balas, 2004).

• Entrega e coleta. As paradas nos locais visitados significam que são feitas entregas e/ou coletas (Subramanian et al., 2010). O planejamento da rota consiste em minimizar os custos considerando o atendimento a todos os clientes, além das restrições da capacidade do veículo e do tempo disponível (Lim et al., 2005). Um exemplo prático para este tipo de PCV é o serviço de transporte escolar.

• Ganho de bônus. Não há necessidade de visitar todas as cidades da rota. O caixeiro ganha prêmios para cada cidade visitada e paga uma penalidade por cada cidade que deixou de visitar (Balas, 2004). O obje- tivo consiste em obter uma rota que minimize os custos de viagem e as penalidades, desde que tenha sido coletada uma quantidade mínima de prêmios ao fim da rota. Usando novamente o exemplo da empresa distri- buidora de refrigerantes, podemos considerar que a penalidade em cada cidade é a venda não realizada por não visitar um cliente. O prejuízo gerado pela não venda pode ser insignificante para a empresa diante de uma quantidade de vendas efetivadas ao atender outros clientes (prêmios maiores).

• Janela de Tempo. O caixeiro deve chegar a cada cidade em um horário que esteja dentro de um intervalo de tempo denominado janela de tempo (Wang e Regan, 2009). Essa é uma restrição importante que influencia diretamente a ordem de visita aos clientes. Sendo assim, a função obje- tivo deve ser minimizada considerando o limite de cada janela de tempo previamente estabelecido para cada vértice.

• PCV Periódico. Um planejamento de rotas pode ser feito visando uma programação de visitas para vários dias. Em cada dia, vários clientes de- vem ser atendidos. Cada cliente pode ser visitado mais de uma vez, desde que não seja no mesmo dia. As rotas são planejadas para minimizar o custo total nos dias planejados (Hemmelmayr et al., 2009).

• PCV com Custo de atraso. Variante do PCV, em que o custo de aresta eij depende da próxima visita na rota (Silva et al., 2012).

• PCV Agrupado. Variante do PCV, em que o conjunto de vértices V é particionado em grupos disjuntos (Mestria et al., 2012).

Para resolver os exemplos de PCV e suas variações, os métodos de oti- mização mais usados se enquadram nas seguintes abordagens: heurísticas construtivas, heurísticas de busca local e meta-heurísticas (Gutin e Punnen, 2002). A seção seguinte descreve os procedimentos inerentes a cada uma dessas abordagens.