HOME | ÍNDICE POR TÍTULO | NORMAS PUBLICACIÓN

Espacios. Vol. 37 (Nº 04) Año 2016. Pág. 17

Problemas de programação e roteamento de caminhões com restrições de horários de motoristas: Um estudo da produção científica

Problem Truck driver scheduling and routing HOS: A study of scientific production

Daiane Maria De Genaro CHIROLI 1; Hidelbrando Ferreira RODRIGUES 2; Sérgio Fernado MAYERLE 3

Recibido: 28/09/15 • Aprobado: 25/10/2015

Contenido

1. Introdução

2. Metodologia

3. Análise e Resultados

4. Estudo dos problemas de roteirização com restrições de HOS

5. Discussão dos resultados e conclusão

Referências Bibliográficas

1. Introdução

Os altos custos logísticos em uma organização podem leva-la a perda de competitividade. Deste modo, é uma área relevante e que permite oportunidades de diferenciais no mercado. Segundo Novaes (2007, p. 65) "Reduzir os custos de produção (...) é uma tarefa quase impossível em tempos atuais, pois todo mundo já vem trabalhando nessa direção há tempo (...). Por isso a necessidade de se trabalhar nos custos que fazem parte das outras partes da cadeia. Dessa maneira, seria nos processos logísticos, referentes à cadeia de suprimentos, o local onde é possível obter maior redução de custos.

Quando se trata de custos logísticos, normalmente os custos da atividade de transporte são os mais representativos (BALLOU, 2006). Com o intuito de reduzir custos operacionais no sistema logístico, o estudo de problemas de roteirização (routing) e programação (scheduling) de veículos se faz necessário, uma vez que permite aos tomadores de decisão, determinar estratégias que permitam práticas mais econômicas e eficientes em seus sistema de distribuição.

No entanto, em pesquisas sobre problemas de routing e scheduling encontra-se uma série de abordagens acerca do assunto. Destaca-se Bodin et al. (1983), referência do assunto, que apresenta a taxonomia destes problemas.

Bodin et al. (1983), destaca que o output básico de qualquer sistema de roteirização e programação é em sua essência o mesmo, onde para cada veículo ou motorista, uma rota e uma programação é fornecida. Geralmente a rota explicita a sequência de locais a ser visitado, e a programação define os tempos em que as atividades nesses locais devem ser efetuadas.

Os problemas de roteirização envolvem decisões em relação à configuração espacial e geográfica pela qual o veículo trafega, podendo estes ser divididos em três grupos de problemas: (1) roteirização pura, (2) programação de veículos, e (3) roteirização e programação.

Outras características importantes na classificação dos problemas de roteirização e programação são relacionadas ao tamanho da frota disponível, ao tipo de frota, garagem dos veículos, à natureza da demanda, à localização da demanda, à características da rede, às restrições de capacidade dos veículos, aos requisitos de pessoal, aos tempos máximos de rotas, ao tipo de operação, aos custos, objetivos e outras restrições (Bodin et al.,1983; Assad,1991; Ronen, 1998; Desrochers et al., 1990; e Laporte et al., 2000).

Tais características permitem determinar a escolha da técnica a ser utilizada no problema em questão, sendo muitas consolidadas, entre elas se destacam o Problema do Caixeiro Viajante (PCV), PCV Múltiplos e com restrição de janela de tempo, Problema de Programação de Veículos com Um Depósito e com Múltiplos Depósitos, Problema de Programação de Veículos com Restrição de Duração de Viagem, PCV com Restrição de Janela de Tempo, entre outros (BODIN et al., 1983; CHIH, 1987; CASCO et al.,1988; BOSE, 1990; ASSAD, 1991; CUNHA, 1997; PELIZARO, 2000; LAPORTE, 2000; NARUO, 2003; ENOMOTO, 2005)..

Embora exista uma literatura significativa para os problemas roteirização e programação de veículos, e que avaliem conjuntamente tanto as condições espaciais quanto as temporais do problema, avaliando as precedências entre as atividades, poucos trabalhos incorporam em seus roteiros os tempos realistas relacionados as horas de serviço (HOS), ou seja, não consideram no roteiro e na programação os tempo específicos de paradas para refeição, descanso, descanso diário e semanal dos motoristas.  Estas restrições foram incorporadas a partir de regulamentações de tempo de serviço do motorista profissional, e introduzidas em alguns países tais como Estados Unidos, Austrália, Canadá e no continente Europeu. O objetivo da inserção destas leis é de obter controle sob a jornada de trabalho de motoristas profissionais, visando mitigar graves problemas sociais e relacionados à saúde do motorista e à segurança no trânsito.

Deste modo, embora exista uma vasta lista de pesquisas sobre problemas de roteirização e programação de veículos, são restritas pesquisas que abordam especificamente sobre problemas relacionados a legislação de motoristas de caminhão. O primeiro trabalho que considerou explicitamente restrições de horário de refeição e descanso noturno foi o de Savelsberg e Sol (1998). No entanto, o trabalho pioneiro a tratar especificamente sobre a questão de programação e roteirização de caminhões, seguindo as restrições de tempo de serviço impostas pela legislação vigente nos Estados Unidos (EUA) foi o de Xu et al. (2003).

No Brasil, em 2012 foi aprovada a Lei No. 12.619, também conhecida por "Lei dos motoristas". Em março de 2015 esta lei foi revogada, passando a vigorar a Lei No 13.103 de 2 de março de 2015. Este ato legislativo alterou a Consolidação das Leis Trabalhistas (CLT) de modo a regular e disciplinar a jornada de trabalho dos motoristas profissionais, estipulando o tempo máximo de direção no dia de trabalho e intervalos para descanso do motorista, com a criação de jornada especial de trabalho. Com o advindo das novas restrições impostas pela legislação as empresas de frete passaram a enfrentar um problema com relação ao aumento no custo do frete, que cresceu cerca de cresceu 7,6%. 

Neste contexto, as organizações devem planejar o tamanho e variedade da frota, envolvendo rotas, programação de veículos, tripulação relacionada com os mesmos, entre outros fatores. Sendo assim, muitas empresas do seguimento, tem reivindicado melhorias na lei, pois com as restrições impostas, houve impactos no tempo de viagem, queda de produtividade, aumento da remuneração dos motoristas fazendo com que as adaptações operacionais e financeiras sejam refletidas no valor do frete e no serviço ofertado.

Diante desta lei e visando trabalhar com problemas de roteirização e cronograma de motoristas, de acordo com a legislação brasileira, se faz necessário ler e revisar a literatura acadêmica na área de interesse, pois como destaca Croom (2009), estas variam no grau de detalhamento, abrangência e complexidade e fornecem uma base sólida para desenvolver novos conhecimentos no campo de estudo.

Deste modo, o presente trabalho objetiva quantificar e avaliar estudos publicados sobre o tema scheduling e roteamento de caminhões com restrições de horário de trabalho (HOS). Também visa identificar a elite de pesquisa, objetivos estudados pelos pesquisadores e métodos utilizados.

Assim, este estudo permitirá obter as publicações que abordam aplicações de roteirização e programação de veículos com restrições de horário de trabalho (HOS), a nível internacional. O estudo se mostra relevante pelo fato de apresentar o que tem sido desenvolvido nesta área de pesquisa até o presente momento; e por poder despertar novos olhares para esta temática, principalmente, pelo fato do Brasil ter revogado uma lei que impõe que as empresas trabalhem considerando fatores específicos a jornada de trabalho do motorista.

Este artigo está estruturado em 5 seções. Na seção 2 apresenta-se o contexto metodológico aplicado na pesquisa, onde realizou-se revisão sistemática e bibliometria para análise de conteúdo. Na seção 3 apresenta a análise dos resultados da pesquisa bibliométrica. Na seção 4 são apresentadas os estudos dos problemas de roteirização e programação com restrições de HOS. E, por fim, na seção 5 traz a discussão dos resultados e as conclusões.

2. Metodologia

Esta pesquisa é classificada como pesquisa exploratória, que tem a finalidade de familiarizar o pesquisador com o problema com a intenção de torná-lo explicito ou ajudar a construir hipóteses (SIENA, 2007). O procedimento técnico utilizado para esta revisão é classificado por revisão sistemática.

A Revisão Sistemática é uma forma de pesquisa que utiliza como fonte de dados a literatura sobre determinado tema. Esse tipo de investigação disponibiliza um resumo das evidências relacionadas a uma estratégia de intervenção específica, mediante a aplicação de métodos explícitos e sistematizados de busca, apreciação crítica e síntese da informação selecionada. As revisões sistemáticas são particularmente úteis para integrar as informações de um conjunto de estudos realizados separadamente [...] (SAMPAIO e MANCINI, 2007, p.84).

Neste contexto, a análise sistêmica, permite ao pesquisador identificar títulos, autores, objetivos, constructos e conceitos, metodologias, resultados e recomendações futuras nos artigos selecionados na base de dados (FERENHOF et al, 2012).

Para realizar a revisão desenvolveu-se o protocolo de Estudo de Revisão Sistemática. O principal objetivo desta revisão sistemática é quantificar e avaliar os estudos publicados sobre o tema programaçãoe roteamento de caminhões com restrições de horário de trabalho.

O processo de busca consistiu de pesquisas em bases de dados disponíveis na internet, utilizando um conjunto de palavras-chave associadas ao tema. A partir do material encontrado, fez-se uma triagem para identificar a coerência com o objetivo da pesquisa. Considerou-se o título e o resumo da publicação como forma de classificação inicial. Neste processo de filtragem avaliou se não haviam artigos repetidos, o alinhamento com o tema da pesquisa e o reconhecimento científico. Foram excluídos da listagem estudos que somente citavam os termos pesquisados ou que não se relacionavam de alguma forma com o objetivo maior do trabalho.

Para a busca por arquivos pertinentes ao trabalho utilizou-se das seguintes palavras-chave: "Truck driver scheduling", "Driver scheduling", "Vehicle scheduling", "Hours of service regulations truck driver".

No Quadro 1 é apresentado o protocolo de pesquisa desenvolvido para o planejamento do estudo. A pesquisa sistemática trabalha dentro de uma perspectiva qualitativa, pois se analisam o alinhamento dos artigos com o enfoque do objetivo da pesquisa. Porém, no contexto da pesquisa também há um ponto de vista quantitativo que se relaciona ao estudo bibliométrico.

A análise bibliométrica é uma técnica para o mapeamento dos principais autores, periódicos e palavras-chave sobre determinado tema, mede os índices de produção e disseminação do conhecimento científico (ARAÚJO, 2006). Permite levantar o que já foi publicado e mapear quem escreveu e o que já foi escrito, o que gera uma sustentação para o desenvolvimento de novos trabalhos. A bibliometria também possibilita a identificação de quais são os principais trabalhos publicados sobre o tema (URIONA, et al., 2010).

Quadro 1 – Apresentação do protocolo de pesquisa.

Fonte: os autores

3. Análise e Resultados

Na primeira etapa do processo de busca de artigos brutos, fez-se a seleção do portfólio bibliográfico de artigos de acordo com o tema da pesquisa, somente pelas palavras-chaves. Não houve recorte temporal na pesquisa, pois se desejou abranger todas as pesquisas relacionadas ao assunto e suas origens, deste modo todos os artigos selecionados foram analisados.

Na seleção do portfólio bibliográfico de artigos, de acordo com o tema da pesquisa, encontrou-se 72.478 artigos brutos. Por meio destes resultados se fez a estratificação, a fim de identificar os artigos mais relevantes. Neste processo a classificação dos artigos se deu por meio da leitura dos títulos, dos quais 105 artigos foram selecionados.

Com o resultado da primeira triagem (105 artigos), iniciou-se a segunda etapa, ou seja, fez-se a leitura dos resumos e dos artigos em sua totalidade. Com esta estratificação, 28 trabalhos foram separados como relevantes. Estes artigos foram classificados de acordo com a quantidade e ano de publicação, onde é possível observar que foi em 1998 que houve a primeira publicação sobre o tema de pesquisa. Na Figura 1, é apresentado o número de publicações referente ao tema pesquisado, por ano de publicação.

Figura 1: Números de Publicações referentes a problemas de roteirização relacionados a HOS

Fonte: os autores

Por meio da Figura 1, é possível visualizar que foi a partir de 1998 que iniciou a publicação de trabalhos referentes a problemas de programação e cronograma de motoristas. Porém, tem-se em destaque os anos de 2009 e 2011, para os quais ocorreu a maior quantidade de publicações, 8 e 5 artigos, respectivamente.

O próximo diagnóstico foi relacionado aos autores que mais publicaram sobre o assunto. Por mais que alguns artigos possuam mais de um autor, nesta análise observou-se a quantidade publicada individualmente. Na Figura 2, estão inseridos os 31 autores identificados, sobretudo os 4 autores mais profícuos. São eles: Goel (17), Savelsbergh e Kok (3), Archetti, Drex e Rousseau (2) e Kok (4).

Figura 2: Perfil de autoria

Tem-se que o principal pesquisador da área é Asvin Goel (Goel, A.), que escreveu 17 artigos relacionados a roteirização e regulamentação, aplicando suas metodologias em países como Canadá, Austrália, Estados Unidos e na União europeia.

Com relação às pesquisas, constata-se que com relação ao título/tema dos trabalhos, todos são similares. No entanto, os métodos utilizados diferem entre si. Por meio da revisão sistemática houve a análise dos objetivos e métodos. Também se observou nos estudos que busca-se definir a priori o roteiro e, a partir desta rota, busca a definição de onde seriam os locais para a realização de paradas. No Quadro 3 se apresenta os objetivos de cada trabalho, bem como sua metodologia e local de pesquisa. Na próxima seção é apresentado um resumo sobre os principais problemas encontrados na literatura.

Quadro 3 – Resumo de cada trabalho: objetivos, metodologia e local de pesquisa

Fonte: Elaborado pela autora

4. Estudo dos problemas de roteirização com restrições de HOS

Savelsbergh e Sol (1998) consideraram um problema no qual os intervalos de almoço e descanso noturno devem ser realizados sem intervalos de tempo fixos. Porém, um dos primeiros trabalhos discorridos sobre a questão de programação e roteirização de caminhões seguindo as restrições de tempo de serviço (HOS) impostas pela legislação vigente nos EUA foi o de Xu et al (2003).

Xu et al (2003) trabalharam com problemas reais de coletas e entregas de mercadorias (PPDP). Consideraram utilizar vários tipos de veículos disponíveis para atender as múltiplas ordens de coleta e entrega dentro de certa janela de tempo. Evidenciaram que cada viagem realizada pelos veículos deve cumprir as regras de trabalho dos motoristas prescritos pelo Departamento de Transporte dos EUA. Consideraram também a compatibilidade dos veículos com as ordens de entrega e relações de precedência relacionada à carga e descarga dos caminhões. O objetivo do trabalho é determinar quantos veículos cada operadora deve usar, de modo a estabelecer uma viagem viável para cada veículo a ser utilizado, e que todos os pedidos sejam enviados a um custo mínimo. No problema, analisaram a existência de várias operadores e vários tipos de veículos disponíveis para cobrir um conjunto de ordens de coleta e entrega, onde cada um desses fatores possuem várias janelas de tempo de coleta e múltiplas janelas de tempo de entrega. Utilizaram o algoritmo de Dijkstra para resolver o problema do caminho mais curto, para posteriormente determinar os subproblemas de otimalidade. Avaliaram um conjunto de restrições de compatibilidade, entre elas: (a) quais seriam as ordens que não podem ser cobertas por qual tipo de veículo, (b) sequenciamento de carga e descarga, com restrições de precedência. Utilizaram também relaxação linear usando algoritmo exato de programação dinâmica para resolver subproblemas de otimalidade. Note-se que através desta abordagem, a rota é fixada previamente, e somente depois disto é que programação das paradas e demais exigências da lei são consideradas.

Em um dos primeiros trabalhos publicados sobre o tema, Goel e Gruhn (2006) descrevem o regulamento das Horas de Serviço na União Europeia e apresentam o problema de roteirização de veículos com horário de trabalho dos motoristas (VRPDWH). Generalizam o problema de roteamento de veículos conhecido com janelas de tempo, utilizando como método de busca a técnica Large Neighboorhood Search.

Shah (2008) desenvolveu um trabalho sobre um problema de programação de motoristas e roteirização de caminhões com tempo dependente das horas de serviços regulamentadas pela legislação Federal Motor Carrier Safety Administration (FMCSA). O autor evidencia sobre a necessidade de estabelecer um modelo de modo a reduzir os custos de empresas transportadoras. O objetivo do trabalho é minimizar o tempo total requerido para servir um determinado número de clientes. Os componentes do tempo total são o tempo de viagem, tempo de parada, tempo e serviço de espera e tempo nas localidades em que se encontram os clientes. O trabalho foi desenvolvido utilizando a metaheurística Simulated Annealing (SA), e consistiu em duas fases principais denominadas de fase de inicialização e de aperfeiçoamento. Os resultados experimentais utilizando SA mostraram que a heurística proporcionou soluções de boa qualidade em tempo de computação razoável. Novamente aqui, a rota é fixada a priori.

Archetti e Savelsbergh (2009) também escreveram sobre o problema de programação de viagem considerando o regulamento de horas de serviço (HOS) dos Estados Unidos. Os autores evidenciam sobre a necessidade de planejamento destas viagens de modo a programar adequadamente o tempo de serviço dos motoristas. Consideraram múltiplas janelas de tempo, tanto na coleta como nos locais de entrega, ponderando uma função de custos complexos (custos fixos, custos por quilometragem, custos de espera e custos de parada). O algoritmo para o problema de programação de viagens foi intitulado por SMARTRIP. O principal componente do algoritmo é uma busca para trás, através da viagem que começa a partir do último local (destino), constrói um caminho respeitando as janelas de expedição, os limites de tempo na direção e tempo de serviço em que os descansos são tomados o mais tarde possível. Se, realizando esta busca for alcançado o primeiro local (origem), o cronograma é viável por simplesmente percorrer o caminho construído na direção oposta. Archetti e Savelsbergh (2009) provam que o algoritmo com o tempo encontra uma programação viável para o roteamento de motorista de caminhão. Esta abordagem pode ser utilizada para determinar os horários de controle do caminhão na presença de múltiplas janelas de tempo.

Goel (2009) destaca que, quando devem ser considerados os regulamentos sobre as horas de trabalho dos motoristas, não é fácil programar a roteirização e programação dos condutores. A complexidade de se considerar regulamentação sobre o tempo de trabalho dos condutores decorre do fato de que, os diferentes planos de trabalho têm impactos diferentes sobre as atividades futuras e devem ser programadas de acordo com os regulamentos e restrições de janela de tempo. Tanto em Goel (2009a) como em Goel (2009b) no problema de agendamento de motorista é descrito um algoritmo de complexidade , onde  é número de locais a serem visitados, com programações para o período de uma semana de calendário, onde cada local deve ser visitado dentro de uma das várias janelas de tempo, se, a distância entre essas janelas de tempo for de pelo menos 10 horas. Também exibe uma heurística gulosa para a programação de direção e horas de trabalho de motoristas de caminhão para o planejamento de horizontes de mais de uma semana. Neste trabalho Goel utiliza a busca em profundidade, e apresenta as condições necessárias para obtenção de uma solução viável. Também estabelece alguns lemas, ou seja, hipóteses simplificadoras para geração de horários, e, para tal, utiliza o conceito de pseudo-viabilidade. De início programou atividades de um único caminhão, único motorista em uma semana de trabalho, depois apresentou como se pode realizar o agendamento de trabalho sem estas considerações. Mostrou que cada programação pseudo-viável pode ser transformada em uma agenda viável através do aumento da duração dos períodos de repouso e redução da duração de períodos ociosos subsequentes.

Prescott-Gagnon et al., (2010) articulam sobre a introdução de um algoritmo Large Neighborhood Search (LNS) para Problemas de Roteirização de Veículos com Restrições de Janela de Tempo para HOS de motoristas (VRPTWDR) segundo as leis europeias. Propuseram uma heurística híbrida que combina a busca local e programação matemática para resolver o problema integrado de construção de rotas de veículos que respeitem janelas de tempo e todas as regras de motoristas ditadas pelo regulamento; consideraram que as paradas e descansos não podem interromper o serviço ao consumidor. Para desenvolver o algoritmo, utilizaram uma heurística de geração de colunas para explorar a vizinhança, onde as colunas são geradas por busca tabu, e uma heurística que verifica a viabilidade das rotas. Testaram o método de solução global no método de inserção de Solomom modificados e relataram que os resultados computacionais se mostraram eficientes. Dessa forma, a contribuição do artigo foi o desenvolvimento de um procedimento heurístico eficiente para avaliar a viabilidade de uma rota depois da introdução de um consumidor.

Staes (2011) também apresenta métodos que incluem a legislação europeia relativa a regras de motorista para o problema de roteamento de veículos. Neste trabalho, o autor pesquisa sobre problemas de programação de veículos sob duas vertentes, sendo a primeira relacionada aos métodos de roteamento que podem ser trabalhados de modo a incluir a legislação europeia de motoristas; e a segunda está na consideração de restrições que adiciona caminhões com vários compartimentos de acordo com a demanda dos clientes para dois produtos heterogêneos. Isto é feito através da utilização de uma abordagem dinâmica chamada de programação restrita, que permite uma adição relativamente fácil de restrições para o problema de roteamento de veículos. Esta abordagem foi sugerida por Kok et al. (2010), e expandida por Staes (2011), o qual incorporou mais restrições aos problemas VRPTW, apresentando melhorias no método.

Em Goel (2009c) aborda-se sobre o problema de programação de viagens realizada por dois motoristas, sob regulamento da união europeia. O autor identifica algumas propriedades estruturais do problema de programação de motorista de caminhão e apresenta um algoritmo de busca em profundidade, inserção de lemas e de pseudo-viabilidade, por meio do aumento de duração dos períodos de repousos e redução de períodos ociosos, que são critérios de dominância, que permite reduzir o tamanho do espaço de busca do problema. O autor apresenta experiências computacionais, e mostra que o algoritmo de busca em profundidade proposto, pode encontrar horários viáveis em tempo muito curto.

Goel e Kok (2009a) apresentam algoritmos mais eficientes que são capazes de encontrar horários viáveis de motorista de caminhão em tempo . Destacam que os métodos desenvolvidos por Archetti e Savelsbergh (2009) e Goel e Kok (2009) não pode ser usado para o caso da União Europeia. Para melhor adequar as condições legais da União Europeia, os autores utilizaram os conceitos de pseudo-viabilidade, como os descritos em Goel (2009c) na forma normal. Os autores apresentaram o algoritmo de busca Depth-First-Breadth-Second (DFBSS) que utiliza os critérios de dominância de pseudo-viabilidade. Com o estudo, mostraram que para o caso da União europeia, onde alguns limites normais de tempo de condução podem ser ultrapassados, o algoritmo DFBSS pode ser resolvido sem aumentar a complexidade.

Goel (2010a) aborda sobre o regulamento de motorista de caminhões na Austrália, e apresenta várias heurísticas para o cronograma de horas de trabalho de caminhoneiros australiano. Definiu critérios para a pseudo-viabilidade e de uma forma normal, que fornece orientação de resolução do problema. Goel e Kok (2010) denominam o problema de agendamento do horário de trabalho dos condutores de transporte rodoviário de mercadorias nos Estados Unidos por US-TDSP. Os autores utilizaram um método de busca em profundidade de modo a encontrar um cronograma viável para cumprir os prazos normais de condução diária. Apresentaram um método em que o US-TDSP resolve o problema de janela de tempo individuais num tempo . Empiricamente mostram que, para uma ampla gama de situações problemáticas que não satisfazem essa propriedade, o esforço computacional exigido pelo algoritmo não aumenta significativamente. Goel e Kok (2010) adotam os critérios de pseudo-viabilidade semelhantes aos trabalhos de Goel (2009a, 2009b, 2009c, 2009d e 2010), porém generalizados a múltiplas janelas de tempo.

Goel e Rousseau (2011) abordam sobre o problema canadense de roteirização de caminhões, o qual visa determinar se uma sequência de localizações podem ser visitadas dentro de uma dada janela de tempo de maneira que as atividades de dirigir e trabalhar realizadas pelos caminhoneiros esteja compatível com as regulamentações canadenses de horas de direção e serviço. As regulamentações canadenses contemplam as condições encontradas nas regulamentações estadunidenses de horas de serviço, adicionando restrições referentes a tempo máximo de direção e tempo mínimo de folga em cada dia. No modelo proposto, denominado por CAN-TDSP, foram apresentadas duas heurísticas ou caminhos exatos para solucionar o problema canadense de roteirização de caminhões. Os experimentos computacionais demonstram uma efetividade nos caminhos propostos e indicam que as regulamentações canadenses são significantemente mais permissiva que as regulamentações americanas.

Em Goel (2012a), é apresentado o estudo do problema de programação de motorista com duração mínima (The Minimum Duration Truck Driver Scheduling Problem - MD-TDSP), onde o autor descreve um modelo genérico, no qual estuda a localização de áreas de descanso adequados. O objetivo é programar um motorista de caminhão com duração mínima. Para regulamentos canadenses, Goel (2012b) apresenta uma formulação de programação inteira mista e uma abordagem de programação dinâmica que pode ser usado para minimizar a duração do cronograma. O método utilizado determina se um cronograma de cumprimento dos regulamentos canadenses existe ou não, e garante encontrar um cronograma que termina o mais cedo possível, se um cronograma factível existe. Os autores afirmam que o modelo apresentado é muito flexível e pode ser configurado para considerar diferentes conjuntos de regras impostas pelos regulamentos governamentais e finalmente demonstram sua eficácia nos regulamentos de horas de trabalho nos Estados Unidos e na União Europeia.

Goel (2013) analisou o problema de programação de roteirização de caminhões, considerando o cenário de implantação da regulamentação da Federal Motor Carrier Safety Administration (FMCSA), que entrou em vigor em Julho de 2013. O objetivo do trabalho é rever as avaliações do impacto da regulamentação já mencionada, e propor uma metodologia para avaliação desta regulamentação, considerando a segurança rodoviária e a produtividade do profissional. Também foi analisado a fadiga e o risco de saúde, calculado pelo Índice de Saúde e Segurança do Trabalho (2006) e pela Regulatory Impact Analysis (RIA). Dessa forma, a metodologia proposta, visa uma programação do horário de trabalho do motorista gerada automaticamente, com base na nova regulamentação, bem como otimizar as rotas usando uma abordagem de planejamento de períodos de saída, chegada, pausa e descanso. O método para otimizar as rotas de caminhões, respeitando o novo regulamento, foi baseado na Savings Heuristic de Clarke e Wright (1964). O modelo gerado, em sua essência, é uma extensão do trabalho apresentado anteriormente por Goel (2009), e que na prática é resolvido por um método aproximado. Os resultados apresentados pelo autor indicam que os custos e benefícios com segurança são da mesma ordem de grandeza para qualquer outra regulamentação. Sendo que os benefícios para saúde podem estar ligados às horas de trabalho.

Goel e Vidal (2014) desenvolveram um algoritmo genético hibrido com controle avançado de diversidade (HGSADC) para problemas de rota de veículo e planejamento de motoristas de caminhões (VRTDSP).  O problema consiste em determinar um conjunto de rotas para uma frota de veículos, tal que cada cliente seja visitado dentro de uma dada janela de tempo, que cada motorista pode cumprir, através das horas de serviço aplicáveis dentro da regulamentação e, que os custos de transporte sejam minimizados. O método proposto pelos autores foi especificamente projetado para lidar com geração de programação explicita durante avaliação de rotas e pode ser aplicado para várias regulamentações de horas de serviço ao redor do mundo, sendo no artigo avaliado e comparado regulamentações de horas de serviço nos Estados Unidos, Canada, União Europeia e Austrália no que diz respeito a custos de operação e riscos de acidentes. Os autores afirmam que os algoritmos genéticos híbridos são conhecidos por contar com um número extenso de rotas avaliadas, especialmente devido a uma busca local baseada em procedimentos de aprendizagem e recompensa.

Drexl et al (2013) desenvolveram um estudo sobre programação e roteirização de veículos rodoviários de carga que trafegam longa distância na Europa. Para tal determinaram que pedidos de recebimento e entrega devem atender a um horizonte de planejamento. Neste trabalho, assumiram uma frota de caminhões e motoristas heterogêneos. Consideraram que os motoristas e veículos pudessem ser mudados em estações de parada dispersos geograficamente, por permitir maior flexibilidade de planejamento e maior utilização dos caminhões. Também relacionam relações de interdependências entre caminhões e motoristas sincronizando suas rotas. Para solucionar o problema, os autores trabalham com uma heurística baseada em duas fases, onde a primeira considerou a legislação da União Europeia para os motoristas, problema de pickup-and-delivery com janela de tempo, estações de retransmissão e restrições adicionais (PDPTWRS) foram utilizadas. A segunda fase consistiu na solução de um problema de roteamento de veículos com janela de tempo e múltiplos depósitos (VRPTWMD). Neste problema, consideraram rotas parciais ou segmentos de rotas para início e/ou fim em um determinado depósito ou estação de retransmissão; como determinada na primeira fase. Assume-se que o condutor pode fazer uma pausa ou descanso em qualquer lugar do caminho. Todavia, o condutor nunca deve visitar uma estação de retransmissão para fazer o descanso. O mesmo deve terminar seu percurso no período determinado, para posteriormente realizar o descanso. Considerando a opção de transporte dos motoristas, utilizam vans para transporta-los até sua estação de trabalho. Um dos objetivos do SVCRSP (Simulataneous Vehicle and Crew Routing and Scheduling Problem) é minimizar o custo global, incluindo o do caminhão, dos motoristas e dos transportes. Para isso, deve haver sincronização de espaço e tempo. O problema de interdependência de motoristas e caminhões se refere ao fato de que uma mudança em uma rota pode ter efeitos sobre a viabilidade de outras. Logo os procedimentos clássicos de resolução para os problemas de roteirização de veículos (VRP), não são aplicáveis para a resolução do SVCRSP, pois são necessários mecanismos de sincronização e interdependência resultante dos problemas. Dado as características do problema, o mesmo é dividido em duas etapas, para as quais Drexl et al. (2013) apresentam um algoritmo heurístico de busca em vizinhança, mantendo sempre a melhor solução encontrada. Para a construção da solução viável, usa-se o melhor procedimento de inserção paralela. Em cada iteração para cada pedido não planejado, leva-se em consideração a posição mais barata em relação a coleta e entrega para se definir a rota. O autor conclui que o algoritmo utilizado obteve êxito em suas respostas.

5. Discussão dos resultados e conclusão

Pela análise dos dados, foi possível verificar, que a produção científica que aborda sobre problemas de scheduling de caminhões e de roteamento com o horário de trabalho dos motoristas ainda é muito pouco expressiva, ou seja foram encontrados apenas 28 publicações num período de 15 anos. Houve um aumento no número de publicações em 2009, passando de 2 em 2008 para 8 em 2009. No entanto, não houve estabilidade ou tendência de crescimento no número de publicações acerca do assunto, mantendo-se em média 4 artigos nos anos subsequentes.

Evidenciou-se que os artigos escritos sobre essa temática foram desenvolvidos por poucos pesquisadores, e que 47% dos artigos foram escritos individualmente, 29% escritos por duplas, 10% por trios e 14% escritos por 4 pesquisadores. Aqui destaca-se o pesquisador Asvin Goel, que é professor associado de Logística Internacional na Universidade Jacobs e Professor Adjunto de Supply Chain Management no Centro Logístico de Zaragoza na Espanha.

Também evidenciou-se 82% dos trabalhos tem como campo de estudo os Estados Unidos e União Europeia, e que os outros 18% foram desenvolvidos baseados em legislação do Canadá, Alemanha e Malásia.

Obteve-se uma visão mais geral dos problemas de roteirização e programação de veículos com HOS tratados na literatura, bem como a forma de solução apresentada, caracterizando, assim, o estado da arte em relação ao problema estudado. Como pode se observar, as diversas abordagens encontradas na literatura para o problema de roteirização e programação de veículos e condutores no transporte rodoviário de cargas convergem em relação a alguns aspectos: (a) a rota é fixada previamente, e somente depois disto a programação das paradas e demais exigências da lei são consideradas; (b) não existe previsão para paradas em locais não obrigatórios a fim de cumprir com a legislação.

Com este estudo foi possível identificar a elite de pesquisa, métodos e problemas específicos, e serem colocados alguns questionamentos, tais como: Por que esta área de estudo ainda é tão incipiente? Por que Europa e Estados Unidos são o campo de estudo dos problemas de scheduling de caminhões e de roteamento com o horário de trabalho dos motoristas? Por que no Brasil, ainda não existem estudos sobre esta temática? E, o quanto estes estudo possibilitam maior eficiência para os países? Portanto, este trabalho evidencia a oportunidade de estudo nacional e internacional voltado para o campo da roteirização de caminhões com restrições de horas de serviços (HOS).

Referências Bibliográficas

ARAÚJO, C. A. Bibliometria: evolução histórica e questões atuais. Universidade Estadual de Minas Gerais, MG. 2006.

ASSAD, A. A. Modeling and Implementation Issues in Vehicle Routing. In: Vehicle Routing: Methods and Studies, edited by: Golden, B. L; Assad, A. A. v. 16, p. 127- 148, second impression, 1991.

ARCHETTI, C.; SAVELSBERGH, M. W. P. The Trip Scheduling Problem. Transportation Science, 43(4), 417–431. 2009. doi:10.1287/trsc.1090.0278.

BALLOU, Ronald H. Gerenciamento da cadeia de suprimentos/Logística Empresarial. 5. ed. Porto Alegre: Editora Bookman, 2006.

BODIN, L. B.; GOLDEN, A.;  ASSAD; BALL. M.  Routing and Scheduling of Vehicles and Crews - The State of the Art. Computers and Opertions Research, (1983). Disponível em: < http://www.sciencedirect.com/science/article/pii/0305054883900308/>. Acesso em: 08 jun. 2014.

BOSE, R. de C. A. Modelos de Roteirização e Programação de entregas em redes de transportes. 1990. Dissertação (Mestrado) – Escola Politécnica da Universidade de São Paulo, Departamento de Engenharia de Transportes, São Paulo. 171p.

BRASIL. Lei no. 12.619 de 30 de abril de 2012. Dispõe sobre o exercício da profissão de motorista; altera a Consolidação das Leis do Trabalho - CLT, aprovada pelo Decreto-Lei nº 5.452, de 1º de maio de 1943, e as Leis nºs 9.503, de 23 de setembro de 1997, 10.233, de 5 de junho de 2001, 11.079, de 30 de dezembro de 2004, e 12.023, de 27 de agosto de 2009, para regular e disciplinar a jornada de trabalho e o tempo de direção do motorista profissional; e dá outras providências.  Diário Oficial da União. 02 mai 2012.

BRASIL. Lei No. 13.103. Dispõe sobre o exercício da profissão de motorista; altera a Consolidação das Leis do Trabalho - CLT, aprovada pelo Decreto-Lei nº 5.452, de 1º de maio de 1943, e as Leis nºs 9.503, de 23 de setembro de 1997 - Código de Trânsito Brasileiro, e 11.442, de 5 de janeiro de 2007 (empresas e transportadores autônomos de carga), para disciplinar a jornada de trabalho e o tempo de direção do motorista profissional; altera a Lei nº 7.408, de 25 de novembro de 1985; revoga dispositivos da Lei nº 12.619, de 30 de abril de 2012; e dá outras providências. Diário Oficial da União. 3 mar 2015.

CASCO, D. O.; GOLDEN, B. L; WASIL, E. A. Vehicle Routing with Backhauls: Models, Algorithms, and Case Studies. In: Vehicle Routing: Methods and Studies, edited by: Golden, B.L; Assad, A. A. v.16, p. 127-148, second impression, 1991.

CHIH, W. Y. Influência dos Custos Fixos e Variáveis na Roteirização de Frotas de Veículos com Capacidades Variadas. 1987. Dissertação (Mestrado) – Escola Politécnica da Universidade de São Paulo, Departamento de Engenharia de Transportes, São Paulo. 128p.

CROOM, S. Introduction to research metodology in operations management. In: KARLSSON, C. (Ed.). Researching Operations Management. New York: Routledge, 2009.

CUNHA, Claudio Barbieri da. Aspectos Práticos da Aplicação de Modelos de Roteirização de Veículos a Problemas Reais. Revista Transportes: ANPET, São Paulo, p.51-74, 10 nov. 2000.

CUNHA, C. B. Uma Contribuição para o Problema de Roteirização de Veículos Com Restrições Operacionais. 1997. Tese (Doutorado) – Escola de Politécnica da Universidade de São Paulo, Departamento de Engenharia de Transportes, São Paulo. 222p.

DESROCHERS, M.; LENSTRA, J. K.; SAVELSBERGH, M. W. P. A Classification Scheme for the Vehicle Routing and Scheduling Problems. European Journal of Operational Research, v. 46, n.3, p. 322-332, 1990.

DREXL, Michael; RIECK, Julia; SIGL, Thomas; PRESS, Bettina. Simultaneous Vehicle and Crew Routing and Scheduling for Partial- and Full-Load Long-Distance Road Transport. BuR -- Business Research Official . Open Access Journal of VHB German Academic Association for Business Research (VHB) Volume 6 | Issue 2 | November 2013 | 242-264.

ENOMOTO, L. M. Análise da distribuição física e roteirização em um atacadista do sul de Minas Gerais. 2005. Dissertação (Mestrado) Universidade Federal de Itajubá, Minas Gerais. 141p.

ERVIN, Eric C.; HARRIS, Russell C. Simulation Analysis of Truck Driver Scheduling Rules. In Proceedings of the 2004 Winter Simulation Conference R .G. Ingalls, M. D. Rossetti, J. S. Smith, and B. A. Peters, eds.2004.

FERENHOF, H. A.; VIGNOCHI, L.; CAMPOS, L. M. S. Bibliometric analysis and systematic review of environmental management in small and medium-sized enterprises. In: II ciKi - Congresso Internacional do Conhecimento e Inovação, 2012, Madrid. Anais: II Congresso Internacional do Conhecimento e Inovação, 2012.

FU, L., SUN, D. RILETT, L. Heuristic shortest path algorithms for transportation applications: state of the art. Computers & Operations Research, 33:3324-3343. 2006.

GOEL, A. Truck Driver Scheduling and Regulation (EC) No 561/2006. 2009a. Available at SSRN: http://ssrn.com/abstract=1370345 ou http://dx.doi.org/10.2139/ssrn.1370345.

GOEL, A. Truck Driver Scheduling and U.S. Hours of Service Regulations. 2009b. Available at SSRN: http://ssrn.com/abstract=1407509 ou http://dx.doi.org/10.2139/ssrn.1407509.

GOEL, A. Scheduling Working Hours of Team Drivers in European Road Transport. 2009c. Available at SSRN: http://ssrn.com/abstract=1532148 ou http://dx.doi.org/10.2139/ssrn.1532148.

GOEL, A. Vehicle scheduling and routing with drivers' working hours. Transportation Science, 43(1): 17–26, 2009d. doi: 10.1287/trsc.1070.0226.

GOEL, A. Truck driver scheduling in the European Union. Transportation Science, 44(4):429–441, 2010. doi: 10.1287/trsc.1100.0330. http://dx.doi.org/10.1287/trsc.1100.0330.

GOEL, A. The Minimum Duration Truck Driver Scheduling Problem. SSRN eLibrary - Working Paper Series, 2012a. URL http://ssrn.com/paper=1798569.

GOEL, A. The Australian Minimum Duration Truck Driver Scheduling Problem. Working paper, Zaragoza Logistics Center, 2012.

GOEL, A. The Canadian Minimum Duration Truck Driver Scheduling Problem. Computers & Operations Research, 39(10):2359–2367, 2012b. doi: 10.1016/j.cor.2011.12.016.

GOEL, A. Truck driver scheduling in the United States and the 2013 rule change. Working paper, Zaragoza Logistics Center, 2012.

GOEL, A., KOK, A. L. Efficient scheduling of team truck drivers in the European Union. Working Paper, University of Leipzig. 2009a.

GOEL, A., KOK, A. L. Efficient truck driver scheduling in the United States. Working Paper, University of Leipzig. 2009b.

GOEL, A; KOK, L. Truck driver scheduling in the United States. Transportation Science, 2010. doi: 10.1287/trsc.1110.0382.

GOEL, A; ROUSSEAU, L. M. Truck driver scheduling in Canada. Journal of Scheduling, 2011. doi: 10.1007/s10951-011-0249-6.

GOEL, A; ARCHETTI, C; SAVELSBERGH, M. Truck Driver Scheduling in Australia. Computers &Operations Research, 39(5):1122–1132, 2011. doi: 10.1016/j.cor.2011.05.021.

GOEL, A.; GRUHN, V. "Drivers' working hours in vehicle routing and scheduling", Working Paper, University of Leipzig, Leipzig, Germany. 2006.

GOEL, A.;VIDAL, T. Hours of Service Regulations in Road Freight Transport: An Optimization-Based International Assessment. Transportation Science. 2014.  48:3, 391-412.

KOK, A. L.; HANS, E. W.; SCHUTTEN, J. M. J. Optimizing departure times in vehicle routes. European Journal of Operational Research 210 (2011) 579–587.

LAPORTE, G.; GENDREAU, M.; POTVIN, J. Y.; SEMET, F. Classical and Modern Heuristics for the Vehicle Routing Problem. International Transactions in Operational Research, v. 7, n. 4/5, p. 285- 300, 2000.

MUNIZ Jr., J., MAIA, F. G. M., VIOLA, G. Os principais trabalhos na teoria do conhecimento tácito: pesquisa bibliométrica 2000-2011. SIMPOI (Simpósio de administração da produção, logística e operações internacionais). Universidade Estadual de São Paulo – UNESP, Campus Guaratinguetá, SP. 2011.

NARUO, M. K. O Estudo do consórcio entre municípios de pequeno porte para disposição final de Resíduos Sólidos Urbanos, utilizando Sistemas de Informação Geográficas. 2003. Dissertação (Mestrado) – Escola de Engenharia de São Carlos, USP, São Carlos. 283p.

NOVAES, Antônio Galvão. Logística e gerenciamento da cadeia de distribuição. 3. ed.Rio de Janeiro: Editora Elsevier LTDA, 2007.

OUGHALIME, A.; ISMAIL, W. R.; LIONG, C.; AYOB, MASRI. Vehicle and Driver Scheduling Modelling: A Case Study in UKM. 2009 2nd Conference on Data Mining and Optimization 27-28 October 2009, Selangor, Malaysia.

PELIZARO, C. Avaliação de Desempenho do Algoritmo de um Programa Comercial para Roteirização de Veículos. 2000. Dissertação (Mestrado) – Escola de Engenharia de São Carlos, USP, São Carlos. 153p.

Problem Modelling. Social Science research network. 2006. Disponível em: http://ssrn.com/abstract=1002565.

PRESCOTT-GAGNON, E.; DESAULNIERS, G.; DREXL, M.; ROUSSEAU, L. M. European driver rules in vehicle routing with time windows. Transportation Science, 44(4):455–473, 2010. doi: 10.1287/trsc.1100.0328.

PRODANOV, C. C.; FREITAS, E. C. Metodologia do Trabalho Científico: Métodos e Técnicas da Pesquisa e do Trabalho Acadêmico. 2. ed. – Novo Hamburgo: Feevale, 2013.

RONEN, D. Perspectives on Pratical Aspects of Truck Routing as Scheduling. European Journal of Operational Research, v. 35, n.2, p. 137-145, 1988.

SAMPAIO, R.F.; MANCINI, M. C. Estudos de revisão sistemática: um guia para síntese criteriosa da evidência científica. Revista Brasileira de Fisioterapia. São Carlos, v. 11, n. 1, p. 83-89, jan./fev. 2007.

SAVELSBERGH, M. W. P.; SOL, M. DRIVE: dynamic routing of independent vehicles. Operations Research, 46:474–490, 1998.

SHAH, VIDIT DIVYANG, "Time dependent truck routing and driver scheduling problem with hours of service regulations" 2008. Operations Research Master's Theses. Paper 2. Disponível em: http://hdl.handle.net/2047/d10016995. Acesso em 13 abr.2014.

SIENA, O. Metodologia da Pesquisa Científica: Elementos para elaboração e apresentação de trabalhos acadêmicos. 2007. 201 f. Tese (Mestrado em Administração) – Fundação Universidade Federal de Rondônia, Porto Velho.

URIONA, M. M.; SILVA SANTOS, J. L.; SANTOS, R. N. M. Inovação e Conhecimento Organizacional: um mapeamento bibliométrico das publicações cientificas até 2009. In: XXXIV ENCONTRO DA ANPAD, Rio de Janeiro, set., 2010

XU, Hang; CHEN, Zhi-Long;  RAJAGOPAL, Srinivas;  ARUNAPURAM, Sundar. Solving a Practical Pickup and Delivery Problem. Transportation Science/Vol. 37, No. 3, August 2003. Disponível em: http://pubsonline.informs.org/doi/abs/10.1287/trsc.37.3.347.16044. Acesso em 30 mar. 2014.

1. Doutoranda do Programa de Pós Graduação em Engenharia de Produção da Universidade Federal de Santa Catarina, dmgenaro@hotmail.com
2. Doutorando do Programa de Pós Graduação em Engenharia de Produção da Universidade Federal de Santa Catarina, hidelrodrigues@gmail.com

3. Programa de Pós Graduação em Engenharia de Produção da Universidade Federal de Santa Catarina, sergio.mayerle@ufsc.br.