[0037] 以下将结合附图对本发明提供的技术方案作进一步说明。
[0038] 对本发明中涉及的一些专业术语作如下说明：
[0039] 社团结构：
[0040] 近年来对众多复杂网络的研究发现它们存在一个共同的特征，称之为网络中的社团结构。它是指网络中的顶点可以分成若干个团，团内顶点间的联系比较稠密，团间顶点的联系比较稀疏。参见图1，所示为社团结构示意图。
[0041] 多目标优化：
[0042] 在线性规划和非线性规划中，如果所研究的问题只含有一个目标函数，则称之为单目标优化问题。在实际生活中往往需要同时考虑多个目标在某种意义下的最优问题；其中包含多个目标函数，各目标函数之间存在着冲突，无法实现所有目标函数都达到最优，这种问题被称为多目标优化问题。
[0043] 多目标优化问题可以描述成如下形式：
[0044] miny＝F(x)＝(f1(x),...,fm(x))T
[0045] gi≤0,i＝1,2,...,q
[0046] hj(x)＝0,j＝1,2,...,p
[0047] 其中， 为n维的决策矢量， 为m维的目标矢量。而F(x)为目标函数，其定义了m个由决策空间向目标空间的映射函数f1,...,fm。多目标函数中一般包含多个约束，gi(x)≤0(i＝1,2,...,q)定义了q个不等式约束；hi(x)＝0(j＝1,2,...,p)定义了p个等式约束。对于某个x∈X，如果x满足约束条件gi(x)≤0(i＝1,
2,...,q)和hi(x)＝0(j＝1,2,...,p)，则称x为可行解。多目标优化的存在很多可行解，这些可行解直接存在着支配关系。假设XA，XB是多目标优化问题的两个解，且存在fi(xA)≤fi(xB)，则称为xA支配xB，记作
[0048] 精英策略：
[0049] 精英策略就是遗传算法中保留父代中的优良个体直接进入子代，防止获得的最优解丢失。首先将产生的子代种群和父代种群合并，然后对合并后的新种群进行非劣排序处理，最后按照非支配顺序添加到原来规模的种群中作为新的父代。
[0050] 本发明首先将公共自行车服务网络抽象为复杂网络，网络中的节点代表各租赁点，而节点间的连线则代表租赁点之间的联系程度。若租赁点间有车辆租还关系的话则节点间存在连接线，否则，不存在连接线；同时，一定时间范围内租赁点间的租还频率作为租赁点之间的相似度。然后，在所抽象出来的复杂网络中使用Fast Unfolding社团发现算法，得到初步的区域划分结果；社团内部的租赁点联系比较紧密，而各社团间的租赁点联系相对松散。最后，在社团发现算法划分结果的基础上，利用多目标优化算法结合公共自行车区域调度工作量对上一步的划分结果进行调整，各社团中的租赁点所围成的空间区域即为一个调度区域。本发明是利用租赁点间的租借关系来实现调度区域划分的，所以可以使调度区域可以维持内部自行车的租还平衡，提高区域内调度效率，区域间的调度工作量相对平衡。
[0051] 参见图2，所示为本发明基于社团发现的公共自行车租赁点调度区域划分方法的流程图，包括如下步骤：
[0052] 步骤1：基于公共自行车历史租还数据将公共自行车服务网络抽象为复杂网络，并用相似度矩阵来表示；设N为所有公共自行车租赁站点的集合，n为租赁站点的个数，其中租赁点间的相似度计算公式为：
[0053]
[0054] 两个租赁点之间的相似度矩阵Rel为:
[0055]
[0056] 其中，Rij i,j∈N代表租赁点i和租赁点j的相似度；Qij代表从租赁点i租车并租赁点j还车的次数；Qji代表从租赁点j租车并在租赁点i还车的次数；M代表以天为单位的时间范围；
[0057] 步骤2：基于步骤1获取的复杂网络，利用社团发现算法将租赁点按照租还规律进行划分，并得到初步区域划分结果；
[0058] 在复杂网络分析中，可以用模块度来评价划分的好坏。如果将连接比较稠密的点划分在一个社区中，模块度的值会变大，而模块度越大代表划分效果越好。模块度指的是网络中社区内部总边数与网络总边数的比值，减去相同社团结构下随机网络的比值，其具体公式如下：
[0059]
[0060] 其中， 表示的是网络中的所有权重；Ai,j表示的是节点i和节点j之间的权重；ki＝∑jAi,j表示的是与顶点i连接的边的权重；ci表示的是顶点i被分配到的社团；δ(ci,cj)用于判断顶点i与顶点j是否被划分在同一个社团中。若是，则返回1；否则，返回0。
[0061] 本发明中，所使用的社团发现算法为Fast Unfolding社团发现算法，FastUnfolding算法的原理为基于模块度的贪心算法，通过划分使得模块度最大化。该算法分为两个阶段：优化模块度阶段和折叠网络阶段，这两个阶段不断的重复迭代直到达到终止条件。Fast Unfolding算法的在N个节点的网络中执行过程如下：
[0062] 1、优化模块度阶段：将抽象网络中每一个租赁点代表的节点都当作一个社团，即此时网络有n个社团。然后对每个节点i，我们考虑它的邻接节点j，尝试将节点从社团移除然后放入节点j的社团中，计算模块度增量ΔQ；如果ΔQ是正的，那么就接纳此次变动将节点i移入到节点j的社团中，否则就保持原来的分配方式。整个过程当网络的模块度Q无法再提升的时候停止。
[0063] 模块度增量ΔQ的计算公式如下：
[0064]
[0065] 其中，∑in是该社团内部的连接权重总和，∑tot是所有与该社团相连的边之权重总和。
[0066] 2、折叠网络阶段：基于优化模块度阶段中的划分结果，对同一个社团的站点进行折叠，折叠后形成一个新的网络。在这个新的网络中，社团间的连接权重为连接两个社团的节点之权重总和；如果社团内部的连接形成一个自环，其权重为该社团内部连接的总和。这两个阶段执行完一次的过程称作一次pass阶段，随着不断迭代进行pass阶段，整个划分的模块度将最大化，从而获得最优划分结果；执行该算法的一个pass阶段，即可获得初步区域划分结果记作R。
[0067] 步骤3：基于区域调度工作量不断调整社团发现算法的社团发现结果直至各区域间的调度工作量方差最小；其中，利用多目标优化算法优化各区域内调度距离的方差和各区域内租赁点数量的方差以此最终确定公共自行车租赁点调度划分区域。
[0068] 本发明所使用的多目标优化算法是NSGA2算法，该算法是传统遗传算法的变种。NSGA2是目前最流行的多目标遗传算法之一，它降低了非劣排序遗传算法的复杂性，具有运行速度快，解集的收敛性好的优点。在NSGA2算法中的染色体的长度为2，分别代表区域调度工作量Wi中预估调度距离的权重ρ1和区域租赁点数量的权重ρ2，一定数量的染色体即构成了种群。NSGA2首先对种群P进行遗传操作，得到种群Q；然后采用精英策略将种群合并成并结合非劣排序和拥挤距离排序形成新的种群。重复执行上述直到满足终止条件，详细过程如下：
[0069] 1、随机产生初始种群P0，然后对种群进行非劣排序，每个个体被赋予非支配序值；然后在初始种群执行选择、交叉和变异，得到新的种群Q0，令i＝0。
[0070] 2、将父代和子代的种群进行合并形成新的种群Ri＝Pi∪Qi，然后对种群Rt进行非劣排序，得到非劣层F1，F2,...。
[0071] 3、对种群Pi+1执行复制、交叉和变异算子，形成种群Qi+1。
[0072] 4、如果终止条件成立，则结束；否则，i＝i+1，转到2。
[0073] NSGA2主要过程图，如图3所示。本步骤中首先初始化一些算法的参数，例如种群数*量popsize，最大迭代次数MaxGen，历史最优解f及其工作量指标参数
[0074] 基于步骤2中的划分结果R，利用最大生成星算法取区域内一点到其他所有租赁点的租赁总和的最大值作为预估调度距离Di，以及统计区域内租赁点数量Ni。种群中的个体基因ρ1，ρ2作为预估调度距离Di和区域内租赁点数量Ni的权重系数；最后通过公式Wi＝ρ1·Di+ρ2·Ni计算出各区域的调度工作量，区域工作量的方差记作V。
[0075] 近一步的，对于每一个租赁点i，尝试将i放入到其他的社团中并计算此次调整工作量方差的增量ΔV，整个过程都记录最大值ΔVmax以及对应的社团k。如果ΔVmax小于0，则租赁点i不作调整；如果ΔVmax>0，则将节点i调整至社团k中。遍历所有的租赁点，直到所有*的租赁点都调整完成，结果记作R。
[0076] 定义区域调度距离方差函数f1、区域站点数量的方差函数f2作为2个目标函数，对整个种群的结果进行快速非支配排序，将当代种群中最优解的记作f′及其对应的调度工作* *量指标参数记作ρ1′，ρ2′。如果 的话，则令ρ1＝ρ1′，ρ2＝ρ2′。
[0077] 最后，判断程序迭代次数是否超过最大迭代次数MaxGen。如果超过，则输出最优的区域划分结果；否则，通过精英策略选择以及基因的交叉、变异过程产生新的种群并重复从步骤2继续执行。
[0078] 以上实施例的说明只是用于帮助理解本发明的方法及其核心思想。应当指出，对于本技术领域的普通技术人员来说，在不脱离本发明原理的前提下，还可以对本发明进行若干改进和修饰，这些改进和修饰也落入本发明权利要求的保护范围内。
[0079] 对所公开的实施例的上述说明，使本领域专业技术人员能够实现或使用本发明。对这些实施例的多种修改对本领域的专业技术人员来说将是显而易见的，本文中所定义的一般原理可以在不脱离本发明的精神或范围的情况下，在其它实施例中实现。因此，本发明将不会被限制于本文所示的这些实施例，而是要符合与本文所公开的原理和新颖特点相一致的最宽的范围。
