英语原文共 13 页

带有分割线的非矩形物流园区设施布局问题

Yanru Chen , Yangsheng Jiang , M.I.M. Wahab , Xiaoqiang Long

摘要：

物流园区是一个精确划分的领域，有很大的空间来有效地组织、管理和运输货物。物流园区的设施布局问题涉及确定若干相互作用的功能区的适当物理组织。它与传统的设施布局问题不同，传统的设施布局问题是在铁路或高速公路等分隔线的背景下进行的，这些分隔线可能跨越一个物流园区，并将其划分为几个部分。物流园区通常也不是矩形的，而是不规则的形状。这些额外的特性使得物流园区的设施布局问题变得复杂，需要显式建模。针对物流园区设施布局问题，提出了两种数学规划模型，以获得具有竞争力的解决方案。第一个模型涉及到根据给定的分割线将功能区域分配到不同的部分。第二个模型使用切片结构技术来确定所有功能区域的最终布局。针对物流园区设施布局问题的np完备性，提出了一种改进的自适应遗传算法与分散搜索相结合的启发式方法。计算结果表明，所提出的模型和求解方法都是有效的。

关键字：

设施布局 物流园区 分线 切片结构 分散搜索 遗传算法

1 简介

现在，企业被迫降低物流成本，提高服务能力，从而减少卡车周转时间，最大限度地利用空间，并毫不拖延地提供服务。所有这些要求都给现有的独立仓库带来了巨大的压力。因此，为了满足这些物流需求，一个新的概念——物流园区应运而生。物流园区是园区内一个精确划分的领域，是高效地组织、管理和运输货物的一种手段。

需特别注意的是，物流园区的发展也带动了中国商业的繁荣。据中国物流与采购联合会(2012)的一项调查显示，2006年国内物流园区约207个，2012年增加到754个，这一显著的增长(264%)表明物流园区在中国物流和商业发展中发挥着重要作用。物流园区通常位于一个战略区域，可以很容易地从主要公路、铁路和机场进入。此外，物流园区通常有较大的空间容纳充足的卡车、大规模仓储、办公停车场，以及信息交易、配送处理、多式联运、支持服务等物流服务功能。物流园区的空间一般划分为几个互不重叠的区域，称为功能区(FAs)。一个功能区能够提供一种特定的物流服务。物流园区一般配置5 - 8个功能区，提供各类物流服务(Liang, Yang, amp; Wang, 2013; Tang, 2009)。

设施布局问题(FLP)是一种以实现最小化运营成本和最大化系统效率为目标的已知规模的管理安排。FLP存在于各种环境中，例如，在车间中定位机器或在厂房中定位建筑物。人们普遍认为，总运营成本的20% - 50%是物料搬运成本，通过改进布局设计，至少可以将成本降低10%—30% (Tompkins, White, Bozer， amp; Tanchoco, 2010)。FLP一般具有以下约束条件:(1)所有部门必须位于给定的区域或设施内；(二)各部门之间不得相互重叠，有的部门必须固定在一定的地点，有的部门不得设在特定的区域；(3)布局必须满足部门尺寸的纵横比(高宽比或宽高比)约束，因为具有适当纵横比的部门在实际应用中更实用(Meller amp; Gau, 1996)。一个FLP的解决方案是指定相对位置的块布局以及各部门的规模。

物流园区内的FLP (FLP- lp)是将功能区定位到物流园区内合适的位置。合理安排物流园区的功能区对物流园区的效率和成本节约具有重要意义。功能区的布置取决于功能区的位置、功能区的邻接、功能区之间的距离、功能区的资源等因素。功能区的不恰当放置会导致大量时间和成本超支。因此，lp是一个重要的基础性战略问题。此外，随着物流园区的快速发展，物流园区的规划越来越受到学者和实践者的关注(Yang, Taudes, Deng, Chen， amp; Tian,2015)。

与FLPs不同，在实际应用中，物流园区通常具有不规则的形状，比如任意的多边形或曲线。这个特性使lp复杂化。例如，一些限制条件表示部门之间不能重叠，部门完全包含在设施内，这些限制条件由矩形部门的坐标和尺寸(宽度和长度)表示。然而，这些约束不适用于部门形状不规则的情况。同样，一些处理矩形块的求解技术可能也不适用，例如，当一个设施是矩形时，长宽比可以用来限制一个非常狭长的部门的发生。然而，当设备具有任意形状时，处理纵横比是一项挑战。此外，铁路或高速公路等分隔线有时会穿越物流园区，将其划分为若干部分，因此有必要采用一种新的策略，以确保产生的功能区不会被分隔线所分割。这些额外的特性使得fp - lp非常复杂，并且需要显式的建模技术。

FLP已经被证明是np完全问题(Konak, Kulturel-Konak, Norman ,amp; Smith,2006)。由于FLP- lp至少和FLP一样困难，所以FLP- lp也属于np完全问题的一类。因此，目前还没有一种计算效率高的方法来获得最优解。因此，开发高效的启发式算法来求解lp问题是十分必要的。

本文的结构如下。第二部分介绍了FLP和lp的最新研究进展。第3节描述了非矩形物流园区中有和没有分隔线的FLP。第4节讨论了FLP-LP的两种数学规划模型。第一个模型将功能区放入不同的部门，第二个模型确定最终的块布局。第5节讨论了启发式算法来求解所提出的模型。此外，第6节给出了计算实验，证明了所提出的模型和启发式算法的强度和潜力。最后，第七部分对全文进行了总结。

2 文献综述

FLP在过去几十年里受到了相当大的关注。Meller和Gau(1996)、Singh和Sharma(2006)、Drira、Pierreval和Hajri-Gabouj(2007)对设施布局设计进行了概述。根据这些调查，有关设施布局的文献可以分为三类。

第一类涉及处理一般FLP的算法。一些研究人员开发了寻找最优解的方法(例如，Meller, Chen， amp; Sherali, 2007)。然而，这些求解FLP的方法存在一个主要的局限性，即不能在合理的时间内得到大型问题的最优解。因此，大多数解决大型问题的方法都是基于启发式的，它承诺在相对较短的时间内找到一个好的解决方案。这些启发式包括模拟退火(如Bozer amp; Wang, 2012)、遗传算法(GA)(如Garcia-Hernandez, Pierreval, Salas-Morera，amp; Arauzo-Azofra, 2013)和禁忌搜索(TS)(如Kulturel-Konak, 2012)、蚁群优化(ACO)(如Kulturel-Konak amp; Konak, 2011;Wong, 2010)，人工免疫系统(如Haktanirlar Ulutas amp; kultuire - konak, 2012)，粒子群优化(Asl amp; Wong, 2015)，以及上述启发式的某些组合(如Ku, Hu, amp;Wang, 2011)。一些研究人员也用其他方法解决了一般的FLP问题。例如，Salas-Morera、Cubero-Atienza和Ayuso-Munoz(1996)提出了FLP的一些计算机辅助技术。Jankovits, Luo, Anjos和Vannelli(2011)描述了一个基于对流优化的两阶段框架，用于高效地为FLPs寻找具有竞争力的解决方案。第一阶段是确定各部门的相对位置，第二阶段是基于半定规划确定最终布局。Tarkesh, Atighehchian和Nookabadi(2009)采用了一种多智能体技术，其中智能体交互构成了设施布局设计。Altuntas、Selim和Dereli(2014)提出了一种基于demat的模糊求解方法，同时考虑了FLP的定性和定量因素。Garcia-Hernandez、Palomo-Romero、Salas-Morera、Arauzo-Azofra和Pierreval(2015)将专家知识引入FLP遗传算法。

第二类是关于一般FLP的扩展，它考虑来自实际应用程序(如动态FLP (DFLP))的附加问题。DFLP包括通过最小化物料处理和重新安排成本的总和，在多个时间段内为不同的部门寻找职位。Rosenblatt(1986)首先提出了一种解决这个问题的技术。然后为DFLP开发了许多解决方案技术(例如，Pourvaziri amp;Naderi, 2014;Ulutasamp;Islier, 2015)。另一种情况同时处理两个或多个目标的优化，即，多目标FLP (MOFLP)，包括定性和定量评估，以获得更有效的解决方案(Sahin, 2011)。解决MOFLP的方法有很多(Matai, 2015; Ripon, Glette, Khan, Hovin, amp; Torresen, 2013)。这一类别下的另一个扩展是多层设施布局，由于土地供应日益不足和昂贵而受到关注(Lee, Roh, amp; Jeong, 2005)。

第三类与问题的特殊结构实例有关。在这个类别中，广泛研究的是单行FLP (SRFLP)。SRFLP侧重于将给定数量的矩形部门按直线排列，以用来最小化所有成对部门之间的中心到中心距离的加权和。针对这一问题，发展了大量的精确和近似方法。精确的方法包括分支和边界(Simmons, 1969)和切割平面(Amaral, 2009)。一些启发式方法被证明是有效的，特别是在大型案例中，如TS(Samarghandi amp; Eshghi, 2010)，助理文书主任(Solimanpur, Vrat, amp; Shankar,2005)，散点搜索(SS) (Satheesh Kumar, Asokan, Kumanan,amp;Varma, 2008)和GA (Kothari amp;Ghosh, 2014)。

随着物流园区的快速发展，物流园区规划越来越受到业界和学术界的关注。Scaron;ulgan(2006)提出了物流园区的基本特征并提出了理论的物流园区发展。Zeng (2008)在定性分析各功能区与物流园区交通条件相互关系的基础上，提出了机场物流园区的布局。系统规划方法(SLP)(如Muther, 1961)是一种定量重新安排现有设施或布置新设施的实用而有组织的方法，被广泛应用于FLP-LP中。由于SLP是手工和主观地安排部门的，这是一项耗时的工作过程，特别是当问题的规模很大时。此外，不同的规划人员可能会得到不同的布局解决方案。这些解决方案需要重新调整为实际的解决方案。因此，将SLP与数学模型相结合。例如，FAs, Feng, Jing, and Yang (2012)， Sun, Ma, and Zhang (2015)， and Xu(2015)之间存在着综合关系和邻接关联度，他们建立了一个结合SLP的数学模型，并通过GA求解，使综合关系或土地利用最大化，同时物流成本最小化。同样的方法，Zhang, Jiang, Zhang, and Wei(2014)最大化了综合关系和邻接关系的产品协会的程度。这种方法的缺点之一是需要功能区之间关系的信息，而从一些物流园区很难获得这些信息。因此，在Ma, Mao, and Li(2008)中，采用模糊聚类理论和仿真代替SLP求解矩形FLP-LP。Ma等人(2008)提出的方法也可用于求解非规则物流园区。然而，为了使用仿真技术，需要大量的信息，如功能区的平均使用时间和物流设备的效率。通常很难获得这样的资料，特别是对新计划建造的一座大楼。

综上所述，虽然在过去的十年中，物流园区和物流规划受到了很大的关注，但是现有的模型并没有考虑物流园区的附加特征，即不规则的形状和分裂的线条。例如，现有的FLP-LP方法大多将物流园区的形状简化为矩形，而忽略了可能划分物流园区的铁路、公路等分隔线。因此，从FLP-LP得到的布局可能不是一个实际的解决方案。这促使作者开发了两种模型及其求解算法来求解lp问题。

3 问题描述

首先，给出了FLP的基本构成;其次，研究了非矩形物流园区内无分割线的物流规划问题;最后，给出了求解带有分割线的非矩形物流园区物流规划问题模型的概念。

3.1 FLP的一般框架

FLP最初由Armour和Buffa(196

资料编号：[5449]