Dynamic Taxi Sharing and Ridesharing: A Framework and Algorithms for the Optimization Problem

• Grant number: 13/06746-4
• Support Opportunities: Scholarships in Brazil - Master
• Effective date (Start): July 01, 2013
• Effective date (End): December 31, 2013
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Theory of Computation
• Principal Investigator: Eduardo Candido Xavier
• Grantee: Douglas Oliveira Santos
• Host Institution: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brazil

Abstract

The goal of this project is to propose methods to facilitate the ridesharing and taxi sharing.Our focus is in the study of how the efficiently share vehicles, especially problems belonging to the class of Dial-a-Ride Problems.We are particularly interested in a problem called dynamic taxi sharing with time windows problem (TSTWP). The problem is to assign taxis vehicles to passengers requests, which are spread over different locations in a given city.Several constraints must be considered: the vehicle capacity , the cost of a shared ride must not exceed the cost of a private ride, each passenger and taxi has time windows, so the problem also consists of assign a time for each pickup and delivery event, within these time windows. We always want to maximize the number of served requests and minimize the total cost incurred to passengers.Although we focus on the taxi sharing problem, we show that our model is easily extendable to model the ride-sharing situation.Our objective is to develop exact and heuristic methods in order to deal with this problem and to develop a framework demonstratinghow the proposed system can be used. It is also our objective the study of algorithms to find minimum paths in large graphs representing maps, sincethis is mandatory to solve the TSTWP efficiently.

Academic Publications

(References retrieved automatically from State of São Paulo Research Institutions)

SANTOS, Douglas Oliveira. Framework e algoritmos para o problema dinâmico de compartilhamento de veículos. 2014. Master's Dissertation - Universidade Estadual de Campinas (UNICAMP). Instituto de Computação Campinas, SP.