本发明涉及地铁运营管控的，尤其是指一种地铁列车时刻表和客流od协同优化的方法。
背景技术：
1、当前多数地铁列车时刻表是根据历史客流分布数据而设计，以被动满足客流需求为目标，但较少关注如何进一步合理利用即时客流od数据，对客流需求进行主动引导。
2、当前现实中采用限制进站客流总人数的控制措施大多是因为方便实施，但是对乘客体验考虑较少，没有考虑对客流od的精细化控制；同时，由于缺乏与列车时刻表的联动，无法保证在降低乘客等待时间的同时优化运行成本，也就无法实现系统效益的最大化。既有的针对轨道线路不同车站列车时刻表与客流od控制优化问题的研究中，采用的客流控制方法多为进站人数总量的控制，少数对客流od精准控制的研究中也忽略了不同车站不同od协同优化对轨道线路整体排队人数和列车运营成本的影响。
3、大规模列车时刻表的优化模型是公认的np问题，目前学术界中普遍认为算法设计是列车时刻表问题最重要和最具有挑战性的内容，设计出有效可靠的求解算法对优化模型的落地应用具有重要的理论和实际意义。由于列车时刻表优化问题有其明显的离散特征，现有的求解算法研究主要集中在定制化或改进的经典算法、基于模型修改的优化求解器求解算法和智能算法这三类。既有研究中已有不少针对模型特性的定制化改进经典算法，但都是结合自身所建立模型的特点，对不同优化模型的适用性较差，而依赖求解器的算法往往在大规模案例中计算效率不能得到保证。因此，构建新的优化模型既需要考虑自身模型特性，同时也需要考虑计算规模的需要，而才能设计出高效高质的求解算法。
技术实现思路
1、本发明的目的在于克服现有技术的缺点与不足，提出了一种地铁列车时刻表和客流od协同优化的方法，对于高峰期大客流地铁线路和站点，从乘客延误时间和列车运行成本最优的角度，主动控制不同od方向上的进站客流人数和进站时间，并和地铁列车时刻表进行联合优化，可以在优化成本的同时，有效减少拥挤和乘客延误时间，提高乘客的出行效率和体验，有利于地铁运营进行精细化客流管控，进而提高地铁系统的服务质量和竞争力。在此基础上基于协同优化模型的理论特性对分支定界算法进行定制化改进，探讨提高算法效率的有效途径，能为解决大规模地铁网络计算效率问题提供一定的参考，有助于研究成果在实际大规模列车时刻表问题中的推广应用。
2、为实现上述目的，本发明所提供的技术方案为：一种地铁列车时刻表和客流od协同优化的方法，包括以下步骤：
3、s1、获取所有乘客的预期到达时间段和起讫点，起点为o，讫点为d，获取列车最小发车间隔、列车容量、线路车站和长度；
4、s2、构造地铁列车时刻表和客流od的协同优化模型，这是个混合整数规划模型，约束条件包括发车间隔约束、延误乘客数量约束和乘客服务约束；
5、s3、设计自适应的分支定界算法，计算上述协同优化模型，输出列车发车方案、所有乘客的成功上车时间段和起讫点。
6、进一步，步骤s2包括如下步骤：
7、s21、根据现有研究和地铁的特点，做出假设，具体如下：
8、列车在所有车站都停留相同长度的时间，列车运行时保持相同的速度行驶，驶过距离相同的两个站点花费的时间相同；基于此，将车站的时间进行偏移处理，使得一趟列车在所有车站的到站和离站时间相同；
9、客流od量已知，相同的客流od乘客采取先到先上车的原则；
10、列车每趟运行成本固定且一致；
11、在运营时间内，列车车底数量充足；
12、s22、决策变量一类为列车发车的0-1决策变量xjs，另一类为整数决策变量和quvj，为在时刻j之前预期到达但暂未分配到预约成功上车时间段的乘客延误排队量；
13、xjs：列车发车的0-1决策变量；等于1表示列车在时刻j车站s发车；等于0表示不考虑发车；
14、为在时刻j之前预期到达但暂未分配到预约成功上车时间段的乘客起讫点经过车站s的延误断面乘客数量；
15、quvj表示起讫点为车站u和车站v，在时刻j之前预期到站，但暂未分配到预约成功上车时间段延误的乘客od数量；
16、s23、根据所述决策变量制定约束条件，各约束条件包括发车间隔约束、延误乘客数量约束和乘客服务约束，数学表述如下：
17、相邻两趟列车的发车间隔不小于最小发车间隔j，其约束表达式如下所示：
18、
19、列车站站停，在所有车站发车时刻都相同，其约束表达式如下所示：
20、
21、在初始时刻，所有车站的延误乘客数量为零，其约束表达式如下所示：
22、
23、在初始时刻，各类延误乘客od数量为零，其约束表达式如下所示：
24、
25、如果列车没有在j时刻发车，则站点s的延误断面乘客数量为时段[j-1,j]内预期到达且经过车站s的延误断面乘客数量之和；如果列车在j时刻发车，则站点s的延误断面乘客数量不小于在时刻j-1站点s的延误断面乘客数量与在时间段[j-1,j]内预期到达且经过车站s的延误断面乘客数量之和减去列车车厢容量之差，其约束表达式如下所示：
26、
27、起讫点为u和v的乘客，在时刻j的延误数量不大于时刻j-1延误数量与时段[j-1,j]内预期到达且起讫点为u和v的乘客od量之和，其约束表达式如下所示：
28、
29、在时刻j-1站点s的延误断面乘客数量，等于经过车站s的延误乘客od数量之和，其约束表达式如下所示：
30、
31、在最后的运营时刻乘客od为u和v的延误数量为零，全部乘客均上车，其约束表达式如下所示：
32、
33、决策变量约束在不同的数值范围内，列车发车变量为0-1变量，车站的断面延误排队数量和乘客od的延误数量为大于或等于零的整数，其约束表达式如下所示：
34、
35、
36、
37、式中：表示车站序号的集合；
38、s,u,v表示车站的序号，
39、表示车站s的上游车站集合和下游车站集合；
40、j表示运营时间范围内时间点序号，
41、表示时间点的集合；j'表示运营时间范围[j-j+1,j]内的时间点序号；
42、xj'1表示列车发车0-1决策变量；等于1表示列车在时刻j'第一个车站发车；等于0表示不考虑发车；
43、xj1表示列车发车的0-1决策变量；等于1表示列车在时刻j第一个车站发车；等于0表示不考虑发车；
44、q0s表示在时刻0之前预期到达但暂未分配到预约成功上车时间段的乘客起讫点经过车站s的延误断面乘客数量；
45、quv0表示起讫点为车站u和车站v，在时刻0之前预期到站，但暂未分配到预约成功上车时间段延误的乘客od数量；
46、表示在时刻j-1之前预期到达但暂未分配到预约成功上车时间段的乘客起讫点经过车站s的延误断面乘客数量；
47、表示在预约时间段[j-1,j]内期望到达上游车站且要前往车站的乘客断面数量；
48、quv,j-1表示起讫点为车站u和车站v，在时刻j-1之前预期到站，但暂未分配到预约成功上车时间段延误的乘客od数量；
49、auvj表示在预约时间段[j-1,j]内期望到达且起讫点为车站u和车站v的乘客数量；
50、c表示列车能容纳的最大乘客数量；
51、s24、得到以最小化乘客总的延误时间成本和列车发车成本的目标函数如下：
52、
53、w表示单个乘客延误一个预约时间段所产生的时间成本；
54、δ表示一个预约时间段的时间间隔时长。
55、进一步，所述分支定界算法的具体情况如下：
56、a、提出理论特性1、理论特性2和理论特性3用于后续的求解中；
57、理论特性1：在时刻如果存在可行解满足以下条件，则解为时刻j1的最优解：
58、即在时刻j1列车发车；
59、即在时刻j1列车发车前，各个车站延误的断面乘客数量不超过列车容量；
60、即在时刻j1列车发车后，各个车站延误的乘客od数量为零；
61、针对可行解表示列车发车的0-1决策变量；等于1表示列车在时刻j1车站s发车；等于0表示不考虑发车；
62、表示在时刻j1之前预期到达但暂未分配到预约成功上车时间段的乘客起讫点经过车站s的延误断面乘客数量；
63、表示起讫点为车站u和车站v，在时刻j1之前预期到站，但暂未分配到预约成功上车时间段延误的乘客od数量；
64、理论特性2：对于协同优化模型的一个可行解时刻j1和j2为两个相邻的列车发车时刻，即满足以下条件时，则该可行解o在[j1,j2]时间范围内是最优解：
65、时刻j1全部车站延误乘客od量之和最小，即
66、在时刻j2列车发车时，所有车站延误的断面乘客数量均不超过列车车厢容量，即
67、
68、理论特性3：在[0,j1]时间范围内，有两个可行解和如果两个解满足以下条件，解优于
69、解从上一次发车到时刻j1所经过的时间不小于从上一次发车到时刻所经过的时间，即
70、解在时刻j1所有车站每一类延误的乘客od量都不大于即
71、
72、解从时刻0至时刻j1所产生的总成本比解从时刻0至时刻j1所产生的总成本小，即
73、式中：表示列车发车的0-1决策变量；等于1表示列车在时刻j1车站s发车；等于0表示不考虑发车；
74、表示列车发车的0-1决策变量；等于1表示列车在时刻j2车站s发车；等于0表示不考虑发车；
75、表示起讫点为车站u和车站v，在时刻j1之前预期到站，但暂未分配到预约成功上车时间段延误的乘客od数量；
76、表示在时刻j1全部车站延误乘客数量之和的最小值；
77、表示在时刻j1之前预期到达但暂未分配到预约成功上车时间段的乘客起讫点经过车站s的延误断面乘客数量；
78、针对可行解表示列车发车的0-1决策变量；等于1表示列车在时刻j车站s发车；等于0表示不考虑发车；表示在时刻j之前预期到达但暂未分配到预约成功上车时间段的乘客起讫点经过车站s的延误断面乘客数量；表示起讫点为车站u和车站v，在时刻j之前预期到站，但暂未分配到预约成功上车时间段延误的乘客od数量；其中，j∈[0,j1]；
79、表示解从上一次发车到时刻j1所经过的时间间隔数；
80、表示解从上一次发车到时刻所经过的时间间隔数；
81、b、提出算法1和算法2用于后续的求解中，算法1用于计算全部车站延误乘客数量之和最小值以及对应的延误乘客od方案，算法2用于计算延误时间成本最小的延误乘客od方案；
82、算法1具体步骤如下：
83、针对存在过饱和车站的发车时刻假设列车发车时预约成功上车的乘客od集合为延误乘客od集合为根据约束对应预约成功上车乘客od的车站断面为对应的延误乘客od的车站断面为根据预约成功上车乘客od和延误乘客od之和守恒，有：
84、
85、式中：表示起讫点为车站u和车站v，在时刻之前预期到站，且分配到预约成功上车时间段延误的乘客od数量；
86、表示起讫点为车站u和车站v，在时刻之前预期到站，但暂未分配到预约成功上车时间段延误的乘客od数量；
87、表示起讫点为车站u和车站v，在时刻之前预期到站，但暂未分配到预约成功上车时间段延误的乘客od数量；
88、表示在预约时间段内期望到达且起讫点为车站u和车站v的乘数量；
89、算法初始时，令
90、step11：计算过饱和车站集合设有k过饱和车站，os＝{s1,s2,...,sk}；
91、式中：s1,s2,...,sk表示过饱和车站；
92、表示在时刻之前预期到达且分配到预约成功上车时间段的乘客起讫点经过车站s的断面乘客数量；
93、step12：判断是否存在经过k车站的od，如果有，从中选择经过站点数量最少的od并设起终点为o和d，有则进入step13，否则令k＝k-1，重新执行step12；
94、式中：表示起讫点为车站o和车站d，在时刻之前预期到站，且分配到预约成功上车时间段延误的乘客od数量；
95、step13：更新
96、
97、
98、
99、
100、式中：si表示过饱和车站，si∈os；
101、step14：判断是否满如果满足，则计算输出时刻全部车站延误乘客数量之和的最小值qj以及对应的延误乘客od集合为结束算法，反之回到step11；
102、式中：表示在时刻之前预期到达但暂未分配到预约成功上车时间段的乘客起讫点经过车站s的延误断面乘客数量；
103、算法2具体步骤如下：
104、step21：初始化j'，令
105、式中：表示起讫点为车站u和车站v，在时刻j1-1之前预期到站，但暂未分配到预约成功上车时间段延误的乘客od数量；
106、表示在时刻j1-1之前预期到达但暂未分配到预约成功上车时间段的乘客起讫点经过车站s的延误断面乘客数量；
107、step22：如果j'＞j2，前往step23，否则计算
108、式中：quvj'表示起讫点为车站u和车站v，在时刻j'之前预期到站，但暂未分配到预约成功上车时间段延误的乘客od数量；
109、表示在时刻j'之前预期到达但暂未分配到预约成功上车时间段的乘客起讫点经过车站s的延误断面乘客数量；
110、表示在时刻j'车站s延误的断面乘客数量的最小值；
111、
112、
113、
114、令j'＝j'+1，重新执行step22；
115、式中：表示在预约时间段[j'-1,j']内期望到达且起讫点为车站u和车站v的乘客数量；
116、xj's表示给定某个列车发车方案；等于1表示列车在时刻j'车站s发车；等于0表示不发车；
117、xj's表示列车发车的0-1决策变量；等于1表示列车在时刻j'车站s发车；等于0表示不考虑发车；
118、表示在预约时间段[j'-1,j']内期望到达上游车站且要前往车站的乘客断面数量；
119、表示在时刻j'-1车站s延误的断面乘客数量的最小值；
120、step23：如果输出在时间段[j1,j2]，给定发车方案下的最小延误时间成本为：
121、
122、算法结束，输出乘客od方案
123、如果当前的最小延误时间成本z为：
124、
125、前往step24；
126、step24：计算j1”，j”2：
127、
128、
129、式中：j”1表示运营时间范围[j1,j2]内的时间点序号；
130、j”2表示运营时间范围[j”1,j2]内的时间点序号；
131、表示在时刻j”-1,之前预期到达但暂未分配到预约成功上车时间段的乘客起讫点经过车站s的延误断面乘客数量；
132、如果j”2不存在，则令j”2＝j2；把经过过饱和车站断面和其它车站断面的延误乘客od替换为少的经过其它车站断面的乘客od，降低其它断面的影响，比较两者的总成本变化，并更新最小成本时的延误乘客od方案令j1＝j”2，重新执行step24，直至j”1不存在，输出在时间段[j1,j2]，给定列车发车方案下的最小延误时间成本为：
133、
134、算法结束；
135、c、为了方便描述定制化的分支定界算法构造的搜索树，定义以下变量：用l表示树的深度，在根节点处，l＝0，树深为l的所有节点集合为该集合节点数量为nl，树深为l的第n个节点表达为(l,n)，每个节点包含的信息有：父节点索引pln、列车发车索引xln、时间索引jln、延误乘客od量车站延误断面乘客量车站延误的断面乘客量的最小值累计总成本cln、列车发车后时间间隔hln、节点的上下界为和bln及全局的上下界分别为和b；
136、式中：表示起讫点为车站u和车站v，在时刻jln之前预期到站，但暂未分配到预约成功上车时间段延误的乘客od数量；
137、表示在时刻jln之前预期到达但暂未分配到预约成功上车时间段的乘客起讫点经过车站s的延误断面乘客数量；
138、表示在时刻jln车站s延误的断面乘客数量的最小值；
139、构造的搜索树采用深度优先搜索策略，所有节点存放在局部选择池集合和全局选择池集合两个不同的池子中，包含当前父节点的所有子节点，包含所有未剪枝的节点；此外，l0、n0、l1、n1分别为父节点所在的树深度、父节点的节点序号、子节点所在的深度、子节点的节点序号。
140、进一步，所述分支定界算法的具体步骤如下：
141、step1：初始化设置：算法开始于根节点(0,0)，父节点索引p00＝1,根节点列车发车索引x00＝0,根节点列车发车后时间间隔h00＝j,根节点时间索引j00＝0,根节点车站延误断面乘客量根节点延误乘客od量根节点车站延误的断面乘客量的最小值根节点累计总成本c00＝0,根节点下界b00＝0,根节点上界此外设置l0＝0,n0＝0,b＝0；
142、式中：quv0表示起讫点为车站u和车站v，在时刻0之前预期到站，但暂未分配到预约成功上车时间段延误的乘客od数量；
143、表示在时刻0之前预期到达但暂未分配到预约成功上车时间段的乘客起讫点经过车站s的延误断面乘客数量；
144、表示在时刻0车站s延误的断面乘客数量的最小值；
145、step2：创建和更新子节点：子节点树深计算为l1＝l0+1，根据父节点(l0,n0)中列车发车后时间间隔的索引和约束条件(1)、(2)创造子节点并更新子节点其它信息：子节点列车发车索引子节点列车发车后时间间隔子节点时间索引子节点延误乘客od量子节点车站延误断面乘客量子节点车站延误的断面乘客量的最小值子节点累计总成本子节点下界子节点上界计算方式如下：
146、
147、
148、
149、
150、
151、
152、式中：表示父节点时间索引；
153、表示子节点时间索引；
154、表示起讫点为车站u和车站v，在时刻之前预期到站，但暂未分配到预约成功上车时间段延误的乘客od数量；
155、表示在预约时间段内期望到达且起讫点为车站u和车站v的乘客数量；
156、表示在预约时间段内期望到达上游车站且要前往车站的乘客断面数量；
157、表示在时刻车站s延误的断面乘客数量的最小值；
158、表示在时刻车站s延误的断面乘客数量的最小值；
159、表示父节点累计总成本；
160、节点(l1,n1)下界为其中为从根节点至当前子节点(l1,n1)所产生的列车发车成本和延误时间成本之和，为子节点(l1,n1)之后节点所产生的未来发车成本，为子节点(l1,n1)之后节点所产生的未来延误时间成本；
161、为方面计算子节点(l1,n1)的下界，根据不等式将计算转为分别计算和其中：是在满足子节点(l1,n1)后续所有乘客都能预约成功的基础上所需要的理论最小发车成本；是在以最小发车间隔运行的情况下，子节点(l1,n1)后续所有乘客的最小延误时间成本，由算法2算出；
162、式中：表示在时刻之前预期到达但暂未分配到预约成功上车时间段的乘客起讫点经过车站s的延误断面乘客数量；
163、表示在预约时间段内期望到达上游车站且要前往车站的乘客断面数量；
164、上界的计算方法如下：从当前节点开始，以满足约束条件(1)、(2)和最小发车间隔运行的情况下，子节点(l1,n1)后续所有乘客的最小延误时间成本和列车发车成本；
165、随后，将能够生成可行解的节点(l1,n1)加入到局部选择池集合中；
166、step3：节点搜索策略：选择一个新的父节点进行分支并更新全局上下界，在节点的探索策略中使用深度优先策略，条件是：如果探索节点的时间索引jln已经到达最后时刻j，即jln＝j，或者局部选择池集合为空，即则在深度优先策略下该分支已经不能再分支，该节点结束分支，并从全局选择池集合中选择下界bln最小的节点作为下个新的父节点进行分支；如果不满足以上条件，将从局部选择池中选择下界最小的节点作为下一个父节点；
167、
168、当选择出下一个父节点后，将局部选择池集合中所有未探索的节点全部添加至全局选择池集合并将局部选择池集合清空，使得等待下次分支时，将节点添加至局部选择池集合中，更新全局选择池集合局部选择池集合及全局上下界和b；
169、
170、式中：表示节点的上界；
171、step4，根据新选择的父节点(l0,n0)，返回step2；如果全局上下界的差值达到给定的收敛值或者算法运行时长达到限定的时长，则算法结束。
172、本发明与现有技术相比，具有如下优点和有益效果：
173、1、本发明设计了一种协同优化列车时刻表和客流od的方法，可以在优化成本的同时，有效减少拥挤和乘客延误时间，提高乘客的出行效率和体验，进而提高地铁系统的服务质量和竞争力。
174、2、本发明结合地铁时刻表和客流od控制协同优化模型的理论特性，探讨提高算法效率的有效途径，能为解决大规模地铁网络计算效率问题提供一定的参考，有助于研究成果在实际大规模列车时刻表问题中的推广应用。
175、总之，本发明能利用精准的全客流时空分布信息，有效解决高峰期站台拥堵，乘客等待时间成本长的问题。
1.一种地铁列车时刻表和客流od协同优化的方法，其特征在于，包括以下步骤：
2.根据权利要求1所述的一种地铁列车时刻表和客流od协同优化的方法，其特征在于，步骤s2包括如下步骤：
3.根据权利要求2所述的一种地铁列车时刻表和客流od协同优化的方法，其特征在于，所述分支定界算法的具体情况如下：
4.根据权利要求3所述的一种地铁列车时刻表和客流od协同优化的方法，其特征在于，所述分支定界算法的具体步骤如下：
