otimização de transporte

Prévia do material em texto

�
Ana Paula Duarte - 201505653101
Caroline Reis - 201512791661
Fábio Meula - 201512613691
Marcela Pamela Rosa Dos Santos - 201001147197
Marli Caroline de Oliveira - 201501478427
Mauricio Capovilla Gandra - 201501478214
São Paulo – SP
2016 �
SUMÁRIO
	INTRODUÇÃO
	2
	1. ANÁLISE TÉCNICA 
	3
	1.1 Caixeiro viajante
	2
	1.1.1 Objetivos do trabalho
	4
	1.1.2 Justificativa do trabalho
	4
	1.1.3 Resumo do trabalho
	4
	1.1.4 Conclusão
	6
	1.2 Caminho mínimo
	6
	1.2.1 Objetivos do trabalho
	6
	1.2.2 Justificativa do trabalho
	7
	1.2.3 Resumo do trabalho
	7
	1.2.4 Conclusão
	9
	1.3 Fluxo máximo
	9
	1.3.1 Objetivos do trabalho
	9
	1.3.2 Justificativa do trabalho
	10
	1.3.3 Resumo do trabalho
	10
	1.3.4 Conclusão
	10
	2. TEORIA DAS FILAS
	11
	2.1 Objetivo do trabalho
	11
	2.2 Justificativa do trabalho
	11
	2.3 Resumo do trabalho
	12
	2.4 Conclusão
	12
	CONCLUSÃO FINAL 
	13
	REFERÊNCIAS
	14
�
INTRODUÇÃO
	O desenvolvimento do presente estudo visa abordar as otimizações do sistema logístico através do estudo dos principais problemas de roteamento bem como a importância dos aplicativos que solucionem em tempo hábil a roteirização urbana. A roteirização urbana cujo foco esta nas grandes cidades é de grande importância, pois os indivíduos necessitam de uma fonte confiável e rápida de acessar esse tipo de informação. CUNHA (1997) compreende que, o termo roteirização, embora não encontrado nos dicionários de língua portuguesa, tem como equivalente ao inglês “routing” (ou “routeing”) para designar o processo para a determinação de um ou mais roteiros ou sequências de paradas a serem cumpridos, com o objetivo de visitar um conjunto de pontos distintos geograficamente e pré-determinados. Para Assad (1988) sobre a roteirização citado por Cunha (1997)
	Fazem parte da roteirização urbana os meios de transporte: a pé, que considera o caminho direto, do ponto de origem ao ponto de destino, sem restrições; de carro, que tem como restrição os sentidos das ruas e caneletas; e ônibus, que considera as linhas de ônibus disponíveis à população.
�
1. ANÁLISE TÉCNICA 
1.1 Caixeiro viajante
	Para o desenvolvimento dessa etapa foi selecionado o trabalho: “Sistema de roteirização urbana”, dos autores Evandro Harrison Hoffmann, Kelvin William Zimmermann, Silvio Bortoleto do Centro Universitário Positi.
	Após a sua leitura é possível identificar os seus objetivo, a justificativa, resumir e concluir acerca do trabalho analisado como segue nas etapas seguintes, onde para Cunha (1997):
Consiste em uma das histórias de grande sucesso da Pesquisa Operacional nas últimas décadas, que pode ser medido pelo expressivo número de artigos que vêm sendo publicados ao longo dos anos na literatura especializada, incluindo os anais de congressos da ANPET (Associação Nacional de Pesquisa e Ensino em Transportes). 
	Problemas de roteirização são muitas vezes definidos como problema de um caixeiro viajante, que foi o primeiro problema de roteirização a ser estudado (no inglês “traveling salesman problem” ou TSP), que consiste em encontrar o roteiro eficaz, minimizando a distância total percorrida. Desde então, novas restrições vêm sendo incorporadas ao problema do caixeiro viajante, de modo a melhor representar os diferentes impasses que envolvem roteiros dos transportes em geral, entre as quais: 
Restrições de horário de atendimento (conhecidas na literatura como janelas de tempo ou janelas horárias); 
Capacidades dos veículos; 
Duração máxima dos roteiros dos veículos (tempo ou distância);
Restrições de tipos de veículos que podem atender determinados clientes.
	Segundo as pesquisas de Cunha (1997), os problemas de roteirização sob a ótica de otimização que incluem o caso particular do caixeiro viajante, pertencem à categoria conhecida como NP-difícil (do inglês “NP-hard”), o que significa que possuem ordem de complexidade exponencial. Em outras palavras, o esforço computacional para a sua resolução cresce exponencialmente com o tamanho do problema (dado pelo número de pontos a serem atendidos). Este problema também pode abranger indivíduos, que precisam localizar um determinado local, partindo do ponto em que está e chegar da forma mais rápida e de menos custo.
1.1.1 Objetivos do trabalho
	O trabalho escolhido para estudo mostrou a importância do trabalho do caixeiro-viajante no transporte a fim de demonstrar a construção de um aplicativo de roteirização urbana para uso público, possibilitando aos usuários o utilizarem através da Internet e através de outros meios eletrônicos, tais como terminais de acesso público, palms, celulares, entre outros. Neste aplicativo serão calculadas rotas para um percurso eficaz.
1.1.2 Justificativa do trabalho
	O trabalho escolhido retrata a realidade das rotas e a forma como o aplicativo contribui para a viabilização da que consideram sentidos de ruas e possíveis obstáculos a veículos e rotas com transporte coletivo no qual levam em consideração os pontos de ônibus da região em que foi implementada, assim uma rota com transporte público compreende a ida a pé do local de origem até o ponto de ônibus mais próximo (considerando que este ônibus chegue ao destino especificado) e a rota que o ônibus irá fazer até chegar ao ponto de ônibus mais próximo do destino e o percurso a pé deste ponto de ônibus até o local desejado
Resumo do trabalho
	É sabido que os transtornos e dificuldades comuns nas grandes metrópoles é o percurso ao destino final, portanto algumas iniciativas foram desenvolvidas pelo governo, iniciando-se pela a ampliação de viadutos e vias expressas, corredores para o trafego de ônibus e construção de linhas.Mas ainda há problemas diariamente enfrentados pelos congestionamentos e as superlotações no transporte coletivo.. A busca de soluções viáveis para minimizar problemas decorrentes do transporte coletivo tem sido explorada por alguns pesquisadores através de propostas de sistemas baseados em aplicativos, capaz de registrar e de transmitir a existência de usuários e de pontos de espera, além de um meio de determinar, de forma dinâmica e rápida, o melhor caminho a ser tomado. 
Segue alguns meios utilizados pelos usuários.
MapLink- Disponível para acompanhar a situação do trânsito sua cobertura estabelece nas seguintes cidades: Salvador/BA, Vitória/ES, Goiânia/GO, Belo Horizonte/MG, Cuiabá/MT, Recife/PE, Curitiba/PR, Rio de Janeiro/RJ, Barueri/SP, Campinas/SP, Diadema/SP, Guarulhos/SP, Osasco/SP, Santo André/SP, São Bernardo do Campo/SP, São Caetano/SP, São Paulo/SP.
Figura 1: Aplicativo em tempo real
Fonte- http://canaltech.com.br/
Waze tem se popularizado bastante no Brasil e já possui dezenas de milhares de usuários diários em todo o mundo
Figura 2: Aplicativo para aparelhos com sistema iOS e Android
Fonte: http://canaltech.com.br
Conclusão
	Aqui, parte-se do princípio da existência desta estrutura, e é proposto um método de otimização de rotas. Sabe-se que o caos levado crescimento das cidades, os meios de transporte tornam-se cada vez mais complexos, devido a grande variedade de maneiras de se chegar a um determinado local. 	Portanto a facilidade encontrada nesses aplicativos sobre o sistema de roteirização é uma ferramenta cada vez mais essencial no dia-a-dia dos indivíduos e das organizações. Existem aplicativos que calculam a rota mais curta entre dois ou mais pontos (endereços), sendo que podem ser consultados diversos meios de transporte. 
	Este artigo objetivou explanar a importância do aplicativo sobre uma rota, visando não somente através de veículos particulares, mas para atender e otimizar. 
	A partir do presente estudo foi possível observar a contribuição para os utilitários em geral bem, como a vida de sacrificiosa que levam diariamente para seus desatinos finais.
1.2 Caminho mínimo
	Para o desenvolvimento dessa etapa foi selecionado o trabalho “O Algoritmo do CaminhoMínimo em Apoio à Logística”, do autor Fábio Akira Monteiro Toyama.
	A presente análise visa identificar e compreender o caminho Mínimo, e explanar de fato sua contribuição para transporte e sua necessidade de otimizar as atividades de logística das empresas. Desta forma identificaremos métodos para solucionar e definir o menor caminho entre dois pontos.. Sua funcionalidade mediante algoritmos que auxilia as rotas. 
1.2.1 Objetivos do trabalho
	A grande motivação para a realização deste trabalho é a contribuição com a melhoria do trânsito das grandes cidades que dia-a-dia tornam-se mais caóticas devido ao grande volume de veículos transitando pelas vias. A partir do gerenciamento eficiente das vias pelo poder público e de um melhor planejamento dos percursos realizados por empresas e cidadãos comuns, é possível melhorar a trafegabilidade e consequentemente gerar economia, reduzir a emissão de poluentes e melhorar a qualidade de vida.
1.2.2 Justificativa do trabalho
	Esta pesquisa visa o relatar a importância do algoritmo para solucionar o problema do caminho mínimo e aplicá-lo no contexto da otimização de Transportes. Este algoritmo tem como base o conceito do Algoritmo de Dijkstra. 	O trabalho aqui desenvolvido não tem a pretensão de ser um sistema para um usuário final, mas de implementar um algoritmo que poderá ser melhorado, adaptado e associados em um Sistema de Informações Geográficas (SIG) para atender as necessidades do usuário de acordo com o contexto onde será utilizado.
1.2.3 Resumo do trabalho
	Dentre as atividades logísticas, o transporte é uma das mais importantes. É o elo entre o fornecedor e o cliente. Os Transportes, esta integrada a atividade logísticas visando fazer uma interligação entre o fornecedor e o cliente de forma satisfatória, eficiente, no menor prazo e custo. 	A Logística visando a otimização de Transportes merece uma atenção especial por ser uma atividade que demanda um custo alto. O mau gerenciamento desta atividade pode acarretar atrasos na distribuição e aumento no preço final dos produtos, serviços, gerando consequentemente muita insatisfação aos clientes. 
	Quando bem aplicada gera economia de recursos financeiros, humanos, materiais, tempo, garante a satisfação de seus clientes e cria a perspectiva de conquistar novos mercados. Uma logística eficiente também contribui com a melhoria do trânsito das cidades e com a preservação do meio ambiente. Ao realizar um percurso potencializado, suaviza o tempo em que o veículo fica circulando pelas ruas.
	Desta forma temos o algoritmo que apoia o caminho mínimo para a tomada de decisão eficaz. 
	Dijkstra Edsger Wybe Dijkstra (1930 - 2002) – criador do algoritmo Dijkstra nascido em Rotterdam, graduado em matemática e física pela universidade de Leyden, e Ph.D. em ciência da computação pela universidade de Amsterdã. Obteve um vasto conhecimento voltado para evolução do caminho mínimo.
	Deste modo expandiu sua carreira, atuando como programador, professor e pesquisador e suas contribuições para a computação, está o algoritmo do caminho mínimo, denominado também de Algoritmo de Dijkstra, a criação é de uma variável especial conhecida como semáforo. O Algoritmo de Dijkstra soluciona o problema do caminho mínimo entre uma única origem e todos os possíveis destinos em um grafo. Considerado eficiente e por isso utilizado para solucionar o problema de caminho mínimo em contextos onde seja possível fazer representação de um problema interface aos grafos, de modo que não possuam arestas com valores negativos.
	Os grafos nada mais é que podem ser aplicados na computação para modelar situações onde haja necessidade de considerar um conjunto de elementos conectados entre si para resolução de problemas tais como: 
• Definir o melhor trajeto, ou o de menor custo entre um elemento e outro. 
• Definir a quantidade de elementos que podem ser acessados a partir de uma origem. 
• Definir quantidade de elementos entre o elemento origem e destino. 
• Definir menor custo para acessar todos os elementos do grafo.
Ziviani (2004) define grafo como sendo uma estrutura abstrata formada por um conjunto de vértices e um conjunto de arestas que conectam pares de vértices.
Figura 3: Representação Gráfica
Fonte: Caminho Mínimo
	A figura acima nos mostra diferentes pontos de um determinado destino, onde as arestas nos posicionam aos pontos, elas auxiliaram para localizar o menor caminho, e conforme figura, temos a associação de ACDGH- indicando que temos um percurso de 17 km para o destino final.
	Figueiredo (2011) define que grafo é uma ferramenta fundamental de abstração que permite modelar relacionamento entre pares de objetos para resolver problemas.
1.2.4 Conclusão
	Através das pesquisas realizadas foi possível constatar que o Algoritmo de Dijkstra é o que melhor soluciona este problema por ter uma menor complexidade e encontrar uma solução ótima para o problema modelado. Vale ressaltar que a melhor solução não é necessariamente a solução com o menor valor, mas sim, aquela que atende a necessidade do usuário. Sendo assim, é possível realizar pequenas adaptações no algoritmo para que ele possa ser utilizado em outras áreas, gerando soluções capazes de auxiliar as tomadas de decisões.
1.3 Fluxo máximo
	O presente “Otimização de fluxos em grafos” do autor Leonardo Ternes Santos, da Universidade Federal do Paraná – UFPR, do curso de ciência da computação, artigo foi compreendido, seguindo o pensamento mediante a análise.
	Enaltecendo a otimização de fluxo os grafos visam a aplicação e integração, utilizando em específico o algoritmo Ford-Fulkerson. 
	Será relatado as aplicações práticas, o funcionamento do algoritmo demonstrando sua função mediante a otimização.
1.3.1 Objetivo do trabalho
	A compreensão mediante as informações colhidas, baseadas no artigo se remete ao conhecimento dessa técnica e sua importância para o desenvolvimento mediante o transporte, o quanto sua aplicalidades é relevante no processo logístico, impactando no percurso mínimo. 
1.3.2 Justificativa do trabalho
	Deste modo o fluxo máximo estuda diversas pesquisas e em outros campos, e encontrar algoritmos eficientes para resolver este problema tem recebido muita atenção. Sua função se justifica no sentido de sanar do problema de fluxo máximo, é, dado um ponto inicial e um ponto final , descobrir qual o fluxo máximo que pode transitar de para dentro de uma rede direcionada. 
1.3.3 Resumo do trabalho
	Entretanto, durante a execução do algoritmo podemos obter outras informações relevantes além do número que delimitará o fluxo, como por quais caminhos devemos trafegar e qual a capacidade de cada caminho. Tendo em vista a capacidade de otimização.
	 A função do algoritmo de Ford-Fulkerson, que atualmente é um dos mais conhecidos dentro do fluxo máximo, pode ser usado para resolver os modelos: de carga (logística de abastecimento e distribuição), o fluxo de gases e líquidos por gasoduto, componentes ou peças em linhas de montagem, que funcionam em redes eléctricas, pacotes de informação em redes de comunicação, tráfego, sistema de irrigação, etc.
Figura 4: Grafo de Ford-Fulkerson
Fonte: Alogaritimo sobre o fluxo máximo 
1.3.4 Conclusão
	Desta forma é possível compreender que a execução do algoritmo é primordial para o desenvolvimento, visando a otimização, tais como observar a necessidade de reduzir todos os nós, auxiliando a melhorara e o desempenho de várias atividades voltadas para a qualidade de vida de todos.
�
2. TEORIA DAS FILAS
	No presente estudo, baseado na análise da , do autor(a) karina Pedrini fraga análise de um processo de atendimento de emergência usando teoria de filas.
	Iremos observar a fila M/M/1, e relatar a importância da melhoria do sistema, o que caracteriza uma melhor utilização dos serviços disponíveis, menor tempo de espera e maior agilidade.
2.1 Objetivo do trabalho
	Para tanto demonstrar a eficiência da teoria das filas naotimização para o transporte inclui o fluxo de tráfego. 
	Desse modo podemos avaliar o comportamento de um sistema de filas e seus parâmetros, exemplos:
Tempo de espera médio
Probabilidade de formação de fila 
 Porcentagem de clientes rejeitados pelo sistema 
Probabilidade de um cliente esperar mais do que certo tempo 
 Número médio de clientes na fila 
Probabilidade de que todos os servidores estejam ociosos.
Portanto, a Teoria das Filas avalia por meio de análises matemáticas qual o ponto de equilíbrio para satisfazer o usuário da via e que torne o sistema viário estudado eficiente com a sua função. Podemos dizer, ainda que as filas surjam porque a demanda é maior que a capacidade de atendimento do sistema viário urbano. 
A História da Teoria das Filas surgiu mediante a abordagem matemática, que se iniciou em 1908 em Copenhague, Dinamarca, através de A. K. Erlang, considerado o pai da Teoria das Filas, trabalhava em uma companhia telefônica centrado na elaboração para o problema de redimensionamento de centrais telefônicas.
2.2 Justificativa do trabalho
	A Teoria das Filas visa oferecer dados que auxiliam na modelagem do serviço para encontrar um balanceamento ideal entre os custos de realizar um 
determinado serviço e os custos que os atrasos ocasionados pelas filas podem gerar. Para Prado (1999, p.33) estudar o comportamento de filas é uma forma de modificar sistemas nos quais existem gargalos. O objetivo de estudar o comportamento de filas é prestar um melhor atendimento ou proporcionar uma redução de custos, estabelecendo uma ordem de prioridade entre as principais opções de intervenção no transito.
	
2.3 Resumo do trabalho
	Deste modo a fila M/M/1 é o modelo mais simples dentre os existentes em teoria de filas, no entanto é um dos modelos mais estudados. Esse tipo de fila configura um processo de nascimento e morte, no qual as chegadas em um intervalo de tempo.
	Trata-se do modelo básico em teoria das filas, com as seguintes características: 
• As chegadas seguem uma distribuição de probabilidade Poisson;
 • O tempo de atendimento é regido por uma distribuição de probabilidade Exponencial;
 • Possui apenas um servidor;
• De capacidade Infinita; 
• Disciplina fila FIFO.
	Quando definido o modelo, é possível identificar a probabilidade do sistema.
Krajewisk, Ritzman & Malhorta (2009) salientam que, é necessário que os gestores das filas observem e monitorem fatores que possam influenciar no desempenho e atendimento dos clientes.
	
2.4 Conclusão
Com a aplicação da Teoria das Filas é possível visualizar de forma geral o processo de transporte, gerando reflexões acerca de tomadas de decisão que favoreçam a otimização do processo do transporte. Conhecendo as peculiaridades do sistema de transporte e suas potencialidades, é possível prever e elaborar um melhor planejamento, e estabelecer metas compatíveis com a realidade. 
Os congestionamentos nos centros urbanos são cada vez mais comuns, principalmente em horários de pico. Entretanto, é possível obter melhorias significativas através do uso adequado de ferramentas de gestão. Com as informações apropriadas é possível a tomada de decisão com maior grau de acerto.
CONCLUSÃO FINAL 
	Através do presente estudo, obtivemos dos presentes artigos um apoio a conceituação acerca do transporte e sua trafegabilidade, o quanto suas técnicas estão associadas para a melhoria no percurso.
	Considerando as informações e conhecimentos relevantes para o principal objetivo é garantir a viabilização mediante a disciplina.
	 A abordagem aqui proposta almeja avaliar e classificar a qualidade dos serviços do setor de transporte partir dos usuários, incorporando critérios técnicos relacionados à qualidade das ferramentas para transportes urbanos e à qualidade de serviços, mediante a informatização e gestão competente para a aplicalidades correta. 
	Tal abordagem, que envolve a proposição de técnicas e sistemas de apoio à decisão, para problemas práticos relevantes de transportes, é uma das prioridades e de contribuir para que o processo de otimização.
	Tendo em vista as constatações acima, propiciou uma reflexão acerca do transporte e a roteirização e como as técnicas de apoio são eficazes para o objetivo final.
	Como comentário final, registra-se na intenção deste trabalho com ênfase aos métodos registrados a fim de redefinir o transporte para as vias com fluxo intenso, garantindo uma boa qualidade de trafego, ressaltando a importância dos aplicativos associados a informação de percurso, dentre eles a variadas algoritmos voltados a excelência de um resultado positivo.
	
REFERÊNCIAS
APLICATIVO EM TEMPO REAL - Disponível em http://canaltech.com.br/dica/apps/aplicativos-que-te-ajudam-a-escapar-do transito Acesso em 30/03/2016.
APLICATIVO PARA APARELHOS COM SISTEMA IOS E ANDROID- Disponível em http://canaltech.com.br/dica/apps/aplicativos-que-te-ajudam-a-escapar-do-transito/ Acesso em 30/03/2016
ASSOCIAÇÃO NACIONAL DE PESQUISA E ENSINO EM TRANSPORTE. ANPET. Disponível em:<http://www.anpet.org.br/anpet/index.php>. Acesso em 01/11/2009.
CUNHA, C.B. Uma contribuição para o problema de roteirização de veículos com restrições operacionais. São Paulo: EPUSP, Departamento de Engenharia de Transportes, 1997.
FIGUEIREDO, Daniel R. Introdução a Redes Complexas. XXXI Congresso da Sociedade Brasileira de Computação, Natal, 2011.
FRAGA, Karine -Análise de um processo de atendimento de emergência usando teoria de filas- Disponível em http://www3.ceunes.ufes.br/downloads/16/engprodTCC_Karina_Pedrini_Fraga_2012_1.pdf- acesso em 04/04/2016
GRAFO DE FORD-FULKERSON- Disponível em - http://slideplayer.com.br/slide/47656/- acesso em 04/04/2016
HOFFMANN, Evandro Harrison, et. al. Sistema de roteirização urbana. Centro Universitário Positi. Disponível no http://conged.deinfo.uepg.br/artigo1.pdf acesso em 29/03/2016
KRAJEWISKI, L. J.; RITZMAN, L.; MALHOTRA, M. Administração de Produção e Operações. São Paulo: Pearson Prentice Hall, 2009.
PRADO, D. S. do.;Teoria das Filas e da Simulação. Belo Horizonte: Editora de Desenvolvimento Gerencial, 1999.
REPRESENTAÇÃO GRÁFICA- Disponível em https://www.youtube.com/watch?v=kYLIAU5EQM- Acesso em 31/03/2016
SANTOS, Leonardo Ternes. Otimização de fluxo em grafos- Disponível em http://www.inf.ufpr.br/andre/files/LeonardoSantos2013.pdf- acesso em 01/04/2016.
TOYAMA, Fábio Akira Monteiro. Caminho Mínimo em Apoio à Logística. Disponível em file:///C:/Users/FABIO%20AUGUSTO/Downloads/003%20%20Fabio_O_Algoritmo_do_Caminho_Minimo_em_Apoio_a_Logistica%20(1).pdf. Acesso em 31/03/2016
ZIVIANI, N. Projeto de Algoritmos com Implementações em Java e C++. São Paulo: Thomson Learning, 2007.