Optimization and simulation of one-way carsharing operations

Abstract

Carsharing is a transportation option with great potential, allowing people to use a private vehicle without having to own it. Nowadays carsharing systems are implemented almost all over the world, being the round-trip system the most predominant. However, the implementation of one-way systems has been expanded considerably since 2008. Despite the proliferation of carsharing, there are few analytical studies addressing its management. One-way systems offer users more flexibility. Contrarily to the typical round-trip systems, one-way systems allow users to pick up the vehicles at one station and deliver them to a different station from the one where they were picked up. This flexibility poses added management complexities which have never been solved completely. Most of the existing studies cannot accurately represent the reality of these systems, due to algorithmic, structural, and functional complexities. Therefore, carsharing is an interesting topic to be addressed under an operations research perspective. This thesis has two main objectives. The first objective consists in assisting one-way carsharing companies to plan and manage their systems in a more profitable way while at the same time offering users a good quality of service. The second objective targets helping round-trip carsharing companies to start offering one-way trips, taking full advantage of idle fleets and offering users a transportation option for other trips than just shopping or leisure. Three optimization models as well as a simulation model have been developed to reach the previously defined objectives. In this thesis, we consider the perspectives of two main stakeholders: the carsharing provider and the carsharing user. It is our belief that the improvement of carsharing systems from these two perspectives is also relevant to transportation authorities and to local and central governments, since it provides a complement to existing private and public transportation modes. The greatest problem of one-way carsharing companies is associated with the imbalance of vehicles across stations. This is due to the imbalance inherent to trip patterns in most of the cities worldwide. In this work, the two approaches proposed to mitigate this problem are: vehicle relocation between stations through a staff of drivers, and changing the price of the trips according to its effect on system balance. With respect to relocation operations, both an optimization model and a simulation model are developed. For the second approach, only an optimization model is proposed. Given the complexity inherent to this optimization model, we resorted to an iterated local search meta-heuristic algorithm. All of the developed models aim at maximizing the profit of the carsharing companies taking into consideration the revenue obtained through the trips paid by carsharing users, and the costs involved, namely fleet, stations and relocation operations costs. For the trip price changing approach, costs associated with relocation operations are not considered since vehicle relocation is not considered. As one-way carsharing systems present greater flexibility in terms of trip purposes (for example, commute, shopping, and leisure), round-trip companies have started to consider providing one-way trips. For instance, in 2014, Zipcar began accepting some one-way trips. Notwithstanding, as it was previously said, one-way trips are more difficult to manage than the round-trip ones. Thus, there is the need to study the integration of both carsharing types, which is another objective of this thesis. For this purpose, an optimization model is developed with the same goal as the previous, the maximization of carsharing companies’ profit. All the models are applied to realistic case studies. For the approaches studied to balance the vehicle stocks in one-way carsharing systems, the municipality of Lisbon, in Portugal, is used. For the integration of both round-trip and one-way carsharing, the Zipcar round-trip carsharing service in Boston, Massachusetts, USA, is considered. The developed methodological approaches are able to deal with the size and complexity of the case studies considered, as all the applications reached satisfactory results and some of them achieved optimal results. Results show the usefulness of these methodologies as viable tools to help carsharing companies plan and manage their systems, improving the level of service offered to the users.

O carsharing é um modo de transporte com grande potencial, permitindo o uso de um carro sem os custos inerentes à sua aquisição e manutenção. Atualmente, os sistemas de carsharing existem em praticamente todo o Mundo, sendo o sistema de round-trip o mais predominante. No entanto, a implementação de sistemas de one-way carsharing tem-se expandido consideravelmente desde 2008. Apesar da proliferação do carsharing, ainda existe um número reduzido de estudos analíticos que tentem resolver os problemas relacionados com a sua gestão. Contrariamente aos sistemas tradicionais de round-trip carsharing, os sistemas de one-way carsharing oferecem aos utilizadores uma maior flexibilidade, permitindo aos utilizadores recolherem os veículos numa estação e devolverem-nos em outra diferente da inicial. Esta flexibilidade implica problemas adicionais para as empresas na gestão da sua frota, os quais nunca foram totalmente solucionados. A maioria dos estudos existentes não consegue representar fielmente a realidade destes sistemas, devido à sua complexidade algorítmica, estrutural e funcional. Deste modo, o carsharing torna-se um tópico interessante de estudo sob uma perspetiva de investigação operacional. Esta tese tem dois objetivos principais. O primeiro objetivo consiste em auxiliar as empresas de one-way carsharing a planear e gerir os seus sistemas de uma forma mais lucrativa, oferecendo, ao mesmo tempo, uma boa qualidade de serviço aos seus utilizadores. O segundo objetivo visa ajudar as empresas de round-trip carsharing a oferecer viagens one-way, tirando completo proveito da sua frota enquanto oferecem aos seus clientes uma alternativa de transporte para outras viagens que não as de compras ou lazer. Três modelos de otimização e um modelo de simulação foram desenvolvidos para alcançar os objetivos referidos. Nesta tese, as perspetivas de dois intervenientes principais nestes sistemas são considerados: a das empresas, e a dos utilizadores. A melhoria dos sistemas de carsharing consoante estas duas perspetivas é relevante para as entidades locais e centrais que gerem os transportes, já que estes sistemas constituem um complemento ao transporte privado e ao transporte público existentes. O maior problema que as empresas de one-way carsharing enfrentam prende-se com o desequilíbrio de stocks de veículos nas estações. Este surge devido ao desequilíbrio no padrão de viagens existente na maioria das cidades. Nesta tese, as duas abordagens propostas para combater este problema são: operações de relocalização de veículos entre estações através de um conjunto de condutores contratados pela empresa de carsharing, e variação dos preços das viagens de acordo com o seu efeito no equilíbrio do sistema. No que se refere à primeira abordagem, um modelo de otimização assim como um modelo de simulação são desenvolvidos. Para a segunda abordagem, um modelo de otimização é desenvolvido. Dada a complexidade inerente a este modelo, recorremos a uma meta-heurística de procura local com iterações para a sua resolução. Todos os modelos propostos têm como objetivo a maximização do lucro obtido pela empresa, considerando a receita obtida através das viagens pagas pelos clientes, e todos os custos envolvidos, nomeadamente os custos relativos à frota de veículos, às estações e às operações de relocalização. Para a abordagem correspondente à variação dos preços das viagens, os custos das operações de relocalização não se consideram, visto que estas não são efectuadas em simultâneo com a política de preços. Devido ao facto do one-way carsharing apresentar uma maior flexibilidade relativa aos motivos de viagem (por exemplo, pendulares, compras e lazer), as empresas de roundtrip carsharing começaram a pensar oferecer viagens one-way. Em 2014, a Zipcar começou a providenciar este tipo de viagem. Não obstante, como já foi referido anteriormente, estas viagens são mais difíceis de gerir do que as viagens de round-trip. Desta forma, existe a necessidade de estudar a integração de ambos os tipos de carsharing, o que constitui outro objetivo desta tese. Com esta finalidade, um modelo de otimização é desenvolvido com o mesmo objetivo dos anteriores, a maximização do lucro da empresa. Todos os modelos desenvolvidos foram aplicados a estudos de caso realistas. Para as abordagens propostas para equilibrar os stocks de veículos nos sistemas de one-way carsharing, é utilizado o município de Lisboa, em Portugal. Para o estudo da integração de ambos os tipos de carsharing é considerado o serviço de round-trip carsharing da Zipcar existente em Boston MA, EUA. As metodologias desenvolvidas são capazes de lidar com a dimensão e complexidade dos estudos de caso considerados, já que todas as aplicações alcançaram resultados satisfatórios, sendo mesmo possível atingir resultados ótimos em algumas delas. Os resultados mostram a utilidade destas metodologias como ferramentas viáveis para ajudar as empresas de carsharing a planear e gerir os seus sistemas.