本发明涉及城市轨道交通，特别是一种基于杂交人工蜂群算法的城轨列车开行方案设计方法。
背景技术：
1、列车开行方案是城市轨道交通线路行车组织的基础性计划，包括列车交路、编组、停站和开行频率等内容，为线路后续列车运行图、车辆配置计划编制提供输入数据。随着我国城市轨道交通的快速发展，尤其是具有里程长和客流分布不均衡的线路(如市域线)的出现，使得多交路和快慢车运营策略受到学术界和行业界越来越多的关注，并陆续在一些城市轨道交通线路上采用。学术研究和行业实践均表明，根据城市轨道交通线路客流特征设计不同交路和停站方案不仅能提高乘客的出行体验，降低乘客出行费用，还可以提高线路服务水平，减少运营费用。
2、针对城市轨道交通线路客流分布不均衡问题，采取选择性的跨站停车和有速度差异的快慢车服务模式，可减少乘客旅行时间，加速车底周转，减少车底运用数量。国内外虽然在一定程度上探讨了城市轨道交通列车交路及停站设计问题的方法，但是鲜有文献研究复杂交路条件下开行快慢车的开行方案设计问题。关于复杂交路研究方面，既有研究多基于预设大小交路和二者开行频率存在相关关系的假设，在此条件下优化列车开行方案。但是，随着客流不均衡和大站客流拥挤情况的出现，既有模型已不能满足设置复杂交路的需要。关于停站模式方面，已有研究多为在单一大交路上开行快车，鲜有研究将快车模式结合多交路进行综合优化。然而，公交和城市轨道交通在运营模式上存在不同，公交服务设计的研究难以为城市轨道交通开行方案设计提供有效参考。
技术实现思路
1、为解决现有技术中存在的问题，本发明的目的是提供一种基于杂交人工蜂群算法的城轨列车开行方案设计方法，本发明可用于辅助现场决策。
2、为实现上述目的，本发明采用的技术方案是：一种基于杂交人工蜂群算法的城轨列车开行方案设计方法，包括以下步骤：
3、步骤1、根据列车交路及停站设计问题以及客流分配问题构建的模型，将多交路快慢车运营策略下的城市轨道交通线路列车开行方案设计问题构建为混合整数线性规划模型tsd：
4、(tsd)z＝z1+z2；
5、其中，z1为列车交路与停站设计问题构建的模型，z2为客流分配问题构建的模型；
6、步骤2、利用杂交人工蜂群算法求解所述混合整数线性规划模型tsd。
7、作为本发明的进一步改进，在步骤1中，列车交路及停站设计问题以及客流分配问题具体为：
8、给定城市轨道交通线路的车站、区间、折返站布置及能力和客流需求等信息，确定列车交路的起讫点、停站和开行频率、以及客流分配方案，使得在不超过给定交路条数上限的情况下，满足车站、区间的客流需求、区间和折返站能力限制，且运营商和乘客出行总费用最低；运营商费用包括车辆购置费用和车辆运营费用两部分，乘客出行费用包括等待时间费用、在途时间费用和换乘惩罚费用。
9、作为本发明的进一步改进，定义集合：n为研究的城市轨道交通线路的物理车站集合，索引为i,k；n1为折返站集合；e为物理区间集合，索引为e；o为列车运行方向集合，索引为o；v为服务网络中的虚拟车站集合，索引为j；a为服务网络中的弧集合，索引为a，a＝a1∪a2∪a3，a1为上车弧集合，a2为运行弧集合，a3为下车弧集合；和分别为服务网络中物理车站k的出发弧集和达到弧集；s为备选列车交路集合，索引为s；l为含列车交路和停站方案信息的备选服务集合，该集合通过枚举研究线路的可行列车交路和停站方案提前生成，l＝l1∪l2，l1为快车服务集合，l2为慢车服务集合；ls为交路s对应的备选服务集合，其中各服务具有多种备选停站方案；f为各服务的列车发车顺序集合，索引为f，|f|取为线路通过能力；w为客流od集合，索引为(i,k)；
10、定义参数：c0为单位时间内的车辆购置费用；c1为单位距离内的车辆运营费用；c2，c3和c4分别为单位乘客等待时间费用，在途时间费用和换乘惩罚费用；tl为服务l所属交路的全周转时间；dl为服务l所属交路的全周转距离；τli，0-1参数，当服务l经由车站i并停车时为1，否则为0；δle，0-1参数，当服务l经由区间e时为1，否则为0；0-1参数，当服务l在车站i往方向o折返时为1，否则为0；为从车站k去往车站i的客流量；为车站i在方向o上的上车客流量，；为区间e在方向o上的断面客流量；u为列车载客能力；γ为要求的列车富余能力；rmax为最大允许开行的交路数量；λmin为交路最小需要的列车开行对数；fmin为车站最小需要停车列车对数；fmax为线路最大允许开行列车对数；为折返站i在方向o上的折返能力；φa为运行弧a对应的服务；ta为列车在运行弧a上的运行时间；为车站k去往车站i的客流量(若k≠i)，或者到车站i的所有客流量的负数(若k＝i)；
11、定义变量：xfl，0-1变量，当服务l开行第f列列车时为1，否则为0；μl，0-1变量，当服务l被选择时为1，否则为0；非负连续变量，表示服务网络中到达车站i的客流通过弧a的人数；非负连续变量，表示服务网络中到达车站i的客流在车站k的等待时间；
12、在步骤1中，所述列车交路及停站设计问题构建的模型为0-1线性规划模型srd，具体如下：
13、(srd)min z1＝∑f∈f∑l∈lxfl·tl·c0+∑f∈f∑l∈lxfl·dl·c1 (1)
14、其约束如下：
15、
16、
17、
18、
19、
20、
21、
22、
23、
24、
25、目标函数(1)中，第一项为车辆购置费用，各服务的车辆购置费用为其开行频率、全周转时间、单位购置费用之积；第二项为车辆运营费用，各服务的车辆运营费用为其全周转距离与单位运营费用之积；约束(2)和(3)为客流需求约束，保证任意车站和区间的客流需求得到满足；约束(4)为开行交路数量的上限约束，开行的交路数量不能高于设定的最大值；约束(5)为各开行交路只能选择一种停站方案；约束(6)为交路的开行频率要求，各交路的开行频率不能低于指定的下限，同时不能超过可发出的列车数量；约束(7)保证挑选服务覆盖所有车站，且各车站的停车列车对数不小于指定下限、不高于线路能力；约束(8)保证挑选服务覆盖所有区间，且各区间的列车对数不超过线路能力；约束(9)保证开行的服务不超过各折返站在各运行方向的折返能力；约束(10)为有效不等式，要求只有当各服务的第f列列车开行后，才能开行第f+1列列车；约束(11)变量取值约束；
26、所述客流分配问题构建的模型pa具体如下：
27、
28、其约束如下：
29、
30、
31、
32、
33、目标函数(12)由三部分费用组成，第一项为等待时间费用，由各到站i的客流在各车站k的等待时间决定；第二项为在途时间费用，由各到站i的客流经运行弧a的人数与弧a的运行时间ta决定；第三项为换乘惩罚费用，由总换乘人数决定，该值等于所有上车弧上的乘客人数与所有乘客人数之差；等式(13)为流量守恒约束，保证了各支客流在服务网络中各个节点的流入等于流出；约束(14)为最优策略约束，表示到达站i的客流经由从站k始发的上车弧a的客流量不超过其在站k的等待时间和弧a对应服务φa的开行频率之积；约束(15)为服务能力约束，即经由运行弧a的客流量不能超过其对应服务的运输能力；约束(16)为变量取值约束。
34、作为本发明的进一步改进，所述步骤2具体如下：
35、首先确定解的表示，并生成初始解，然后对不可行解进行修复，基于适应度函数与邻域搜索优化获得结果，最后进行非有效解过滤。
36、作为本发明的进一步改进，确定解的表示具体如下：
37、采取θ行π列的0-1矩阵表示模型tsd中的备选服务集l，其中，行数θ表示指定的备选服务的数量，列数π表示研究线路的车站数量，即π＝|n|；0-1矩阵的每一行表示1条备选服务对应的交路的起讫点和停站方案，该行第一个和最后一个1元素分别表示服务的起点站和终点站，中间的元素取0和1分别表示服务在对应车站不停车和停车。
38、作为本发明的进一步改进，生成初始解具体如下：
39、枚举所有可行交路的备选服务集；对于研究线路的每条可行交路s∈s，令其途经中间站集合为ns，为每条交路s的每个中间站i∈ns，引入1个参数表示车站i的客流量占交路s覆盖车站总客流量的比重，即为生成每条交路s的备选服务集ls，首先，考虑到交路s途经车站i的客流量越大，值越大，交路s停靠车站i的概率越高，故利用交路s途经车站i的使用轮盘赌方法确定交路s是否在车站i停车，从而生成1个基本备选服务记交路s在服务中未停车的车站集合为ωs；其次，对集合ωs中的车站考虑所有可能的停站组合生成其他备选服务；从而，交路s包含的总备选服务数量为
40、按各交路备选服务数成比例生成初始解，根据每个解中指定的备选服务数量θ，按成比例原则依次从各交路s的备选服务集ls中随机挑选个服务，从而生成1个初始解。
41、作为本发明的进一步改进，采取以下规则对不可行解进行修复：
42、规则(1)、覆盖所有车站：在给定解中的备选服务集l中随机挑选某条途经该车站但不停车的服务，并将该服务在该站的停车状态由0逆转为1；
43、规则(2)、覆盖所有区间：在给定解中的备选服务集l中选择折返端点与未被覆盖区间距离最近的服务，并将该服务的折返端点延长至可覆盖该区间的线路端点站；
44、规则(3)、最大允许交路数量：为每条备选服务l∈l，引入1个参数ψl，表示其可覆盖且可服务的客流量占总客流量的比例，即其中，wl为可由服务l覆盖的od的集合；从l中选出前rmax-1条ψl值最大且属于不同交路的服务构成l′，检查基于l′是否可覆盖所有车站和区间；若否，则采用规则(1)和规则(2)进行修复，若修复不成功，则从l/l′中任意选择1条途径还未被覆盖车站和区间的、且所属交路与l′对应所有交路不同的服务，再采用规则(1)和规则(2)进行修复。
45、作为本发明的进一步改进，在适应度函数中，对于任意蜜蜂，首先基于其解表示中的备选服务集l构造服务网络；然后，依次求解列车交路与停站设计模型srd和客流分配模型pa，得到目标函数值z；接着，使用sigmoid函数计算解的适应度函数f(z)，即f(z)＝1/(1+e-z)。
46、作为本发明的进一步改进，所述领域搜索具体包括6种规则：规则(a)交换起始站，规则(b)交换终点站，规则(c)交换单个中间站，规则(d)交换中间站序列，规则(e)逆转单个中间站，规则(f)逆转中间站序列；在每次邻域搜索时，随机选取一种规则执行；
47、执行规则(a)或规则(b)时，从解中随机挑选两条服务，交换其起始或终点车站，在交换之前要保证一条服务的起始/终点车站能与另外一条线路的终点/起始车站组成可行交路；执行规则(c)时，从解中随机挑选两条服务，交换其共有区段的不包括端点站的中间车站；执行规则(d)时，从解中随机挑选两条服务，交换其共有区段的不包括端点站的中间车站序列；执行规则(e)或规则(f)时，从解中随机挑选一条服务，逆转其中间车站或者中间车站序列的状态(0或1)。
48、作为本发明的进一步改进，非有效解过滤具体如下：
49、设运营商费用z1的取值范围首先确定为列车交路及停站设计模型srd输入所有可行备选服务，求解模型srd至最优，将所获得的运营商费用作为同时，基于模型srd的最优解，求解客流分配模型pa至最优，所获得的乘客出行费用记为总费用记为
50、其次确定为客流分配模型pa输入唯一的1个全程大交路并站站停的服务，此服务可为乘客提供最小的等车时间费用和换乘费用；求解模型pa至最优，所获得的乘客出行费用记为考虑到列车开行方案设计是在运营商费用最小值的基础上，通过逐步增加运营商费用z1，降低乘客出行费用z2，进而搜索可能比zope更低的总费用z；同时，乘客出行费用最小值估计不会小于所以，将运营商费用最大值设置为
51、基于运营商费用z1的取值范围非有效解过滤规则对非有效解的判定方法为：对于任意给定解，求解其对应的列车交路及停站设计模型srd，判断获得的运营商费用z1是否在范围内；若不在，基于此解求解后续的客流分配模型pa不太可能找到比zope更小的总费用z，因此，判断该解无效，不再求解模型pa，为该解赋值1个非常大的目标函数值c。
52、本发明的有益效果是：
53、本发明提出了城市轨道交通线路开行方案优化方法，在对既有问题和研究分析的基础上，同时考虑多交路、快慢车的运营策略，以运营商费用和乘客出行费用最小为目标，满足运营能力和最优策略客流分配方法，构建了混合整数线性规划模型；设计了杂交人工蜂群算法，结合非有效解过滤程序，解决实际生产中的大规模问题，优化交路和停站设计，高效使用车辆，减少运能浪费，提高列车能力利用率；对切实算例的计算分析结果显示，基于杂交人工蜂群算法可在合理时间内获得满意开行方案，可用于辅助现场决策。
1.一种基于杂交人工蜂群算法的城轨列车开行方案设计方法，其特征在于，包括以下步骤：
2.根据权利要求1所述的基于杂交人工蜂群算法的城轨列车开行方案设计方法，其特征在于，在步骤1中，列车交路及停站设计问题以及客流分配问题具体为：
3.根据权利要求2所述的基于杂交人工蜂群算法的城轨列车开行方案设计方法，其特征在于，定义集合：n为研究的城市轨道交通线路的物理车站集合，索引为i,k；n1为折返站集合；e为物理区间集合，索引为e；o为列车运行方向集合，索引为o；v为服务网络中的虚拟车站集合，索引为j；a为服务网络中的弧集合，索引为a，a＝a1∪a2∪a3，a1为上车弧集合，a2为运行弧集合，a3为下车弧集合；和分别为服务网络中物理车站k的出发弧集和达到弧集；s为备选列车交路集合，索引为s；l为含列车交路和停站方案信息的备选服务集合，该集合通过枚举研究线路的可行列车交路和停站方案提前生成，l＝l1∪l2，l1为快车服务集合，l2为慢车服务集合；ls为交路s对应的备选服务集合，其中各服务具有多种备选停站方案；f为各服务的列车发车顺序集合，索引为f，|f|取为线路通过能力；w为客流od集合，索引为(i,k)；
4.根据权利要求3所述的基于杂交人工蜂群算法的城轨列车开行方案设计方法，其特征在于，所述步骤2具体如下：
5.根据权利要求4所述的基于杂交人工蜂群算法的城轨列车开行方案设计方法，其特征在于，确定解的表示具体如下：
6.根据权利要求5所述的基于杂交人工蜂群算法的城轨列车开行方案设计方法，其特征在于，生成初始解具体如下：
7.根据权利要求6所述的基于杂交人工蜂群算法的城轨列车开行方案设计方法，其特征在于，采取以下规则对不可行解进行修复：
8.根据权利要求7所述的基于杂交人工蜂群算法的城轨列车开行方案设计方法，其特征在于，在适应度函数中，对于任意蜜蜂，首先基于其解表示中的备选服务集l构造服务网络；然后，依次求解列车交路与停站设计模型srd和客流分配模型pa，得到目标函数值z；接着，使用sigmoid函数计算解的适应度函数f(z)，即f(z)＝1/(1+e-z)。
9.根据权利要求8所述的基于杂交人工蜂群算法的城轨列车开行方案设计方法，其特征在于，所述领域搜索具体包括6种规则：规则(a)交换起始站，规则(b)交换终点站，规则(c)交换单个中间站，规则(d)交换中间站序列，规则(e)逆转单个中间站，规则(f)逆转中间站序列；在每次邻域搜索时，随机选取一种规则执行；
10.根据权利要求9所述的基于杂交人工蜂群算法的城轨列车开行方案设计方法，其特征在于，非有效解过滤具体如下：
