| dc.description.abstract | Carsharing systems have emerged as an attractive form of transport in urban areas since the beginning of the 21st century. Effective carsharing systems carry significant environmental advantages as well as economic advantages for its users. Challenges faced by carsharing organizations can be modeled and solved using Operations Research (OR) methods in order to enhance system performance. As a result, carsharing has received increased attention in the OR community in the recent years. In this thesis, three gaps are identified in the existing carsharing literature: Operation of free-floating systems, repositioning under realistic conditions, and integrated routing of rental cars and operators to handle rental cars in repositioning operations.
Aiming to close the aforementioned gaps, the Static Free-Floating Electric Vehicle Carsharing Handling Problem (SFFEVCHP) is defined and modeled. In the SFFEVCHP, electric rental cars in a free-floating carsharing system are repositioned to charging stations when their battery level fall below a predefined threshold. The charging location decision takes balancing the distribution of cars in the business area into account. The rental cars are moved by operators that are transported between charging stations and rental cars by service vehicles. The problem includes several connected decisions. First, the optimal location to charge rental cars must be determined. Second, the routes of service vehicles transporting operators between rental cars in need of charging must be decided. The time and location to drop off an operator affects the pick up of the operator leading to temporal and spatial interdependencies between the routing of operators and service vehicles. Central to the problem is the trade off between the cost of not meeting demand due to a disadvantageous distribution of cars in the system and the cost of transporting operators to charge and reposition rental cars.
We first model the SFFEVCHP as a mixed integer program. The complexity of the problem requires an approximate solution method in order to solve real world instances. A Hybrid Genetic Search with Adaptive Diversity Control (HGSADC) based on the work of Vidal et al. (2012) is therefore developed. To be able to use the HGSADC on this complex problem type, new chromosomes to represent individuals have been developed and the Genetic Algorithm (GA) operators are adapted to the problem. Also, a novel construction heuristic inspired by construction heuristics for the Dial-A-Ride problem is proposed.
To demonstrate the capabilities of the presented algorithm, 15 instances with sizes ranging from 100 to 200 rental cars in need of handling are solved. Ten algorithm runs are executed for each instance. The algorithm is able to solve all the instances with an average gap to the best known solution of 1.3 percent and a gap coefficient of variance of 0.9 percent in less than an hour. Furthermore, solutions with an average gap of 1.9 percent are found after ten minutes with a coefficient of variance of 0.9 percent. To demonstrate the value of repositioning in conjunction with handling, the algorithm is run while prohibiting repositioning. Comparing these results to the results with repositioning for an instance with 100 rental cars yield a net total cost improvement of 3.7 percent. As the total cost captures the profit effect of the repositioning activities, this improvement can likely be directly transferred to the gross profit margin of the carsharing companies.
The results are a clear indication of the strength of the proposed algorithm. Realistic systems studied typically have 100 to 150 rental cars in need of handling at a given time. Hence, we are consistently able to solve realistic problem sizes yielding high quality solutions. Furthermore, the problem formulation combining repositioning with necessary charging and maintenance provide the opportunity for operators to realize the added profits of repositioning while only marginally increasing operational costs. We believe this presents a significant enhancement of existing models and algorithms. In addition to establish the effectiveness of the HGSADC for the SFFEVCHP, this thesis exhibits the capabilities of the algorithm for routing problems with complex synchronization constraints including spatial and temporal interdependencies. | |
