超市班车线路设计两阶段模型

曹 奕

（上海建瓴工程咨询有限公司，上海 200032）

0 前言

超市班车系统严格意义上不能算作城市公交系统的一部分，但也能发挥一定的公交补充作用。国外由于居民的居住地区分散，且私车保有量高，并无该类公交业态，因此海外相关研究和文献几乎为零，国内也鲜有针对此类线路设计的专门方法研究。由于超市班车系统其自身的特性，因此该系统的服务水平对其的吸引力的大小起很大作用，也决定了班车线路是否能发挥最大效用。该文结合成熟的最短路径计算方法和实际算例，提出了两阶段的班车线路设计和优化方法。

1 超市班车交通线路的设计优化

1.1 研究意义

超市班车公交系统处于公共交通最低层，严格意义上还不能算作城市公交系统的一部分，但它却可以对公交系统产生一定的影响。它起连接主要商业区，尤其是大型超市和周边居民集散点的作用。但是国外由于巨大的私车保有量以及相对比较分散的居住区分布，并没有这样的社会现象，因此国外相关研究和文献几乎为零。国内关于该项目的研究也并不多，在超市班车运营中，由于运营者和乘客间的矛盾往往导致一些棘手的问题，这些问题会影响线路运营者的积极性，增加乘客的不满情绪，不利于提高超市班车系统的整体效率，但是由于超市班车系统其自身的特性，因此该系统的服务水平对班车系统的吸引力的大小起很大作用，也决定了班车线路是否能发挥最大效用。笔者结合现在已有的研究结论，并整合自身的研究，给出了针对该问题的理论与实际相结合的方法，为超市班车未来的发展提供依据，保证超市班车系统的顺利运行。

1.2 超市班车路线线型的分类

一般公交线路有2种线性形式，即直线型和环线型。2种线形的特点和适用性见表1。

表1 公交线路线形特地和适用性对照表

在该文中，综合考虑超市班车服务对象为一定区域范围内的小区居民，且以超市作为线路起讫点，因此超市班车更适合使用环形型线路（该文的线路设计都默认为环线线路）。

1.3 超市班车线路的设计步骤

超市班车线路的设计一般要经过以下3个步骤：1） 概念性线路设计。结合超市的运营实际情况和经营战略目标，摸排线路需要覆盖的范围和点位。一般可通过调查问卷来分析卖场顾客的主要分布，也可对相邻的竞争超市开设的线路进行调研（该文不对此进行深入探讨，后续算例中的中间点位为给定）。2） 第一阶段为线路初步设计。线路初步设计就是对概念性线路设计方案的具体化过程，具体包括对中间站点进行区域划分，一般根据扇形分区将相近点位划入同一个区域，对区域内中间站的先后顺序进行最优组合。3） 第二阶段为方案比选和优化。对线路初步设计中某些明显划分不合理的点（例如因该点而造成该线路无法一笔画、部分点位处于其他线路最优路径中等）进行区域调整，并优化线路长度。步骤二、步骤三是该文的研究重点。

1.4 超市班车线路优化问题的数学简化模型

超市班车线路优化实际上是一种路径选择问题。在中间站点一定的情况下，会有不同的线路组合、不同的线路数量以及不同的站点排序，如何在众多组合间选择一条适合的超市班车线路（在提高顾客对班车满意度的同时，使超市班车运营成本最小化）就是班车线路优化主要的研究问题。该问题将会以整个班车系统的线路长度作为指标，力求寻找相对物理距离比较短的环状线路。

班车线路设计是以超市为必经点的闭合最短环路问题，也就是运筹学中经典的旅行商问题，是由超市出发，途中刚好不重复地经过所有中间站点，最后又回到超市，形成一个闭合型环路的问题。在对该类问题的研究中，需要解决的是如何形成一个闭合的最优环路问题。

该类问题通常运用运筹学中的旅行商问题（Traveling Salesman Problem，TSP）求解。这个问题很复杂，如果个站点两两相连，那么就有（-1）!/2条线路需要考虑，这是一个至今还没有被完美解决的非线性规划问题。

因此在该文中提出了一种针对超市班车线路模型这样的小型系统路线设计的手算方法：1） 要对给定的站点进行区域划分，将其归入不同的线路中。2） 对同一条线路中的节点进行排序，求得较优的环形线路。3） 在不同的划分和计算方法中进行比较，求出系统路线的最优解。

2 超市班车两阶段模型及实际算例

该部分将会把线路设计分为2个阶段，分别为线路初步设计与方案调整比选。其原因是在阶段一进行线路初设的过程中，是利用启发式算法进行较优解的搜索，然而，由于启发式算法是一种以经验为基础的最短路径算法，并不是精确的数学方法，因此，需要在第二阶段中进行方案比选和线路调整。

两阶段模型的具体步骤如下：1）第一阶段为线路初步设计。包括区域初步划分、区域内部线路单点环路最优解计算。2）第二阶段为方案比选和优化。包括对区域内点位划分进行微调、区域内部线路单点环路优化设计以及细节部分中间点调整。

2.1 案例背景

该文选取现实生活中的一家具有代表性的大型超市来简述运用上述启发式算法进行手算线路设计的步骤。根据地图中超市周边的住宅小区的分布，已确定需途径的中间站点共39个。

2.2 第一阶段：结合实际算例的线路初步设计

第一阶段的任务是用1条或若干条合适的线路将给定的线路站点串联在一起，其中给定的站点一般是超市经调研需要覆盖的各小区的出入口或其他较大的客源产生地，线路的起点、终点设在超市。初步设计需要解决的问题是要覆盖已知站点、应开设多少线路、哪些站点属于同一条线路以及该线路的最优长度。

根据以超市为圆心的扇形对现有的39个中间站点进行区域划分，划分在同一区域的点位视为由一条班车线路进行覆盖。根据问卷调查显示（此处不进行展示），82%的购物者能够接受单程购物路程耗时为大约30 min，因此，对一般的线路来说，运行一周的时间必须保持在满足75%乘客乘坐在班车上的时间不超过30 min。根据该要求并假设班车行驶时速为20 km/h，暂时设定每条线路的站点数大约为10个。以超市为圆心，放射线条把区域分割为扇形，分割原则如下：1） 保证距离比较近的密集点被划分到同一个扇区。2）保证每个扇区的中间点个数大约为7～11个。根据上述原则对案例进行扇区划分，按顺时针划分的结果如图1所示，共分为区域1、区域2、区域3和区域4，分别对应线路1、线路2、线路3和线路4。

学者对两点间路径选择问题的研究主要集中在模型的构建和算法的求解上。一般采用运筹学中的最短路径问题来解决，选取传统的Dijkstra法对模型进行最后的求解。

该文在检索了大量相关资料的基础上，发现在现有的线路选择研究中，目标函数的“最优”标准单一，一般以考虑出行距离最短或出行时间最短为目标，算例中以2个站点间的距离作为目标，对目标函数求解最小值得到该线路的最优解，如公式（1）所示。

式中：X为0-1的变量；C为站点和站点之间公交车运行的平均距离，，=1，2，…。

当X=1时，表示站点在一条线路中紧随站点（，=1，2，…），所谓“紧随”是指站点和站点之间没有其他站点。在这里需要假定班车的运行方向，一般认为班车是朝超市站进发的；在其他情况下，X=0，保证对每条非终点的站点来说，有且只有1个站点紧随其后，因此约束条件∑ X=1（=1，2，3，…-1）。

C可以排成1个×的矩阵。其中，站点是超市站，即超市班车线路的起终点。

根据区域划分分为4条线路，对每条线路中的各中间站点进行标注，并进行测距，将任意2点之间的行驶距离进行列表：1） 线路一。对线路一来说，超市所在点位命名为#，其余区域内的中间站点如图1中标识字母所示（用圈（○）来表示），线路的点位分布如图1所示，每两点间的距离见表2。根据计算较优路线为---------#-；等价路线为 #----------#。电子地图上测距得路线一的最短长度为7.5 km，如果按假设中的超市班车以时速=20 km/h行驶，则行驶1圈的时间为22.5 min。2） 线路二 。字数受限图表省略，计算方法同线路一，仅表述结论，后同经计算，线路二的较优路线为 #-/--------#。在电子地图上测距得路线二的最优长度为14.1 km。如果按假设中的超市班车以时速=20 km/h行驶，则行驶1圈的时间为42.3 min。3） 线路三。经计算较优路线为----------/-#-。等价路线为 #----------/-#。由电子地图上测距得路线三的最优长度为9.7 km。如果按假设中的超市班车以时速V=20 km/h行驶，则行驶1圈的时间为29.1 min。4） 线路四。经计算较优路线为-----------# 和。等价路线为 #------------#。在电子地图上测距得路线四的最优长度为9.77 km。如果按假设中的超市班车以时速=20 km/h行驶，则行驶1圈的时间为29.31 min。

表2 任意线路站点间距离表

图1 线路1中间点位图

2.3 第二阶段：结合实际算例的方案比选和优化

第二阶段的任务是在第一阶段计算结果的基础上对奇点进行观察，对中间站的区域划分进行微调，并对各线路长度进行优化。通过方案对比，挑选最短路径和最优方案，并且讨论造成差异的原因，对实例进行分析，将其中原因一般化。

在为线路三定线的过程中，发现由于存在点/，导致线路三无法一笔画出，因此，线路为满足经过站点/而绕行了大量路程。另外发现点/恰好处于线路一的途径线路上，因此考虑将点/调整进入线路一中。如果线路一增加点/，线路一的长度不发生改变。

而线路三则需要进行重新定线计算长度，经计算线路三+的较优路线为----------#-。等价路线为 #-----------#。在电子地图上测距得线路三的最优长度为7.05 km，较原有线路三最优长度9.7 km缩短了1.375 km。如果按假设中的超市班车以时速=20 km/h行驶，则行驶1圈的时间较原设计最优线路三缩减了约8 min。优化前-后的总线路长度见表3、表4（将局部点/从线路三调整到线路一中各条线路长度）。

对表3和表4进行比较，发现由于存在/点位，导致线路三无法一笔画成，而该店恰好处于线路一的最优线路路径中，因此调整了该点之后，没有增加线路一的长度，但是却通过减少绕行而减少了线路三的长度，调整点的确有改善系统的线路长度。

表3 第一阶段最优路径设计结果

表4 第二阶段优化后最优路径计算结果

3 结语

两阶段班车线路设计模型可以在一定边界条件下得到相对的最优解，即得到班车系统的最短路线。

模型成立的假设是线路条数给定的前提下，通过位置接近的点位划入同区域（同线路），再对单一线路进行最短的线路求解。由于线性规划目标的单一性，这些本该作为目标函数的参数却作为约束条件限制可行解的取值。当班车系统很小时，这个缺陷并不能体现出来；随着班车系统规模的扩大，这个缺陷将被成倍地放大。因此这个模型只适用于比较简单的情况。由于现实条件下的复杂的情况，例如机动车限制形式、道路的单向通行等情况都会导致模型中的约束数量大增，使模型求解更加困难，而且也会弱化精确的数学模型求解的优势。

由于上述的理论算法需要通过计算机程序才能够实现，因此适用于模型比较简单但是点数较多的情况，而事实上，超市班车系统是一个相对比较小型和简单的系统，利用理论的最短路径方法进行计算复杂度太高，并且由于现实中的约束条件太复杂，例如单行道、机动车禁行等，在建立模型时用数学形式表达现实约束还存在困难。