Exact algorithms and heuristics for Car-Sharing

• Grant number: 17/23343-1
• Support Opportunities: Scholarships in Brazil - Master
• Start date: April 01, 2018
• End date: March 31, 2019
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Theory of Computation
• Agreement: Coordination of Improvement of Higher Education Personnel (CAPES)
• Principal Investigator: Rafael Crivellari Saliba Schouery
• Grantee: Welverton Rodrigues da Silva
• Host Institution: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brazil
• Associated research grant: 15/11937-9 - Investigation of hard problems from the algorithmic and structural stand points, AP.TEM

Abstract

This research project considers a combinatorial optimization problem that arises in car-sharing. The car-sharing problem is based on the selection of a set of driving demands with flexible drop-offs in order to satisfy the maximum number of customers. The drop-offs are said to be flexible because customers can leave the vehicles on parking different from the pick-up location. A customer is satisfied only if all his demands are fulfilled. In particular, the electric car-sharing service has applications in sustainable mobility in urban centers, leading to economic and ecological benefits. Moreover, this problem is also relevant to Computer Science and Operational Research as it is an NP-hard problem even when there are two parking and every customer has two demands. Despite this, until the moment there are only theoretical studies for the car-sharing problem. Therefore, this project proposes the development and implementation of algorithms, both exact and heuristic, and the empirical analysis of these algorithms in real or randomly generated instances, which instances can be solved much more quickly in practice. (AU)

Academic Publications

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

SILVA, Welverton Rodrigues da. Exact and heuristic algorithms for a car-sharing problem. 2019. Master's Dissertation - Universidade Estadual de Campinas (UNICAMP). Instituto de Computação Campinas, SP.