A importância do enfoque sistêmico para problemas de roteirização

Revista Pesquisa e Desenvolvimento Engenharia de Produção n.5, p. 64 – 86, Jun 2006

©Copyright 2006

64

A IMPORTÂNCIA DO ENFOQUE SISTÊMICO PARA PROBLEMAS

DE ROTEIRIZAÇÃO DE VEÍCULOS

Sérgio Renato Carmo Brejon

Doutorando em Engenharia Naval e Oceânica

e-mail: [email protected]

Universidade de São Paulo

Patrícia Prado Belfiore

Doutoranda em Engenharia de Produção

e-mail: [email protected]

Universidade de São Paulo

RESUMO

Os problemas de roteirização de veículos possuem uma grande quantidade de parâmetros, o

que dificulta a modelagem e resolução do problema. Este trabalho tem como objetivo a

aplicação do enfoque sistêmico para entendimento, análise e classificação dos problemas de

roteirização de veículos. O entendimento profundo do problema e sua adequada classificação

permitem uma melhor compreensão dos aspectos mais relevantes, facilitando a modelagem e

resolução do problema.

Palavras-chave: Problema de Roteirização de Veículos, Enfoque sistêmico, Pesquisa

Operacional.

The importance of the systemic focus to Vehicle Routing Problems


©Copyright 2006

65

ABSTRACT

The vehicle routing problems have got a great number of parameters, what worsen the

problems’ resolution and modeling. This paper aims to apply the systemic focus in order to

understand, analyze and classify the vehicle routing problems. The deep understanding of the

problem and its adequate classification allow a better comprehension of the most important

aspects, making it easier to model and solve the problem.

Keywords: Vehicle Routing Problem, Systemic Focus, Operational Research.

1. INTRODUÇÃO

Na Engenharia de Transportes, bem como em outros ramos de Engenharia, são comuns

os problemas que podem ser abordados e resolvidos por técnicas de Pesquisa Operacional. Os

problemas estudados em Pesquisa Operacional podem ser classificados em diversos grupos,

tais como problemas de Seqüenciamento, Alocação, Roteamento, Substituição, Filas,

Competição, Busca (Nicolau, 1995).

Os Problemas de Roteirização (ou roteamento) de veículos pertencem a uma categoria

ampla de problemas de pesquisa operacional conhecida como Problemas de Otimização de

Rede. Nessa categoria encontram-se problemas clássicos, como Problema de Fluxo Máximo,

Problema do Caminho Mais Curto, Problema de Transporte, Problema de Designação

(Golden, Ball e Bodin, 1981).

Uma das dificuldades de se modelar e resolver um problema de roteirização advém da

grande quantidade de parâmetros que podem influenciar esse tipo de problema. A adequada

classificação dos problemas de roteirização permite uma melhor compreensão dos aspectos

mais relevantes. Esses aspectos mais relevantes devem ser considerados com maior atenção

quando da proposição de algum procedimento de solução, já que o tipo de problema e seus

parâmetros direcionam a estratégia de solução a ser adotada.

Como os problemas de roteirização exigem soluções específicas em função do tipo de

problema a ser resolvido, a fase de modelagem e análise do problema de roteirização se torna

bastante relevante e importante, sendo um pré-requisito essencial para a proposição de uma

estratégia de solução adequada.

O objetivo deste trabalho é aplicar os conceitos de Enfoque Sistêmico para auxiliar o


©Copyright 2006

66

correto entendimento, análise e classificação de Problemas de Roteirização de veículos, como

fase preliminar, porém, indispensável para solução dessa classe de problemas de pesquisa

operacional.

1.1. Pesquisa Operacional e enfoque sistêmico

Desde o nascimento da Pesquisa Operacional, esse novo campo de análise de decisão

caracterizou-se pelo uso de técnicas e métodos científicos qualitativos por equipes

interdisciplinares, no esforço de determinar a melhor utilização de recursos limitados e para

programação otimizada das operações de uma empresa. Essa característica multidisciplinar

das aplicações de Pesquisa Operacional deu origem a um novo enfoque, o Enfoque Sistêmico

aos problemas de decisão das empresas, pois ultrapassou as fronteiras da especialidade.

A natureza e o ambiente de negócios, mesmo que possam ser logicamente explicados

pelo raciocínio especialista, são muito mais complexos e abrangentes e por isso exigem

abordagem mais aberta que permita reconhecer os múltiplos aspectos envolvidos.

Existem duas dificuldades que são inerentes ao problema e que podem influenciar

fundamentalmente a qualidade da decisão:

a) Escolha do Problema certo para resolver

O primeiro passo para uma tomada de decisão de qualidade é saber qual o problema

que requer solução. Deve-se, portanto, identificar claramente qual é o problema estudado. A

fonte mais comum para enganos é a ênfase em encontrar a resposta certa ao invés de procurar

a questão certa para responder.

b) Conhecimento insuficiente

Por um lado, pouca informação cria um ambiente de incerteza para o processo de

decisão. Por outro lado, informação demais também pode prejudicar, já que exigiria tempo e

habilidades extras para análise.

A Pesquisa Operacional tem sido vista pelos gerentes e praticantes sob dois enfoques

diferentes quanto à abordagem, mas coerentes e complementares na aplicação prática no

campo da gestão empresarial:

a) Enfoque clássico: busca da solução ótima

O enfoque clássico ou tradicional é derivado do conceito quantitativo clássico da

Pesquisa Operacional. Neste enfoque, a Pesquisa Operacional é definida como a arte de


©Copyright 2006

67

aplicar técnicas de modelagem a problemas de decisão e resolver os modelos obtidos através

de métodos exatos, visando à obtenção de uma solução ótima, sob uma abordagem sistêmica.

Esse enfoque de busca da solução ótima para os problemas foi, por muito tempo,

extremamente útil ao desenvolvimento dessa metodologia, pois envolveu pesquisadores de

diversas áreas, resultando no desenvolvimento de métodos para a solução de problemas.

No entanto, na área da administração, os administradores ou executivos responsáveis

pela tomada de decisões se sentiam incomodados com o rigor matemático dos métodos de

Pesquisa Operacional e, muitas vezes, frustrados pela pouca flexibilidade dos modelos.

b) Enfoque atual: identificação do problema correto

A outra visão decorre de um conceito qualitativo da Pesquisa Operacional. Busca-se

uma compreensão mais profunda do próprio problema, identificando melhor seus elementos

internos, suas interações com o ambiente externo, as informações necessárias e os resultados

possíveis de obter.

A importância da Pesquisa Operacional estaria, então, na sua influência sobre o modo

pelo qual os administradores abordam os problemas, na maneira como os formulam, na

avaliação que fazem do relacionamento com outros problemas e na forma usada para sua

comunicação a outras pessoas.

Nessa abordagem qualitativa, perde importância o rigor matemático da solução, e ganha

relevância o espírito crítico, a sensibilidade para descobrir o problema correto e analisar quais

informações são fundamentais para a decisão e quais são acessórias, sem afetar os resultados.

O enfoque qualitativo da Pesquisa Operacional é o reconhecimento de que a abordagem

quantitativa dos problemas fornece uma estrutura de raciocínio e análise que permite

desenvolver a “visão sistêmica” do processo.

Neste enfoque, portanto, é importante procurar enfocar a estrutura básica dos problemas

ao invés de suas características particulares.

1.2. Etapas do enfoque sistêmico

O enfoque sistêmico pode ser aplicado para auxiliar a compreensão e modelagem de um

problema de transportes, porém não se restringe às ciências exatas, tendo aplicação também

em vários outros campos, tais como ciências biológicas, economia, ciências sociais

(Churchman, 1971; Bertalanffy, 1972).

No estudo de um problema, as seguintes etapas podem ser consideradas na aplicação do


©Copyright 2006

68

Enfoque Sistêmico, conforme apresentado por Gualda (1995):

1. Identificação do sistema, de seus componentes, dos seus objetivos, dos recursos

disponíveis, dos aspectos inerentes à sua administração, e de seu ambiente (restrições).

2. Formulação do problema e das medidas de rendimento a considerar.

3. Geração de alternativas para solução do problema.

4. Avaliação das alternativas geradas a partir das medidas de rendimento

formuladas.

5. Seleção das alternativas.

Neste trabalho, Gualda (1995) apresenta a utilização do enfoque sistêmico e de métodos

quantitativos na formulação e na solução de problemas voltados para o balanceamento de

capacidade e dimensionamento operacional de terminais de transporte e de seus componentes.

As etapas 1 e 2 estão relacionadas com o estudo e compreensão do problema a ser

resolvido. As etapas 3, 4 e 5 devem ser aplicadas na fase final de resolução de um problema,

e estão relacionadas à proposição de métodos de resolução, avaliação dos métodos propostos,

e seleção dos métodos (ou alternativas) de resolução mais adequadas.

No presente trabalho estaremos abordando as etapas 1 e 2 propostas por Gualda (1995).

Essas etapas serão utilizadas para o correto entendimento, análise e classificação de

Problemas de Roteirização.

2. MOTIVAÇÃO DA APLICAÇÃO DO ENFOQUE SISTÊMICO NO

ENTENDIMENTO DE PROBLEMAS DE ROTEIRIZAÇÃO

Problemas de roteirização de veículos pertencem a uma categoria ampla de problemas

de pesquisa operacional conhecida como Problemas de Otimização de Rede. Nessa categoria

encontram-se problemas clássicos, como Problema de Fluxo Máximo, Problema do Caminho

Mais Curto, Problema de Transporte, Problema de Designação (Golden, Ball e Bodin, 1981).


grande quantidade de parâmetros que podem influenciar esse tipo de problema. A


mais relevantes, que devem ser considerados com maior atenção quando da proposição de

algum procedimento de solução.

2.1. Procedimentos de solução de problemas de roteirização: a necessidade de se gerar

um procedimento informatizado


©Copyright 2006

69

A proposição de um procedimento informatizado para um problema qualquer pode

gerar a seguinte pergunta: O que se ganha nesse processo de informatização? O aumento de

velocidade do processo de resolução de um problema por si só pode não ser uma boa

justificativa, principalmente se o computador apenas permitir obter o resultado errado de

maneira mais rápida!

Para responder a essa pergunta no contexto particular de problemas de roteirização,

pode-se consultar o trabalho de Sutcliffe e Board (1991). Nesse trabalho os autores analisam

os benefícios gerados pela utilização de procedimentos informatizados para roterização de

veículos. Foram analisados somente trabalhos teóricos publicados, dos quais apenas alguns se

referiam aos casos reais, com resultados efetivamente alcançados na prática.

Utilizando análise de regressão, Sutcliffe e Board tentam correlacionar o benefício

atingido com as características dos problemas resolvidos. Os autores concluem que quanto

mais complexo o problema (por exemplo, maior número de clientes, veículos e rotas, e a

presença de janelas de tempo), maior o benefício alcançado.

Como benefícios principais, os autores apontam:

• A obtenção de rotas mais curtas e mais rápidas

• Menor número de veículos empregados

• Menores custos

Outros benefícios apontados são:

• A empresa torna-se menos dependente da pessoa responsável pela roteirização

(roteirista)

• Aumento da produtividade do roteirista em relação ao processo manual

• Melhoria do processo de registro das operações efetuadas

• Promoção de uma melhor compreensão do processo de roteirização

• Melhor controle da função de transporte na empresa

• Capacidade de se efetuar análises de sensibilidade

• Capacidade de se testar hipóteses (“what-if”)

• Capacidade de decidir entre operar uma frota própria ou contratar frota de

terceiros

• Benefícios para os motoristas (programação de horários adequados)

• Benefícios para os clientes (melhor nível de serviço)


©Copyright 2006

70

Se a informatização do procedimento de roteirização parece justificável, então se

poderia simplesmente utilizar um pacote comercial de roteirização, ou apenas alterar algum

algoritmo existente para contemplar a estrutura de dados particular do problema a ser

resolvido. Essa alternativa foi estudada por Golden, Bodin e Goodwin (1986), que analisaram

os pacotes comerciais disponíveis para utilização em microcomputadores. Os autores

concluem que os softwares de roteirização podem gerar grandes economias, mas que há um

grande campo a ser pesquisado, pois muitas necessidades e problemas específicos não são

bem tratados pelos pacotes existentes, demandando soluções específicas. Rosseau (1988), e

Assad (1988) também comentam a necessidade de soluções específicas para cada tipo de

problema.

Essa necessidade de soluções específicas surge da grande variedade de problemas e das

características específicas de cada problema, conforme será visto na classificação dos

problemas de roteirização. Bodin et al. (1983) comentam a esse respeito que a maioria dos

problemas de roteirização compartilha objetivos comuns (como redução de custos, redução de

frota, etc), mas que as diferentes características e hipóteses de cada problema levam a

diferentes modelagens, com diferentes métodos de resolução.

2.2. Dificuldade de se resolver problemas práticos de roteirização e o uso de heurísticas

Segundo Lenstra e Rinnooy Kan (1981), quase todos os problemas de roteirização e

programação de veículos são NP-hard, ou seja, não se conhece um algoritmo para sua solução que possa

ser resolvido em tempo polinomial.

Como o VRP por si só é NP-hard (Lenstra e Rinnoy Kan, 1981), a incorporação de

restrições para tornar o problema modelado mais próximo do problema real só vem aumentar

a complexidade do modelo e de um algoritmo de solução. Por um lado é óbvio que a modelagem

matemática de um problema deve incorporar os aspectos relevantes do mesmo, tornando o

modelo o mais próximo possível da realidade. Por outro lado, isso pode se tornar inútil, já que

um modelo mais próximo da realidade não garantirá a existência de um procedimento que

gere soluções melhores.

Em função disso, muitas vezes a aplicação de métodos de solução exata é inviável,

sendo freqüente a utilização de algoritmos do tipo heurístico para a resolução de problemas de

roteirização mais complexos (Christofides, Mingozzi e Toth, 1979; Magnanti, 1981; Bodin et

al.., 1983; Golden e Assad, 1986; Solomon e Desrosiers, 1988; Haimovich, Rinnooy Kan e

Stougie, 1988; Ballou, 1989; Powers, 1989; Bodin, 1990; Cunha, 2000).


©Copyright 2006

71

2.3. Aplicação do enfoque sistêmico

Pela grande diversidade de problemas de roteirização existente, pela dificuldade de se

resolver problemas de roteirização com características próximas das encontradas na prática,

pela necessidade de se gerar procedimentos informatizados e pela especificidade desses

procedimentos para cada tipo de problema, é de fundamental importância que se compreenda

profundamente o problema a ser resolvido.

Conforme progridem os estudos a respeito dos métodos de solução para os problemas

de roteirização, problemas cada vez mais complexos vão sendo estudados, incorporando

novas restrições e características que tornam esses problemas bastante específicos e

singulares, sendo difícil enquadrá-los ou caracterizá-los como um tipo determinado de

problema.

Nesse cenário pode ser útil, portanto, elaborar um roteiro que permita ajudar na

determinação dos parâmetros e variáveis que interferem nos problemas de roteirização.

O Enfoque Sistêmico se configura uma metodologia adequada na fase de compreensão

dos diversos problemas de roteirização, servindo de guia para a identificação dos

componentes do problema, dos aspectos relevantes, das restrições, enfim, da identificação dos

fatores que serão mais importantes para a proposição de um método de solução adequado.

O Enfoque Sistêmico pode ser ainda mais útil considerando que os problemas mais

complexos são resolvidos por meio de heurísticas. Nesse caso, pela própria essência dos

métodos heurísticos, é de vital importância a compreensão da natureza do problema e dos

aspectos que influenciam a obtenção de soluções e a qualidade das mesmas, o que pode ser

facilitado pela utilização do Enfoque Sistêmico.

3. CLASSIFICAÇÃO DE PROBLEMAS DE ROTEIRIZAÇÃO DE VEÍCULOS

3.1. Parâmetros que caracterizam um problema de roteirização

Antes de se pensar na classificação dos problemas de roteirização, devemos

inicialmente estudar os diversos parâmetros e fatores que caracterizam e afetam esses

problemas, nas suas diversas formas.

Os problemas de roteirização de veículos podem ser classificados em diversas

categorias e tipos. Os vários problemas diferem entre si em aspectos relacionados ao tipo de

operação, ao tipo de carga, ao tipo de frota utilizada, à localização dos clientes, ao tipo de

restrições, ao tipo de função objetivo e vários outros fatores relacionados adiante.


©Copyright 2006

72

A seguir serão relacionados alguns dos principais parâmetros que caracterizam os

problemas de roteirização (Bodin e Golden (1981), Bodin et al.. (1983), Assad (1988) e

Ronen (1988)):

• Operação de coleta

• Operação de entrega

• Coleta e entrega simultaneamente

• Coleta (ou entrega) com carga de retorno

• Carga de um único tipo

• Cargas de vários tipos

• Cargas que demandam veículos especiais

• Demanda determinística

• Demanda estocástica

• Demanda localizada somente em arcos

• Demanda localizada somente em nós

• Demanda localizada em arcos e nós

• Restrições junto aos clientes

• Necessidade ou não de atender toda a demanda

• Existência de clientes com prioridade

• Existência de janelas de tempo

• Tempo máximo permitido para carga/descarga

• Necessidade ou restrição de serviço em algum dia específico da semana

• Frota com um único veículo

• Frota com mais de um veículo

• Frota com mais de um veículo e todos do mesmo tipo

• Frota com mais de um veículo e com mais de um tipo de veículo

• Veículos especiais (dedicados a um ou mais tipos específicos de carga)

• Veículos localizados em um único depósito

• Veículos localizados em mais de um depósito

• Restrições de autonomia dos veículos

• Capacidade de carga do veículo

• Tipo de carga do veículo

• Tipo de carga e descarga do veículo


©Copyright 2006

73

• Duração da jornada de trabalho

• Horários de almoço

• Horários de pausa

• Permissão para viagens com mais de um dia de duração

• Número de tripulantes por veículo

• Pagamento dos tripulantes por jornada de trabalho

• Pagamento dos tripulantes por produtividade

• Pagamento dos tripulantes por jornada de trabalho

• Pagamento dos tripulantes por jornada de trabalho e horas extras

• Estrutura de rede de transportes direcionada

• Estrutura de rede de transportes não direcionada

• Estrutura de rede de transportes direcionada e não direcionada (mista)

• Estrutura de rede de transportes euclidiana

• Duração de rotas imposta, igual para todas as rotas

• Duração de rotas imposta, diferente para todas as rotas

• Duração de rotas não imposta

• Limite de peso do veículo

• Limite de altura, largura e comprimento do veículo

• Restrições de carga e descarga

• Número de rotas permitido por veículo

• Necessidade de balanceamento da rota

• Existência de pontos de parada (descanso)

• Proibição de contornos a esquerda por questões de segurança

• Obrigatoriedade de se utilizar rotas pré-determinadas

• Custos variáveis envolvidos

• Custos fixos envolvidos

• Objetivo de minimizar custos variáveis

• Objetivo de minimizar custos fixos

• Objetivo de minimizar soma de custos fixos e variáveis

• Objetivo de minimizar duração das rotas

• Objetivo de minimizar o número de veículos necessários

• Objetivo de maximizar função de utilidade baseada no nível de serviço e/ou


©Copyright 2006

74

satisfação e/ou prioridades dos clientes

• Necessidade de balanceamento de rotas

• Objetivo de minimizar o uso de frota afretada.

Os parâmetros não se restringem aos acima citados, existindo alguns outros

relacionados a tipos particulares de problemas de roteirização. Como se vê, a quantidade de

parâmetros existentes é muito grande. Vamos discutir um poucos alguns desses parâmetros e

tentar encontrar uma maneira de agrupá-los.

A operação (ou serviço) executada no cliente pode ser de coleta ou entrega. Na

primeira, a visita ao cliente é marcada pela coleta de mercadorias ou pessoas (é o que ocorre

respectivamente na coleta de lixo e no transporte de passageiros por ônibus fretados que

levam os passageiros ao trabalho). Na segunda, a visita ao cliente é marcada pela entrega de

mercadorias ou pessoas.

A carga a ser transportada pode ser de um único tipo, ou de vários tipos. A frota

utilizada no transporte pode ser composta por um único veículo ou por vários veículos. Os

veículos empregados podem ser todos iguais, ou podem ter capacidades, desempenhos, custos

fixos e custos operacionais diferentes. Os veículos podem carregar um único tipo de carga ou

podem levar vários tipos. Os veículos podem ser guardados (ou consertados, abastecidos, etc)

em um único depósito, ou então podem escolher entre vários depósitos existentes.

Os clientes podem estar localizados de maneira dispersa ou ao longo das vias de

transporte (por exemplo, é o que ocorre respectivamente na entrega urbana de encomendas e

na entrega urbana de cartas). Além disso, os clientes podem exigir condições de serviço

diversas, por exemplo, que sejam visitados num determinado horário, ou que sejam visitados

por um único veículo por dia.

Diversas restrições podem ser relevantes. Por exemplo, restrições da via ao veículo,

como limite de peso permitido e altura máxima; ou proibições de conversões à esquerda em

entregas urbanas, por razões de segurança de trânsito.

O objetivo a ser atingido na resolução do problema também pode variar. Por exemplo,

pode-se desejar diminuir os custos fixos, operacionais ou totais. Ou pode-se tentar otimizar

uma função de custo que incorpore também a satisfação do cliente.

Podemos agrupar alguns desses parâmetros em categorias que permitam uma melhor

visualização como, por exemplo, o agrupamento sugerido adiante:


©Copyright 2006

75

• Tipo de operação

• coleta

• entrega

• coleta e entrega simultaneamente

• coleta (ou entrega) com carga de retorno

• Tipo de carga

• única

• múltiplas cargas

• necessidade de veículo especial para efetuar o transporte

• Tipo de demanda

• determinística

• estocástica

• Localização da demanda

• demanda localizada somente em arcos

• demanda localizada somente em nós

• demanda localizada em arcos e nós

• Restrições junto aos clientes

• necessidade ou não de atender toda a demanda

• existência de clientes com prioridade

• existência de janelas de tempo

• tempo máximo permitido para carga/descarga

• necessidade ou restrição de serviço em algum dia específico da semana

• Tamanho da frota

• um único veículo

• vários veículos

• Tipo de frota

• homogênea

• heterogênea

• veículos especiais (dedicados a um ou mais tipos específicos de carga)

• Localização dos veículos

• em um único depósito

• em vários depósitos


©Copyright 2006

76

• Restrições dos veículos

• com relação à autonomia de cada veículo

• com relação à quantidade de carga

• com relação ao tipo de carga

• com relação à operação de carga e descarga

• Jornada de trabalho

• duração

• horário de almoço e outras interrupções

• permissão para viagens com mais de um dia de duração

• Número de tripulantes por veículo

• Pagamento dos tripulantes

• por jornada de trabalho

• por produtividade

• jornada e horas extras

• Estrutura da rede

• direcionada

• não direcionada

• mista

• euclidiana

• Duração de rotas

• imposta, igual para todas as rotas

• imposta, diferente para cada rota

• não imposta

• Restrições aos veículos

• limite de peso do veículo

• limite de altura, largura e comprimento do veículo

• restrições de carga e descarga

• número de rotas permitido por veículo

• Outras restrições

• necessidade de balanceamento da rota

• existência de pontos de parada (descanso)

• proibição de contornos a esquerda por questões de segurança


©Copyright 2006

77

• obrigatoriedade de se utilizar rotas pré-determinadas

• Estrutura de custos

• custos variáveis

• custos fixos

• Objetivos

• minimizar custos variáveis

• minimizar custos fixos

• minimizar soma de custos fixos e variáveis

• minimizar duração das rotas

• minimizar o número de veículos necessários

• maximizar função de utilidade baseada no nível de serviço e/ou

satisfação e/ou prioridades dos clientes

• balanceamento de rotas

• minimizar o uso de frota fretada

Como se vê, a grande quantidade de parâmetros dificulta o entendimento, ordenação e

classificação dos diversos problemas de roteirização que ocorrem na prática.

A seguir será visto como os problemas de roteirização são classificados em função dos

diversos parâmetros aqui relacionados.

3.2. Classificação e descrição dos principais problemas de roteirização de veículos

Os problemas de roteirização são classificados em três categorias principais (Bodin e

Golden, 1981; Bodin et al., 1983):

• Problemas de Roteirização de Veículos, onde não há restrições temporais por

parte dos clientes (ou seja, não há nenhum horário pré-estabelecido), nem relações de

precedência entre os clientes (ou seja, nenhum cliente precisa ser atendido

especificamente antes ou depois de algum determinado cliente). Num problema desse tipo

apenas os aspectos espaciais são levados em consideração, e o objetivo é construir um

conjunto de rotas viáveis e de menor custo.

• Problemas de Programação de Veículos, quando a definição das rotas deve levar

em consideração horários pré-estabelecidos para cada atividade a ser executada (horário

limite para chegada e nos pontos de demanda, horário limite para saída dos pontos de


©Copyright 2006

78

demanda, ou também o instante programado para outras tarefas como, por exemplo,

horário de saída do depósito, parada para reabastecimento, etc). Nesse tipo de problema, a

elaboração das rotas leva em consideração, além dos aspectos espaciais dos problemas,

também os aspectos temporais.

• Problemas Combinados de Roteirização e Programação de Veículos, quando

existe algum tipo de restrição de precedência e/ou janela de tempo. Relações de

precedência ocorrem, por exemplo, quando a entrega de uma mercadoria deve ser

precedida pela sua coleta. Janelas de tempo são restrições horárias normalmente

associadas ao intervalo desejado para que um dado serviço seja executado num cliente.

Podem existir outros tipos de janela de tempo, como, por exemplo, o intervalo de tempo

que um veículo fica disponível, ou o intervalo de tempo em que o depósito (ou depósitos)

fica disponível aos veículos. Em problemas combinados tanto os aspectos espaciais

quanto temporais são levados em consideração. Segundo Bodin e Golden (1981) os

problemas que ocorrem na prática normalmente estão nessa categoria.

A classificação de um problema específico leva em consideração os parâmetros citados

anteriormente. Em cada uma dessas três categorias encontramos alguns problemas típicos,

com formulações propostas, e eventualmente com algoritmos de solução já desenvolvidos.

Como se pode perceber pela grande quantidade de parâmetros, nem todas as

combinações possíveis leva a um problema já abordado na literatura, para o qual já exista uma

modelagem proposta, e para o qual já tenha sido desenvolvido algum algoritmo de solução.

A seguir serão descritos alguns problemas típicos de cada uma das três categorias

principais de problemas de roteirização de veículos de acordo com Bodin et al. (1983). Na

categoria de problemas combinados foram acrescentados alguns problemas descritos por

Solomon e Desrosiers (1988), que descrevem uma série de problemas de roteirização com

restrições temporais.

3.2.1. Problemas de Roteirização

• Problema do Caixeiro Viajante

Problema clássico, onde se procura determinar um conjunto de rotas de mínimo custo

que permitam ao caixeiro viajante (veículo) visitar os nós (clientes) de uma rede. Todos os

nós devem ser visitados uma e somente uma vez. Nesse problema não há nenhuma outra

restrição. O problema pode ser simétrico, se o custo de deslocamento for invariável com a


©Copyright 2006

79

direção, ou não simétrico, caso contrário.

• Problema de Múltiplos Caixeiros Viajantes

Extensão do problema do caixeiro viajante, onde vários caixeiros devem visitar todos os

nós da rede, saindo de uma base e retornando à mesma. Cada caixeiro deve visitar pelo menos

um nó, e cada nó deve ser visitado uma e somente uma vez.

• Problema Clássico de Roteirização de Veículos

Dado uma rede onde a cada nó está associada uma demanda conhecida, e a cada arco

está associado um custo; e dado um conjunto de veículos com restrição de capacidade, deve-

se determinar um conjunto de rotas de menor custo, atendendo à demanda de todos os nós. Os

veículos devem partir e retornar ao depósito. Esse problema é uma generalização do problema

de múltiplos caixeiros viajantes, onde se acrescenta a restrição de capacidade dos veículos.

• Problema de Roteirização de Veículos com Múltiplos Depósitos

Extensão do problema clássico de roteirização, onde os veículos devem sair e retornar a

um dos depósitos existentes.

• Problema do Carteiro Chinês

Nesse problema, dada uma rede, deve-se determinar um ciclo de custo mínimo que

permita ao carteiro (veículo) passar pelo menos uma vez por todos os arcos da rede, onde se

localizam os clientes. O problema pode ser direcionado, caso os arcos sejam direcionados;

não direcionado, caso contrário; ou misto, caso alguns arcos sejam direcionados e outros não.

• Problema de Roteirização com Demanda em Arcos

Extensão do problema do carteiro chinês, acrescentando-se restrição de capacidade para

os veículos. É semelhante ao problema clássico de roteirização, mas com demanda localizada

nos arcos ao invés dos nós.

3.2.2. Problemas de Programação

• Problema de Programação de Veículos com Um Depósito

Nesse problema define-se uma rede onde a cada nó está associada uma tarefa com ínício

e duração pré-determinada, e a cada arco pode ser associado um peso que corresponde ao

intervalo mínimo entre uma tarefa e outra. Os veículos devem partir e retornar de um único

depósito. Deve-se dividir a rede em caminhos, cada um correspondendo à programação de um

veículo, de acordo com uma função objetivo. Uma função objetivo que procure minimizar o

número de caminhos equivale à minimização do número de veículos empregados e, portanto,

equivale à minimização do custo de capital. Uma função objetivo que procure minimizar a


©Copyright 2006

80

soma total dos pesos associados a cada arco equivale à minimização do tempo de trânsito dos

veículos e, portanto, equivale à minimização dos custos operacionais. Uma função objetivo

que combine as duas anteriores tenta minimizar os custos totais.

• Problema de Programação de Veículos com Múltiplos Depósitos

Extensão do problema de programação, onde cada veículo deve partir de um dos

depósitos existentes, e retornar ao mesmo depósito.

• Problema de Programação de Veículos com Restrição de Duração de Viagem

Extensão do problema de programação acrescentando-se restrições que tentam

incorporar os limites de autonomia dos veículos. Essas restrições podem se referir ao tempo

máximo que o veículo pode ficar fora do depósito ou se referir à distância máxima que o

veículo pode percorrer antes de retornar ao depósito.

• Problema de Programação de Veículos com Múltiplos Tipos de Veículos

Extensão do problema de programação, considerando-se a existência de veículos com

diferentes características operacionais.

3.2.3. Problemas Combinados de Roteirização e Programação

• Problema do Caixeiro Viajante com Restrição de Janela de Tempo

Extensão do problema do caixeiro viajante, onde cada nó deve ser visitado numa janela

de tempo específica.

• Problema de Múltiplos Caixeiros Viajantes com Restrição de Janela de Tempo

Extensão do problema de múltiplos caixeiros viajantes, onde cada nó deve ser visitado

numa janela de tempo específica.

• Problema de Roteirização e Programação de Veículos com Restrição de Janela de

Tempo

Extensão do problema clássico de roteirização, onde cada cliente deve ser visitado numa

janela de tempo específica.

• Problema de Roteirização e Programação de Veículos com Restrição de Janela de

Tempo Flexível

Extensão do problema de roteirização e programação de veículos com restrição de

janela de tempo, porém permitindo a violação das janelas de tempo mediante pagamento de

penalidades.

• Problema de Coleta e Entrega com Restrição de Janela de Tempo (“dial-a ride”)

Extensão do problema anterior, onde se acrescenta relações de precedência entre os


©Copyright 2006

81

clientes, conforme a tarefa que o veículo executa no cliente (coleta ou entrega). Num

problema desse tipo, as cargas não são transportadas somente entre o depósito e os clientes,

mas também entre os clientes, daí surgindo a relação de precedência. A expressão “dial-a-

ride” vem de uma aplicação típica, onde os clientes telefonam requisitando a visita de um

veículo, e determinando os pontos de origem e destino, bem como os horários

correspondentes.

• Problema de Roteirização Multi-Periódica

Extensão do problema de roteirização e programação de veículos com restrição de

janela de tempo, onde os clientes devem ser visitados um determinado número de vezes

dentro de múltiplas janelas de tempo (por exemplo, entrega urbana de leite onde cada cliente

deve ser visitado três vezes por semana, sempre pela manhã).

• Problema de Roteirização e Programação com Demanda em Arcos

Extensão do problema de roteirização com demanda localizada em arcos,

acrescentando-se janelas de tempo para que os arcos sejam visitados.

• Problema de Roteirização Costeira (“shoreline”)

Semelhante ao problema de coleta e entrega com restrição de janela de tempo. A

diferença consiste em que no problema “shoreline” os veículos são embarcações, e a

distribuição espacial dos clientes tem características específicas, tipicamente encontradas na

roteirização de navios visitando vários portos ao longo da costa.

3.3. Esquema genérico de classificação para Problemas de Roteirização e Programação

de Veículos

As restrições adicionais presentes nos diversos tipos de Problemas de Roteirização

podem ser visualizadas seguindo-se o esquema de classificação para problemas de

roteirização e programação de veículos proposto por Desrochers, Lenstra e Savelsbergh

(1990).

A idéia básica dos autores é que o esquema sirva de orientação na fase inicial de

desenvolvimento de um sistema de roteirização, ou seja, durante a compreensão dos aspectos

relevantes do problema em estudo e sua modelagem. O esquema proposto, segundo os

autores, permite classificar a maioria dos modelos já considerados na literatura, servindo

como ferramenta para esclarecer a grande variedade de parâmetros existentes nos problemas

de roteirização e programação de veículos.

Os principais parâmetros abordados nesse esquema estão agrupados em quatro


©Copyright 2006

82

categorias:

• ENDEREÇOS, referente aos parâmetros relacionados aos clientes e aos

depósitos;

• VEÍCULOS, referente aos parâmetros relacionados à frota;

• CARACTERÍSTICAS DO PROBLEMA, referente aos parâmetros relacionados

à rede, ao tipo de serviço, às restrições entre endereços, às restrições entre endereços e

veículos, e às restrições entre veículos;

• OBJETIVO, referente ao tipo de otimização que se procura obter.

O esquema de classificação proposto, com algumas alterações para facilitar o

entendimento é:

CLASSIFICAÇÃO

ENDEREÇOS

• Número de depósitos

• Tipo de demanda

- localizada nos nós, arcos ou ambos

- tipo (entrega, coleta, ambas, tarefa (ex. passar por n nós))

- determinística ou estocástica

• Restrições de programação nos endereços

- sem restrições

- programação fixa

- janelas de tempo simples

- múltiplas janelas de tempo

• Restrições na seleção dos endereços

- todos endereços com demanda devem ser visitados

- um subconjunto de endereços deve ser visitado

- pelo menos um endereço em cada subconjunto deve ser visitado

- um determinado número de programações deve ser executada dentro

de um horizonte de tempo

VEÍCULOS

• Número de veículos


©Copyright 2006

83

- fixo

- variável (função das condições do problema em cada momento)

• Restrições de capacidade

- sem restrições

- veículos com capacidades iguais

- veículos com capacidades diferentes

• Restrições de carga

- sem restrições

- veículos com compartimentos de uso comum (qualquer carga)

- veículos com compartimentos dedicados

• Restrições de programação dos veículos

- sem restrições

- janelas de tempo iguais para os veículos

- janelas de tempo diferentes para cada veículo

• Restrições de duração de rotas

- sem restrições

- limites de duração iguais

- limites de duração diferentes para cada veículo

CARACTERÍSTICAS DO PROBLEMA

• Tipo de rede

- custos satisfazem (ou não) “triangle inequality”

- rede direcionada

- rede não direcionada

- rede mista

• Tipo de estratégia de serviço

divisão da demanda

- demanda não pode ser dividida (não se pode atender a demanda com mais de

uma visita)

- permissão para divisão da demanda

- a priori, antes de se iniciar o roteiro

- a posteriori, no momento da visita a um endereço (quando a demanda é

estocástica)


©Copyright 2006

84

Cargas de retorno

- não há coletas

- há coletas, sem restrição de precedência

- há coletas, com restrição de precedência (coletas só podem ser carregadas

após as entregas)

Rotas por veículo

- veículo pode fazer somente uma rota

- veículo pode fazer mais de uma rota

Origem das rotas

- rotas devem começar terminar no mesmo depósito

- rotas podem começar e terminar em depósitos diferentes

• Restrições entre endereços

- existência ou não de restrições de precedência entre endereços de entrega

e/ou coleta (ex. visitar um cliente antes de outro)

- existência ou não de restrições entre depósito e endereços de entrega e/ou

coleta (ex. cliente deve ser atendido por um certo depósito)

- existência ou não de restrições entre endereços de entrega e/ou coleta

(ex. dois clientes que precisam estar numa mesma rota)

Restrições entre endereços e veículos

- existência ou não de restrições entre veículos e depósitos (ex. veículo deve

carregar ou descarregar num certo depósito)

- existência ou não de restrições entre veículos e endereços de entrega e/ou

coleta (ex. cliente só pode ser atendido por um tipo de veículo)

Restrições entre veículos

- existência ou não de restrições entre veículos (ex. sincronização de 2 veículos

que se complementam numa entrega)

OBJETIVO

• Otimizar função incorporando custos e/ou penalidades

4. CONCLUSÕES

Este artigo teve como objetivo aplicar os conceitos de Enfoque Sistêmico para auxiliar o

entendimento e análise dos problemas de Pesquisa Operacional, em especial os problemas de


©Copyright 2006

85

roteirização de veículos.

Ao invés de focar na resposta ou estratégia de solução do problema, o primeiro passo na

tomada de decisão é o entendimento profundo do problema, para que, a partir daí, possa ser

tomada a decisão correta. O enfoque sistêmico é fundamental nesta etapa.


grande quantidade de parâmetros que podem influenciar esse tipo de problema. A adequada


mais relevantes. Esses aspectos mais relevantes devem ser considerados com maior atenção

quando da proposição de algum procedimento de solução, já que o tipo de problema e seus

parâmetros direcionam a estratégia de solução a ser adotada. Portanto, é fundamental uma

visão sistêmica do problema, primeiramente para classificá-lo corretamente e, em seguida,

identificar os parâmetros mais relevantes.

Enfocando a estrutura básica dos problemas ao invés de suas características particulares,

através do enfoque sistêmico, chega-se mais facilmente à resolução correta do problema.

Como futura pesquisa, sugere-se a aplicação do Enfoque Sistêmico em outras áreas da

Pesquisa Operacional, como também em qualquer área que exija tomada de decisões.

REFERÊNCIAS BIBLIOGRÁFICAS

ASSAD, A. Modeling and implementation issues in vehicle routing. In: GOLDEN, B.; ASSAD, A. (eds), Vehicle Routing: Methods and Studies. North-Holland, Amsterdam, p.7-45, 1988.

BALL, M.; MAGAZINE, M. The design and analysis of heuristics. Networks, v.11, n.2, p.215-219, 1981.

BERTALANFFY, L. V. Teoria geral dos sistemas. Petrópolis, Editora Vozes, 1973.

BODIN, L.; GOLDEN, B. Classification in vehicle routing and scheduling. Networks,v.11, n.2, p.97-108, 1981.

BODIN, L.; GOLDEN, B.L.; ASSAD, A., BALL, M. Routing and scheduling of vehicles and crews: The state of the art. Computers and Operations Research, v.10, n.2, 1983.

BONABEAU, Eric; DORIGO, Marco; THERAULAZ, Guy. Swarm Intelligence: From Natural to Artificial Systems. Nova York, Oxford University Press, 1999.

CHRISTOFIDES, N.; MINGOZZI, A.; TOTH, P. The vehicle routing problem. In: CHRISTOFIDES, N.; MINGOZZI, A.; TOTH, P.; SANDI, C. (eds), Combinatorial optimizations. John Wiley & Sons, New York, p. 315-337, 1979.

CHURCHMAN, C.W. Introdução à teoria dos sistemas. Petrópolis, Editora Vozes, 2a. edição, 1972.

CUNHA, C. B. Algoritmos para roteamento e programação de veículos no contexto da distribuição física. Dissertação (Mestrado) - Departamento de Engenharia de Transportes, Escola Politécnica, Universidade de São Paulo. São Paulo, 1991.

DESROCHERS, M.; LENSTRA, J. K.; SAVELSBERGH, M. W. P. A classification scheme for vehicle routing


©Copyright 2006

86

and scheduling problems. European Journal of Operational Research, v.46, n.3, p.322-332, 1990.

DORIGO, M.; STÜTZLE, T. Ant Colony Optmization. Cambridge, The MIT Press, 2004.

GUALDA, N. F. Terminais de transportes: contribuição ao planejamento e ao dimensionamento operacional. Tese (Tese Livre Docência) – Departamento de Engenharia de Transportes, Escola Politécnica, Universidade de São Paulo. São Paulo, 1995.

GOLDEN, B.; BALL, M.; BODIN, L. Current and future research directions in network optimization. Computers and Operations Research, v.8, n.2, p. 71-81, 1981.

GOLDEN, B. L.; ASSAD, A. A. Perspectives on vehicle routing: exciting new developments. Operations Research, v.34, n.5, p.803-810, 1986.

GOLDEN, B. L.; BODIN, L.; GOODWIN, T. Microcomputer-based vehicle routing and scheduling software. Computers and Operations Research, v.13, n.2/3, p.277-285, 1986.

HAIMOVICH, M.; RINNOOY KAN, A. H. G.; STOUGIE, L. Analysis of heuristics for vehicle routing problems. In: GOLDEN, B.; ASSAD, A. (eds), Vehicle Routing: Methods and Studies. North-Holland, Amsterdam, p.47-61, 1988.

LENSTRA, J.; RINNOOY KAN, A. Complexity of vehicle routing and scheduling problems. Networks, v.11, n.2, p.221-227, 1981.

MANIEZZO, V.; GAMBARDELLA, L. M.; DE LUIGI, F. Ant Colony Optimization. In: G. C. Onwubolu, B. V. Babu (eds), New Optimization Techniques in Engineering, Springer-Verlag Berlin Heidelberg, 101-117, 2004.

POWERS, R. F. Optimization models for logistics decisions. Journal of Business Logistics, v.10, n.1, p106-121, 1989.

RONEN, D. “Perspectives on pratical aspects of truck routing and scheduling”. European Journal of Operational Research, v.35, n.2, p.137-145, 1988.

ROUSSEAU, J. M. Customization versus general purpose code for routing and scheduling problems: A point of view. In: GOLDEN, B.; ASSAD, A. (eds), Vehicle Routing: Methods and Studies. North-Holland, Amsterdam, p.469-479, 1988.

SOLOMON, M. M.; DESROSIERS, J. Time window constrained routing and scheduling problems. Transportation Science, v.22, n.1, p.1-13, 1988.

SUTCLIFFE, C.; BOARD, J. The ex-ante benefits of solving vehicle-routeing problems. Journal of the Operational Research Society, v.42, n.2, p. 135-143, 1991.

http://www.idsia.ch/%7Eluca/aco2004.pdf

Documents

A importância do enfoque sistêmico para problemas de roteirização