Optimization for Joint Relocation of Carsharing Based on Modular Simulation
-
摘要:
运营商在调度车辆时单独采用员工或顾客调度策略均难以有效解决共享汽车分布不均衡导致的盈利难问题. 为此,在传统时空网络基础上,考虑道路拥堵和用车需求随时间变化对运营的影响,基于C# 语言和O2DES (object-oriented discrete event simulation)离散事件仿真框架,建立由模块化站点和路段模型组成、可高效率运行的共享汽车仿真系统;在此基础上,提出一个以运营商日均净收益最大化为目标,联合决策车辆库存量阈值和行程定价的仿真优化模型,并为解决随机环境下的全局优化问题,设计了EGA-OCBA (elitist genetic algorithm with optimal computing budget allocation)算法;最后,以成都市的5个共享汽车站点为例,验证了仿真优化模型的有效性. 仿真优化结果表明:在相同车队规模下,与采用固定价格的顾客调度策略相比,联合策略可使日均净收益提升10.37%~162.30%;与单独的员工调度策略相比,联合策略可使日均净收益提升15.34%.
-
关键词:
- 共享汽车 /
- 离散事件仿真 /
- 动态定价 /
- 阈值触发调度 /
- 精英遗传算法(EGA) /
- 最优计算量分配(OCBA)
Abstract:It is difficult for operators to effectively solve the profitable difficulty caused by the imbalanced distribution of shared vehicles when considering staff-based and customer-based relocation alone. Thus, based on the traditional space-time network, the impact of time-varying road congestion and trip demands on the operation is considered. Based on C# language and O2DES (object-oriented discrete event simulation) framework, an efficient carsharing system model composed of modular station and road segment models is built. Moreover, a simulation-optimization model that jointly determines vehicle inventory thresholds and trip pricing is proposed to maximize the daily net revenue of operators. In order to solve the global optimization problem in a random environment, an elitist genetic algorithm (EGA) with optimal computing budget allocation (OCBA) is designed. Finally, a case study in Chengdu with five sites is conducted to demonstrate the efficiency of the proposed simulation-optimization model. The results show that with the same fleet size, the optimal design can increase the average daily net revenue by 10.37%−162.30% compared with customer-based relocation (fixed pricing); the optimized scheme can increase the profit by 15.34% compared with separate staff-based relocation.
-
共享汽车的普及有效降低了私家车使用率和尾气污染,缓解了停车位紧张和交通拥堵[1]. 单程式共享汽车具有灵活便捷的优点,为大多数共享汽车运营公司所采用,但这种运营模式会导致站点车辆积压,或无车可用[2]. 学者们从优化调度策略出发提出了解决方法,分为员工调度和用户调度两种[3].
员工调度策略通过提高调度员调度车辆决策的科学性提升调度效率,从而减少运营成本,提升盈利能力[4]. Barth等[5]采用需求预测和动态规划的方法,分析了不同场景下调度机制对系统的影响,但该类研究[6-7]假定用户取车时间是固定的,未考虑用车需求的随机性和车辆调度的滞后性. Kek等[8-9]基于“库存平衡”的理念提出了阈值触发调度策略,并先后建立了三阶段调度决策模型和调度阈值的启发式算法. Cao等 [10]也提出过以调度次数最小为目标的两阶段调度触发阈值优化模型.
上述研究结果表明,即使采用员工调度策略,调度员调度效率的提升空间仍是有限的. 因此,部分学者提出了用户调度策略,即通过动态定价策略来影响甚至改善用户车辆使用的时空均衡性,实现用户调度,进而提升调度的有效性,降低运营成本,提升盈利能力. 王宁等[11-12]分析用户对价格的敏感性,提出了动态定价机制下自适应调度模型,在此基础上,根据用车需求进行定价,进一步降低了调度成本;Jorge等[3,13]以利润最大化为目标对调度方案进行优化,通过定价解决车辆分布不平衡的问题;Xu等[14]以运营商利润最大化为目标建立模型,基于定价对顾客用车需求的非线性影响,解决了单程式共享汽车站点车队规模和调度等问题.
上述研究成果首先都是基于单一策略,并未考虑员工与顾客调度的联合,其次,都采用时间驱动机制模型构建系统,导致迭代所需的时间步长不能过长,否则严重影响模型速率[7-8,15-16]. 因此,有必要采用事件驱动机制模型构建系统. Li等[17-18]提出的O2DES (object-oriented discrete event simulation)仿真模型框架已成功应用于多个类似领域.
基于上述分析思路,并充分考虑站点间路径拥堵率、共享汽车数量等因素对车辆速率的影响,建立了动态Mandl基准网络,基于O2DES框架搭建共享汽车仿真系统. 同时,采用阈值触发和动态定价两种方法,实现上述员工和顾客调度策略的组合. 借助上述仿真模型的高效性,建立以运营商净收益最大化为目标的仿真优化框架. 相较于单一调度策略,期望优化结果进一步提升了利润.
1. 建模方法
采用O2DES框架建立模型,该框架主要功能包括:1) 预订事件在未来某个具体时刻发生;2) 借助于事件驱动机制,将仿真时钟推进到下一个已预订的临近事件. 如图1所示,相较于时间驱动,事件驱动避免了产生大量空事件时间戳,有效地提升了仿真速率[18],为“仿真-优化”提供条件.
基于O2DES框架,构建如图2所示的单程式共享汽车网络,使用路段和站点两种模块描述系统,假设顾客在站点取车后总能选择最短线路,并依次穿越当前线路中的路段,即:车辆驶出当前路段后会进入线路中的下一个路段或被归还至目的站点. 遵循DEVS (discrete event system specification)中的模块化概念[19-20],采用静态、动态和事件三种属性描述模块. 图中:
$ A_{ij} $ 为站点i到j的线路;$ a_{i j, n} $ 为$ A_{ij} $ 中的第n个路段,$ a_{ij, n} \in A_{ij} $ .1.1 车辆动态数据集模型
设h为某辆共享汽车,H为系统内共享车辆的集合,有
$ h \in H $ . 车辆的提取、转移与归还等行为都由路段和站点模块主导. 因此,车辆模型不需要包含任何事件,仅作为动态属性集保存,并向其他模块提供参数. 车辆h的动态属性集定义为Dh={th,o,th,d,sh,mh,rh,th}, (1) 式中:
$ {t_{h,{\text{o}}}} $ 、$ {t_{h,{\text{d}}}} $ 分别为车辆h离开起点站和到达终点站时刻;$ {s_h} $ 为车辆h的驾驶状态,sh=1,表示顾客使用,sh=0,表示调度员驾驶;$ {m_h} $ 为$ {D_h} $ 最近一次更新时的时间戳;$ {r_h} $ 为车辆h在当前路段的剩余行驶距离;$ {t_h} $ 为车辆h离开当前路段的预计时刻.1.2 单向路段模型与线路
尽管不同路段在车道数量、长度和宽度等方面存在差异,但仍具有共性[21]:
1) 根据交通流基本理论,车辆运行时间受路径拥堵率、路长、道路宽度等因素的影响;
2) 路段容量是有限的,如果路段容量达到上限,路段中的平均车速降到最低,即阻塞速度.
1.2.1 路段静态属性
站点i到j第n个路段的静态属性表示为
Sij,n={lij,n,wij,n,kij,n,cij,n,fij,n,oij,n,dij,n}, (2) 式中:
$ {l_{ij,n}} $ 、$ {w_{ij,n}} $ 和$ {k_{ij,n}} $ 分别为路段长度(km)、车道数量(车道)和阻塞密度(辆/(km·车道));$ {c_{ij,n}} $ 为路段容量,且$ {c_{ij,n}}{\text{ = }}{l_{ij,n}} {w_{ij,n}} {k_{ij,n}} $ [22];$ {f_{ij,n}} $ 为路段的自由流速度;$ {o_{ij,n}} $ 、$ {d_{ij,n}} $ 分别为路段的起点、终点.1.2.2 路段动态属性
路段
$ a_{i j, n} $ 的动态属性(即状态)定义为Dij,n={Hij,n(τ),xij,n(τ),Vij,n(xij,n(τ)),ηij,n(τ)}, (3) 式中:
$ \tau $ 为仿真时间;$ H_{i j n}(\tau) $ 为路段$ a_{i j, n} $ 内共享汽车的集合;$ x_{ij,n }(\tau) $ 为共享汽车数量,$ {x_{ij,n}}\left( \tau \right){\text{ = }}\left| {{H_{ij,n}}\left( \tau \right)} \right| $ ,$\left| {\text{•}} \right|$ 表示集合内元素的个数;$ {V_{ij,n}}\left( {{x_{ij,n}}\left( \tau \right)} \right) $ 为路段车辆的平均行驶速度;$ \eta_{ij,n}(\tau) $ 为引入共享汽车前的道路占用率,$\eta_{ij,n}(\tau) \in [0,1]$ ,当$ \eta_{4, n}(\tau)=1 $ 时,路段完全堵塞.考虑路径车辆数和道路拥挤度对速度的影响,将
$ {V_{ij,n}}\left( {{x_{ij,n}}\left( \tau \right)} \right) $ 描述为指数函数模型,如式(4)所示. 与线性速度模型不同,当路段完全堵塞时,指数函数模型的数值并不会降至0,而是维持在阻塞速度,表示车辆仍在缓慢行驶[23],更能真实反映实际运行情况.Vij,n(xij,n(τ))={vij,nexp[−(xij,n(τ)+cij,nηij,n(τ)cv/ij,nβvij,n)γij,n],xij,n(τ)⩽cij,n[1-ηij,n(τ)],vij,nexp[−(1βij,n)γvij,n],xij,n(τ)>cij,n[1-ηij,n(τ)], (4) 式中:
$ {v_{ij,n}} $ 为无拥堵状态下车辆的自然速度;$ {v_{bij,n}} $ 和$ {v_{cij,n}} $ 分别为道路状态是b和c时车辆在道路内的平均速度,道路状态与道路的长度和车道数以及道路拥堵率有关,一般设$ b = 12{l_{ij,n}}{w_{ij,n}} $ ,$ c = 87{l_{ij,n}}{w_{ij,n}} $ ;$ {v_{bij,n}} $ 、$ {v_{cij,n}} $ 、b和c均为已知的固定输入参数;系数$ {\gamma _{{v_{ij,n}}}} $ 、$ {\beta _{{v_{ij,n}}}} $ 分别如式(5)、(6)所示.γvij,n=ln[ln(vbij,n/vbij,nvij,nvij,n)/ln(vbij,n/vbij,nvij,nvij,n)ln(vcij,n/vcij,nvij,nvij,n)ln(vcij,n/vcij,nvij,nvij,n)]ln(b/bcc), (5) βvij,n=b[ln(vij,n/vij,nvbij,nvbij,n)]1/γvij,n. (6) 1.2.3 路段事件
如表1所示,采用输入、内部和输出等3类事件来描述车辆行驶过程,路径模块各符号如表1所示,流程关系如图3所示.
表 1 路径模块事件Table 1. Events of path module类型 符号 说明 输入 $\alpha _{ij,n}^{( { {\text{p} }1} )}$ 车辆 h 进入路段,$ \forall h \notin {H_{ij,n}}\left( \tau \right) $ 内部 $ \beta _{ij,n}^{( {{\text{p}}1} )} $ 更新车辆的剩余路程和时间戳 $\beta _{ij,n}^{( { {\text{p} }2} )}$ 车辆 h 加入到路段车辆集合 $ \beta _{ij,n}^{( {{\text{p}}3} )} $ 根据路径状态计算平均速度 $ \beta _{ij,n}^{( {{\text{p}}4} )} $ 更新共享汽车的预计离开时刻 $ \beta _{ij,n}^{( {{\text{p}}5} )} $ 共享汽车 h “尝试”离开路段 输出 $ \gamma _{ij,n}^{( {{\text{p}}1} )} $ 车辆 h 离开路段,$ \forall h \in {H_{ij,n}}( \tau ) $ 车辆在路段的到达与离开流程具体说明如下:
1) 到达流程
步骤1 车辆到达,触发
$ \beta _{ij,n}^{( {{\text{p}}1} )} $ 更新路段内其余车辆的剩余路程和时间戳,如式(7)、(8)所示,$ \forall h \in {H_{ij,n}}\left( \tau \right) $ ,符号“$ \leftarrow $ ”表示对某个属性或集合的更新.rh←rh−(τ−mh)Vij,n(xij,n(τ)), (7) mh=τ. (8) 步骤2
$ \beta _{ij,n}^{( {{\text{p}}2} )} $ 将车辆h添加至集合$ H_{i j n}(\tau) $ ,并初始化rh和th表示h抵达路段入口.Hij,n(τ)←Hij,n(τ)∪{h}, (9) Dh←{oh,dh,sh,τ,lij,n,th}. (10) 步骤3 由于车辆数变化,
$ \beta _{ij,n}^{( {{\text{p}}3} )} $ 根据式(4)~(6)更新当前的车辆平均行驶速度.步骤4 根据当前行驶速度,更新车辆驶出时刻:
th = τ + rhVij,n(xij,n(τ)),∀h∈Hij,n(τ), (11) 并使用O2DES框架预订
$ \beta _{ij,n}^{( {{\text{p}}5} )} $ 在时刻th发生.2) 离开流程
步骤1 由于车辆驶出时刻受行驶速度的影响,在执行
$ \gamma _{ij,n}^{( {{\text{p}}1} )} $ 前应进行判断,若${t_{h_0}}{\text{ = }}\tau$ ($ {h_0} $ 为排头车)表示${r_{h_0}} = 0$ ,车辆即将离开路段,否则终止.步骤2
$ \gamma _{ij,n}^{( {{\text{p}}1} )} $ 将车辆送入下一路段或目的站,有$ {H_{ij,n}}\left( \tau \right) \leftarrow {H_{ij,n}}\left( \tau \right)\backslash \left\{ h \right\} $ ,使用“$ \backslash $ ”表示将元素从集合中剔除.1.3 动态容量站点模型
设
$ \varPi $ 为车站集合,车站$\; i \in \varPi = \left\{ {1,2,\cdots,N} \right\} $ .1.3.1 站点静态属性
站点i的静态属性定义为
Si={μi,Oi}, (12) 式中:
$ {\mu _i} $ 为站点i的取车服务率;$ {O_i}{\text{ = }}\left\{ {{a_{ij,1}}\left| {\forall {o_{ij,1}} = i} \right.} \right\} $ ,表示所有以i为起点的路段集合.1.3.2 站点动态属性
站点i的动态属性定义如式(13)所示.
Di={Hi(τ),xi(τ),ni,a(τ),ni,u(τ),ni,c(τ),λi(τ),{bij(τ)|∀aij,n∈Oi},{θij(τ)|∀aij,n∈Oi}}, (13) 式中:
$ {H_i}\left( \tau \right) $ 为在站点i停放的共享汽车的集合;$ {x_i}\left( \tau \right) = \left| {{H_i}\left( \tau \right)} \right| $ ,为站点i内的共享汽车数量;$ {n_{i,{\text{a}}}}\left( \tau \right) $ 为空闲的调度员数量;$ {n_{i,{\text{u}}}}\left( \tau \right) $ 为正在工作的员工数量;$ {n_{i,{\text{c}}}}\left( \tau \right) $ 为当前站内顾客数量;$ {\lambda _i}\left( \tau \right) = \displaystyle \sum {_{\forall {a_{ij,n}} \in {O_i}}} {b_{ij}}\left( \tau \right) $ ,为顾客到达率;$ {b_{ij}}\left( \tau \right) $ 为输入数据,表示时刻$ \tau $ 车站i到j的出行需求;$ {\theta _{ij}}\left( \tau \right) $ 为顾客选择从车站i到j的转移概率,有$ {\theta _{ij}}\left( \tau \right) = {{{b_{ij}}\left( \tau \right)} \mathord{\left/ {\vphantom {{{b_{ij}}\left( \tau \right)} {{\lambda _i}}}} \right. } {{\lambda _i}}} $ .1.3.3 站点事件
站点模块的输入、内部和输出事件见表2. 表2所描述事件间的流程关系如图4所示.
表 2 站点模块事件Table 2. Events of station module类型 符号 说明 输入 $ \alpha _i^{( {{\text{p}}1} )} $ 顾客到达车站 $ \alpha _i^{( {{\text{p2}}} )} $ 下达调度指令,向车站 i 调车 $ \alpha _i^{( {{\text{p3}}} )} $ 表示车辆 h 归还到站点 i 内部 $ \beta _i^{( {{\text{p1}}} )} $ 判断车辆库存是否足够 $ \beta _i^{( {{\text{p2}}} )} $ 更新车辆集合,车辆选择去向 $ \beta _i^{( {{\text{p3}}} )} $ 判断是否执行调度指令 $ \beta _i^{( {{\text{p4}}} )} $ 更新车辆和调度员数量 输出 $ \gamma _i^{( {{\text{p1}}} )} $ 表示车辆 h 离开站点 i,$ \forall h \in {H_i\left( \tau \right)} $ 流程具体说明如下:
1) 取车流程
步骤1
$ \alpha _i^{( {{\text{p}}1} )} $ 触发事件$ \beta _i^{( {{\text{p1}}} )} $ 以判断车辆库存量. 若$ {x_i}\left( \tau \right) \gt {n_{i,{\text{c}}}}\left( \tau \right) + {n_{i,{\text{u}}}}\left( \tau \right) $ ,则$ {n_{i,{\text{c}}}}\left( \tau \right) \leftarrow {n_{i,{\text{c}}}}\left( \tau \right){\text{ + 1}} $ ,表示顾客开始取车,并预订在时刻$ \tau {\text{ + }}{{\text{1}} \mathord{\left/ {\vphantom {{\text{1}} {{\mu _i}}}} \right. } {{\mu _i}}} $ 进入步骤2;否则,终止流程;为保证系统持续运行,预订在时刻$ \tau {\text{ + }}{{\text{1}} \mathord{\left/ {\vphantom {{\text{1}} {{\lambda _i}}}} \right. } {{\lambda _i}}}\left( \tau \right) $ 触发$ \alpha _i^{( {{\text{p}}1} )} $ ,表示下一个顾客的到来.步骤2 执行事件
$ \beta _i^{( {{\text{p2}}} )} $ ,表示车辆h已经被顾客提取,随后更新站点车辆集合,为车辆h添加离站时间,并将其驾驶状态变为“顾客驾驶”:Hi(τ)←Hi(τ)∖{h}, (14) Dh←{τ,dh,1,mh,rh,th}, (15) 此外,由于车站连接多条路段,在车辆准备出发前,根据转移概率
$ {\theta _{ij}} $ 和轮盘赌算法确定$ {a_{ij,1}} $ ,$ {a_{ij,1}} \in {O_i} $ .步骤3 执行
$ \gamma _i^{( {{\text{p1}}} )} $ 触发路段的车辆到达.2) 还车流程
步骤1 触发
$ \alpha _i^{( {{\text{p3}}} )} $ 执行$ \beta _i^{( {{\text{p4}}} )} $ 更新站点车辆集合,表示车辆进入站点:Hi(τ)←Hi(τ)∪{h}. (16) 步骤2 判断车辆驾驶情况,若
$ {s_h} = 0 $ ,本次车辆归还为调度员调车归还,令$ {n_{i,{\text{a}}}}\left( \tau \right) \leftarrow {n_{i,{\text{a}}}}\left( \tau \right) + 1 $ .3) 调度流程:
步骤1 与取车相似,由外部调度系统下达调度指令,触发
$ \alpha _i^{( {{\text{p2}}} )} $ 开始调出车辆.步骤2 执行
$ \beta _i^{( {{\text{p3}}} )} $ ,当$ {n_{i,{\text{a}}}}\left( \tau \right) \gt 0 $ 且$ {x_i}\left( \tau \right) \gt 0 $ 时,$ {H_i}\left( \tau \right) \leftarrow {H_i}\left( \tau \right)\backslash \left\{ h \right\} $ ,更新调度员工作状态,将车辆驾驶状态变为员工驾驶:ni,a(τ)←ni,a(τ)−1, (17) ni,u(τ)←ni,u(τ)+1, (18) Dh←{τ,dh,0,mh,rh,th}, (19) 并预订在时刻
$ \tau {\text{ + }}{{\text{1}} \mathord{\left/ {\vphantom {{\text{1}} {{\mu _i}}}} \right. } {{\mu _i}}} $ 执行$ \gamma _i^{( {{\text{p1}}} )} $ .步骤 3 当员工驾驶的车辆通过
$ \gamma _i^{( {{\text{p1}}} )} $ 被交出时,令$ {n_{i,{\text{u}}}}\left( \tau \right) \leftarrow {n_{i,{\text{u}}}}\left( \tau \right) - 1 $ ,车辆驶入路段$ {a_{ij,n}} $ .2. 联合调度策略
由于出行需求的潮汐性,单程式共享汽车时常会出现车辆站间分布不平衡的问题. 大多数研究认为车辆调度是解决该问题的关键. 本节提出动态定价和阈值触发调度相结合的方法,分两阶段实现顾客和员工联合调度:首先,将分时价格作为模型输入,确定实际出行需求;其次,根据阈值触发调度实现运营过程中的动态人工车辆调度.
2.1 基于动态定价方法的顾客调度策略
顾客出行需求的时空不平衡性是导致车辆站间分布的不平衡主要原因. 据Xu等[14]的研究,顾客的用车需求受价格的影响. 因此,可采用动态定价的方法影响需求:为需求较小线路提供低价出行,提升需求较高线路上的价格,引导顾客“自发地”进行车辆调度. 出行需求与定价可表达为弹性需求函数:
bij(τ)={Bij(τ)exp(−σij(τ)Rij(τ)),0⩽Rij(τ)⩽Rijmax (20) 式中:
$ {B_{ij}}(\tau ) $ 、$R_{ij}(\tau) $ 分别为车站i到车站j的用户潜在需求和价格;$ {\sigma _{ij}}(\tau ) $ 为价格弹性系数;$R_{ij}^{\max } (\tau ) $ 、$R_{ij}^{\min }(\tau ) $ 分别为定价上限、下限.式(20)表明,当价格
$ {R_{ij}}(\tau ) $ 超过$ R_{ij}^{\max }(\tau ) $ ,需求下降到0. 同时,价格过低甚至免费,可能导致现有车队规模无法承担用户需求,为了避免这种情况,设置定价下限$ R_{ij}^{\min }(\tau ) $ ,则$ R_{ij}^{\min }(\tau ) \leqslant {R_{ij}}(\tau ) \leqslant R_{ij}^{\max }(\tau ) $ .2.2 基于阈值触发方法的员工调度策略
除采用动态定价的顾客调度方式外,雇佣调度员的员工调度是最为主流的策略,其中,参考“库存理论”的阈值触发调度为不少学者采用. 基于Kek等[8-9]的研究,设计的阈值调度策略如式(21)~(24)所示.
{Q_i}\left( \tau \right){\text{ = }}{x_i}\left( \tau \right) + \sum\limits_{{a_{ij,n}}} {{x_{ij,n}}\left( \tau \right)} , (21) I_i^{{\text{out}}}\left( \tau \right) = \left\{ \begin{gathered} 1,\quad {Q_i}\left( \tau \right) \geqslant S_i^{{\text{up}}}\left( \tau \right) , \\ 0,\quad S_i^{{\text{low}}}\left( \tau \right) \lt {Q_i}\left( \tau \right) \lt S_i^{{\text{up}}}\left( \tau \right), \\ \end{gathered} \right. (22) I_i^{{\text{in}}}\left( \tau \right) = \left\{ \begin{gathered} 1,\quad {Q_i}\left( \tau \right) \leqslant S_i^{{\text{low}}}\left( \tau \right), \\ 0,\quad S_i^{{\text{low}}}\left( \tau \right) \lt {Q_i}\left( \tau \right) \lt S_i^{{\text{up}}}\left( \tau \right), \\ \end{gathered} \right. (23) 0 \leqslant S_i^{{\text{low}}}\left( \tau \right) \lt S_i^{{\text{up}}}\left( \tau \right) \leqslant \sum\limits_{i \in \varPi } {{x_i}({\tau _0})} , (24) 式中:
${Q_i}\left( \tau \right) $ 为车站i可用车辆数,考虑车辆调度滞后性,将即将到站的车辆也考虑在内;$ S_i^{{\text{up}}}\left( \tau \right) $ 、$ S_i^{{\text{low}}}\left( \tau \right) $ 分别为车站i可用车辆库存的上、下限;$ I_i^{{\text{out}}}\left( \tau \right) $ 、$ I_i^{{\text{in}}}\left( \tau \right) $ 分别为车辆的调出和调入需求量;$ \displaystyle\sum\limits_{i \in \varPi } {{x_i}({\tau _0})} $ 为区域内共享汽车总量;$ \tau_0 $ 为初始时刻.本文将一个运营周期分为不同运营时段,在同一时段内,决策变量
$ S_i^{{\text{up}}}\left( \tau \right) $ 、$ S_i^{{\text{low}}}\left( \tau \right) $ 和$ {R_{ij}}\left( \tau \right) $ 不发生改变,运营策略的实时变化只发生在不同时段之间.3. 优化框架与算法设计
3.1 目标函数
以各车站调度阈值和分时段各线路定价为决策变量,运营商日均净收益最大化为目标函数建立优化模型:
\max \;Z\left( \theta \right) = I - C , (25) I = \sum\limits_{\rho \in \varLambda } {\sum\limits_{i \in \varPi } {\sum\limits_{j \in \varPi } {T_{ij}^{{\text{Cus}}}\left( \rho \right) {R_{ij}}\left( \rho \right)} } } , (26) C = \sum\limits_{\rho \in \varLambda } {\sum\limits_{i \in \varPi } {\sum\limits_{j \in \varPi } {\left( {T_{ij}^{{\text{Sta}}}\left( \rho \right){\text{ + }}T_{ij}^{{\text{Cu}}s}\left( \rho \right)} \right) {c_{\text{o}}}} } } + \sum\limits_{i \in \varPi } {{T_i} {c_{P} }} , (27) 式中:
$ Z\left( \theta \right) $ 为在设计$ \theta $ 下的净收益,$ \theta $ 由分时段阈值和定价组成;I为运营收入;$ \rho $ 为运营时段;$ \varLambda $ 为整个运营周期,$ \rho \in \varLambda $ .$ T_{ij}^{{\text{Cus}}}\left( \rho \right) $ 、$ T_{ij}^{{\text{Sta}}}\left( \rho \right) $ 分别为在$ \rho $ 内顾客驾驶、调度员驾驶的汽车在线路$ {A_{ij}} $ 上运行的总时长;C为运营支出;co为车辆单位运行成本;Ti为运营周期内车辆在站点i停靠的总时长;cP为单位停车成本.3.2 算法设计
随着网络规模的扩大和运营时段
$ \rho $ 的细分,决策变量呈指数增长,模型求解难度大. 为解决该高维问题,首先设计精英遗传算法(elitist genetic algorithm,EGA)算法,在遗传算法中引入精英策略,防止进化过程中产生的最优解被交叉和变异所破坏.此外,由于仿真结果存在随机性,大多数情况下,为减少这种干扰需要多次仿真求平均值,这严重影响了优化效率. 为了寻求算法效率和仿真次数的契合点,以最小计算量求得众多候选设计中的最佳值,提出最优计算量分配(optimal computing budget allocation,OCBA)算法[23-24]. 基于Xiao等[25]的研究,计算种群个体的适应度时,将计算量合理分配到最可能成为最优个体的设计上. 为防止过早收敛设置循环跳出,设计EGA-OCBA算法流程,如图5所示.
4. 案例分析
4.1 案例背景
以成都市EVCARD的5个共享站点为例,6:00—24:00作为运营周期,均分为6个运营时段. 如图6所示,遵循Mandl基准网络构建路网[26],道路旁数字依次表示
$ {k_{ij}} $ (通过百度API获取)、$ {w_{ij}} $ 、$ {l_{ij}} $ .设置停车收费0.5元/h,运行成本5元/h,弹性需求系数
$ {\sigma _{ij}} $ 根据Xu等[14]可取0.1. 定价上、下限分别为10、60元/h,速度公式中的标准点根据Hu等[22]在路段相对密度为0.1和0.2时的回归分析研究,可分别取0.71和0.52. 站点初始车辆与调度员见表3.表 3 车站初始状态Table 3. Initial state of stations站点 车辆数/辆 调度员数/人 1 6 2 2 4 2 3 5 2 4 5 2 5 5 2 4.2 案例结果
优化算法迭代过程如图7所示,在第1500代之后,最优设计长时间保持不变,算法搜索到较优解. 得到最优联合调度策略净收益为10374.68元.
如表4所示,在时间维度上,由于顾客出行具有潮汐性,使得各站点供需匹配程度不相同,同一线路的不同运营时段定价差别明显,例如
$ {A_{32}} $ 最高与最低定价差值达到了41元/h;由于案例所处出行需求较高,随着运营时段进入后期,共享汽车需求未出行显著下降;相反,出行需求在21:00—24:00时段再次增加,运营商能够随之制定更合理的租赁价格. 此外,相同站点、不同线路间的出行需求存在显著的不平衡性,以路径$ {A_{13}} $ 和$ {A_{31}} $ 为例,前者定价几乎全程高于后者. 在实际运行中,运营商同样可以根据历史数据,调查出行需求进行定价调整.表 4 动态定价方案Table 4. Dynamic pricing scheme元 时段 $ {A_{12}} $ $ {A_{13}} $ $ {A_{14}} $ $ {A_{15}} $ $ {A_{21}} $ $ {A_{23}} $ $ {A_{24}} $ $ {A_{25}} $ $ {A_{31}} $ $ {A_{32}} $ 06:00—09:00 37.0 22.0 40.0 24.0 48.0 40.0 34.0 28.0 16.0 54.0 09:00—12:00 39.0 56.0 12.0 12.0 51.0 23.0 31.0 25.0 13.0 19.0 12:00—15:00 50.0 38.0 41.0 19.0 43.0 58.0 13.0 51.0 27.0 57.0 15:00—18:00 37.0 34.0 20.0 35.0 17.0 20.0 47.0 43.0 38.0 13.0 18:00—21:00 36.0 36.0 42.0 14.0 55.0 50.0 54.0 15.0 23.0 53.0 21:00—24:00 33.0 54.0 28.0 33.0 44.0 32.0 43.0 43.0 44.0 10.0 时段 $ {A_{34}} $ $ {A_{35}} $ $ {A_{42}} $ $ {A_{42}} $ $ {A_{43}} $ $ {A_{45}} $ $ {A_{51}} $ $ {A_{52}} $ $ {A_{53}} $ $ {A_{54}} $ 06:00—09:00 46.0 31.0 33.0 37.0 56.0 37.0 54.0 10.0 10.0 34.0 09:00—12:00 48.0 58.0 10.0 25.0 35.0 12.0 27.0 59.0 36.0 34.0 12:00—15:00 48.0 32.0 27.0 14.0 34.0 48.0 55.0 32.0 12.0 22.0 15:00—18:00 25.0 48.0 37.0 29.0 28.0 27.0 30.0 16.0 20.0 19.0 18:00—21:00 53.0 30.0 21.0 58.0 24.0 22.0 12.0 18.0 57.0 42.0 21:00—24:00 45.0 23.0 39.0 40.0 50.0 54.0 54.0 42.0 51.0 39.0 阈值触发调度方案见表5,以12:00—15:00时段的站点4为例:
$ S_{\text{4}}^{{\text{up}}}\left( \tau \right) $ 仅稍高于$ S_4^{{\text{low}}}\left( \tau \right) $ ,两者之间差值较小,意味着该站点库存缓冲区间($ S_i^{{\text{low}}}\left( \tau \right), S_i^{{\text{up}}}\left( \tau \right) $ )较窄,存在较为密集的调出或调入需求[10]. 相反,同时段车站3的阈值差异显著,缓冲区间大,调度需求相对较小.表 5 阈值触发调度方案Table 5. Threshold-triggering relocation scheme辆 时段 $S_{ 1}^{ {\text{up} } }\left( \tau \right)$ $S_{ 1}^{ {\text{low} } }\left( \tau \right)$ $S_{ 2}^{ {\text{up} } }\left( \tau \right)$ $S_{ 2}^{ {\text{low} } }\left( \tau \right)$ $S_{ 3}^{ {\text{up} } }\left( \tau \right)$ $S_{ 3}^{ {\text{low} } }\left( \tau \right)$ $S_{ 4}^{ {\text{up} } }\left( \tau \right)$ $S_{ 4}^{ {\text{low} } }\left( \tau \right)$ $S_{ 5}^{ {\text{up} } }\left( \tau \right)$ $S_{ 5}^{ {\text{low} } }\left( \tau \right)$ 06:00—09:00 19 18 17 5 17 6 15 12 9 6 09:00—12:00 23 13 11 7 12 5 24 4 17 2 12:00—15:00 13 11 20 19 4 2 21 20 21 2 15:00—18:00 15 5 15 6 19 1 7 5 22 0 18:00—21:00 9 6 12 6 13 2 24 4 23 7 21:00—24:00 12 6 17 16 7 0 22 1 23 15 设置了多组对照实验(固定价格或无人工调度)以进一步验证联合调度的优势. 如表6所示,动态定价仅能提升10.76%的净收益(对比定价40元/h的运营环境);员工调度也仅提升了5.29%~23.44%的利润. 采用阈值触发调度和动态定价联合的策略,不仅能刺激顾客用车、协助调度车辆、减少调度成本,还使得利润相较于动态定价的情况提升15.54%,相较于固定定价提升10.37%~162.30%.
表 6 策略净收益对比Table 6. Net income comparison among strategies元 策略 收益 策略 收益 联合调度策略 10374.68 动态定价无调度 8979.37 定价 15 元有调度 3955.25 定价 15 元无调度 3756.46 定价 20 元有调度 5888.43 定价 20 元无调度 5466.05 定价 25 元有调度 7055.95 定价 25 元无调度 6880.96 定价 30 元有调度 7863.41 定价 30 元无调度 7193.02 定价 35 元有调度 9234.57 定价 35 元无调度 8043.68 定价 40 元有调度 9826.50 定价 40 元无调度 8106.93 定价 45 元有调度 9504.22 定价 45 元无调度 7698.97 定价 50 元有调度 7973.05 定价 50 元无调度 7203.43 5. 结论与未来展望
1) 在仿真方面,基于C# 语言和O2DES离散事件仿真框架,建立事件驱动机制下的共享汽车运营仿真模型,采用模块化的建模方式能够方便地搭建大规模仿真网络. 模型考虑了路径堵塞率和用车需求随时间的动态变化以及路段共享汽车实时数量对平均速度的影响,真实地反映共享汽车运行情况.
2) 在运营优化方面,借助仿真模型的高效性搭建仿真优化框架,以运营方利润最大化为目标,结合阈值触发调度和动态定价相联合对运营策略进行优化. 设计EGA-OCBA算法求解该随机环境下的全局优化问题. 以成都的5个站点为例,仿真优化结果表明,相较于单一调度方式,所得最优联合策略能更为合理地找到调度、需求和定价之间的平衡关系,可使运营商日均净收益提升10.37%~162.30%.
3) 后续研究中可考虑扩展运营时长,研究因用户需求未满足而造成的长期损失.
-
表 1 路径模块事件
Table 1. Events of path module
类型 符号 说明 输入 $\alpha _{ij,n}^{( { {\text{p} }1} )}$ 车辆 h 进入路段,$ \forall h \notin {H_{ij,n}}\left( \tau \right) $ 内部 $ \beta _{ij,n}^{( {{\text{p}}1} )} $ 更新车辆的剩余路程和时间戳 $\beta _{ij,n}^{( { {\text{p} }2} )}$ 车辆 h 加入到路段车辆集合 $ \beta _{ij,n}^{( {{\text{p}}3} )} $ 根据路径状态计算平均速度 $ \beta _{ij,n}^{( {{\text{p}}4} )} $ 更新共享汽车的预计离开时刻 $ \beta _{ij,n}^{( {{\text{p}}5} )} $ 共享汽车 h “尝试”离开路段 输出 $ \gamma _{ij,n}^{( {{\text{p}}1} )} $ 车辆 h 离开路段,$ \forall h \in {H_{ij,n}}( \tau ) $ 表 2 站点模块事件
Table 2. Events of station module
类型 符号 说明 输入 $ \alpha _i^{( {{\text{p}}1} )} $ 顾客到达车站 $ \alpha _i^{( {{\text{p2}}} )} $ 下达调度指令,向车站 i 调车 $ \alpha _i^{( {{\text{p3}}} )} $ 表示车辆 h 归还到站点 i 内部 $ \beta _i^{( {{\text{p1}}} )} $ 判断车辆库存是否足够 $ \beta _i^{( {{\text{p2}}} )} $ 更新车辆集合,车辆选择去向 $ \beta _i^{( {{\text{p3}}} )} $ 判断是否执行调度指令 $ \beta _i^{( {{\text{p4}}} )} $ 更新车辆和调度员数量 输出 $ \gamma _i^{( {{\text{p1}}} )} $ 表示车辆 h 离开站点 i,$ \forall h \in {H_i\left( \tau \right)} $ 表 3 车站初始状态
Table 3. Initial state of stations
站点 车辆数/辆 调度员数/人 1 6 2 2 4 2 3 5 2 4 5 2 5 5 2 表 4 动态定价方案
Table 4. Dynamic pricing scheme
元 时段 $ {A_{12}} $ $ {A_{13}} $ $ {A_{14}} $ $ {A_{15}} $ $ {A_{21}} $ $ {A_{23}} $ $ {A_{24}} $ $ {A_{25}} $ $ {A_{31}} $ $ {A_{32}} $ 06:00—09:00 37.0 22.0 40.0 24.0 48.0 40.0 34.0 28.0 16.0 54.0 09:00—12:00 39.0 56.0 12.0 12.0 51.0 23.0 31.0 25.0 13.0 19.0 12:00—15:00 50.0 38.0 41.0 19.0 43.0 58.0 13.0 51.0 27.0 57.0 15:00—18:00 37.0 34.0 20.0 35.0 17.0 20.0 47.0 43.0 38.0 13.0 18:00—21:00 36.0 36.0 42.0 14.0 55.0 50.0 54.0 15.0 23.0 53.0 21:00—24:00 33.0 54.0 28.0 33.0 44.0 32.0 43.0 43.0 44.0 10.0 时段 $ {A_{34}} $ $ {A_{35}} $ $ {A_{42}} $ $ {A_{42}} $ $ {A_{43}} $ $ {A_{45}} $ $ {A_{51}} $ $ {A_{52}} $ $ {A_{53}} $ $ {A_{54}} $ 06:00—09:00 46.0 31.0 33.0 37.0 56.0 37.0 54.0 10.0 10.0 34.0 09:00—12:00 48.0 58.0 10.0 25.0 35.0 12.0 27.0 59.0 36.0 34.0 12:00—15:00 48.0 32.0 27.0 14.0 34.0 48.0 55.0 32.0 12.0 22.0 15:00—18:00 25.0 48.0 37.0 29.0 28.0 27.0 30.0 16.0 20.0 19.0 18:00—21:00 53.0 30.0 21.0 58.0 24.0 22.0 12.0 18.0 57.0 42.0 21:00—24:00 45.0 23.0 39.0 40.0 50.0 54.0 54.0 42.0 51.0 39.0 表 5 阈值触发调度方案
Table 5. Threshold-triggering relocation scheme
辆 时段 $S_{ 1}^{ {\text{up} } }\left( \tau \right)$ $S_{ 1}^{ {\text{low} } }\left( \tau \right)$ $S_{ 2}^{ {\text{up} } }\left( \tau \right)$ $S_{ 2}^{ {\text{low} } }\left( \tau \right)$ $S_{ 3}^{ {\text{up} } }\left( \tau \right)$ $S_{ 3}^{ {\text{low} } }\left( \tau \right)$ $S_{ 4}^{ {\text{up} } }\left( \tau \right)$ $S_{ 4}^{ {\text{low} } }\left( \tau \right)$ $S_{ 5}^{ {\text{up} } }\left( \tau \right)$ $S_{ 5}^{ {\text{low} } }\left( \tau \right)$ 06:00—09:00 19 18 17 5 17 6 15 12 9 6 09:00—12:00 23 13 11 7 12 5 24 4 17 2 12:00—15:00 13 11 20 19 4 2 21 20 21 2 15:00—18:00 15 5 15 6 19 1 7 5 22 0 18:00—21:00 9 6 12 6 13 2 24 4 23 7 21:00—24:00 12 6 17 16 7 0 22 1 23 15 表 6 策略净收益对比
Table 6. Net income comparison among strategies
元 策略 收益 策略 收益 联合调度策略 10374.68 动态定价无调度 8979.37 定价 15 元有调度 3955.25 定价 15 元无调度 3756.46 定价 20 元有调度 5888.43 定价 20 元无调度 5466.05 定价 25 元有调度 7055.95 定价 25 元无调度 6880.96 定价 30 元有调度 7863.41 定价 30 元无调度 7193.02 定价 35 元有调度 9234.57 定价 35 元无调度 8043.68 定价 40 元有调度 9826.50 定价 40 元无调度 8106.93 定价 45 元有调度 9504.22 定价 45 元无调度 7698.97 定价 50 元有调度 7973.05 定价 50 元无调度 7203.43 -
[1] MARTIN E W, SHAHEEN S A. Greenhouse gas emission impacts of carsharing in North America[J]. IEEE Transactions on Intelligent Transportation Systems, 2011, 12(4): 1074-1086. doi: 10.1109/TITS.2011.2158539 [2] DI FEBBRARO A, SACCO N, SAEEDNIA M. One-way carsharing[J]. Transportation Research Record: Journal of the Transportation Research Board, 2012, 2319(1): 113-120. doi: 10.3141/2319-13 [3] JORGE D, CORRELA G H D A. Carsharing systems demand estimation and defined operations: a literature review[J]. European Journal of Transport & Infrastructure Reaserch, 2013, 13(3): 201-220. [4] WANG L, LIU Q, MA W J. Optimization of dynamic relocation operations for one-way electric carsharing systems[J]. Transportation Research Part C: Emerging Technologies, 2019, 101: 55-69. doi: 10.1016/j.trc.2019.01.005 [5] BARTH M, TODD M. Simulation model performance analysis of a multiple station shared vehicle system[J]. Transportation Research Part C: Emerging Technologies, 1999, 7(4): 237-259. doi: 10.1016/S0968-090X(99)00021-2 [6] CATALANO M, CASTO B L, MIGLIORE M. Car sharing demand estimation and urban transport demand modelling using stated preference techniques[J]. European Transport, 2008, 40: 33-50. [7] CHEU R L, XU J X, KEK A G H, et al. Forecasting shared-use vehicle trips with neural networks and support vector machines[J]. Transportation Research Record: Journal of the Transportation Research Board, 2006, 1968(1): 40-46. doi: 10.1177/0361198106196800105 [8] KEK A G H, CHEU R L, CHOR M L. Relocation simulation model for multiple-station shared-use vehicle systems[J]. Transportation Research Record: Journal of the Transportation Research Board, 2006, 1986(1): 81-88. doi: 10.1177/0361198106198600111 [9] KEK A G H, CHEU R L, MENG Q, et al. A decision support system for vehicle relocation operations in carsharing systems[J]. Transportation Research Part E: Logistics and Transportation Review, 2009, 45(1): 149-158. doi: 10.1016/j.tre.2008.02.008 [10] CAO G Y, WANG L, JIN Y, et al. Determination of the vehicle relocation triggering threshold in electric car-sharing system[C]//Proceedings of 2016 Chinese Intelligent Systems Conference. [S.1.]: Spring, 2016: 11-22 [11] 王宁,舒雅静,唐林浩,等. 基于动态定价的共享汽车自适应调度策略[J]. 交通运输系统工程与信息,2018,18(5): 12-17,74. doi: 10.16097/j.cnki.1009-6744.2018.05.003WANG Ning, SHU Yajing, TANG Linhao, et al. Adaptive scheduling strategy in car-sharing system based on feedback dynamic pricing[J]. Journal of Transportation Systems Engineering and Information Technology, 2018, 18(5): 12-17,74. doi: 10.16097/j.cnki.1009-6744.2018.05.003 [12] 王宁,郑文晖,刘向,等. 基于用户激励的共享电动汽车调度成本优化[J]. 同济大学学报(自然科学版),2018,46(12): 1668-1675,1721. doi: 10.11908/j.issn.0253-374x.2018.12.008WANG Ning, ZHENG Wenhui, LIU Xiang, et al. Relocation cost optimization model of electric vehicle sharing based on user incentive[J]. Journal of Tongji University (Natural Science), 2018, 46(12): 1668-1675,1721. doi: 10.11908/j.issn.0253-374x.2018.12.008 [13] JORGE D, MOLNAR G, DE ALMEIDA CORREIA G H. Trip pricing of one-way station-based carsharing networks with zone and time of day price variations[J]. Transportation Research Part B: Methodological, 2015, 81: 461-482. doi: 10.1016/j.trb.2015.06.003 [14] XU M, MENG Q, LIU Z Y. Electric vehicle fleet size and trip pricing for one-way carsharing services considering vehicle relocation and personnel assignment[J]. Transportation Research Part B: Methodological, 2018, 111: 60-82. doi: 10.1016/j.trb.2018.03.001 [15] NOURINEJAD M, ROORDA M J. A dynamic carsharing decision support system[J]. Transportation Research Part E: Logistics and Transportation Review, 2014, 66: 36-50. doi: 10.1016/j.tre.2014.03.003 [16] CHEN C H, LEE L H. Stochastic simulation optimization: optimal computing budget allocation[M]. Singapore: World Scientific, 2010: 40-60. [17] LI H B, ZHOU C H, LEE B K, et al. Capacity planning for mega container terminals with multi-objective and multi-fidelity simulation optimization[J]. IISE Transactions, 2017, 49(9): 849-862. doi: 10.1080/24725854.2017.1318229 [18] LI H B, ZHU Y C, CHEN Y X, et al. The object-oriented discrete event simulation modeling: a case study on aircraft spare part management[C]//2015 Winter Simulation Conference (WSC). Piscataway: IEEE, 2015: 3514-3525. [19] ZEIGLER B P. Hierarchical, modular discrete-event modelling in an object-oriented environment[J]. Simulation, 1987, 49(5): 219-230. doi: 10.1177/003754978904900506 [20] ZEIGLER B P, PRAEHOFER H, KIM T G. Theory of modeling and simulation: integrating discrete event and continuous complex dynamic systems[M]. Pittsburgh: Academic Press, 2000: 4-5. [21] ZHOU C H, LEE L H, CHEW E P, et al. A modularized simulation for traffic network in container terminals via network of servers with dynamic rates[C]//Proceedings of 2017 Winter Simulation Conference (WSC). Las Vegas: IEEE, 2017: 3150-3161. [22] HU L, ZHAO B, ZHU J X, et al. Two time-varying and state-dependent fluid queuing models for traffic circulation systems[J]. European Journal of Operational Research, 2019, 275(3): 997-1019. doi: 10.1016/j.ejor.2019.01.020 [23] CHEN H C, CHEN C H, YUCESAN E. Computing efforts allocation for ordinal optimization and discrete event simulation[J]. IEEE Transactions on Automatic Control, 2000, 45(5): 960-964. doi: 10.1109/9.855560 [24] CHEN C H, LIN J W, YÜCESAN E, et al. Simulation budget allocation for further enhancing the efficiency of ordinal optimization[J]. Discrete Event Dynamic Systems, 2000, 10(3): 251-270. doi: 10.1023/A:1008349927281 [25] XIAO H, LEE L H. Simulation optimization using genetic algorithms with optimal computing budget allocation[J]. Journal of Simulation, 2014, 90(10): 1146-1157. doi: 10.1177/0037549714548095 [26] MANDL C E. Evaluation and optimization of urban public transportation networks[J]. European Journal of Operational Research, 1980, 5(6): 396-404. doi: 10.1016/0377-2217(80)90126-5 期刊类型引用(4)
1. 侯博宇,刘洪汛,胡路. 自动驾驶电动共享车系统自适应集中调度优化. 交通运输工程与信息学报. 2024(04): 25-36 . 百度学术
2. 杨凯,吴芳,罗维壮. 基于共享电动汽车时空分布规律的高峰时段车辆调度研究. 兰州交通大学学报. 2023(03): 32-38 . 百度学术
3. 胡路,梁志梅,蒋阳升. 拥挤传播对汽车共享系统运行影响的仿真分析. 西南交通大学学报. 2023(03): 499-510 . 本站查看
4. 王琪. 基于蜂窝物联网技术的汽车共享模式及其解决方案研究. 电子技术与软件工程. 2022(04): 21-24 . 百度学术
其他类型引用(9)
-