基于最小费用最大流改进算法的多种交通方式开行方案协同优化研究论文

基于最小费用最大流改进算法的多种交通方式开行方案协同优化研究

赵璐阳1,王丽娟1,宋金凤2

(1.石家庄铁道大学 交通运输学院,河北 石家庄 050043;2.河北东方学院 交通学院,河北 廊坊065001)

摘 要: 为降低日常非拥挤状态下城际间综合运输系统的客运总成本,对运输通道内多种交通方式的列车开行方案或车辆运行作业计划进行了协同优化。以广义运输成本最小为目标函数,以成本和客流为约束条件,将协同优化归纳为最小费用最大流问题。为提高计算效率,根据图论中最小费用最大流常用算法之一的最小费用路算法设计出协同优化改进算法。以示例路网为基础,构建协同优化合适算例进行改进算法应用。结果表明,协同优化可以有效降低非拥挤状态下综合运输系统客运总成本,其改进算法表现出良好的有效性和准确性。

关键词: 城际铁路;开行方案;协同优化;非拥挤状态;最小费用最大流;广义成本

0 引言

城际铁路具有快速、便捷、舒适、环保等特点,《中长期铁路网规划》中明确提出要发展城际铁路以补充现代高速铁路网。城际铁路在城际间客运市场内与原有的既有铁路和公路运输存在竞争,同时因其票价较高、定线定员开行、路网规模有限等特点,又与既有铁路和公路运输存在协同优化的可能。因此,加强城际铁路、既有铁路和公路的协同合作,可以更好地服务于城市间客运市场。

目前国内对列车开行方案优化的研究较多,如从坐席分配、列车运行图、开行时段[1-3]等角度入手,通过对基于Logit[4]等模型构建的客流分配模型的求解,采用“按流开车”原则对铁路列车开行方案进行优化。除从微观角度针对某种交通方式的开行方案进行优化研究外,还有学者从宏观角度对多种交通方式间协同优化进行了研究。李国文等[5]研究了客运通道内多种交通方式间客流分配的协同优化问题;胡辉等[6]利用Benders分解技术对多方式物流运输网络优化模型的求解进行研究。求解交通相关问题时,图论理论被部分学者应用,Gutiérrez-Jarpa等[7]通过最小费用最大流算法为公路配送及轨道交通选线提供了优化思路;张天伟等[8]利用最短路求解思路优化了城际铁路设站时的城市选择方法。目前协同优化方法多样,图论相关理论虽然被广泛应用于求解各类交通问题,但利用最小费用最大流理论对多种交通方式开行方案进行协同优化的研究还相对较少。为此,在现有研究基础上,关注非拥挤状态下城际间运输通道内多种交通方式的旅客运输问题,并设计最小费用最大流的改进算法,对多种交通方式开行方案进行协同优化。

A:近年来,上海印刷企业和高校确实获得了许多奖项,但我认为要理智地看待这件事。在参评国内外印制奖项时,我们会派出专家组,深入地与企业交流,帮助他们选择参评产品。在这个过程中,我们发现行业的整体水准并不高。获奖的印制作品只能代表部分企业在部分印制领域的水平。以我个人看来,国家提出的“高质量的产业发展”不是说尖端产品的高质量,而是说普通产品也要达到高质量,全行业的水准都要提高到这个层次。集中精力去做一两件精品是容易的,但是整体达到高水准还有很长的路要走。至于奖项,是起到一个激励的作用,需要企业有更多的创新,不断提高自身印制水平。

1 问题描述

1.1 假设条件

城际间交通系统大部分时期处于运能充足的状态即客流非拥挤状态的情况,通过对多种交通方式开行方案的协同优化研究,可以减少运能浪费并降低广义运输总成本,引导旅客合理选择出行方式并引导多种交通方式有序竞争。因此,非拥挤状态下城际间运输通道内多种交通方式的开行方案协同优化,主要考虑如何满足城际综合运输系统内大城市与中小城市间的旅客运输需求,包括旅客的换乘可能。城际间运输通道多种交通方式客运路网如图1中所示。

使用多功能测温仪(型号DT-131)测量土壤表层(0~20 cm)温度(ts),每组重复3次。使用照度计(HT-8318)测量群落顶部(距离地面 60 cm处)光照度(Il),每组重复 3次。在每个样地内使用直径 5 cm的土钻沿着对角线采集 5钻土壤(0~20 cm),混合后立即装入铝盒,带回实验室称量湿重,然后在105 ℃下烘干称量干重,最后计算其土壤含水量(SWC),计算公式如下:

图1 城际间运输通道多种交通方式客运路网
Fig.1 Multiple transport modes network in intercity transport corridors

注:圆圈中数字代表城市编号。

城际间运输通道内多种交通方式开行方案协同优化研究,假设相邻城市间至少存在1种即公路运输的客运直达交通方式,而城际铁路及既有铁路只在大城市设枢纽站可始发或终到列车,2个大城市间的中小城市所设车站均为中间站,仅可停靠列车。

1.2 参数及变量定义

大城市1与大城市N 分别为城际列车的起点和终点,依次对沿线中小城市进行1,2,…,N 的自然序列编号。对城际间K 种常用交通方式进行编号,规定K = 1表示城际铁路,K = 2表示既有铁路,K = 3表示公路运输。其余参数及变量分为以下4类。

发展表现在各个层面,不只是国家宏观经济层面的发展,也包括每一个行业、每一个产业的发展。现阶段,我国十分重视农村地区的发展。开展农田水利现代化建设,解决水资源缺乏对原州区发展的桎梏,可以提高原州区生产力水平,对于实现原州区经济发展和建设社会主义新农村有积极意义。

(1)成本类参数。 为城市i 到相邻城市j 之间第K 种直达交通方式的广义运输成本(i ,j = 1,2,…,N ,K = 1,2,3),元/人,取值范围 ≥0或 = -1。认为当i =j 时 = 0;当城市i 与相邻城市j 间不存在K 种直达交通方式时,或当城市i 与城市j 不是可直达的相邻城市时 = -1 (K = 1,2,3)。CK 为开行一列列车的广义运输成本(K = 1,2),元/列,取值范围CK > 0。

(2)0-1变量。 为判断是否为最低广义运输成本的0-1变量,当第K 种直达交通方式是城市i 到相邻城市j 之间最低广义运输成本时, 为1,否则为0。此时 = 1的集合形成了城际运输通道内最低成本路网。Txy 为城市x 与城市y 间相邻OD路段最低广义运输成本的集合,即Txy = { = 1 |=1,…, = 1},为首尾相连的相邻OD路段的0-1变量集合,其中x 与c ,以及d 与y 分别为相邻城市。

(3)客流量类参数。axy 为城市x 至城市y 的OD客流量,人,取值范围axy ≥0。Aij 为城市i 到相邻城市j 间路段客流承担量,人,取值范围Aij ≥ 0。

(4)其他参数及变量。VK 为K 种交通方式的单位载客量即每趟列车或客车的载客量,人/列或人/辆,取值范围VK > 0。LK 为城际铁路与既有铁路的合理开行数(K = 1,2),列。其中合理开行数包括基础开行数 和可调开行数 2个部分。 为城市i 与相邻城市j 间公路运输的合理开行数,辆,取值范围LK ≥0,且为整数。

1.3 协同优化

为方便计算,需简化实际运输网络。首先,判断各城市间是否存在直达交通方式,即2个城市是否相邻;其次,比较各相邻城市间广义运输成本,确定成本最低的交通方式,逐一为0-1变量 赋值,从而得到城际运输通道内最低广义运输成本客运路网,形成实际问题的赋权有向简单图。城际运输通道内最低广义运输成本客运路网示意图如图2所示。

图2 城际运输通道内最低广义运输成本客运路网示意图
Fig.2 Lowest social generalized transport cost passenger transport network

(1)成本参数逻辑关系。根据已知各相邻城市间多种交通方式的广义运输成本可得出城际铁路或既有铁路单向开行一列列车的广义运输成本,即

式中,认为相邻城市间上行和下行列车开行时广义运输成本相等,故列车单向开行时的广义运输成本等于往返开行时的一半。

(2)客流参数逻辑关系。根据已知OD客流量及计算出的OD间成本最小路径,对客流进行0-1分配,从而得到各相邻OD路段的初始客流承担量Aij ,此时计算出的各OD间客流承担量应满足

式中,如果Txy 的集合中不存在 = 1的成员,则取 = 0。当某OD间并非成本最小路径或并非相邻OD路段时认为其不承担客流,即Aij = 0。在计算时,Aij 的数值可能会被调整,调整后的客流承担量仍记为Aij

(3)目标函数。所构建优化模型的目标函数为广义运输总成本最低,即

1.4.4 湿度指数(NDMI) 湿度指数NDMI对湿度、含水量信息非常敏感[8,16],因为短波红外波段(相当于MODIS的Ref6)受水吸收带的影响,并且绿波段(相当于MODIS的Ref4波段)对水体反射敏感强,选用MODIS的这两个波段通过规格化处理的计算公式:

式中:为城际铁路与既有铁路当前开行方案产生的总广义运输成本;为公路运输当前开行方案产生的总广义运输成本,具体费用大小与问题求解结果有关。

(4)0-1变量约束。求解最短路时为避免重复选线,已确定的0-1变量应满足

(5)客流约束。去往某城市的客流量及该城市发出的客流量应满足以下关系

即从城市i 发出路段的总客流承担量与进入城市i 路段的总客流承担量之差,应等于客流OD表中在城市i 下车的总客流量与在城市i 上车的总客流量之差。

(6)开行约束。为保证协同优化的开行方案可提高运能的利用率,故开行方案应满足

根据运筹学图论中的最短路理论,使用Dijkstra算法求出每一对OD点间已知的广义运输成本的最短路,并将结果记录在最短路集合表中。最短路集合表样式如表1所示。在表1的基础上利用0-1分配法将已知OD交通客流量表中所有客流分配至其对应的最短路上,分配时需确保客流的连续,从而可快捷准确得出路段客流承担量表。路段客流承担量表样式如表2所示。

由于公路运输时每辆车载客量较少,在协同优化开行方案时认为其合理开行数量应与客运需求相匹配,即公路运输提供的运能刚好满足公路运输需求。即

基于CIM/G的电网调度控制系统Web图形展示技术//王民昆,韩晓,伍凌云,孙云枫,汪燕,翟明玉//(6):81

仿真时,将额定工频50 Hz及采样值输入三角函数神经网络进行训练,即可快速获得基波和各次谐波的谐波频率、幅值及其相位,目标误差eobj设为0.001。

由于此类问题使用数学模型求解较复杂,当与实际网络相结合,利用网络的某些性质求解将有效提高其计算效率,因而将此类问题归纳为图论中最小费用最大流问题,并设计相关改进算法进行求解。

2 多种交通方式开行方案协同优化模型改进算法

对传统的最小费用最大流理论进行改进,认为其弧容量为各路段客流承担量而非路段通过能力,弧费用为各路段广义运输成本。在计算时对最小费用最大流常用算法之一的最小费用路算法进行了改进。首先,认为弧容量为弧流量的下限而非上限,计算结束时各弧流量需大于等于其容量但不宜过大;其次,认为弧容量是动态可变的,允许客流承担量即弧容量在路段间进行合理调整;最后,当弧流量大于等于弧容量时表示该弧已被满足,不能再作为增广链的一部分。改进算法分为3个部分,第1部分仅考虑铁路运输并依据传统算法求解出基础开行数;第2部分考虑3种交通方式并依据上述要求,通过寻找最小费用增广链调整系统流量,迭代至所有弧容量被满足;第3部分比较得出总费用最低的开行方案,确定可调开行数。

2.1 基础数据计算

根据假设条件,在非拥挤状态下城际间运输通道内多种交通方式的开行方案协同优化运能充足,可满足客流需求,即如公式 ⑹ 所示。公式 ⑺ 目的是为确保运能的高效利用,避免开行过多列车。

在计算最短路时可能出现成本相等的线路,称其为“可相互替换线路”,2条线路分别被括起或用斜体表示。按照“括起初始计算线路,斜体表示可替换线路”的原则进行标注,此2条线路不同时参与计算。

表1 最短路集合表样式
Tab.1 Shortest path set table style

表2 路段客流承担量表样式
Tab.2 Section passenger flow bearing table style

将相邻城市间的路段客流承担量及其最低广义运输成本按照(Aij )的形式记录下来,从而得到计算所需的最小费用最大流基础图。多种交通方式协同优化最小费用最大流基础图如图3所示。

图3 多种交通方式协同优化最小费用最大流基础图
Fig.3 Basic map of minimum cost maximum flow for collaborative optimization of multiple traffic modes

2.2 算法步骤

步骤5:将剩余客流需求统一分配给各相邻城市间的公路运输。

图4 多种交通方式协同优化最小费用最大流计算图
Fig.4 Calculation of minimum cost maximum flow for collaborative optimization of multiple traffic modes

(1)计算第1部分。

在诊断妊娠合并甲状腺功能异常疾病时,需要对孕妇的临床表现进行观察,同时对孕妇血清促甲状腺激素、游离甲状腺素(FT4)、TT4、TT3、游离三碘甲状腺原氨酸(FT3)等数据进行监测,从而有效诊断妊娠合并甲状腺功能异常[19]。

步骤1:使用最小费用最大流理论解法求解出当前计算图的最小费用最大流。

选择2015年11月至2017年10月入住我院ICU的51例重症肺炎合并呼吸衰竭患者,均接受俯卧位机械通气治疗,均符合重症肺炎合并呼吸衰竭的诊断[4]。纳入标准:①患者在呼吸机辅助后仍存在低氧血症;②对于该研究内容知情并签署了书面的同意书。排除标准:①血流动力学变化较大者;②颅内压升高;③严重感染者;④颌面部创伤、脊柱损伤、骨盆骨折等不宜使用俯卧位机械通气的患者;⑤合并恶性肿瘤、精神或神经系统疾病、妊娠者。本研究中男28例,女23例,年龄35~76岁,平均年龄(51.26±8.6)岁。该研究由我院伦理委员会审核后批准。

步骤2:得到协同优化开行方案的基础开行数 ,并确定计算第2部分迭代算法的初始值。在计算基础开行数时可采用四舍五入的方法提高运输效率。

以图1为例,对城市1至城市8上行方向的协同优化开行方案进行计算,以验证协同优化及其改进算法的有效性和准确性。

步骤3:设还需增开n 趟城际列车或m 趟既有列车,并设n 和m 的初始值为0。

步骤4:调整图中弧容量,将铁路沿线可由公路运输改为铁路运输的客流需求进行调整。

由于城际铁路及既有铁路在开行时,需从城市1始发至城市N 终到,期间提供的运能一定,适用最小费用最大流的求解原则。而公路运输可从任意城市始发至周边城市终到,根据客流需求可直接求解开行方案,但不适用最小费用最大流的求解原则。故在计算的第1部分,即使用最小费用最大流理论计算时暂不考虑 = 1 的路段。在计算的第2部分即使用迭代算法计算时再加入此部分。多种交通方式协同优化最小费用最大流计算图如图4所示。

步骤6:求解得出当前开行方案下目标函数z 的值,记作znm

步骤7:判断城际铁路及既有铁路线路上是否存在剩余客流需求未被满足,若存在则n =n + 1或m =m + 1,转至步骤4分别迭代1次,并记录成本较低的znm 开行方案,以简化后期迭代;若不存在则转至步骤8。

(3)计算第3部分。

2.课后的面批面改,因为是一对一的互动,所以可以帮助怕写作,怕修改的心理。现在的小学生由于平时知识和语言的积累较贫乏,对习作都有一定的害怕心理,而我们老师在平时的批改评语时不可能写具体,即使写清楚了,学生也不一定会去仔细看,即使看了老师的批语,也不能够理解领会,也不知怎样才能针对老师所指出的问题,作自我修改。所以,我们教师的面批面改可以给予学生修改的方法,也可以帮助学生克服怕写作、怕改作文的心理。

步骤8:求解出znm 的最小值。

由于班额变小,所以教师的教学任务比原来增加不少,这对原本就师资短缺的高职院校来讲是一个实际存在的困难和问题。从长远来讲,提高高职人才培养质量势在必行,而小班化教学是提高教学质量的行之有效的措施,要寻求措施增加师生比缓解这种矛盾。

步骤9:确定出开行方案的可调开行数 ,得出非拥挤状态下城际间多种交通方式协同优化的开行方案,计算结束。

算法中步骤4所提到的可由公路运输改为铁路运输的客流需求是指某OD对间客流有多种交通方式可选,从广义运输成本角度公路运输的成本最低。但是,如果增开城际铁路或既有铁路,需将此部分客流需求从公路运输调整至城际铁路或既有铁路上来,从而提高城际间综合运输系统整体的运能利用率。

周转材料租赁主要在于对施工项目的主体结构起到辅助成型的作用,租赁公司的租赁材料主要覆盖了建筑施工项目多次周转的施工材料,包括主体施工中的模板脚手架的各项材料,这类材料在主体施工的过程中存在用量大、损耗大的问题,由于其用量大及损耗大的施工问题,对于承租单位(施工单位)来说工程造价中所占的比例也大,稍微管理不当对于租赁单位及承租单位都会出现不可预估的经济损失。

3 算例应用

(2)计算第2部分。

假定已知运输通道内相邻城市间多种交通方式的广义运输成本及各城市间OD客流,且在换乘时暂不考虑旅客换乘时间成本。成本及客流取值差异不影响模型计算过程及结果有效性,即利用该模型总能找到当前问题的最优协同开行方案,故算例按城际铁路、既有铁路、公路运输成本依次增大设置广义运输成本,依据大中小城市规模间出行数量依次减少设置OD客流,具体如下。

(1)城际铁路各OD点间的广义运输成本。城际铁路线路为:1→2→3→4→6→8。各段线路成本为: = 40元, = 30元, = 30元, = 30元, = 40元。

(2)既有铁路各OD点间的广义运输成本。既有铁路线路为:1→2→5→6→8。各段线路成本为: = 50元, = 60元, = 40元,= 50元。

转换后行为认知成本,指的是用户在全新电商平台下,付出成本和学习新课程的成本。当前电商平台在对界面设计、网页浏览操作等环节上存在较大差别,因此用户所感知的服务质量上会出现较为明显的差异,不利于后续工作的开展,甚至对用户忠诚度的维持也将产生负面影响。

(3)公路运输各OD点间的广义运输成本。公路广义运输成本如表3所示。

表3 公路运输广义运输成本表 元
Tab.3 Generalized transport cost table for road transport

(4)OD调查上行客流量。OD调查上行客流量如表4所示。

表4 OD调查上行客流量表 万人
Tab.4 OD survey traffic flow at up direction

(5)多种交通方式的单位载客量。V 1 = 600,V 2 = 1 500,V 3 = 50。

通过已知数据可完成准备工作,首先使用Dijkstra算法得出各OD点间最短路集合,在此基础上,可计算出各OD点间路段客流承担量。其次计算出开行每列车的广义运输成本C 1 = 10.2万元/列,C 2 = 30万元/列。

2)分析智慧城市需要具备的功能,结合智慧城市理念规划设计的现代化新型城市要求具备多种功能,尤其需要具有信息化功能;

在此基础上,通过第1部分算法,可计算出2种铁路交通方式的基础开行数 = 32列 = 1列。

通过第2部分算法,经11次迭代后,城际铁路及既有铁路线路上均不存在剩余客流需求,故迭代完成。其中在第7次迭代后,城际铁路线路上已不存在剩余客流,故不再参与迭代。

进入算法第3部分,比较11次迭代所得出的18种开行方案,可得minznm =z 10 = 499.3万元,相应可调开行数为 = 1列, = 0列。故通过协同优化问题计算可得到3种交通方式的合理开行数分别为:L 1 = 33列,L 2 = 1列, = 24辆, = 40辆, = 30辆, = 20辆, = 40辆, = 20辆, = 44辆, = 110辆, = 120辆, = 60辆。

4 结束语

研究以城际铁路为主导的城际间运输通道内多种交通方式开行方案的协同优化,对有效降低旅客运输系统在非拥挤状态下的广义运输总成本具有重要意义。考虑广义运输成本及OD客流2个要素,将协同优化归纳为最小费用最大流问题,并依据其常用算法设计出协同优化改进算法以提高计算效率。协同优化结果为城际间运输通道内多种交通方式的日常开行方案提供了合理方案建议,在降低综合运输系统日常广义运输总成本的同时,可以促进多种交通方式间有序竞争,还可以对更大规模的城市群或更多种类的交通方式进行深入研究,考虑换乘成本等因素,探讨更加高效的算法。

参考文献:

[1]蓝伯雄,吴李知. 高速铁路客运网络列车开行方案优化模型[J]. 中国管理科学,2010,18(6):51-58.LAN Boxiong,WU Lizhi. Optimization Model for Line Planning in Rail Passenger Transport Network[J]. Chinese Journal of Management Science,2010,18(6):51-58.

[2]苏焕银,史 峰,邓连波,等. 面向时变需求的高速铁路列车开行方案优化方法[J]. 交通运输系统工程与信息,2016,16(5):110-116,135.SU Huanyin,SHI Feng,DENG Lianbo,et al. Timedependent Demand Oriented Line Planning Optimization for the High-Speed Railway[J]. Journal of Transportation Systems Engineering and Information Technology,2016,16(5):110-116,135.

[3]张琳奇,聂 磊,付慧伶,等. 高速铁路节假日列车开行方案优化研究[J]. 铁道运输与经济,2017,39(11):57-62,66.ZHANG Linqi,NIE Lei,FU Huiling,et al. Optimization Model for High-Speed Railway Line Planning during Holidays[J]. Railway Transport and Economy, 2017,39(11):57-62,66.

[4]吴文娴. 铁路通道内客流分担率及客运组织策略研究[J].中国铁道科学,2011,32(2):126-130.WU Wenxian. Research on the Share Rate of Passenger Flow and Transportation Organization Strategy in Railway Transportation Corridor[J]. China Railway Science,2011,32(2):126-130.

[5]李国文,张建旭. 客运通道出行 OD 多方式划分模型及其实现算法[J]. 公路,2016,61(3):144-148.

[6]胡 辉,顾丽琴,倪 明. 基于 Benders 分解的多方式物流运输网络优化模型[J]. 华东交通大学学报,2015,32(2):72-77.HU Hui,GU Liqin,NI Ming. Optimization Model of Multi-mode Logistic Transportation Network based on Benders Decomposition[J]. Journal of East China Jiaotong University,2015,32(2):72-77.

[7]GUTIÉRREZ-JARPA G,DONOSO M,OBREQUE C,et al. Minimum Cost Path Location for Maximum Traffic Capture[J]. Computers & Industrial Engineering,2010,58(2):332-341.

[8]张天伟,赵媛媛,闫绍辉,等. 城际铁路设站城市选择优化模型[J]. 铁道运输与经济,2018,40(1):75-80.ZHANG Tianwei,ZHAO Yuanyuan,YAN Shaohui,et al. Optimization Model of Selecting Cities Setting Intercity Railway Stations[J]. Railway Transport and Economy,2018,40(1):75-80.

A Study on the Collaboration and Optimization for Multiple Traffic Modes Operation Plan based on the Minimum Cost and Maximum Flow Improvement Algorithm

ZHAO Luyang1,WANG Lijuan1,SONG Jinfeng2

(1.School of Traffic and Transportation, Shijiazhuang Tiedao University, Shijiazhuang 050043, Hebei, China; 2.School of Traffic, Hebei Oriental University, Langfang 065001, Hebei, China)

Abstract: To reduce the total passenger transport cost of the intercity integrated transport system in the daily non-congested state, this paper collaboratively optimizes the train operation plan or vehicle running plan of the multiple traffic modes in the system. Collaborative optimization is summed up to the minimum cost maximum flow problem which takes the minimum social generalized transport cost as objective function and takes the cost and passenger flow as constraints in the public perspective. It designs plans to improve related algorithms according to one of the most commonly used algorithms about the minimum cost maximum flow in graph theory to improve the computational efficiency. After using an appropriate numerical example of collaborative optimization based on the example road network which is designed to improve algorithm application, the results show that the collaborative optimization can effectively reduce the total passenger transport cost of the integrated transport system under non-congested conditions,and the improved algorithm is effective and accurate in solving problems.

Keywords: Intercity Railway; Operation Plan; Cooperation and Optimization; Non-congested State; Minimum Cost Maximum Flow; Generalized Cost

文章编号: 1003-1421(2019)03-0006-06

中图分类号: U116.1

文献标识码: A

DOI: 10.16668/j.cnki.issn.1003-1421.2019.03.02

收稿日期: 2018-01-09

基金项目: 河北省社会科学基金项目 (HB16GL075)

责任编辑: 金 颖

标签:;  ;  ;  ;  ;  ;  ;  ;  

基于最小费用最大流改进算法的多种交通方式开行方案协同优化研究论文
下载Doc文档

猜你喜欢