Mostrar registro simples

dc.contributor.advisorRitt, Marcus Rolf Peterpt_BR
dc.contributor.authorSilva, Fernando Bombardelli dapt_BR
dc.date.accessioned2016-08-25T02:16:33Zpt_BR
dc.date.issued2016pt_BR
dc.identifier.urihttp://hdl.handle.net/10183/147638pt_BR
dc.description.abstractO problema Dial-a-ride (DARP) é um problema de otimização combinatória NP-difícil com aplicações práticas em transporte público orientado a usuário. O DARP é um problema de roteamento de veículos cujas instâncias consistem de um conjunto de veículos e um conjunto de solicitações para o embarque e desembarque de passageiros. Seu objetivo é atribuir as solicitações aos veículos e calcular as rotas de cada um destes, minimizando os custos operacionais e garantindo que todas as restrições, tais como capacidade dos veículos, janelas de tempo de partida e chegada, e tempo máximo de viagem do usuário, sejam obedecidas. Esse trabalho apresenta uma formulação matemática do problema e procura resolvê-lo através do Algoritmo Firefly (FA). O FA é uma nova meta-heurística baseada na natureza e inspirada no comportamento de vaga-lumes, que aplica o conceito de inteligência de enxame com o objetivo de otimizar funções matemáticas procurando por soluções quase ótimas. Com o auxílio dessa técnica nós visamos modelar e implementar um solucionador para o DARP que explore o enorme espaço de busca combinatorial, gerado pelas instâncias do problema, de uma maneira eficiente. Por fim, conduzimos uma comparação de desempenho entre o método proposto e os algoritmos encontrados na literatura científica, o que mostrou que o primeiro atinge um coeficiente de otimalidade de, em média, 90% para um conjunto de instâncias específico, e entrega, em alguns casos, resultados mais rápidos que aqueles entregues por um dos algoritmos da literatura.pt_BR
dc.description.abstractThe Dial-a-ride problem (DARP) is an NP-hard combinatorial optimization problem with practical applications in user-oriented public transportation. The DARP is a vehicle routing problem whose instances consist of a set of vehicles and a set of pick-up and drop-off requests from passengers. Its goal is to assign the requests to the vehicles and to calculate the routes of each one of them, minimizing the operation costs and ensuring that all the constraints, such as vehicle capacity, departure and arrival time windows, and maximal user ride time, are fulfilled. This work presents a mathematical formulation of the problem and seeks to solve it through the firefly algorithm (FA). The FA is a novel nature-based metaheuristic inspired by the behavior of fireflies, which applies the concept of swarm intelligence in order to optimize mathematical functions by looking for nearoptimal solutions. With the aid of this technique we aimed to model and implement a solver to the DARP which explores the huge combinatorial search space, generated by the problem instances, in an efficient way. Finally, we carried out a performance comparison between the proposed method and the algorithms found in the scientific literature, and found that the former achieves an average of 90% of optimality for a specific set of instances, and delivers, in some experiments, faster results than those delivered by one of the algorithms from the literature.en
dc.description.abstractDas Dial-a-Ride-Problem ist ein NP-schweres kombinatorisches Optimierungsproblem, das bei benutzerorientiertem öffentlichen Personenverkehr Anwendung findet. Das DARP ist ein Tourenplanungsproblem, dessen Instanzen aus einer Menge von Fahrzeugen und einer Menge von von Fahrgästen eingetragenen Aufträgen zum Abholen und zum Absetzen bestehen. Sein Ziel ist es, den Fahrzeugen die Aufträge zuzuweisen und die Routen jedes Wagens zu berechnen, sodass die Betriebskosten minimiert werden und alle Nebenbedingungen, wie z.B. Fahrzeugnutzlast, Zeitfenster für Ein- und Ausstieg, maximale Fahrtdauer, erfüllt werden. Diese Arbeit stellt eine mathematische Formulierung des Problems vor und versucht, es durch den Einsatz des Firefly-Algorithmus (FA) zu lösen. Der FA ist eine neue naturbasierte Metaheuristik, die vom Verhalten von Glühwürmchen inspiriert ist und das Konzept von Schwarmintelligenz anwendet, um mathematische Funktionen zu optimieren, indem sie quasi-optimale Lösungen sucht. Anhand dieses Verfahrens hat diese Arbeit einen Löser des DARP modelliert und implementiert, der den riesigen kombinatorischen, von Probleminstanzen generierten Suchraum effizienterweise erforscht. Letztendlich wurde ein Leistungsvergleich zwischen der vorgeschlagenen Methode und den Algorithmen aus der wissenschaftlichen Literatur durchgeführt, der zeigte, dass die vorgeschlagene Methode einen Durchschnitt von 90% von Optimalität für eine bestimmte Menge von Instanzen erreicht und in einigen Experimenten schnellere Ergebnisse liefert, als die von einem der Algorithmen, die von der Lietratur stammen, gelieferten Ergebnisse.de
dc.format.mimetypeapplication/pdf
dc.language.isoengpt_BR
dc.rightsOpen Accessen
dc.subjectOtimizacao combinatoriapt_BR
dc.subjectDial-a-ride problemen
dc.subjectInformatica : Transportespt_BR
dc.subjectVehicle routingen
dc.subjectInteger programmingen
dc.subjectMetaheuristicen
dc.subjectFirefly algorithmen
dc.subjectDial-a-Ride-Problemde
dc.subjectTourenplanungde
dc.subjectGanzzahlige Optimierungde
dc.subjectMetaheuristikde
dc.subjectFirefly-Algorithmusde
dc.titleSolving the dial-a-ride problem with the firefly metaheuristicpt_BR
dc.typeTrabalho de conclusão de graduaçãopt_BR
dc.contributor.advisor-coHebler, Axelpt_BR
dc.identifier.nrb000999673pt_BR
dc.degree.grantorUniversidade Federal do Rio Grande do Sulpt_BR
dc.degree.departmentInstituto de Informáticapt_BR
dc.degree.localPorto Alegre, BR-RSpt_BR
dc.degree.date2016pt_BR
dc.degree.graduationCiência da Computação: Ênfase em Ciência da Computação: Bachareladopt_BR
dc.degree.levelgraduaçãopt_BR


Thumbnail
   

Este item está licenciado na Creative Commons License

Mostrar registro simples