基于Actor-Critic网络深度强化学习的定制公交线网优化
doi: 10.11918/202502033
李冰 , 周晓倩 , 轩华
郑州大学 管理学院,郑州 450001
基金项目: 国家社会科学基金(24BJY113)
Optimization of customized bus route based on deep reinforcement learning with Actor-Critic neural network
Li Bing , Zhou Xiaoqian , Xuan Hua
School of Management, Zhengzhou University, Zhengzhou 450001, China
摘要
为了研究一类考虑多车种可用的多对多定制公交线网优化问题,以乘客出行成本和公交运营成本最小为目标,考虑乘降点服务、乘降点数量、线路总长度以及公交车队规模等限制,构建多对多定制公交线网优化双层混合整数规划模型。传统方法在求解大规模数学模型方面效率不高,提出一种基于Actor-Critic双重神经网络的深度强化学习方法。该方法将定制公交视为智能体,利用无监督聚类建立智能体学习环境,构造智能体状态-动作-奖励机制,设计Actor-Critic双重神经网络用于乘降点选择与评价,构建基于Actor-Critic双重网络的深度强化学习过程。选取郑州市高新区-郑东新区公交乘降点分布与居民出行数据搭建实验场景,对学习率、折扣因子、批尺寸和神经元数等超参数进行优化调试,利用双重网络深度强化学习过程求解模型,得到多对多定制公交线网方案,其乘降点分配、行驶距离、上座率与车型安排都较为合理。与基于Actor单重网络的深度强化学习进行结果对比,算法收敛速度提高了28.57%,奖励值增加了13.65%;进一步地,与启发式算法对比也验证了本文提出的方法可以快速高效完成模型求解,合理确定定制公交乘降点位置和具体线路走向。
Abstract
The optimization of customized bus route with multiple boarding sites and alighting sites considering heterogeneous fleet is studied. Aiming at minimizing passenger trip cost and bus operating cost, the problem is formulated as a mathematical programming model where some constraints indicating the boarding and alighting mode, site number, the length of bus route, the number of customized buses are considered. The traditional methods are not efficient in solving large-scale mathematical models. So a deep reinforcement learning procedure based on Actor-Critic dual neural network is proposed. Here the customized bus is regarded as agent. The learning environment of the agent is established by the unsupervised clustering approach. And then the state space-action space-reward function of the agent is presented and a Actor-Critic double neural network is given to select and evaluate boarding sites and alighting site. So a deep reinforcement learning algorithm based on Actor-Critic dual neural network is obtained. The coordinate data of boarding-alighting sites and resident trip is collected together to set up testing experiment. These hyper-parameters, which is composed of learning rate, discount factor, batch size and number of neurons, are debugged by New Actor neural network and Old Actor neural network. The customized bus route scheme based on multiple boarding sites and alighting sites can be obtained by the proposed deep reinforcement learning algorithm. The performance measures, which consist of the layout of boarding and alighting sites, customized bus route distance, bus occupancy rate and bus type allocation, verify the rationality of the customized bus route scheme. The deep reinforcement learning algorithm based on single Actor neural network is used as a comparison testing. The convergence speed of proposed algorithm is improved by 28.57% and the reward value is increased by 13.65%. Furthermore, compared with the heuristic algorithms, this paper also verifies that the proposed method can quickly and efficiently complete the model solution, and reasonably determine the location of the customized bus stops and the specific route direction.
随着城市公共交通优先发展战略的实施,城市公交系统快速发展,公交服务水平显著提升,公交出行成为居民最主要的出行方式之一。然而,居民的多样化出行需求与常规公交单一服务模式之间的矛盾越来越突出,制约了城市公交系统进一步提升。在“互联网+交通”背景下,出现了以乘客出行需求为导向,提供个性化服务的定制公交,根据客流预约出行需求选择乘降点,将区域预约需求转化为线路需求,从而给出更为合理的公交线路,满足乘客出行需求。对于跨区域长距离城市通勤需求,定制公交服务具有良好的需求响应效果。但是定制公交的实际运营存在上座率不高、运行成本高、运行时间长等问题,使得中国城市定制公交系统发展缓慢。如何依据乘客出行需求,合理布局乘降点位置、有序安排公交线路走向亟待深入研究。
关于定制公交的研究起源于“预约+共享”这一概念,早期研究主要集中在理论探讨层面。Liu和Ceder[1]首次使用定制公交这一概念,根据开通定制公交的30个城市数据,总结了定制公交的背景、分类、规划运营等方面内容。Wang等[2]研究了定制公交系统在整个城市公共交通系统中的定位,即定制公交的主要服务群体、市场定位、系统建设,Wang等[3]研究了定制公交服务的空间依赖性问题。
引入量化技术是解决定制公交问题的有效方法。在面向多上车点单下车点的多对一定制公交线路优化问题研究方面,Ellegood等[4]研究一类校车接送的多对一定制公交路线,采用连续近似模型为多个学校运送学生路线提供有利条件;安久煜等[5]研究考虑回程空载的资源浪费的接驳性定制公交线网调度优化模型;王正武[6]提出接驳公交基于关键点的路径优化方法。在面向多上车点多下车点的多对多定制公交线路优化方面,Guo等[7]研究定制公交路线设计,构建混合整数规划模型并用遗传和分支定界算法求解对比。马昌喜等[8]以现有多个上下车站点,构建突发公共卫生事件下的应急定制公交线路优化方法。现有研究集中关注乘降点数量而未考虑基于乘客出行需求的乘降点位置规划,但定制公交线路受乘降点数量和位置等因素影响。
目前开展的定制公交线网优化研究主要从乘客便利度或公交公司运营效率角度展开。马昌喜等[8]以定制公交总运行时长最短为目标构建模型;王超等[9]考虑总运营里程最小建立模型;Li等[10]考虑运营车辆数量最少构建目标函数。只有少数学者研究了考虑乘客和企业的优化目标,Wang等[11]以乘车消耗和公交运营成本最小为目标,提出两阶段优化模型进行求解。陈汐等[12]以最小化乘客出行成本、车辆运营成本为优化目标;Huang等[13]在最大服务率和最小运营成本目标条件下研究定制公交线路优化问题。上述研究均未考虑多种车型,仅探讨了优化目标对定制公交线网优化的影响。也有学者研究了多车型的定制公交单目标优化问题,胡郁葱等[14] 以总成本最小构建了考虑多起终点、多车型的定制公交线路规划模型,并利用遗传算法改进编码规则;何民等[15]采用不同车型来体现乘客舒适性,构建考虑响应式定制公交运营商成本最小和出行可靠性、舒适性要求的公交线路设计模型。随着人工智能的高速发展,利用人工智能算法来解决线网优化问题成为进一步的发展方向,Wang等[16]研究考虑跨区域的路径规划,提出基于Q-learning算法的定制公交路线优化方法。彭理群等[17]提出一种跨区域定制公交的搭乘方案,通过改进Q-learning算法对公交线路进行优化。现有研究利用启发式算法或强化学习求解优化模型,但是面对复杂的环境和高维的数据,启发式算法或强化学习算法求解效率不理想。表1根据乘降点数量、乘降点规划、优化目标、车型以及求解算法的不同,罗列了相关研究问题的结果。
由表1可知,已有研究工作在开展线网优化工作中,在公交车型多样化、乘降点规划调整等方面考虑不多,且在研究方法设计方面多采用商用求解器、启发式算法来完成求解任务。面对市场的竞争化机制和乘客实际使用需求,运营公司需要建立定制公交服务的快速需求响应机制[18],但考虑到定制公交线路规划是一个动态实时决策过程,会存在乘降点位置变化、乘客出行需求异动、公交车型变动等诸多可变因素干扰,为快速需求响应机制带来不小的挑战。显然,已有研究所采用的方法无法有效应对需求响应式定制公交的实时应答要求。为弥补上述研究的不足,本文将在以下方面进行拓展:一是研究考虑多车型定制公交车队;二是综合考虑乘客出行成本与公交运营成本;三是依据乘客出行需求完成乘降点实时规划;四是提出双重神经网络深度强化学习求解方法。
表 1 相关研究问题结果展示
Tab. 1 Results for the research problems considered
1 问题建模
1.1 问题描述
多对多定制公交线网优化问题可描述为:运营公司根据乘客的出行需求划分出上车区域和下车区域,上车区域和下车区域之间存在多个乘客行程。每辆定制公交从上车区域某个上车点出发,并继续前往其他上车点搭载乘客,然后再将乘客一一送至下车区域的相应下车点,直至完成车上所有乘客出行需求。公交运营公司需要根据乘客出行需求,在上车区域和下车区域合理安排上下车站点位置,设计不同车型定制公交的运行线路,在满足公交载客量以及线路开行条件下,将乘客送达目的地,并最小化乘客出行成本和公交企业运营成本。
为简化模型,本文作出以下假设:首先,每辆车只能服务上车点的一个行程(一个上车点可能存在多个行程);其次,定制公交车辆在上车区域接完所有乘客后,才能前往下车区域将乘客送到相应下车点;最后,上车区域内上车点乘客在只上不下,下车区域内下车点乘客只下不上。
1.2 符号说明
为构建模型,引入集合、参数与变量见表2。
表 2 符号说明
Tab. 2 Notation and definitions
1.3 双层混合整数规划模型构建
上层模型以考虑乘客出行成本和公交运营成本最小为优化目标。
(1)
∑i,j∈λ[mw](αijmw⋅pij)⩽l,∀w∈W,∀m∈M
(2)
∑i∈λ[mw]αimw=1,∀i∈λ[mw]
(3)
∑i∈λ[mw]γimw=1,∀i∈λ[mw]
(4)
αimw+γimw⩽1,∀i∈λ[mw]
(5)
∑j=1,j≠ij∈λ[mv]βjimw=1−αimv,∀i∈λ[mw]
(6)
∑j=1,j≠ij∈λ[mv]βijmw=1−γimv,∀i∈λ[mw]
(7)
ujmw⩾uimw+1−n(1−βijmw),∀i∈λ[mw],i≠j
(8)
uimw⩾1,uimw⩽‖λ[mw]‖
(9)
式(1)为上层模型优化目标,其中第1部分是公交车固定发车成本,f(g)是公交车发车数量,为下层模型的优化目标;第2部分是公交车运行成本;第3部分是乘客出行的时间成本。式(2)为定制公交线路长度约束,要求定制公交车辆满足续航要求。式(3)~(5)为始发和终到站点唯一性约束。对任意定制公交,其运营线路只能有一个始发站点和终到站点,且同一乘降点不能同时作为始发站点和终到站点。式(6)为节点访问约束,对于定制公交的任意乘降点(非始发站点),都有定制公交车辆访问。式(7)同理,为节点离开约束,对于定制公交的任意乘降点(非终到站点),都有定制公交车辆离开。式(8)、(9)为子环路消除约束,‖λ[mw]‖是m型公交车辆w投入运营需要访问的乘降点数量。
Ming=∑m∈M∑w∈Wxmw
(10)
∑m∈M∑w∈Wy(od)mv=1,∀(o,d)∈ψ
(11)
∑(od)∈ψ2y(od)mv⩽φ,∀w∈W,m∈M
(12)
∑(o,d)∈ψy(od)mw⋅nod⩾μfm,∀w∈W,m∈M
(13)
∑(o,d)∈ψy(od)mw⋅nod⩽fm,∀w∈W,m∈M
(14)
xmv=y(od)mw,∀w∈W,m∈M
(15)
zomw=y(od)mw,zdmw=y(od)mw,∀w∈W,m∈M,o,d∈V
(16)
λ[mw]=V⋅zimw
(17)
式(10)为下层模型的优化目标,是最小化公交车辆使用数量。式(11)为乘客od行程服务约束,要求任意乘客od行程都应该被一辆定制公交车服务。式(12)为线路乘降点访问数量约束,要求单条定制公交线路的乘降点访问数量不能超过最大访问数量限制。式(13)为最低乘车人数约束,要求公交线路的开通必须满足定制公交最低乘车人数限制。式(14)为最大运力约束,定制公交服务的乘客总数量不超过最大运力限制。式(15)为公交车投入运营约束,当m型公交车辆w服务乘客(od)行程时,该辆公交车应投入运营,否则无需投入运营。式(16)为乘降点访问约束,od行程如果被定制公交车辆服务,该od行程的上车点o和下车点d应被纳入定制公交运营线路。式(17)定制公交线路服务站点集合生成。
2 基于Actor-Critic网络的深度强化学习
作为连接值函数逼近与策略优化两大技术路线的桥梁,基于Actor-Critic网络的深度强化学习近年来在动态调度、机器人控制等复杂决策领域的应用取得突破性进展。Actor-Critic双重网络的深度强化学习算法将策略梯度方法与价值函数评估进行有机融合,能够直接优化策略并利用价值函数提供实时反馈。通过Critic神经网络的价值评估,该算法能够在每一步决策后更新策略,这种单步更新机制显著提升了学习效率。Critic神经网络的价值估计能够有效降低策略梯度估计中的方差,使训练过程更加稳定。此外,Critic神经网络对策略潜在价值的评估能够指导探索过程,有助于解决强化学习中智能体的探索与利用平衡问题。与传统的Q-learning或策略梯度方法相比,Actor-Critic双重网络的深度强化学习算法兼具高效性与稳定性,能够更好地适应复杂环境中的连续决策任务。
此外,多对多定制公交线网优化问题属于大规模车辆路径问题,精确求解效率不高。深度强化学习是深度学习和强化学习的结合,利用深度学习技术来处理高维复杂数据,并在强化学习框架下指导智能体在复杂环境中作出智能决策。本文设计基于Actor-Critic双重网络的深度强化学习方法。设置基于乘客数-乘降点-行驶距离的状态空间,构建基于接续乘降点选择的动作空间,给出基于乘客出行与公交运营的奖励函数,利用Actor神经网络(actor network,简称AN)进行定制公交接续乘降点动作选择、Critic神经网络(critic network,简称CN)进行接续乘降点动作选择的优劣评价,给出基于乘降点选择与评价的Actor-Critic网络训练方法,形成基于Actor-Critic网络的深度强化学习过程。
2.1 定制公交智能体学习环境
以定制公交为智能体,乘降点位置和距离为定制公交智能体学习环境,使得定制公交智能体在学习环境的反馈奖励中不断优化策略以获得更大奖励值的动作优化策略。利用无监督聚类,依据上车点和下车点坐标位置,确定定制公交线路乘降点,构建公交智能体学习环境,步骤如下:
步骤1​   确定上车点坐标位置。通过定制公交乘客出行需求调查,收集乘客的经纬度位置信息,利用坐标转换工具将经纬度位置信息映射到平面坐标系。
步骤2​   生成上车点初始聚类划分。给定乘客步行距离,利用层次聚类法对上车点坐标位置数据进行聚类,得到K​个上车点初始聚类划分。
步骤3​   更新上车点聚类划分。依次从K​个初始聚类划分中随机选择K​个上车点作为聚类中心,分别计算其余上车点与K​个聚类中心之间的距离,并将上车点重新分配到距离最近的聚类中心所在划分,从而形成K​个新聚类划分。
步骤4​   更新聚类划分中心上车点。对K​个新聚类划分,分别计算聚类划分内所有上车点横坐标的平均值和纵坐标的平均值,并将横坐标的平均值和纵坐标的平均值作为新的聚类划分中心上车点。
步骤5​   上车点位置确定。重复执行步骤3和步骤4,直至聚类划分中心位置不再改变,从而得到上车区域上车点位置。
步骤6​   下车区域下车点位置确定。对下车区域下车点坐标位置数据执行上述步骤,从而得到定制公交线路的下车区域下车点位置。
定制公交智能体与学习环境交互可用马尔科夫决策过程表示,即下一状态取决于智能体当前状态和采取的动作。以定制公交智能体从当前乘降点到接续乘降点为时段t,下面对定制公交智能体的状态-动作-奖励机制进行设置。
2.2 定制公交智能体状态-动作-奖励机制
2.2.1 基于乘客数-乘降点-距离的状态空间
设定定制公交的乘客数、所在乘降点和已行驶距离为状态空间St,以表示时段t定制公交智能体与学习环境进行交互产生的信息,即
St={ntmw,vstart mw,vend mw,vθmut,btmv}
式中:ntmω表示m型定制公交w在时段t的乘客数,vstart mw表示m型定制公交w运营线路的始发站点;vend mw表示m型定制公交w运营线路的终到站点;vθmωt表示时段t定制公交智能体所处状态,当θ=0时,表示智能体处在运营线路的始发站点,当θ=1时,表示智能体处在两个乘降点途中,当θ=2时,表示智能体处在运营线路的终到站点;btmw表示m型定制公交w在时段t行驶距离。
2.2.2 基于接续乘降点选择的动作空间
设定定制公交智能体状态为St时,即乘客数为ntmw、乘降点状态为vθmwt和已行驶距离为btmw时,可选择的下一接续乘降点集合为动作空间At,即
At={v∣v∈V}
式中v表示定制公交智能体可选择下一乘降点的动作。
2.2.3 基于乘客出行与公交运营的奖励函数
设定定制公交乘客出行成本Z1的倒数与公交运营成本Z2的倒数之和为奖励函数Rt,以表示时段t定制公交智能体与学习环境交互后,执行动作后获得奖励值,即Rt=1/Z1+1/Z2。
2.3 基于乘降点选择与评价的Actor-Critic网络训练
利用Actor网络(actor network,简称AN)进行定制公交接续乘降点动作选择,Critic网络(critic network,简称CN)进行选择不同接续乘降点的概率分布评价,如图1所示,具体步骤如下:
图 1 Actor-Critic网络训练过程
Fig. 1 Training process of the Actor-Critic network
步骤1​   Actor-Critic网络训练的超参数设置。设置学习率α​、折扣因子γ​、批尺寸β​、神经元数η​作为Actor-Critic网络训练的超参数。
步骤2​   基于接续乘降点选择的Actor网络输入输出设置。Actor网络分为用于更新控制参数的New Actor网络和用于收集经验数据的Old Actor网络,设置其控制参数分别为θ​和δ​,将定制公交状态空间St​和动作空间At​作为New Actor网络和Old Actor网络输入,输出定制公交从动作空间At​中选择不同接续乘降点的概率分布πθ​(St​,At​)和πδ​(St​,At​)。
步骤3​   基于评价不同接续乘降点概率分布的Critic网络输入输出设置。设置Critic网络的控制参数λ​,将Old Actor网络的状态空间St​和动作空间At​作为Critic网络输入,输出状态空间St​的价值估计值H​(St​|πδ​)和动作空间At​的价值估计值U​(At​|πδ​)。
步骤4​   Critic神经网络训练。利用优势函数ψ​(St​,At​)评估在状态St​下执行选择不同乘降点的动作At​对于当前策略的价值提升,如式(18)所示。采用时序差分误差的方法计算Critic网络损失函数LCN​,并反向传播更新参数λ​,如式(19)所示。通过最小化损失函数,Critic神经网络更准确地估计状态价值,从而为Actor网络提供反馈,即
ψ(St,At)=U(At∣πδ)−H(St∣πδ)
(18)
LCN(λ)=Et(Rt+γH(St+1∣πδ)−H(St∣πδ))2
(19)
​式中Et​( )为t​时段的期望函数;γ​为折扣因子;H​(St+1​|πδ​)为下一状态St+1​的价值估计值;ψ​(St​,At​) 为定制公交状态St​下采取动作At​的优势函数,当ψ​(St​,At​)>0时,说明此动作优于平均动作,增加选择该动作的概率;当ψ​(St​,At​)<0时,说明此动作劣于平均动作,减少选择该动作的概率。
步骤5​   Actor神经网络训练。计算New Actor和Old Actor网络概率分布比率τ​和Actor网络损失函数LAN​并反向传播更新New Actor网络参数θ​,间隔固定迭代次数S​复制New Actor网络参数θ​来更新Old Actor网络参数δ​,即
τ=πϑ(St,At)πδ(St,At)
(20)
LAN(θ)=−Et[min(τ⋅ψ(St,At),ψ(St,At)⋅clip(τ,1−ε,1+ε))]
(21)
式中min(·)为最小值函数;τ为New Actor和Old Actor网络概率分布比率;clip为Python内置截断函数,将New Actor和Old Actor网络参数更新限定在[1-ε,1+ε]之间;ε为截断系数,参照张玺君等[19]将该系数设置为0.2。
2.4 基于Actor-Critic网络的深度强化学习过程
基于Actor-Critic网络深度强化学习的定制公交线网优化过程,如图2所示,具体步骤如下:
图 2 基于Actor-Critic网络的深度强化学习过程
Fig. 2 Deep reinforcement learning process based on the Actor-Critic network
步骤1​   初始化定制公交智能体学习环境、基于乘客数-乘降点-行驶距离的状态空间和基于接续乘降点选择的动作空间。
步骤2​   设置用于Actor-Critic网络训练的超参数,即学习率α​、折扣因子γ​、批尺寸β​、神经元数η​。
步骤3  ​ 随机初始化生成New Actor网络控制参数θ​、Old Actor网络控制参数δ​和Critic网络控制参数λ​。
步骤4  ​ 根据定制公交状态空间St​,智能体选择不同接续乘降点的动作空间At​,得到奖励Rt​和下一时段状态空间St+1​。
步骤5​   记录每一时段t​的当前状态空间St​、下一状态空间St+1​、动作空间At​以及奖励Rt​构造并存放到经验数据集。
步骤6​   从经验数据集中随机抽取β​个数据用于训练Actor-Critic网络训练。
步骤7  ​ 利用式(1)计算评价定制公交智能体接续乘降点动作好坏的优势函数ψ​(St​,At​)。
步骤8​   利用式(2)计算Critic网络损失函数值,使用梯度下降法更新参数λ​,以最小化损失函数。
步骤9​   利用式(3)计算New Actor和Old Actor网络概率分布比率τ​。
步骤10  ​ 利用式(4)计算Actor网络损失函数值,反向传播更新New Actor网络控制参数θ​,间隔固定迭代次数ς​复制New Actor网络控制参数θ​更新Old Actor网络参数δ​。
步骤11​   判断迭代次数是否达到最大迭代次数,若未达到,则转到步骤4,直至满足最大迭代次数结束。
3 案例研究与结果分析
3.1 数据采集与处理
借助公共交通大数据平台,并通过实地调研郑州市高新区、郑东新区乘客流量相对集中的商圈、居住小区和工作区出行数据,同时利用百度地图捕获乘客出行起讫点经纬度坐标,借助COORD软件,利用高斯三度带地图投影方法,将乘客出行经纬度坐标转换为平面坐标,其分布如图3所示。
图 3 定制公交乘客起讫点转换平面坐标分布
Fig. 3 Distribution of converted planar coordinates of customized bus passenger origins and destinations
定制公交车队的车辆配属规模为6辆,大小2种车型配属,小车型满载18人,大车型满载30人,单次发车成本分别为80元/车和100元/车,单位距离运行成本为2元/km,行驶速度为35 km/h,单条线路乘降点最大允许访问数量限制为6个,公交车辆最低上座率为75%,单条线路最长运行距离为40 km,乘客在车时间成本为6元/(人·h)。
3.2 基于无监督聚类的智能体学习环境构建
利用层次聚类法对乘客出行起讫点坐标位置数据进行聚类,给定乘客步行距离800 m,得到8个上车点初始聚类划分和6个下车点初始聚类划分。依次更新上车点和下车点聚类划分及其聚类划分中心,得到上车点聚类划分中心位置和下车点聚类划分中心位置,如图4、5所示。
图 4 上车点聚类划分中心位置转换坐标分布
Fig. 4 Distribution of converted coordinates of boarding-stop cluster centers
图 5 下车点聚类划分中心位置转换坐标分布
Fig. 5 Distribution of converted coordinates of alighting-stop cluster centers
对上下车区域聚类划分结果进行评估,计算出上车区域聚类平均轮廓系数为0.451,下车区域聚类平均轮廓系数为0.500,达到较好聚类效果。通过无监督聚类分析获取乘降点的平面坐标,利用COORD坐标转换工具将平面坐标转换为经纬度坐标,依据上下车点附近常规公交站点和道路环境,调整站点的位置,得到满足定制公交乘客出行要求的上下车点以及距离矩阵,如表3和表5所示,其中编号为o开头的表示上车点,标号以d开头的表示下车点。
表 3 定制公交上下车站点的经纬度
Tab. 3 Longitude and latitude of customized bus boarding and alighting stops
进一步的,将8个上车点依次执行以下步骤:首先,统计上车点覆盖范围内所有乘客OD行程;接着,将相同目的地(即相同下车点)的OD行程合并,得到合并后的OD行程及相应客流量,如表4所示。
表 4 乘客出行OD行程信息
Tab. 4 Origin-destination (OD) trip information of passengers
表 5 上下车站点距离矩阵
Tab. 5 Distance matrix of boarding and alighting stops
3.3 Actor-Critic网络训练的超参数设置
利用Anaconda平台使用python在Intel(R)Core(TM)i5-8250U CPU@1.60 GHz 1.80 GHz环境下编译基于Actor-Critic网络的深度强化学习算法,对定制公交智能体进行训练学习。设定最大迭代次数为100 000,利用New Actor网络控制参数更新Old Actor网络控制参数的间隔固定迭代次数S=1 000。
为实现基于Actor-Critic网络的深度强化学习算法的最佳性能,对学习率α、折扣因子γ、批尺寸β和神经元数η四个超参数进行对比验证,分析超参数对训练速率的影响,如图6所示。横轴表示迭代次数,纵轴表示训练速率。
图 6 超参数不同取值对训练速率的影响
Fig. 6 Effects of different hyperparameter settings on training speed
图6(a)表示学习率不同取值对训练速率的影响。当学习率α=1×10-3时,训练速率值呈现下降趋势;当学习率α=1×10-5时,训练速率值在80~100低值之间波动;当学习率α=1×10-4时,训练速率值呈现上升趋势,且数值明显高于学习率为1×10-3、1×10-5。故学习率选取1×10-4。
图6(b)表示折扣因子不同取值对训练速率的影响。当折扣因子γ=0.90时,训练速率值波动于85~105的低值之间;当折扣因子γ=0.95时,训练速率值有所提升,但训练速率值仍较低;当折扣因子γ=0.99时,训练速率值呈现先下降后回升的趋势同时保持105~110的高值之间。故折扣因子选取0.99。
图6(c)表示批尺寸不同取值对训练速率的影响。当批尺寸β=512时,训练速率值呈现大幅度下降后小幅度回升,其数值稳定在60~80之间;当批尺寸β=1 024时,训练速率值出现显著的下降趋势;当批尺寸β=2 048时,训练速率值呈现先下降后回升的趋势,且数值均高于批尺寸为512、1 024。故批尺寸选取2 048。
图6(d)表示神经元数不同取值对训练速率的影响。当神经元数η=64、128时,训练速率值均先下降后稳定在一定的区间内;当神经元数η=256时,训练速率值呈现微小波动,且数值都高于学习率为64、128时的表现。故神经元数选取256。
通过对学习率α、折扣因子γ、批尺寸β、神经元数η进行灵敏度分析,超参数取值如表6所示。
表 6 超参数取值
Tab. 6 Hyperparameter settings
3.4 研究结果分析
利用基于Actor-Critic网络的深度强化学习进行求解,图7表示迭代次数与奖励值的收敛效果图,迭代次数达到2×104后奖励值收敛且平稳保持在0.003 2附近,寻优能力强且收敛速度快。当训练次数大于2×104次后,Actor网络的损失值逐渐趋于0,Critic网络的损失函数值在0.016~0.025之间震荡,说明基于Actor-Critic网络深度强化学习的公交智能体训练效果较好。
图 7 迭代次数与奖励值的收敛效果
Fig. 7 Convergence of reward values over iterations
如图7所示,奖励值在迭代次数2×104后趋于稳定,计算公交运营成本Z1=756.4元,乘客出行成本Z2=506.3元,得到定制公交线网优化方案如表7和定制公交线路分布如图8所示。
表 7 定制公交线网优化方案
Tab. 7 Optimization scheme of the customized bus network
图 8 定制公交线路分布
Fig. 8 Spatial distribution of customized bus routes
由表7可以看出,定制公交线网优化方案的线路平均上座率为88.66%,共配属2辆载客量为18的公交和3辆载客量为30的公交,车辆行驶距离均控制在合理范围内,且线路中乘降点个数均未超过6个,从而保障了定制公交一人一座、舒适直达的优势。
从定制公交运行时间来看,图9表示定制公交不同线路的运行时间分布图,任意一辆定制公交完成服务所需最长时间均小于66 min,5辆车的总运行时间为276 min。
图 9 定制公交运行时间分布
Fig. 9 Distribution of customized bus travel times
从定制公交车辆上座率来看,图10表示定制公交不同线路的上座率分布图,5辆定制公交的上座率均超过80%,其中有1辆定制公交车的上座率接近或达到100%,充分利用车辆资源。
图 10 定制公交车辆上座率分布
Fig. 10 Distribution of customized bus vehicle load factors
通过分析与对比,利用Actor-Critic双重网络深度强化学习算法得到的定制公交开行方案,其车辆行驶时长、车辆上座率与车型安排等指标数据均反映出较好的性能。
3.5 Actor-Critic网络与Actor网络对比
为了验证基于Actor-Critic双重网络深度强化学习的可行性和优越性,将其与基于Actor单重网络的深度强化学习进行对比,采取相同的状态、动作、奖励机制和相同的超参数取值进行训练学习,对比结果如表8所示,不同算法下迭代次数与奖励值的关系如图11所示。由表8可知,基于Actor单重网络的深度强化学习的计算时间为6 h,而基于Actor-Critic双重网络深度强化学习的计算时间为4.5 h,相比于Actor单重网络的深度强化学习减少了1.5 h。
较基于Actor单重网络的深度强化学习算法,基于Actor-Critic双重网络的深度强化学习算法收敛速度快且奖励值高,其原因在于Critic网络具有提高算法稳定性、加速收敛和提高样本效率的优势,提高定制公交智能体学习的效率和稳定性。
表 8 Actor-Critic网络与Actor网络对比结果
Tab. 8 Performance comparison between the Actor-Critic network and the Actor network
图11表示不同算法下迭代次数与奖励值的对比关系,基于Actor-Critic双重网络深度强化学习算法的奖励值在迭代次数为0~20 000之间时波动性较大,但在20 000~50 000之间时波动性逐渐降低,50 000次之后趋于稳定;而基于Actor单重网络深度强化学习算法的波动性在迭代次数为0~20 000之间没有趋于稳定,直至70 000次之后趋于稳定收敛。基于Actor-Critic双重网络深度强化学习算法较基于Actor单重网络深度强化学习算法的收敛速度提高了28.57%,奖励值增加了13.65%,说明本文算法能够快速高效解决多对多定制公交线网优化问题。
图 11 不同算法下迭代次数与奖励值的关系
Fig. 11 Reward convergence under different algorithms
3.6 Actor-Critic网络强化学习算法求解性能评估
为进一步验证Actor-Critic(为便于表述,简写为AC)网络强化学习算法的高效性,本节引入遗传算法(genetic algorithm,GA)和邻域搜索算法(Neighborhood Search,NS)作为对比,并导入五种更大规模试验中进行测试。同时选取行驶距离、总运营成本和运行时间作为指标对不同算法的求解性能进行试验比对。GA和NS为十次求解的平均值。这里改进率η1=(GA算法的总运营成本-AC的总运营成本)/AC的总运营成本×100%,改进率η2=(NS算法的总运营成本-AC的总运营成本)/AC的总运营成本×100%。5种不同规模试验场景下的连续10次测试得到的平均值如表 9所示。
表 9 5种不同规模试验场景下的算法性能比对
Tab. 9 Performance comparison of algorithms across five test scenarios of different scales
由表9中数据可以看出:1)由总运营成本指标可知,AC求解的总运营成本最低、NS次之、GA最高。总运营成本指标比较结果为AC< NS<GA。2)由改进率指标可知,小规模场景下,AC相较GA和NS的求解优越性不突出;但随着规模逐渐增加,AC的优越性愈发明显。
综上,Actor-Critic双重网络深度强化学习算法在模型求解质量上具有明显优势,尤其随着问题规模的增加,优势愈加明显。
4 结论
本文研究多对多定制公交线网优化问题,以乘客出行成本和公交运营成本最小为目标,考虑乘降点服务、乘降点数量、线路总长度以及公交车队规模等限制,构建多对多定制公交线网优化模型。
鉴于多对多定制公交线网优化问题属于大规模车辆路径问题,精确求解效率不高。故提出基于Actor-Critic双重网络的深度强化学习方法。该方法将定制公交视为智能体,利用无监督聚类建立智能体学习环境,构造智能体状态-动作-奖励机制,设计基于乘降点选择与评价的Actor-Critic神经网络,搭建基于Actor-Critic网络深度强化学习过程。通过选取郑州市高新区-郑东新区为实验场景,对学习率、折扣因子、批尺寸和神经元数等超参数进行优化调试,求解得到多对多定制公交线网优化方案,并通过与其他算法对比,得到如下结论:
1)与基于Actor单重网络的深度强化学习进行对比,算法收敛速度提高了28.57%,奖励值增加了13.65%,从而更加快速高效解决多对多定制公交线网优化问题。
2)与启发式算法对比结果表明,本文所提出的方法可以快速高效完成多对多定制公交线网优化模型求解,合理确定定制公交乘降点位置和具体线路走向,最大限度解决乘客通勤需求问题,缩减乘客的出行时间成本和公交企业的运营成本。
考虑定制公交行程时间的不确定性以及乘客出行行程取消等因素扰动,对定制公交线网优化模型进一步完善,是未来进一步的研究方向。
图 1 Actor-Critic网络训练过程
Fig. 1 Training process of the Actor-Critic network
图 2 基于Actor-Critic网络的深度强化学习过程
Fig. 2 Deep reinforcement learning process based on the Actor-Critic network
图 3 定制公交乘客起讫点转换平面坐标分布
Fig. 3 Distribution of converted planar coordinates of customized bus passenger origins and destinations
图 4 上车点聚类划分中心位置转换坐标分布
Fig. 4 Distribution of converted coordinates of boarding-stop cluster centers
图 5 下车点聚类划分中心位置转换坐标分布
Fig. 5 Distribution of converted coordinates of alighting-stop cluster centers
图 6 超参数不同取值对训练速率的影响
Fig. 6 Effects of different hyperparameter settings on training speed
图 7 迭代次数与奖励值的收敛效果
Fig. 7 Convergence of reward values over iterations
图 8 定制公交线路分布
Fig. 8 Spatial distribution of customized bus routes
图 9 定制公交运行时间分布
Fig. 9 Distribution of customized bus travel times
图 10 定制公交车辆上座率分布
Fig. 10 Distribution of customized bus vehicle load factors
图 11 不同算法下迭代次数与奖励值的关系
Fig. 11 Reward convergence under different algorithms
表 1 相关研究问题结果展示
Tab. 1 Results for the research problems considered
表 2 符号说明
Tab. 2 Notation and definitions
表 3 定制公交上下车站点的经纬度
Tab. 3 Longitude and latitude of customized bus boarding and alighting stops
表 4 乘客出行OD行程信息
Tab. 4 Origin-destination (OD) trip information of passengers
表 5 上下车站点距离矩阵
Tab. 5 Distance matrix of boarding and alighting stops
表 6 超参数取值
Tab. 6 Hyperparameter settings
表 7 定制公交线网优化方案
Tab. 7 Optimization scheme of the customized bus network
表 8 Actor-Critic网络与Actor网络对比结果
Tab. 8 Performance comparison between the Actor-Critic network and the Actor network
表 9 5种不同规模试验场景下的算法性能比对
Tab. 9 Performance comparison of algorithms across five test scenarios of different scales
Liu T, Ceder A. Analysis of a new public-transport-service concept: customized bus in China[J]. Transport Policy, 2015, 39: 63
Wang J B, Yamamoto T, Liu K. Role of customized bus services in the transportation system: insight from actual performance [J]. Journal of Advanced Transportation, 2019, 2019: 6171532
Wang J B, Yamamoto T, Liu K. Spatial dependence and spillover effects in customized bus demand: empirical evidence using spatial dynamic panel models[J]. Transport Policy, 2021, 105: 166
Ellegood W A, Campbell J F, North J. Continuous approximation models for mixed load school bus routing [J]. Transportation Research Part B: Methodological, 2015, 77: 182
安久煜, 宋瑞, 毕明凯, 等. 高铁车站接驳公交灵活线路优化设计研究[J]. 交通运输系统工程与信息, 2019, 19(5): 150
An Jiuyu, Song Rui, Bi Mingkai, et al. Optimization flexible route design for high-speed railway station feeder bus [J]. Journal of Transportation Systems Engineering and Information Technology, 2019, 19(5): 150
王正武, 向健, 喻杰. 响应型接驳公交系统基于关键点的动态路径优化[J]. 长沙理工大学学报(自然科学版), 2020, 17(3): 51
Wang Zhengwu, Xiang Jian, Yu Jie. Dynamic route optimization based on key points for responsive feeder transit system[J]. Journal of Changsha University of Science & Technology (Natural Science), 2020, 17(3): 51
Guo R G, Guan W, Zhang W Y. Route design problem of customized buses: mixed integer programming model and case study [J]. Journal of Transportation Engineering, Part A: Systems, 2018, 144(11): 04018069
马昌喜, 王超, 郝威, 等. 突发公共卫生事件下应急定制公交线路优化[J]. 交通运输工程学报, 2020, 20(3): 89
Ma Changxi, Wang Chao, Hao Wei, et al. Emergency customized bus route optimization under public health emergencies[J]. Journal of Traffic and Transportation Engineering, 2020, 20(3): 89
王超, 马昌喜. 基于遗传算法的定制公交多停车场多车线路优化[J]. 交通信息与安全, 2019, 37(3): 109
Wang Chao, Ma Changxi. Optimization of parking lot and multivehicle route of customized buses based on genetic algorithm[J]. Journal of Transport Information and Safety, 2019, 37(3): 109
Li Z J, Song R, He S W, et al. Methodology of mixed load customized bus lines and adjustment based on time windows[J]. Plos One, 2018, 13(1):
Wang C, Ma C X, Xu X C. Multi-objective optimization of realtime customized bus routes based on two-stage method[J]. Physica A: Statistical Mechanics and its Applications, 2020, 537: 122774
陈汐, 王印海, 刘剑锋, 等. 多区域通勤定制公交线路规划模型及求解算法[J]. 交通运输系统工程与信息, 2020, 20(4): 166
Chen Xi, Wang Yinhai, Liu Jianfeng, et al. Multi-region commuting bus route design model and solution method[J]. Journal of Transportation Systems Engineering and Information Technology, 2020, 20(4): 166
Huang K, Xu L, Chen Y, et al. Customized bus route optimization with the real-time data [J]. Journal of Advanced Transportation, 2020, 2020: 8838994
胡郁葱, 陈栩, 罗嘉陵. 多起终点多车型混载的定制公交线路规划模型[J]. 广西师范大学学报(自然科学版), 201, 36(4): 1 Hu Yucong, Chen Xu, Luo Jialing. Network design model of customized bus in diversified operation of multi-origin-destination and multi-type vehicle mixed load[J]. Journal of Guangxi Normal University (Natural Science Edition), 2018, 36(4): 1
何民, 李沐轩, 税文兵, 等. 可靠性和舒适性对响应式定制公交线路设计的影响[J]. 公路交通科技, 2019, 36(5): 145
He Min, Li Muxuan, Shui Wenbing, et al. Influence of reliability and comfort on responsive custom bus route design[J]. Journal of Highway and Transportation Research and Development, 2019, 36(5): 145
Wang A G, Guan H Z, Wang P F. Cross-regional customized bus route planning considering staggered commuting during the COVID19[J]. IEEE Access, 2021, 9: 20208
彭理群, 罗明波, 卢赫, 等. 基于 Q-learning 的定制公交跨区域路径规划研究[J]. 交通运输系统工程与信息, 2020, 20(1): 104
Peng Liqun, Luo Mingbo, Lu He, et al. Cross-regional customized bus path planning based on Q-learning [J]. Journal of Transportation Systems Engineering and Information Technology, 2020, 20(1): 104
马昌喜, 郝威, 沈金星, 等. 定制公交线路优化综述[J]. 交通运输工程学报, 2021, 21(5): 30
Ma Changxi, Hao Wei, Shen Jinxing, et al. Review on customized bus route optimization [J]. Journal of Traffic and Transportation Engineering, 2021, 21(5): 30
张玺君, 聂生元, 李喆, 等. 基于自注意力机制的深度强化学习交通信号控制 [J]. 交通运输系统工程与信息, 2024, 24(2): 96
Zhang Xijun, Nie Shengyuan, Li Zhe, et al. Traffic signal control with deep reinforcement learning and self-attention mechanism[J]. Journal of Transportation Systems Engineering and Information Technology, 2024, 24(2): 96