技术摘要：
本发明公开了一种基于可变邻域下降混合算法的轮渡服务网络优化方法，包括先针对轮渡服务网络，构建FNDP‑SA的整数规划模型；基于给定的航段，采用第一启发式算法生成可行的轮渡时间表；然后采用第二启发式算法，根据轮渡时间表生成初始解；再设计可变邻域下降算法使用  全部
背景技术：
对游客和居住在离岛上的居民而言，轮渡是至关重要、有时甚至是唯一的用于穿 行于群岛间的交通工具。作为公共交通的重要组成部分，轮渡网络设计问题(FNDP)已被广 泛研究了数十年。 正如Karapetyan和Punnen(2015)所指出的那样，即使只有四艘轮渡和七个港口的 小规模问题，其最优化设计也被证明具有很大的挑战性。Lai和Lo(2004)研究了一个轮渡的 调度问题，并得出了最优的船队规模、渡轮路线和时间表。在An和Lo(2014)中，随机需求被 纳入渡轮服务设计中，并且开发了一种基于服务可靠性且具有用户均衡流的建模方式，其 中考虑了两种类型的服务(即常规服务和临时服务)。最近，Bell等(2019)提出了一种熵最 大化方法来解决FNDP问题，其中采用了熵最大化和效用最大化之间的等价关系，从乘客的 角度寻找最佳渡轮路线。 以上学者都对海岛轮渡网络提出了相应的优化方法，但其都是适用于乘客和轮渡 信息规模较小的情况。随着海岛旅行业的不断发展，乘客和轮渡信息规模越来越大，这些算 法都不再适用或者表现出低况性能。因此，面对海岛运输问题中出现的数据暴增的这一困 境，迫切需要优化当前的渡轮服务网络。
技术实现要素：
本发明的第一目的在于克服现有技术的缺点与不足，提供一种基于可变邻域下降 混合算法的轮渡服务网络优化方法，该方法可以为乘客提供更优化的渡轮服务方案，优化 渡轮服务网络，适用于乘客和轮渡信息规模较大的轮渡运输。 本发明的第二目的在于提供一种存储介质。 本发明的第三目的在于提供一种计算设备。 本发明的第一目的通过下述技术方案实现：一种基于可变邻域下降混合算法的轮 渡服务网络优化方法，步骤如下： S1、针对轮渡服务网络，构建FNDP-SA的整数规划模型； S2、对于步骤S1构建的FNDP-SA的整数规划模型，先基于给定的航段，采用第一启 发式算法生成可行的轮渡时间表；然后采用第二启发式算法，根据轮渡时间表生成初始解， 初始解即是为乘客提供渡轮服务的初始解决方案； S3、设计可变邻域下降算法使用的一系列邻域； S4、为避免搜索陷入局部最优状态，基于禁忌搜索TS设计接收准则； S5、采用基于可变邻域下降算法迭代地对初始解进行改善：在每一次迭代中，基于 接收准则，搜索邻域内是否有更优的解决方案，直至搜索过程终止，以此完成对初始解决方 6 CN 111581580 A 说　明　书 2/14 页 案的优化。 优选的，在步骤S1中，通过合并泊位限制和容量分配策略，得出FNDP-SA的集合划 分公式，即整数规划模型： subject  to: 其中，f为轮渡，F为轮渡集合；s为轮渡时间表，S为基于候选航段生成的所有轮渡 时间表的集合； 为决策变量，如果将时间表s分配给渡轮f，则 等于1，否则， 等于0； 为轮船f执行的时刻表s的运营成本； Cf为轮渡f的容量；d为乘客的旅行需求，对于每个d，其出发和目的地港口以及所 需的出发时间都是已知的，D为旅行需求集合；r为航段，R为候选航段， Rs为时间表 s中的候选航段；md为有需求d的乘客人数； 是指航段r中可用于满足需求d的最大比率； τ为时间周期，T为时间周期集合；k为港口，P为港口集合；Bk为港口k的泊位数量； 等于1或者等于0， 表示在τ时期内，时间表s占用了港口k的泊位； 表示在τ 时期内，时间表s没有占用港口k的泊位； 表达式(1)为目标函数，表示最小化所有已执行轮渡时间表的总运营成本；表达式 (2)～(4)为约束条件，表达式(2)确保在时间范围内最多可以将一个渡轮分配给一个时间 表；表达式(3)要求在容量分配策略下必须满足所有要求；表达式(4)确保在任何时间周期 内每个港口上的占用泊位数量都不会超过可用泊位数量；决策变量 都是二进制的，如表 达式(5)中所定义。 优选的，在步骤S2中，基于给定的航段，采用第一启发式算法生成可行的轮渡时间 表，过程如下： S211、设可行的轮渡时间表的集合 可供选择的随机航段集合R*＝R；令MAX 表示未能将航段扩展到给定时间表的连续迭代的最大次数； S212、判断R*是否为 若是，则结束算法；若否，则从中选择一随机航段r，r∈R*， R*＝R*\{r}，每个航段仅用作一次初始航段； 7 CN 111581580 A 说　明　书 3/14 页 S213、判断该随机航段r的出发港口αr是否属于出发港口集合Π， P为港口 集合，若是，则创建一个新的轮渡时间表s＝{r}，一个轮渡时间表是由一系列航段前后衔接 而成的航段序列，s＝{r}表示时间表中先选择一个航段r作为该航段序列中的第一个航段； 若否，则返回步骤S212； S214、设迭代次数count＝0；当新的轮渡时间表s的目标港口βs∈Π时，令S＝S∪ s； S215、令count＝count 1，若count≤MAX，则选择新的随机航段r'∈R，若count> MAX，则返回步骤S212； S216、判断新的随机航段r'的出发港口αr '是否等于βs，ts ls π是否小于或等于 tr '，ts为轮渡时间表s的出发时间，ls为轮渡时间表s的总服务时间，tr '为航段r'的出发时 间， 若αr'＝βs且ts ls π≤tr'，则令s＝s∪r'，count＝0；若αr'不等于βs或者ts ls π大 于tr'，则返回步骤S215； S217、输出最终的所有可行的轮渡时间表S。 优选的，在步骤S2中，采用第二启发式算法，根据轮渡时间表生成初始解，过程如 下： S221、令Δ表示初始解： 令可供选择的随机旅行需求集合D*＝D，D为旅行需 求集合； S222、判断D*是否等于 若是，则结束算法；若否，则从中随机选择一个旅行需求 d*，d*∈D*，D*＝D*\{d*}； S223、判断有需求d*的乘客人数 是否大于0，若否，则返回步骤S222；若是，则随 机选择一个轮渡时间表s＝{r1,r2,...,rn}∈S； S224、判断需求d*是否可以被随机选择的轮渡时间表s服务，即 是否大 于0，若否，则返回步骤S222；若是，则为需求d*随机选择一个轮渡f∈F； S225、选择新的随机旅行需求d'∈D，并判断d'是否属于D*，若是，则有需求d'的乘 客人数 表示一个航段r由轮渡f来执行时，可用 于满足需求d'的最大座位数量， 表示时间表s内所有航段由轮渡f来执行时， 可用于服务需求d'的最大座位总数；初始解Δ＝Δ∪{s,f}，并返回步骤S223；若否，则返回 步骤S222； S226、输出最终的所有初始解。 优选的，在步骤S3中，利用突变、交换和循环交换这三种运算符来开发一系列不同 的邻域结构 κ为邻域序号；突变运算符和交换运算符可反复使用； 邻域是指使用运算符对当前的解决方案进行变换而得到潜在解的集合；邻域结构 是指解决方案中的轮渡时间表和分配给时间表的轮渡；开发过程如下： 1)利用突变运算符从第一启发式算法生成的所有可行的轮渡时间表中随机选择 8 CN 111581580 A 说　明　书 4/14 页 一个轮渡时间表， 如果该时间表已包含在现有解决方案中，则将当前分配给该时间表的轮渡进行随 机变异，在船队中增加一条虚拟渡轮，当选择了虚拟渡轮并将其分配给时间表时，则该时间 表被视为已从现有解决方案中删除； 如果现有解决方案中没有这个随机选择的时间表，则为该时间表分配随机渡轮， 这等效于在以前的解决方案中添加新的轮渡时间表； 2)利用交换运算符从第一启发式算法生成的所有可行的轮渡时间表中随机选择 两个轮渡时间表，并交换分配给它们的轮渡， 如果在现有解决方案中同时使用了这两个时间表，则将简单地交换分配的渡轮； 如果当前仅使用这两个时间表中的一个时间表，则将这个被使用的时间表从当前 解决方案中删除，而其渡轮将分配给另一个时间表； 如果当前解决方案中未使用这两个时间表，则选择新的随机时间表对，直到当前 使用这两个时间表中的至少一个为止，然后按照上述过程分配渡轮； 3)利用循环交换运算符在一次迭代中干扰两个以上的轮渡时间表：仅选择当前使 用的时间表来执行循环交换，每次迭代选择一组m个时间表{s1,f1},{s2,f2},...,{sm,fm}， 然后从第一个时间表s1开始，将其分配到的渡轮与先前分配给第二个时间表s2的 轮渡进行重新分配，即f1分配给s2，f2分配给s1，然后从第二个时间表开始s2，将其分配到的 渡轮与先前分配给第三个时间表s3的轮渡进行重新分配，即f1分配给s3，f3分配给s2，以此类 推，最后，第m个时间表sm分配到f1，由此完成m个所选船期表的循环交换，并且所有所选择的 时间表均已更改。 优选的，在步骤S4中，基于禁忌搜索TS设计接收准则，具体如下： 1)定义解决方案x的目标值obj(x)的计算公式为： obj(x)＝E(x) ε1·U(x) ε2·V(x) ε3·G(x)； 其中，E(x)为总成本和；U(x)为违反了船队规模约束的成本；V(x)为违反了泊位限 制约束的成本；G(x)为违反了旅行需求约束的成本；ε1为违反了船队规模约束的惩罚系数； ε2为违反了泊位限制约束的惩罚系数；ε3为违反了旅行需求约束的惩罚系数； 2)对于各个违规成本： 由于每个轮渡最多可以分配给一个轮渡时间表，如果将轮渡同时分配给多个时间 表，则每次使用都会给加上一个违规成本U(x)； 如果在任何时间周期内某个港口停泊的渡轮数量大于可用泊位的数量，则将被计 为违规成本V(x)； 由于要求解决方案中的轮渡时间表能够满足所有要求，如果轮渡时间表未完全满 足任何要求，则将添加一项违规成本G(x)； 3)对于惩罚系数： ε1、ε2和ε3在开始时均以1作为初始值，并根据搜索过程中接受的解决方案的可行 性进行动态调整： 如果在最近接受的解决方案中违反了船队规模，泊位限制或者旅行需求约束，则 对应的惩罚系数将乘以1.1，否则将被除以1.1。 优选的，步骤S5包括如下步骤： 9 CN 111581580 A 说　明　书 5/14 页 在每次迭代期间，按照邻域顺序从第一个邻域 开始搜索第一个邻域内的局 部最优，将x的第一个邻域 内的局部最优表示为x'，并基于接收准则，判断x'是否优 于x，即判断局部最优是否有改善初始解： 如果局部最优有改善初始解，当前邻域中有更好的解决方案，则将x'代替x成为新 的初始解，每当在邻域中找到更好的解决方案时，重复此过程； 如果在当前邻域中没有找到更好的解决方案，则令κ＝κ 1，让搜索将切换到邻域 序列中的下一个邻域，继续搜索局部最优； 在上述过程中，每次找到新的解决方案时，令κ＝1，让搜索从序列中的第一个邻域 开始； 当最后一个邻域 无法提供更好的解决方案，或者达到了设置的计算时间 限制，则终止搜索过程。 本发明的第二目的通过下述技术方案实现：一种存储介质，存储有程序，所述程序 被处理器执行时，实现本发明第一目的所述的基于可变邻域下降混合算法的轮渡服务网络 优化方法。 本发明的第三目的通过下述技术方案实现：一种计算设备，包括处理器以及用于 存储处理器可执行程序的存储器，所述处理器执行存储器存储的程序时，实现本发明第一 目的所述的基于可变邻域下降混合算法的轮渡服务网络优化方法。 本发明相对于现有技术具有如下的优点及效果： (1)本发明基于可变邻域下降混合算法的轮渡服务网络优化方法，先给出了FNDP- SA的整数规划模型，并针对轮渡服务网络中存在大量可行的轮渡时间表，采用精确算法来 解决大型实例在计算上会非常棘手的这一问题，提出了一种混合算法，先开发了两个启发 式算法，一个是基于给定的服务弧(服务弧即航段)生成可行的渡轮时间表，另一个是构造 初始解决方案，然后开发了基于可变邻域下降(VND)算法来迭代地改善初始解，并且考虑到 研究问题的性质，还设计了一组邻域结构，使混合算法能够在一系列越来越大的邻域中搜 索高质量的解决方案。因此，本发明采用可变邻域下降混合算法，能够为乘客提供更优化的 渡轮服务方案，同时也能减少运输数据暴增，优化渡轮服务网络，因此更适用于乘客和轮渡 信息规模较大的轮渡运输。 (2)本发明方法根据违反船队规模、泊位限制和旅行需求约束这些行为的违规成 本和对应的惩罚系数设计了接收准则，在每一次寻找更优解的迭代中，基于接收准则搜索 邻域内是否有更优的解决方案，能够更方便地找出更优解，多次迭代能够最大程度上提供 更好的解决方案。 (3)本发明方法利用突变、交换和循环交换这三种运算符来开发一系列不同的邻 域结构，能够充分干扰现有解决方案，同时又要保留重要部分，实现对邻域的有效开发。 附图说明 图1是本发明基于可变邻域下降混合算法的轮渡服务网络优化方法的流程图。 图2是珠海群岛分布图。 10 CN 111581580 A 说　明　书 6/14 页