Constructive population algorithm for vehicle relocation problem in free-return car-sharing systems

This article proposes the operator-based vehicle relocation problem in free-return car-sharing systems. With the objective of minimizing total cost, considering factors such as differences in employee capabilities, network demand and capacity and whether vehicles must be relocated, we build a parking-lot based mixed integer programming and design a Constructive population algorithm based on probabilistic elite set (CPAPES). CPAPES uses virtual employee combinations to control the quality and diversity of individuals in the population, uses virtual cost vectors as genetic information, adopts an elite-set based probability construction method to generate individuals and multiple neighborhood search operators and variable neighborhood search techniques to improve individuals. Based on the characteristics of real data, we generate 832 instances in different scales under 16 scenarios to conduct numerical experiments. The experimental results validate the effectiveness of CPAPES and reveal the impact of employee capabilities, the proportion of vehicles that must be relocated, the spatial distribution of vehicles and the number and capacity of parking lots on the total cost of relocating vehicles. This article not only enriches the research on vehicle relocation problem, but also provides scientific decision support for car-sharing operators to reduce costs and improve efficiency. © 2024 Systems Engineering Society of China. All rights reserved.