技术摘要：
本发明提供了一种共享汽车车辆调度及调度员路径优化方法。该方法包括：根据共享汽车的调度需求、站点的位置、每个站点的容量和站点之间的最短距离数据信息，获取所有可行的备选车辆调度任务，根据共享汽车车辆的三种状态和设定的假设条件构建并求解第一阶段的线性整数  全部
背景技术：
共享汽车是一种新兴的交通模式，随着社会经济发展及网络技术的成熟，以及其 本身既拥有小汽车便捷的特点，又具有公共交通节能环保的属性，共享汽车近几年得到快 速发展，其规模与辐射范围不断扩大，有着广阔的发展前景。虽然共享汽车灵活性高，用户 租还方便，在提高资源利用率、减少汽车保有量等方面发挥了作用，但在运营方面还具有诸 多挑战，其中车辆分布不均衡现象引起人们极大重视。用户用车需求非均衡性导致站点间 车辆失衡从而无法满足用车需求，进而产生了用户体验差、订单流失等不良影响。运营公司 为解决该问题通常会派调度员将车辆从过饱和站点调度到车辆短缺的站点。如何制定有效 的调度方案，缓解汽车分时租赁系统的供需不平衡，这是运营公司亟待解决的问题，也是共 享汽车能否大规模推广的关键因素。 共享汽车的车辆调度任务需要调度员执行，在研究如何调度车辆时应考虑到调度 员如何安排，两种资源是否能够很好的配合。但是现阶段，对于如何确定调度任务的研究已 经有一定的积累，但是在调度车辆时考虑调度员活动的相对较少。现有技术中的求解调度 车辆是车辆及调度员的路径的常用方法有两种：集计模型方案和非集计模型方案。 集计模型方案是根据用户的使用时间将用户划分，将同属于一个时间段的用户划 分为一类考虑，不为用户指定车辆。该方法基于时空网络的表达方式，将规划时段按等间距 划分为若干时间步，网络中的每个点代表在某个时间步站点的状态，每个弧线代表与车辆、 用户和调度员相关的活动。根据已知的站点信息(如位置、容量、数量等)，通过不同状态之 间的相互关系构建数学模型表达式，求解该数学模型进而产生车辆和员工的时空路径。有 研究基于时空网络对调度员的活动进行了细分，分为：在站点等待、两种维修活动、调度车 辆和利用其他交通方式，建立混合整数规划模型安排参与每类活动的调度员。有研究将弧 线划分为4类：用户使用车辆、车辆或调度员在站点等待、车辆被调度员驾驶和调度员利用 其他交通方式，以收益最大化为目标分别针对运营时段和非运营时段构建数学模型。上述 集计模型方案的缺点为：基于集计的思想构建模型时，现有研究假定调度员在站点之间的 旅行时间以时间步长为单位(多假定时间步长为15分钟)，求解的结果只能告知调度员所执 行任务的出发时间段，调度员不知道具体出发时刻，得不到调度员紧凑的时刻表，会使得效 率降低。在实际运作中，调度员通常会凭经验决策，缺乏科学合理的决策工具。 非集计模型方案考虑用户与用户之间的衔接关系，记录每辆车的行驶路径。有方 案将车辆调度与调度员调度问题分别用多旅行商模型表示，将每个调度任务和订单看作多 旅行商问题中的一个顶点。上述非集计模型方案的缺点为：该模型得到了每个车辆的轨迹 以及调度员应该执行的调度任务，但是没有分工明确，没有安排每个调度员的路径和时刻 表，没有解决调度员路径问题。 6 CN 111612358 A 说　明　书 2/13 页
技术实现要素：
本发明的实施例提供了一种共享汽车车辆调度及调度员路径优化方法，以克服现 有技术的问题。 为了实现上述目的，本发明采取了如下技术方案。 一种共享汽车车辆调度及调度员路径优化方法，包括： 根据共享汽车的调度需求、站点的位置、每个站点的容量和站点之间的最短距离 数据信息，获取所有可行的备选车辆调度任务，所述共享汽车的调度需求包括取车站点、还 车站点以及出发时间； 设置共享汽车车辆的三种状态为：被用户使用、被调度和停放在站点，根据所述共 享汽车车辆的三种状态和设定的假设条件构建第一阶段的线性整数规划模型，所述线性整 数规划模型的目标函数是最小化未满足需求的惩罚成本和车辆调度成本之和；求解所述线 性整数规划模型，得到调度员需要执行的车辆调度任务； 对所述调度员需要执行的车辆调度任务的出发时间段和到达时间段属性进行时 间粒度转换，求解出车辆调度任务的时间窗，将所述调度员需要执行的车辆调度任务的取 车站点、还车站点和时间窗参数输入到第二阶段的数学模型中，求解出调度员的时刻表和 路径。 优选地，所述的根据共享汽车的调度需求、站点的位置、每个站点的容量和站点之 间的最短距离数据信息，获取所有可行的备选车辆调度任务，所述共享汽车的调度需求包 括取车站点、还车站点以及出发时间，包括： 获取共享汽车站点的位置、每个站点的容量、站点之间的最短距离数据信息，根据 所述数据信息和共享汽车调度需求构建所有可行的车辆调度任务； 给定某个共享汽车的调度需求包括取车站点Ou、还车站点Du、出发时间Su以及的组 合，根据式(1)得到满足该调度需求的车辆调度任务的到达时间的取值集合G(Ou,Du,Su)； 每个车辆调度任务u∈U有4个属性：(Ou,Du,Su,Au)，其中Ou表示取车站点，Du表示还 车站点，Su表示出发时间段，Au表示到达时间段，其中，将规划时段按照等间距划分为若干时 间步，|T|是所有时间步的数量，wt是时间步t的初始时刻，et是时间步t的结束时刻， 是 两个站点之间的旅行时间，令集合U表示所有可行的车辆调度任务，这些车辆调度任务满足 所述共享汽车调度需求。 优选地，所述设定的假设条件包括： 假设条件1：用户提前一天预约车辆，且用户在同一天取、还车辆； 假设条件2：调度员的数量足够； 假设条件3：调度成本低于购买车辆的成本； 假设条件4：每个调度员在一天的开始于某个站点出发，该天结束后调度员也要回 到该站点； 7 CN 111612358 A 说　明　书 3/13 页 优选地，所述的设置共享汽车车辆的三种状态为：被用户使用、被调度和停放在站 点，根据所述共享汽车车辆的三种状态和设定的假设条件构建第一阶段的线性整数规划模 型，所述线性整数规划模型的目标函数是最小化未满足需求的惩罚成本和车辆调度成本之 和；求解所述线性整数规划模型，得到调度员需要执行的车辆调度任务，包括： 设置共享汽车车辆的三种状态为：被用户使用、被调度和停放在站点，根据共享汽 车车辆的三种状态和所述所有可行的车辆调度任务构建第一阶段的线性整数规划模型，并 求解线性整数规划模型，得到所述所有可行的车辆调度任务中的调度员需要执行的车辆调 度任务； 所述线性整数规划模型的目标函数是最小化未满足需求的惩罚成本和车辆调度 成本之和，设置的约束有容量约束、流量平衡约束和最大借车量约束，所述线性整数规划模 型中的参数和符号定义如下： t,t'        时间步序号 i           订单序号 j,j'         站点序号 I           订单集合 J            站点集合 Oi          订单i的取车站点 Di          订单i的还车站点 Si          订单i的出发时间步 Ai          订单i的到达时间步 q            总车辆数 cj           站点j的容量 djj '         站点j和j'之间的距离 α            每个未满足的预定需求惩罚费用 β           单位车辆调度费用 xi           0-1变量，若订单i被满足则取1否则取0 zu          执行车辆调度任务u的车辆数            在时间步t的结束时刻停放在站点j的车辆数 第一阶段的线性整数规划模型如下： 8 CN 111612358 A 说　明　书 4/13 页 优选地，所述的对所述调度员需要执行的车辆调度任务的出发时间段和到达时间 段属性进行时间粒度转换，求解出车辆调度任务的时间窗，包括： 对于任意一个第一阶段的车辆调度任务u，定义λu为调度员从出发站点出发的时 间点，Δ为每个时间步的长度，利用公式(10)-(11)对第一阶段的车辆调度任务中以时间步 为单位的时间变换为以分钟为单位的时间窗，该时间窗的约束条件为(12)-(13)： eu为调度任务u的时间窗的开始时间，lu为调度任务u的时间窗的结束时间，则调度 任务u的时间窗为[eu,lu]。 优选地，所述的将所述调度员需要执行的车辆调度任务的取车站点、还车站点和 时间窗参数输入到第二阶段的数学模型中，求解出调度员的时刻表和路径，包括： 将调度员需执行的调度任务的取车站点、还车站点和时间窗作为参数输入到第二 阶段的数学模型中，用ILOG  CPLEX求解器求解第二阶段的数学模型，求解出调度员的时刻 表和路径； 所述第二阶段的数学模型的目标函数约束调度员利用除共享汽车之外的其他交 通方式来往于站点之间，约束有调度员从某个站点出发一天结束后要回到该站点，每个调 度任务都能被执行且只执行一次，某个调度任务的取车和还车站点被同一个调度员访问， 调度任务的取车站点的访问时间是上一个调度任务的取车站点访问时间加上调度任务的 时间加上利用其他交通方式的时间，访问取车站点的时间在时间窗范围以内； 所述第二阶段的数学模型的求解中用到以下的索引、参数及变量： s                 调度员索引 p,q               调度任务索引                 调度员s的虚拟起始任务                 调度员s的虚拟结束任务 Sr                调度员集合 Q                从第一阶段得到的待执行的调度任务 Q-               所有调度员的虚拟起始任务 Q                所有调度员的虚拟结束任务      Q的扩展集合 9 CN 111612358 A 说　明　书 5/13 页      Q的扩展集合 χ                调度员利用其他交通方式来往站点时单位成本费用 M               一个足够大的正数               如果调度员s执行完调度任务p从该任务的还车站点到达调度                  任务q的取车站点则取1，否则取0，其中p≠q 所述第二阶段的数学模型为： 求解结果包括多个调度员的时刻表和路径，求得集合Sr中每个调度员的路径及时 刻表。 由上述本发明的实施例提供的技术方案可以看出，本发明提出的优化人工调度共 享汽车时的路径及时刻表方法，操作简单，结果清晰明了。本发明能为共享汽车运营商提供 科学合理的决策依据，进而减少车辆的不均衡现象，提高用户的满意率。此外，还能高效利 用车辆、停车位及调度员等资源，避免资源浪费。 本发明附加的方面和优点将在下面的描述中部分给出，这些将从下面的描述中变 得明显，或通过本发明的实践了解到。 附图说明 为了更清楚地说明本发明实施例的技术方案，下面将对实施例描述中所需要使用 的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本发明的一些实施例，对于本 领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他的 附图。 图1为本发明实施例提供的一种共享汽车车辆调度及调度员路径优化方法的实现 原理示意图； 图2为本发明实施例提供的一种共享汽车车辆调度及调度员路径优化方法的处理 流程图； 图3为本发明实施例提供的一种福建泉州泉港区10个站点的分布示意图； 10 CN 111612358 A 说　明　书 6/13 页 图4为本发明实施例提供的一种单位调度成本对结果的影响示意图。