Problema share-a-ride : uma proposta de pontos e depósitos intermediários

Abstract

Resumo: O transporte urbano vem sendo modificado por novas tecnologias, permitindo aplicações que atendam necessidades específicas e aumentem a taxa de ocupação dos veículos. O transporte por aplicativo sob demanda é uma aplicação das tecnologia no meio urbano, oferecendo viagens individuais e compartilhadas, inclusive para fretes. Uma abordagem que trata disso na literatura é o Share-a-Ride Problem (SARP), que busca o planejamento a mínimo custo de viagens entre origens e destinos especificados, para serem atendidos por uma frota também especificada, em que é permitido o compartilhamento de veículos entre os clientes. Cada viagem pode ser diferenciada entre bens ou pessoas. Este cenário é uma aplicação atual das tecnologias de Mobility as a Service (MaaS), conhecidas como viagens por aplicativos ofertadas por grandes empresas, que buscam menores despesas para os clientes, maior ocupação dos veículos e, por consequência, menores emissões de gases poluentes. Usualmente, as frotas responsáveis pelos atendimentos nestes ambientes é composta por motoristas sem vínculo direto com a empresa. Estes motoristas são chamados de motoristas ocasionais, por combinarem seus trajetos pessoais com entregas ocasionais. No intuito de construir um ambiente mais colaborativo e adaptado às necessidades dos motoristas, a presente tese propõe a inserção do conceito de paradas planejadas. Desse modo, neste trabalho foram propostas quatro variações do SARP, sendo que duas contemplam o conceito de paradas planejadas para o motoristas, os Depósitos Intermediários, e duas contemplam o conceito de paradas intermediárias para os clientes, chamadas de Pontos Intermediários e baseadas no Multi-Drop Pickup and Delivery Problem. Além disso, o SARP apresenta limitações em tempo de processamento na resolução exata para instâncias de médio e grande porte. Portanto, foram adaptadas a matheurísticas Fix & Optimize e a metaheurística ALNS para resolver o problema. Comparando os resultados com a resolução exata, as estratégias propostas alcançaram soluções factíveis para todas as instâncias, de até 55 clientes e 5 veículos. Além disso, chegaram ao ótimo em 35% dos casos.

Abstract: Urban transport has been modified by new technologies, allowing applications that answer specific needs and increase the occupancy rate of vehicles. Transport by on-demand application is an application of technology in urban areas, offering individual and shared trips, including freight. An approach that deals with this in the literature is called the Share-a-Ride Problem (SARP), which seeks to plan trips at a minimum cost between specified origin and destination points to be served by a specified fleet, allowing the sharing of vehicles between customers. Each trip can be assigned between goods or people. This scenario is a current application of Mobility as a Service (MaaS) technologies, known as travel by applications offered by large companies, which provides lower expenses for customers, higher vehicle occupancy, and, consequently, lower-emission greenhouse gases. Usually, the fleets responsible for services in these environments are composed of drivers with no direct relationship with the company. These drivers are called occasional drivers, as they combine their personal journeys with occasional deliveries. In order to build a more collaborative environment adapted to the needs of drivers, this thesis proposes the insertion of the concept of planned stops. Thus, four variations of the SARP were proposed in this work, two of which contemplate the planned stops for the drivers, the Intermediate Deposits, and two the concept of intermediate stops for the customers, called Intermediate Points and based on the Multi-Drop Pickup and Delivery Problem. In addition, SARP has processing time limitations on an exact resolution for medium and large instances. Therefore, the Fix & Optimize matheuristics and the ALNS metaheuristics were adapted to solve the problem. Comparing the results with the exact resolution, the proposed strategies achieved feasible solutions for all instances, up to 55 customers and 5 vehicles. In addition, they reached the optimum in 35% of cases.