GREEDY ALGORITHM FOR RELOCATION PROBLEM IN ONE-WAY CARSHARING SYSTEMS Report as inadecuate




GREEDY ALGORITHM FOR RELOCATION PROBLEM IN ONE-WAY CARSHARING SYSTEMS - Download this document for free, or read online. Document in PDF available to download.

1 UTBM - Université de Technologie de Belfort-Montbeliard 2 Artelys

Abstract : -In one-way carsharing systems, users can take a car from a station and return it to any other one. Available cars and free parking space at each station, play a major role in the success of these systems. Therefore, carsharing operators recruit employees to relocate cars between the stations to avoid rejection of users’ demands for taking cars or returning them. In this paper, we developed a greedy algorithm in order reduce the number of rejected users- demands, using the minimum number of employees. We used mobility data collected from an operational system to build the users’ demand matrices as input for our algorithm. For example, in a carsharing system which has 20 stations, 150 cars, through 1,374 trips made during one day and 556 expected rejected demands, results show that our algorithm is able to solve 55% of expected rejected demands using 5 employees and more than 80% of these rejected demands using 10 employees. We compared the algorithm with an exact Mixed Integer Linear Programming model solved using IBM ILOG CPLEX optimizer and made the proof of performance also, we evaluated the robustness of the two approaches with stochastic input data using different numbers of employees.-

Keywords : Transport Carsharing Optimization Approximation algorithm





Author: Rabih Zakaria - Laurent Moalic - Alexandre Caminada - Mohammad Dib -

Source: https://hal.archives-ouvertes.fr/



DOWNLOAD PDF




Related documents