英语原文共 8 页，剩余内容已隐藏，支付完成后下载完整资料

在多层机器人全自动停车场中的一组电梯的实时最佳调度

Jayanta K. Debnath and Gursel Serpen*

电气工程和计算机科学系，托莱多大学，托莱多，OH43606，美国

摘要

这项研究提出了一个基于模拟的可行性研究，用于开发一个有一组电梯的多层的全自动停车结构的实时调度算法。每个电梯被构想为在楼层之间运载一辆车（轿车，小卡车，SUV或小型货车）。使用排队理论的等待线模型，在假定的顾客到达率和平均服务率下，导出具有在4至20范围内的楼层数量的特定停车结构的电梯计数，并且在每个楼层上400个停车位。基于嵌套分区和遗传算法的调度算法并通过仿真研究进行评估。模拟环境模型拟在繁忙的城市商业多层停车场的早上繁忙时间的客户和电梯动力的平均到达时间。通过使用MATLAB软件模拟相关环境实现的电梯调度系统的性能评估。与此同时，监测平均客户等待和电梯服务时间的性能指标，以及最大客户等待时间。模拟结果表明，所提出的设计方便了可接受的客户等待和服务时间，以及良好的电梯利用率。

关键词

全自动机器人停车场; 电梯调度; 即时的; 最佳; 遗传算法; 排队理论; 嵌套分区

介绍

在全球人口高度密集的地铁城市普遍缺乏房地产空间，这其中有许多原因，其中停车场问题是最突出的。多层停车场是一个非常有前景的探索方向，可以解决对停车位的急切需求。为了在整个停车场结构中更加有效使用地空间还需要消除其中的行驶车道，使得行驶车道空间也可以用作停车场。这样一个完全自动化的机器式停车结构，进而可以成为一个事实上的选择去探索。然而在楼层之间利用电梯运输车辆这是一个需要解决工程挑战，才能使得这样的停车结构成为现实。

前人已经对住宅结构中的传统乘客电梯系统进行了广泛的研究，特别是用于调度算法。许多基于启发式的调度算法已经开发[11] - [14]。这些方法对于特定的交通模式执行良好，同时计算效率高。另一种方法是“分区”，其中每个电梯被分配多个分组在一起作为区域的楼层[15-17]。这种分区方法使得电梯系统能处理各种各样的交通模式，同时在交通繁忙中也是健壮有效的。基于上下文电梯调度是利用无处不在的计算机控制与传感器技术，基于当前和不久未来以预测的客运流量交通情景动态选择和调整调度算法[18,19]。利用遗传算法尝试优化调度其中的过程[20-24]。利用遗传算法尝试优化调度过程[20-24]。队列模型应用于电梯调度问题，动态规划用于推导最优策略[25] - [26]。在目的地输入系统中，乘客在进入电梯轿厢[10]之前可以通过键盘进入目的地。对于这些系统，乘客到达时间，起点和目的地在系统进行调度决定之前是已知的。对于目的地条目系统，在[27]中开发了精确的优化算法，而在[5,28]中开发了动态规划和所谓的混合嵌套分区和基于遗传算法的方法。

本文的研究报告考虑了电梯调度问题在一个多层的全自动机器式停车结构[4]。 这种结构中的电梯是目的地登入系统的一部分。 这种全自动多层停车结构的每个电梯被构想为在楼层之间运载一辆车（轿车，小卡车，SUV或小型货车）。 这种对电梯承载能力的限制使得最小化客户等待时间更具挑战性。 本文使用排队理论，线性规划和遗传算法的想法，首先制定最小电梯数量的边界，并在早晨高峰时段制定电梯的最佳时间表。

方法

2.1． 电梯调度作为优化问题

调度算法的问题域是多层停车结构。停车过程是完全自动化的。对于停车的车辆，客户驾驶车辆进入停车结构中的入口或底层，并将车辆留在电梯装载区。为了取回停放的车辆，顾客在地面或入口楼层进入多层停车结构，并请求车辆从卸货区被运送到车主处。对于停车，车辆被装载到机器式手推车上，并且使用电梯从入口楼层输送到高楼层，在那里车辆被机器式手推车再次移动到其指定的停车位置。每个电梯只能携带一个没有或装载有车辆的机器式手推车。为了取回，已经装载到机器式手推车上的被请求的车辆被带到在同一楼层上的电梯，并且由电梯运输到地面或入口楼层。接下来，机器式推车将车辆移动到卸货区，以供客户取走和驶离。由于空间的原因，在这里将只考虑在本文范围内的早上高峰时间的车辆停车。

考虑一个具有N_F楼层和N_E电梯的停车场。令N_V表示已经在等待存储的停车结构内的那些车辆的数量。这些车辆排队为先到先得：车辆按照到达时间的升序排序。对于每辆车辆i,N_V，到达时间，到达楼层和目的地楼层在客户进行停车或存储请求时被跟踪。两级整数规划公式适用于[6]中的电梯调度问题，其中每个电梯必须将多个乘客运送到其目的地楼层。在这种情况下，问题被简化，每个电梯只运载一辆车（乘客）。因此，只有一个分配考虑，即车对电梯分配。决策变量是车对电梯分配，定义为二进制变量的N_Vtimes;N_E矩阵，其中第（i，j）个元件等于1，如果第i个车辆被分配给第j个电梯和0，反之。为了保证决策变量是可行的，应当满足以下约束：每个车辆必须被分配给一个且仅一个电梯，即：

(1)

对于在每个调度迭代之前已经在电梯内的车辆，其中的值是固定的。 作业决定只对那些等待装载到电梯中的车辆进行。

目标是通过平均客户等待交货或提货的等待时间来衡量客户满意度。 用于停车的车辆的交付相对更快，而用于拾起停放的车辆的等待时间可能相当长，特别是在高峰时间。 对于已经到达停车结构底层以停放汽车的客户，在队列中的等待时间直到顾客将轿厢递送到电梯装载舱之一构成了其满意水平的基础。这个时间段由测量，其中是递送时间，是到达时间。对于在队列中拾取停放的车辆的客户，等待时间是到达时间和拾取时间之间的时间间隔。该时间周期由车辆从当前停泊位置到电梯装载区域的检索时间和电梯到地面或入口楼层的运输时间组成。这忽略了另外两个时间：在车辆当前停放的楼层处的电梯到达时间，其可能与车辆的检索时间重叠，并且因此可能为零，以及从电梯卸载并移动车辆的等待时间到一楼的皮卡舱。 在这项研究中，由于本文只考虑存储请求，目标函数是平均客户等待时间，以能够将客户的车辆送到电梯装载台的队列。目标函数由下式给出：

(2)

调度的总体目标是找到问题的解决方案，以最小化等式2中的J函数，遵循等式1中给出的约束。为了优化，本文使用基于嵌套分区和遗传算法的混合技术，如下所述。

混合嵌套分区和遗传算法的电梯调度

本文采用所谓的混合嵌套分割和遗传算法（HNPGA）方法来计算使方程2中的J函数最小化的解决方案，受方程1中的约束[5]。 嵌套分区（Nested Partitioning，NP）方法将可行的决策空间稳定地划分为子区域，同时尝试识别最有希望的子区域。 最佳解决方案被教导在最有希望的子区域中，其通过采样定位。 一旦确定了最有希望的次区域，NP就集中在该次区域上。 通过迭代，最有希望的子区域通过进一步分割和回溯而逐渐减少。NP方法的前景是计算具有概率1的最优解，同时是简单和健壮的[9]。对于NP方法的应用，可以使用长度为N_V的向量来表示车对电梯调度问题，其中该向量的第i个元素等于j（1le;jle;N_E），其中N_E（k）表示 在第k次调度迭代期间可用电梯的集合。 初始可行空间需要所有那些长度为N_V的矢量，其中任何j（特定可用电梯）值可以由矢量（表示第i辆车）的不超过一个第i个元素假定。

类似于其在[5]中的应用，遗传算法（GA）在NP方法的每次迭代中使用两次，一次用于选择最佳子区域，另一次用于比较最佳子区域与周围区域。 对于这两种情况，其用于优化一组车辆N_V的分配，以最小化等式2中定义的目标函数。染色体被定义为长度为N_V的向量，其中元素i（1le;ile;N_I）等于 如果第i个车辆被分配给第j个电梯，则元素j（1le;jle;N_E）。 使用两种类型的变异算子：（1）一个车辆的电梯分配的随机改变，以及（2）两个车辆的电梯分配的随机交换。 实现的GA采用标准单点交叉算子，其将具有良好分配段的两个分配结合用于不同的车辆子组以生成更好的分配。每个染色体的适应度被定义为每个等式2的相应分配的性能。GA的伪代码如下：

• 初始化随机生成的可行的车对电梯分配的总体。
• 通过交叉和突变扩展群体。
• 评估各个作业的适合度。
• 基于适合度值为下一代群体选择分配的子集。
• 重复上述步骤，直到预定时间段到期或找到可接受的质量分配。

M / M / S队列模型

本文采用M / M / S队列模型，这是本文设计的具有多个服务器（电梯）的单个队列的系统（在线等候的车辆等待由电梯运输用于停车）。 根据Kendall [7]，其描述了一种系统，其中到达形成单个队列并且由泊松过程控制; 有N_E服务器（电梯）和工作服务时间呈指数分布。

M / M / S队列操作映射到状态空间为集合{0,1,2,3，...}的随机过程，其中该值对应于系统中的客户的数量，包括当前在服务。到达根据泊松过程以的速率发生，并将过程从一个状态移动到下一个状态。服务时间具有指数分布，M / M / S队列中的平均服务速率为。所有N_E服务器（电梯）从队列的前面服务。如果少于N_E作业（车辆），则一些服务器将空闲。如果有多个N_S作业，作业将在缓冲区中排队。缓冲器是无限大小的（其类似于将等待的车辆的队列沿着城市街区周围的街道的侧面延伸到停车结构的外部），因此其可以包含的客户（车辆）的数量没有限制。 M / M / S队列模型可以描述为连续时间马尔可夫链，并且是一种生死死亡过程。令=/（times;N_E）表示服务器利用率，并要求以下为队列稳定（见参考文献[8]）。

（3）

2.4． 电梯动力学模型

本文假设电梯将在恒定加速度a_E下从零初始速度开始达到V_E的最大速度，在电梯行进距离之后。 类似地，电梯需要行进相同的距离以从最大速度开始并且以-a_E的恒定减速度降至零速度进行完全停止。 根据起始楼层和目的地楼层之间的行驶距离，电梯行驶可能有两种可能的情况。

如果起始楼层和目的地楼层之间的距离大于，则电梯以恒定的加速度行驶，直到达到其设计允许的最大速度。 之后，电梯以恒定速度行进，并开始在离目的地的距离为的点处降低其速度。 因此，存在三种运动状态，并且电梯正在加速，以恒定速度行进并且如图1（a）所示减速。 另一方面，如果起始楼层和目的地楼层之间的距离小于，则电梯以恒定加速度中途行驶，之后（在达到其最大速度之前）以恒定减速度减速至完全停止在目的地楼层。有两种行驶模式作为加速，减速如图1（b）所示。

M / M / S排队模型和电梯动态调度

客户到达由泊松分布描述，平均到达率为lambda;，即每单位时间到达的平均客户数[2]。 这意味着连续的客户到达之间的时间遵循指数分布，平均为秒。 客户服务速率由泊松分布描述，平均服务速率为（客户数），即每单位时间可以服务的客户的平均数。 这意味着一个客户的服务时间遵循指数分布，平均值为。 该模型假设有N_E个相同的电梯，每个电梯的服务时间分布是指数的，平均服务时间是秒。

总服务速率必须大于到达速率，即等式3给出的。否则，等待线将最终无限大地增长。 通过这个界限，本文将针对给定的多层停车结构制定相对于楼层数量的最小所需数量的电梯。

多层停车场[4]的每层楼的停车位总数为N_Ctimes;N_R。 假设每个电梯占用两个空间，N_E电梯将在每个楼层上占用总共2N_E个空间。 由于每台电梯都有一个装载区，装载区的数量为N_E，这将需要额外的N_E空间。 然后，将每层的可用停车点的数量计算为（N_Ctimes;N_R）-2N_E-N_E = N_Ctimes;N_R-3N_E。 在这些（N_Ctimes;N_R-3N_E）停车点中，至少0.05（N_Ctimes;N_R-3N_E）停车位（为N_Ctimes;N_R-3N_E的5％）必须始终打开或为空[4]。 因此，每个停车场的总容量为（N_Ctimes;N_R-3N_E）-0.05（N_Ctimes;N_R-3N_E）= 0.95N_CN_R-2.85N_E停车点。 因此，就可用停车空间的总数而言，整个多层停车结构的容量（C）可以被定义为N_Ftimes;（0.95N_CN_R-2.85N_E）。

假设早晨高峰时段持续两个小时以填充整个停车结构，则车辆的平均到达率（）（每秒钟间隔到达的平均车辆数）是感兴趣的，其可以被计算为总数“每小时到达的车辆数”改为“每小时的秒数”。每小时到达的车辆总数等于“每小时每个停车位到达的平均车辆数”

（N_V，ave）与“总数的停车空间在停车场（C）”。平均到达率的公式由 =（N_V，avetimes;C）/ 3600给出。 电梯的平均服务率（每

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[140160]，资料为PDF文档或Word文档，PDF文档可免费转换为Word