1、2023 年 2 月总第 349 期基金项目 成都市哲学社会科学规划项目（2022BZ121）收稿日期：20221009；修回日期：20221114作者简介：张苗（1983），女，四川内江人，硕士，工程师，主要从事物流与供应链管理研究，E-mail：。“双碳”目标下基于双层规划的通勤定制电动公交单车路径优化张苗，张卫林，李瑞麒，周舒翼摘要：“双碳”目标下，大力推行通勤定制公交，优化公交路径，满足乘客出行需要，对缓解城市交通拥堵，提升减排协同治理成效具有重要作用。文章在现有通勤定制公交路径研究基础上，通过引入电动公交充电站条件制约，以及乘客在选择乘车站点的自主偏好因子，构建更符合实际的双层规划模
2、型，并通过算例模拟，进一步优化定制行驶路线，为通勤定制电动公交线路规划提供依据。关键词：双碳；路径优化；定制电动公交中图分类号：U121文献标识码：ADOI：10.3969/j.issn.1674-9146.2023.02.051（成都职业技术学院，四川成都610041）文章编号：1674-9146（2023）02051041研究背景我国于2020年9月明确提出碳达峰与碳中和的“双碳”目标，该目标是我国推动人类命运共同体构建的责任体现和大国担当，也是加快生态文明建设和实现高质量可持续发展的重要抓手。我国碳排放总量巨大，要实现碳达峰、碳中和的目标，需要逐步形成一条融绿色生产、绿色消费、绿色流通为
3、一体的绿色产业链，促进资源全面节约和循环利用。其中，大力宣传“公交优先、绿色出行”理念，倡导绿色、安全、文明出行新方式，不断完善绿色出行基础设施，做优地面公交，构建多元化的公共交通服务模式，提升绿色出行服务品质，对实现“双碳”目标具有至关重要的作用。自2013年起，北京、上海、广州、深圳、南京、太原等20多个城市为通勤者开通定制公交服务。定制公交依托自身便捷、经济的共享式服务，可吸引部分通勤者将通勤出行方式由私家车出行转为公交出行，进而缓解出勤日城市交通道路拥堵情况。同时，公交路径优化决策是影响定制公交服务质量的核心环节，也是平衡通勤者出行需求和公交公司经济效益的关键因素。2现有研究文献综述通
4、勤定制公交（又叫通勤高峰快线）路径优化属于一类特殊的车辆路径问题（Vehicle RoutingProblem，VRP），它是在一定约束条件下借助行驶路径的设计达到期望目标。但是，通勤定制公交服务对象为对出行时间较为敏感的通勤人员，出行时段为工作日早晚高峰，同时通勤定制电动公交还受到可用电量、充电站等条件制约。通过对通勤定制电动公交路径优化研究，可为校车和物流配送车辆调度及线路优化相关研究提供参考，助力车辆路径理论的发展与完善1-2。2.1定制公交路径优化目标研究卢小林等3在允许公交车临时偏移基准线路服务乘客需求站点，途径特殊路段可同时服务道路两侧的乘客需求的假设下，以最小化公交车运营时间为目
5、标；陈汐等4在乘客需求已知条件下，以最小化乘客出行成本、车辆运营成本为优化目标；孙继洋等在已知乘客需求量、车辆载客容量和站点间行程时间的条件下，将车辆的运行时间和乘客出行时间最小化作为目标。2.2定制公交路径优化模型研究潘述亮等在已知乘客需求和车队规模的条件下，建立了灵活型接驳公交路径优化和协同调度的同步优化混合整数规划模型；王玉生等5建立 01整数规划模型，对电动公交选址和服务范围进行决策；薛运强等6考虑现实中公交站点乘客数量不确定性因素，构建不确定理论构建公交线路配车的不确定双层规划模型；Liu T 等7考虑需求分配的综合公交时刻表同步与车辆调度问题，构建出基于赤字函数法的双目标双层模型。
6、2.3定制公交路径优化算法研究卢小林等3将待求解问题转化为旅行商问题，设计出一种三阶段求解算法；杨熙宇等使用遗传算*-051-SCI-TECH INNOVATION&PRODUCTIVITYNo.2 Feb.2023，Total No.349法求解多服务模式公交优化设计模型；郭戎格等2围绕运营总收益最大化的单目标混合整数规划模型，设计新的自适应大邻域搜索算法，提出相应的初始解生成规则和邻域搜索算子；姚恩建等基于DBSCAN 算法，对乘客目的地聚类，求解针对铁路车站夜间乘客疏散问题的多线路动态规划模型。纵观现有研究成果，主要包括 3 个方面：一是定制公交路径优化目标一般分为单目标优化和多目标优化
7、。单目标主要围绕公交运行成本、公交行驶时间、公交服务质量、乘客出行成本等某一目标展开，多目标主要围绕公交运营和乘客效用两方面展开。二是与 VRP 类似，定制公交路径优化模型构建以整数规划模型和双层规划模型为主要形式。三是定制公交路径优化出行需求一般较大，算法设计通常采用启发式智能算法，具体形式呈多样化。随着电动公交的逐渐推广，定制公交的路径优化需要考虑停车场设置、停靠点选择、充电站设点，以及针对不同类型的乘客需求设置特定的时间窗属性、设置差异化票价机制等，这些将为未来研究提供方向。3模型构建3.1条件假设考虑通勤定制公交单车情况，假设各站点候车总乘客人数小于单车容量；乘客群选择偏好相同，均关注
8、步行到站点的时间，且乘客对既定路径公交车达到各站点的时间已知；公交公司确定定制公交路径时只考虑运行成本、乘客服务成本以及充电成本，其他如空驶成本、车辆固定成本、路段堵塞成本等不予考虑；充电站点也为乘车站点；任意公交站点互通，只考虑直线距离，并且起点和终点不上客。3.2符号说明1）已知参数。i 为车辆可选第 i 个停车站点；tij为车辆从站点 i 到站点 j 的行驶成本；Tki为乘客群 k 到站点 i 的步行时间；Tki为乘客群 k 到站点 i的步行时间成本；ck为乘客群 k 的人数；di为车辆从始点沿既定路径到达站点 i 的行驶时间；k为乘客群 k 在候车站点选择时的偏好概率；为公交车单位充电
9、成本；V 为车辆可选停车站点集合；F 为车辆可选充电站点集合；C 为乘客群的集合。2）决策变量。若校车经过候选站点 i，yi=1，否则 yi=0；若车辆在充电站 m 充电，wm=1，否则wm=0；若车辆从站点 i 直接到站点 j，Zij=1，否则Zij=0；若车辆从站点 i 到充电站点 m 充电，uim=1，否则 uim=0；若乘客群 k 到达站点 i 候车，xkt=1，否则 xkt=0。3.3模型构建单车辆通勤定制公交路径优化问题分别以公交公司和乘客群为两个互相独立又互相影响的决策对象：公交公司可以自主选择停车站点和充电站点并承担相应的成本变化，进而影响但不完全决定乘客对乘车站点的选择；乘客
10、可以根据自己的关注偏好和行为习惯，自主选择唯一乘车站点并承担相应的乘车步行成本，并反过来影响公交公司对停车站点和充电站点的修正调整。故可将该问题看成 Lead-er-Follower 问题，通过构建双层规划模型对问题进行描述。模型描述如下。上层规划模型（U）的目标函数为F1=miniVjVtijzij+kCiVTkixkick+iVmFtimuim（1）其约束条件为iVyi1mFwm1iVzij=lVzjl=yi，jViVuim=jVumj=wm，mFjVzsj=iVzie=1yi 0，1，iVwi 0，1，iVzij 0，1，i，jVxki 0，1，iV，iCuim 0，1，iV，mF|下层
11、规划模型（L）的目标函数为F2=miniVkF（kTkixki+（1-k）dixki/ck）（3）其约束条件为iVxki=1，kCxki 0，1，iV，k|C（4）上层规划模型（U）描述为公交公司为追求单车定制公交最小总成本，需选择合适的停车站点和充电站点，并确定行车路径。其中，上层目标函数明确最小总成本由运行成本、服务成本和充电成本三部分组成。第 1 条约束条件要求行车路径除起点和终点外，至少有一个中间停车站点；第 2 条约束条件限制行车路径至少途经一个充电站点；第 3 条约束条件保证进入站点（非起点和终点）的车辆经上客后必须驶向唯一的下一站点；第 4 条约束条件表示车辆经充电站 m 后必须
12、驶向唯一的下一站点；可持 续 发 展Sustainable Development（2）-052-2023 年 2 月总第 349 期第 5 条约束条件表示车辆从起点 s 出发必须到达终点 e；第 6 条 第 10 条约束条件为变量 01 限制。下层规划模型（L）描述为乘客群为追求乘车时间成本最小，在通勤公交行车路径中选择一个合适的候车站点。下层目标函数明确乘客群在选择偏好影响下，总乘车时间成本最低。第 1 条约束条件确保任意乘客群能且仅能选择一个候车站点；第 2 条约束条件为变量 01 限制。4算法设计由于通勤定制公交路径优化属于特殊 VRP，故上述模型可基于 A*算法设计求解方法。A*算法
13、是路径规划中应用最为普遍的启发式算法之一。相较于遗传算法、蚁群算法等其他路径规划算法，A*算法过程简单，易于理解，运行速度快。因此，整体性价比较高。A*算法的基本思想是从起点节点出发，通过目标函数对待搜寻节点到目标节点进行价值评估，以确定下一最优节点，如此循环扩展，一直搜寻到目标节点，终止循环。其中，A*算法中目标函数 f(x)=g(x)+h(x)。f(x)表示从起点出发，经过中间节点 x 后到目标节点的估计代价；g(x)表示从起点到中间节点 x 的实际代价；h(x)表示从中间节点 x 到目标节点的估计代价。假设父节点为 U，相邻节点为 V，则 g(V)=g(U)+h(U,V),则目标函数等于
14、乘客选择偏好概率下的公交运行总成本和乘客选择成本的权重求和。用伪代码将 A*算法主要过程描述如下。1）设置起点为 S，终点为 E。2）将起点 S 添加到开放列表 Openlist 中。3）计算 S 的目标函数 g(V)。4）查找 Openlist 中 g(V)最小的节点，记为 Nmin。5）将 Nmin从 Openlist 中删除，并添加 Nmin到封闭列表 Closelist 中。6）查找 Nmin的所有邻居节点，得到集合为 Nlist。7）对于 Nlist 中的每个元素 N，进行如下循环。8）if N 属于 Closelist，跳过该节点。9）if N 不属于 Openlist，添加 N
15、到 Openlist。10）设置节点 N 的父节点为 Nmin。11）计算节点 N 的目标函数 g(V)。12）else if N 属于 Openlist。13）节点 N 以前计算过 g(V)，记原有的 g(V)为g(V)_old。14）计算节点 N 以 Nmin为父节点的新的目标函数 g(V)_new。15）if g(V)_new g(V)_old，设置节点 N 的父节点为 Nmin。16）更新节点 N 的目标函数 g(V)=g(V)_new。17）转入步骤 7，循环遍历列表 Nlist 中的所有邻居节点。18）转入步骤 4，直到 Openlist 为空或者 Nmin等于终点 E。5算例模拟
16、分析5.1算例设计本文以成都市高峰通勤快线需求入手，以成都现有 12 条通勤公交路线数据为模拟，基于模型构建假设，设计算例仿真，参数初始化设置如下8。乘客出行时间成本=当地人均小时收入Tki。成都市统计局关于 2021 年全市城镇全部单位就业人员平均工资的公告数据显示，2021 年成都市城镇全部单位就业人员平均工资为 91 857 元，人均日工作时间按 8 h 计算，则乘客到站点 i 的每分钟步行时间成本 Tki=（91 857Tki）/（603658）=0.52Tki。电动公交载客量 C=40；乘客群 k 在进行乘车站点选择的偏好概率 k=0.8；候选站点集合 V 中站点个数 maxVi=6；充电点集合 F 中站点个数范围maxFi=2；乘客群集合 S 中个数范围 maxCi=5,表 1 为乘客群各点人数，各乘客群点乘客人数 Ck见表 1；车辆从站点 i 到 j 的行驶时间范围为（1，30）；乘客群与侯选站点之间的步行时间 Tki范围为（1，25）；公交车单位充电成本=0.5；乘客可接受最大步行距离l10；候选站点 V2 和 V5 亦为充电站点，公交车所经充电站点数。5.2模拟分析根