任意还模式共享汽车重新安置问题的构造式种群算法

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

本文提出任意还模式下基于运营商的共享汽车重新安置问题,以最小化总成本为目标,考虑员工能力差异、网点需求和容量、车辆是否必须安置等条件,建立基于网点的混合整数规划模型,设计基于概率精英集的构造式种群算法.算法使用虚拟员工组合控制种群个体质量和多样性,使用虚拟成本向量作为遗传信息,采用基于精英集的概率构造方法生成种群个体,并且通过多个邻域搜索算子和变邻域搜索技术改进种群个体.本文根据真实数据特征生成了16种场景下832个不同规模的算例进行数值实验,实验结果验证了算法的有效性,并且揭示了员工能力、必须安置的车辆数量占比、待安置车辆的空间分布、网点数量和网点容量对车辆重新安置成本的影响.研究成果在丰富重新安置问题相关研究的同时,能够为共享汽车运营商降本增效提供科学决策支持.

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.