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

来源:《系统工程理论与实践》时间:2025-01-14


图源摄图网

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

一、研究背景与意义

随着我国经济的飞速发展, “低碳经济” 、“共享经济”等概念不断被提出,共享单车、网约车、共享汽车(分时租赁)等一系列共享出行商业模式被社会广泛接受。其中,共享汽车是一种“消费+出行”的O2O(Online to Offline)商业模式,企业通过互联网平台出售车辆的使用权,提供以“里程+时间”计费的随取随停的汽车分时租赁服务,用户通过线上(Online)购买车辆使用权实现消费并满足线下(Offline)的出行需求。相较于传统出行模式,共享汽车除了能低成本且灵活的满足用户的出行需求,还可以有效提高车辆利用率,缓解交通问题和环境问题。自2013年开始,中国的共享汽车行业得到了迅速地发展(2013年EVCARD成立;2015年GoFun成立)。2017年,交通运输部、住房和城乡建设部联合发布《关于促进小微型客车租赁健康发展的指导意见》,明确鼓励分时租赁新业态发展,合理确定分时租赁在城市综合交通运输体系中的定位,进一步促进了共享汽车行业的发展。截至2022年末,50余家汽车分时租赁企业开展经营,180多个城市开通运营,共享汽车投入车辆超过20万辆。

共享汽车主要有双向(two way)、单向(one way)和自由浮动(free floating)三种运营模式。其中,双向模式要求用户从指定网点A取车并归还至A;单向模式下用户从指定网点A取车但是可以归还至任意网点B;自由浮动模式中不存在网点,即用户可以从某个公共停车位取车并且可以停放在任意公共停车位。近年来,包括GoFun和蜗享出行在内的多家共享汽车运营商开始尝试实施任意还模式(free return)。任意还模式下用户从指定的网点A取车但是可以将车辆停放在任意网点或者经营区域内的任意公共停车位。相比于双向和单向模式,任意还模式更具灵活性;相比于自由浮动模式,任意还模式更便于运营管理。但是由于用户出行需求具有不确定与不对称的特点,任意还模式不仅更容易出现网点之间车辆分布不均衡问题,而且还会出现网点内同时短缺车辆以及额外的停车费用等问题。为了满足用户需求同时尽可能减少车辆投入和运营成本,任意还模式更加需要进行车辆重新安置。

任意还模式可以视为单向模式的拓展,任意还模式下的重新安置问题与单向模式下的重新安置问题本质上是资源优化分配与调度问题,但是任意还模式下待安置车辆通常较多并且停放的位置更加分散(不能打包安置),所以问题规模有所提高;再加上同时考虑员工能力不同、网点需求和容量限制、部分车辆必须被安置(累计停车费用过高等原因)而其他车辆可以有选择的安置等条件,使得决策变量增加,决策变量之间的约束关系更为复杂,所以求解难度大大增加。因此,解决任意还模式下的共享汽车重新安置问题,不仅是共享汽车运营商面临的现实管理需求,也是运筹管理学界的一个极大挑战。

二、主要内容

在任意还模式中,共享汽车运营商通常会与一些停车场合作,租赁其停车位停放共享汽车,本文将这些停车场称为共享汽车网点(简称网点)。用户只能从网点取车,但是可以将车辆停放在网点以外的公共停车位(包括路边划线停车位等)。为了尽量满足用户需求同时减少运营成本,运营商需要派遣员工将停放在外的共享汽车重新安置到网点内。每位员工按照指定的顺序对共享汽车进行重新安置,其基本流程是:从基地出发,步行、骑车或者乘坐公共交通工具等找到第一个待安置车辆,将其驾驶至指定的网点内停放,然后重新出发找到第二个待安置车辆,以此类推,直到完成所有指派给员工的车辆安置任务为止,再返回基地。因此,本文提出了任意还模式下基于运营商的共享汽车重新安置问题,即在员工能力限制、网点容量限制以及必须安置的车辆全部被安置等条件下,决定安置哪些车辆、每辆车的目的地网点以及每位员工安置车辆的路径,使得重新安置车辆的总行驶成本、员工的雇佣总成本和未满足网点需求的机会成本之和最小。

本文的主要研究内容包括以下三个方面:

第一,本文构建了一个基于网点的混合整数规划模型。在基于停车位的模型中,通常会将包含Q个停车位的网点拆分为Q个只包含1个停车位并且地址相同的虚拟网点。如果车辆被安置到一个虚拟网点上可以得到可行解,那么将该车辆安置到另外Q-1个地址相同的虚拟网点上仍然可以得到可行解,并且目标函数值相同,此时我们称这Q个可行解互为对称解。对称解的存在会导致大量的退化解,影响求解算法的效率。相比较而言,基于网点的模型具有更少的对称解,因此求解效率更高。

第二,本文设计一个基于概率精英集的构造式种群算法(Constructive Population Algorithm based on Probabilistic Elite Set, CPAPES)。该算法通过构造虚拟员工组合控制种群个体质量和多样性,使用虚拟成本向量作为遗传信息,通过基于精英集的概率构造方法生成种群个体,并且使用多个邻域搜索算子以及变邻域搜索技术优化种群个体。

第三,本文挖掘真实数据特征,考虑员工能力差异情况、网点容量情况、车辆是否必须安置以及待安置车辆的空间分布情况,构造16种测试场景,每种场景下使用不同的参数组合,生成832个不同规模的测试算例。然后通过与CPLEX求解器和其他启发式算法的对比实验验证CPAPES算法的性能,探究员工能力、必须安置的车辆数量占比、待安置车辆的空间分布、网点数量和网点容量等因素对车辆重新安置总成本的影响。

三、主要结论及政策建议

本文针对任意还模式下基于运营商的共享汽车重新安置问题展开研究。该问题要求为每一辆待安置的共享汽车指定网点和员工,同时为每一位员工指定安置顺序,在考虑员工能力差异、网点需求和容量限制、车辆是否必须安置等限制条件下,使得车辆重新安置的总成本最小。本文首先建立了一个基于网点的混合整数规划模型,相较于传统的基于停车位的模型,该模型具有更少的对称解。然后设计了一个基于概率精英集的构造式种群算法。最后依据中国大连某共享汽车平台提供的运营数据特征,生成832个测试算例,在这些算例上进行对比实验测试算法的性能。

实验结果表明,任意还模式下员工能力、必须安置的车辆数量占比、待安置车辆的空间分布和网点容量都会影响车辆重新安置的总成本。员工能力差异越大、必须安置的车辆数量占比越小、车辆空间分布越集中并且网点容量越均匀,总成本越小。其中,必须安置的车辆数量占比对总成本的影响最大。为了降低运营成本,运营商一方面可以建议用户调整停车地点使其靠近网点,另一方面也可以从自身出发,尽量降低必须被安置的车辆的数量、雇佣能力不同的员工、平衡各网点的容量并且增加网点的数量。

四、边际贡献与未来拓展

本文研究成果在丰富重新安置问题相关研究的同时,能够为共享汽车运营商降本增效提供科学决策支持。本文的边际贡献包括以下两点:

(1)本文研究成果为共享汽车运营商实施任意还模式提供解决方案,有助于共享汽车行业降低运营维护成本、提高服务质量,并为我国共享出行行业健康稳定发展提供理论方法和技术支持。

(2)本文提出的任意还模式下基于运营商的共享汽车重新安置问题考虑了员工能力差异、网点需求和容量限制、车辆是否必须安置等现实的运营条件,使得研究内容更加符合实际要求、研究结果更加容易被共享汽车运营商采纳并实践。

未来的研究方向可以包括:

(1)研究同时使用运维车辆和员工的共享汽车重新安置问题,即每位员工从基地出发搭乘运维车辆到达一辆共享汽车停放处,驾驶该共享汽车到达指定的网点,然后从该网点出发再搭乘运维车辆前往下一辆共享汽车停放处,以此类推。

(2)设计更高效的启发式算法、机器学习与启发式相结合的算法以及精确算法求解共享汽车重新安置问题。

五、写作、投稿过程的心得体会

基于车辆路径规划相关问题的研究经验和共享汽车行业的调研经历,我们从现实场景中提炼出了任意还模式以及该模式下的共享汽车重新安置问题,构建了数学规划模型,并在多次实验和调试下,确定了基于概率精英集的构造式种群算法。通过认真撰写和修改,完成了论文的初稿,并投稿至《系统工程理论与实践》。

在审稿过程中,外审专家和编辑部对文章的研究贡献、模型和算法的细节、实验设计、研究启示、参考文献等部分提出了十分重要的建议。在经过反复修改后,本文的质量得到了实质性的提升,我们也对研究问题有了更加深刻的理解。论文的发表离不开编辑部老师的辛勤付出以及各位专家的指导与帮助,对此我们表示衷心的感谢。

 

本文摘编自《系统工程理论与实践》2024年,第44卷,第11期论文《任意还模式共享汽车重新安置问题的构造式种群算法》(点击题目链接全文)
作者:田甜(通讯作者)1,2, 博士,副教授,研究方向:运作管理与优化决策,商务数据分析;刘玉学1, 博士研究生,研究方向:运作管理与优化决策,;唐加福1,博士,教授,研究方向:运作管理与优化决策,数据挖掘与商务智能
       1. 东北财经大学 管理科学与工程学院, 大连 116025;
       2. 辽宁省大数据管理与优化决策重点实验室, 大连 116025