Loading...
Publication
Transporte flexível: modelação, análise e simulação
| Name: | Description: | Size: | Format: | |
|---|---|---|---|---|
| 2.43 MB | Adobe PDF |
Authors
Advisor(s)
Abstract(s)
Neste trabalho é discutido e apresentado todo o processo de modelação e
implementação de uma solução que permita resolver tanto a vertente estática, como a
dinâmica, do problema de routing de transporte flexível, muitas vezes chamado de DARP (Diala-Ride Problem). De forma geral, este problema requer que um conjunto de clientes efetuem
pedidos de serviço, no qual é indicado o ponto origem e destino, assim como os tempos
pretendidos para a prestação do serviço. O objetivo é gerar soluções possíveis e viáveis
(percursos) para os veículos disponíveis, de forma a minimizar os custos totais e tendo em conta
o conjunto de pedidos (e informações relativas aos mesmos) e o conjunto de restrições impostas
ao problema. A vertente estática caracteriza-se pelo facto de toda a procura ser conhecida
inicialmente, sendo então necessário apenas gerar uma única solução (conjunto de percursos)
com custos mínimos. A outra vertente (dinâmica) distingue-se pelo facto de a procura se ir
revelando dinamicamente ao longo da execução do serviço, sendo então necessário ir
efetuando reajustes em tempo real aos percursos de cada veículo tendo em conta o surgimento
de novos pedidos. Este tipo de problema permite dar um papel ativo ao cliente, permitindo
melhorar a qualidade do serviço, uma vez que são tidas em conta as necessidades do mesmo.
Um outro aspeto vantajoso deste tipo de sistemas, é permitir aos operadores de transporte
conhecer a procura atual, levando a que possa ser otimizada a sua frota de veículos e conseguir
dar resposta às necessidades identificadas.
De forma a validar, testar e analisar a solução proposta numa situação mais aproximada
da real e tendo em conta diferentes configurações, foi ainda modelada e desenvolvida uma
simulação de eventos discretos (DES), que reflete o funcionamento de um sistema de transporte
flexível, estando neste documento descrito todos os aspetos fundamentais para a modelação e
implementação da mesma. Para além disto, ainda são apresentados um conjunto de testes
efetuados a alguns mecanismos (algoritmos) de procura de soluções que permitem otimizar os
percursos obtidos para o problema formulado para uma abordagem estática e tendo ainda em
conta diferentes configurações do mesmo. Por fim, são ainda apresentados os resultados dos
testes efetuados em simulação para a abordagem dinâmica do problema de routing formulado
de forma a compreender a influência que o aumento da procura tem na solução proposta.
With this work, we discuss and present the whole modelling and implementation process of a solution for the static and dynamic Dial-a-Ride Problem (DARP). Overall, this problem requires a set of customers to perform set of transportation requests, where in each request, it is provided the customer desired pickup and drop-off locations, as well as the desired times to be fulfilled for the service being requested. The objective is to generate a set of viable routes, considering a set of available vehicles and a set of transportation requests, as well as some additional restrictions imposed on the problem, while minimizing the total cost of the solution. In the static DARP, all the requests are known initially, meaning that we only need to generate the solution (set of routes) once. While on the dynamic approach of the DARP, the requests are revealed dynamically throughout the execution of the transportation service, meaning that there is the need to carry out adjustments on each vehicle route in real time, with the appearance of new requests. This routing problem gives an active role to the customer by considering its needs, which, in way, improves the quality of the service provided. Another advantage of this type of system is the fact that transportation providers, are able to know the current demand and needs related to it, thus, making it possible for them to optimize their vehicle fleet in order to respond to it. In order to validate, analyze and evaluate the proposed solution for the DARP using different configurations and in a context closer to the real world, we also propose in this document, all the modeling and development process of a Discrete Event Simulation that reflects in a way a flexible transportation system operation. Additionally, we also present the results of a set of tests done using different configurations, to some mechanisms (search algorithms) for finding and optimizing solutions, for the static approach of the modeled DARP. Finally, we also present the results for the tests performed using simulation for the dynamic DARP, in order to understand the influence that the increase in the demand has in the proposed DARP solution.
With this work, we discuss and present the whole modelling and implementation process of a solution for the static and dynamic Dial-a-Ride Problem (DARP). Overall, this problem requires a set of customers to perform set of transportation requests, where in each request, it is provided the customer desired pickup and drop-off locations, as well as the desired times to be fulfilled for the service being requested. The objective is to generate a set of viable routes, considering a set of available vehicles and a set of transportation requests, as well as some additional restrictions imposed on the problem, while minimizing the total cost of the solution. In the static DARP, all the requests are known initially, meaning that we only need to generate the solution (set of routes) once. While on the dynamic approach of the DARP, the requests are revealed dynamically throughout the execution of the transportation service, meaning that there is the need to carry out adjustments on each vehicle route in real time, with the appearance of new requests. This routing problem gives an active role to the customer by considering its needs, which, in way, improves the quality of the service provided. Another advantage of this type of system is the fact that transportation providers, are able to know the current demand and needs related to it, thus, making it possible for them to optimize their vehicle fleet in order to respond to it. In order to validate, analyze and evaluate the proposed solution for the DARP using different configurations and in a context closer to the real world, we also propose in this document, all the modeling and development process of a Discrete Event Simulation that reflects in a way a flexible transportation system operation. Additionally, we also present the results of a set of tests done using different configurations, to some mechanisms (search algorithms) for finding and optimizing solutions, for the static approach of the modeled DARP. Finally, we also present the results for the tests performed using simulation for the dynamic DARP, in order to understand the influence that the increase in the demand has in the proposed DARP solution.
Description
Keywords
Transporte flexível DARP Problemas de routing de veiculos Simulação e otimização Flexible transportation Dial-a-Ride problem Vehicle routing problem Simulation and optimization Engenharia Informática Faculdade de Ciências Exatas e da Engenharia