Dissertação

{en_GB=Go-Together - A novel trajectory-based journey sharing platform for collective events} {} EVALUATED

{pt=Os automóveis estão enraizados no nosso modo de vida e são de longe o transporte terrestre mais utilizado. No entanto, o seu uso acarreta um custo financeiro, psicológico e ambiental. Numa procura por soluções e alternativas, a partilha de carro surge como uma opção promissora e viável. Apesar de a partilha de carro poder ser planeada de boca em boca, o crescimento de algumas plataformas proeminentes tem provado que é uma área que beneficia de soluções online. O desafio intrínseco a estas plataformas é o de agrupamento de utilizadores. As aplicações comuns fazem um agrupamento 1-para-n, visto que a sua utilização é iniciada para uso pessoal. Esta dissertação explora a implementação de uma plataforma focada em eventos colectivos, que são partilhados entre conhecidos, e que calcula o melhor agrupamento de participantes. Este foco torna as soluções existentes insuficientes devido há mudança de paradigma para n-para-n, que, em nosso conhecimento, nunca foi previamente abordado. Múltiplos métodos e tecnologias foram analisados para providenciar uma solução eficiente, escalável e capaz de calcular a melhor (ou quase melhor) rota possível. Os utilizadores interagem com a plataforma através de uma aplicação móvel onde colocam os seus parâmetros. De seguida, o backend agrupa os utilizadores empregando uma combinação de heurísticas e optimizações combinatórias para minimizar a distância percorrida e o número de carros. Com a nossa avaliação descobrimos que as soluções de optimização combinatória produzem os melhores resultados. No entanto, as abordagens heurísticas sobressaem em eventos maiores., en=Automobiles are an intrinsic part of our way of life and are by far the dominant form of inland transport. Its use, however, entails a financial, psychological and environmental cost. Among fierce search for alternatives, ride-sharing becomes a promising and viable solution. Ride-sharing can be organized through word of mouth, however, prominent ride-sharing platforms have shown that this is an area that greatly benefits from online platforms. The intrinsic challenge faced is that of clustering users in groups. General solutions have 1-to-n matchmaking, as the participation in ride-sharing is usually initiated solo. This dissertation explores the implementation of a platform that focuses on collective events, which are distributed amongst acquaintances, and calculates the best clusters of participants. This focus renders mainstream solutions inappropriate by changing the paradigm to n-to-n matchmaking which has, to the best of our knowledge, never been tackled before. Several different methodologies and technologies were analyzed in order to provide an efficient and scalable solution capable of providing the best route possible (or close to best). Users will interact with the platform via a mobile application where they input constraints for the event. Subsequently, the backend will cluster users together using a combination of heuristics and combinatorial optimization solution to minimize the distance traveled and the number of cars. With our evaluation we found that combinatorial optimization solutions provide the best results. However, for events of larger size, heuristic approaches excel with faster execution times.}
{pt=Partilha de carro, Eventos colectivos, Aplicação móvel, Agrupamentos, Heuristicas, Optimização combinatória, en=Ride-sharing, Collective events, Mobile application, Clustering, Heuristics, Combinatorial optimization}

Maio 30, 2019, 10:30

Orientação

ORIENTADOR

João Pedro Faria Mendonça Barreto

Departamento de Engenharia Informática (DEI)

Professor Auxiliar