Research On Car-sharing Relocation Problems Based On Variable Neighborhood Tabu Search Algorithm

Sharing economy has become a popular way of life at present.Bicycles and chargers can be used anytime and anywhere,and renting idle rooms and items brings many conveniences to people.In recent years,the car-sharing industry has gradually grown,and automotive technology has gradually improved.The launch of electric vehicles has made the competition between the industries more and more intense.Due to the limitations of urban terrain,climate and other factors,electric vehicles are not suitable for nationwide deployment.The Northeast region uses fuel-based vehicles as the main models of car-sharing.Compared with environmentally-friendly and economical electric car-sharing companies,fuel-based car-sharing companies need a more reasonable operation model while paying attention to energy consumption and environmental protection.There are currently two ways to return cars in the current car-sharing industry:return cars at designated sites(two-way mode)and return cars at any site(one-way mode).In order to improve their competitiveness,the fuel-based car-sharing companies surveyed in this article proposed the service mode of returning vehicles in the operating area(free-floating mode),so companies need to hire Operators to relocate idle vehicles.According to the survey,the daily operation and maintenance cost of enterprises occupies a considerable proportion and needs to be optimized.According to the specific working methods of enterprise relocation sharing cars,this paper determines that the problem to be solved is the relocation problem of car-sharing,and abstracts it as a pick-up and delivery problem.Because the driver can only drive one car at the same time,and needs to visit the shared car before the parking site,and the parking lot can be accessed many times,we finally proposes Vehicle Routing Problem with Ordered Relocation Pickup and Delivery Problems(VRPORPD),the goal is to optimize the relocation path for operators and reduce operation and maintenance costs.In the existing studies,the literature on route optimization in the staff-based carsharing relocation problem is mostly focused on the study of the one-way operation model.The literature on the staff-based car-sharing relocation path optimization problem in the free-floating mode is less,most of the literature to determine the enterprise’s decision support system through demand forecasting or improve the mathematical model,there are few studies on minimizing the distance of the carsharing relocation path.The VRPORPD problem is a single parking lot,single vehicle type,vehicle(referring to staff)load constraint is 1,no hard and soft time window constraints,the parking lot is accessible multiple times,customers(sharing car spots and parking lot vacant spots)have a strict order of pick-up and delivery.In response to this problem,the main content of this article is:(1)With the goal of minimizing the cost of relocating vehicles,relevant constraints are added to the vehicle routing problem model,and a combined optimization model of the VRPORPD problem is constructed.(2)Design the Variable Neighborhood Tabu Search Algorithm(VNTS)to solve the VRPORPD problem.(3)The collected actual operation and maintenance records were processed by data cleaning,demand assignment,and marking of longitude and latitude coordinates,forming a total of 30 sets of travel calculation examples for 21 different scales.At the same time,according to the three distributions of the Solomon cases,21 types of Solomon construction cases of the same scale were randomly constructed,a total of 21 groups.In this paper,the study example of Woxiang travel and Solomon construction example are used as research test and experimental examples to verify the correctness and effectiveness of the model and algorithm.(4)Use the three-operator tabu search algorithm to determine the two ideal operator connection methods,and use the experimental results as the benchmark group to compare whether the variable neighborhood tabu search algorithm can improve it.The main contributions of this paper are as follows:(1)A new delivery problem model,VRPORPD model is proposed.(2)Two kinds of experimental examples which can be applied to VRPORPD are constructed to provide reference for future scholars.(3)A variable neighborhood tabu search algorithm is designed to solve the practical example.The effectiveness of vnts is proved by comparing the three-operator tabu search algorithms.(4)From the perspective of staff scheduling distance of shared vehicles,it provides decision-making reference for car-sharing enterprises in daily operation and maintenance,and supplements the relevant research on "free floating car-sharing mode" and "pick-up and delivery problem".The experimental results in this paper show that the VNTS framework is constructed based on the connection sequence of the two operators determined by the three-operator tabu search.The average improvement of the travel example of Woxiang is 6.4203%and 5.3249%.There is only 1 group of results in 30 groups.The reason is that there is almost no difference between the longitude and latitude coordinates of each shared car and parking lot,and a better solution has been found in the process of the three-operator tabu search.The solutions of the 21 sets of Solomon structural cases have been improved,with an average improvement of 5.3409%and 5.6997%.The overall improvement effect of VNTS is obvious.