英语原文共 11 页，剩余内容已隐藏，支付完成后下载完整资料
基于多蚁群优化算法的具有容量约束的选址与路径问题研究
摘要
一个物流系统的成功取决于决定仓库位置和车辆路径。为了使得系统总成本极小化，选址路径问题（LRP）同时为选址和路径提供决策。本文提出了一种多蚁群优化算法（MACO）以解决具有容量限制的仓库选址和路径问题（CLRP）。我们将具有容量限制的路径选址问题（CLRP）分解为设施选址问题（FLP）和多仓库车辆路径问题（MDVRP），其中后者被视为第一个问题的一个子问题。多蚁群优化算法（MACO）采用一种分层蚁群结构来优化不同的子问题：选址、客户分配和车辆路径问题，其中后两个为多仓库车辆路径问题（MDVRP）的决策。群体之间的合作是通过选址和客户分配之间的信息素更新这种交换信息方式来实现的。所提出的算法由四个不同的基准实例集合进行评估，并与文献中的其他算法做比较。与其他知名算法相比较而言，计算结果表明了多蚁群优化算法（MACO）能够获得许多新的最佳解决方案。
1．引言
由于配送成本对供应链总成本的重要贡献，物流系统的设计是当今竞争环境中的一个重要问题。这类问题一般都是在两个阶段中得到解决的：长期策略中的设施选址和车辆路径，以满足客户为经营决策的需求。这两个部分可以单独处理，但可能导致次优的解决方案(Salhi and Rand, 1989)。选址路径问题（LRP）将设施选址问题（FLP）整合，决定了仓库的位置和分配客户到所选的每个位置，以及车辆路径问题（VRP），从而组成选定仓库的车辆路线。在现实世界的应用可以在文献中找到，例如，账单的交付(Lin等人, 2002)，包裹的递送 (Wasner和Zapfel, 2004),和可移动网络的设计(Billionnet等人，2005). 在仓库和路径被约束的选址路径问题（LRP）叫做约束选址路径问题（CLRP），这是本文的重点。
CLRP可以用图表示，其中 。 是用户节点的集合，表示候选仓库地址的集合，每个用户 有一个需求。一个限制条件 和开放成本 与每个候选仓库位置 相关。相关联的每个，有一个表示节点和之间的运输距离和运输成本，存在一个由具有约束条件Q和成本C的同类车辆的一个集合K。每一个用户在每次只能刚好由一辆车服务，每个路径必须由同一个仓库出发和结束，并且总负载不能超过车辆的容量。分配到一个仓库的车辆的总负荷不能超过该仓库的容量，目标是找到每个仓库的最佳数量和位置，以及各个开放仓库的车辆路线，以减少固定设施成本、运输成本和车辆成本的总和。
CLRP很难解决，因为它包含两个NP难问题：设施选址问题和车辆路径问题(Garey和Johnson, 1979)在CLRP中，地址分配的决策将影响到车辆路线的总成本，并且车辆路线的结构将影响仓库和客户分配的位置。因此，如何处理这些决定之间的相互依存关系是一个重要的问题。在本文中，我们以基于蚁群优化算法的嵌套方法同时解决位置和路由问题，而不是分开单独解决。以设施选址为主要问题，把车辆路径作为一个子问题。也就是说，我们将它为设施选址和多车场车辆路径问题，后者的问题是嵌入到第一个。这一概念的层次也由Balakrishnan等人(1987)和Nagy 和 Salhi (1996)强调。所提出的多蚁群优化算法（MACO）是从文献及其计算结果四套基准评估CLRP与国家的最先进的算法比较。
本文的其余内容如下。2节提供文献中LRP的广泛审查。多蚁群优化算法解决CLRP描述在3节。在第4节中，四组基准问题的计算结果的报告。每台not;标志集我们与最好的算法。最后，在第5节进行了总结。
2．文献综述
LRP已经研究了几十年，有几个LRP调查文献中(Laporte, 1988; Min et al., 1998; Nagy and Salhi, 2007)。Laporte (1988)回顾了早期研究的位置路由问题，并总结了不同类型的配方，解决方案的算法和计算结果发表之前发表的研究1988。Min等人(1998) 综合了过去路径选址文献的演变并在结合更现实的方面，算法的设计和模型的复杂性，探索了有前景的研究机会。最近，Nagy 和Salhi (2007)调查的国家的最先进的定位路线问题。他们提出了一个分类方案，并研究了一些问题的变种。他们还研究了精确和启发式算法，并为今后的研究并提出了一些建议。
对LRP早期的研究工作将有约束条件的路线和约束条件的仓库分开考虑，而不是一起考虑(Laporte等人, 1988; Chien, 1993; Srivastava, 1993; Tuzun和Burke, 1999)，近年来，大量的研究一直致力于以约束的仓库和路线(Wu等人, 2002; Prins等人, 2006a, 2006b; Bouhaf等人, 2006;等人, 2007; Barreto等人, 2007; Duhamel等人, 2010; Yu等人, 2010)。我们的研究还同时考虑了仓库和路线的约束条件。一些精确的方法一直致力于解决LRP，但最优解仅限于中型或基本无约束限制的例子。Laporte和Norbert (1981)针对一个单一的开放仓库的LRP设计了一个分支定界算法，并且最高可以解决50个用户的问题。Laporte等人 (1986) 对一个车辆容量约束的LRP的解决方案是通过一个分支切割法，子回路消除约束和限制约束保证每个路径链的开始和结束在同一设施。Laporte等人 (1988)提出了一个不对称的成本解决LRP,其中车辆约束由最大路径长度代替。他们详细阐述了一个分支定界算法，它能够解决多达40个用户的实例，但仓库的数量是小的（2或3）并且每个开放仓库的路径数量被限制到2。Akca等人（2009）提出了一套基于LRP规划的集合分解并且提出了一个列生成方法以解决多达40个用户的实例。Belenguer等人（2011）提出了基于由有效不等式加强的0-1线性模型的分支和切割算法来解决CLRP。他们解决了50个客户和五个仓库的最优性的实例。Baldacci等人（2011）提出了基于集合划分等问题制定的CLRP分支切割和价格算法。下界的产生基于动态规划和双上升的方法，是通过一种算法将LRP分解为一个MDVRP的有界集。他们的模型提供的边界是非常紧张的，能够解决多达199个客户和14个设施的实例。
由于LRP问题是NP难问题，大多研究者采用启发式算法求解LRP。Nagy and Salhi (2007)将启发式算法分类为四种不同的类型：顺序、聚类、迭代和分层。顺序的方法基于按顺序选定的仓库来最小化设施到用户的距离和路径的问题。基于聚类的方法（Srivastava，1993；Barreto等人，2007）将用户群划分为聚类，然后针对每一个聚类指定一个仓库，这样VRP就是求解每个聚类。迭代(Hansen等人, 1994; Wu等人, 2002; Prins等人, 2007; Duhame等人, 2010)将LRP分解为两个子问题，那么，子问题是通过从一个问题的其他反馈信息的迭代求解。分层方法(Nagy and Salhi, 1996; Albareda-Sambola 等人, 2005)将路径问题看作是主要问题，将VRP看作是子问题。Nagy and Salhi (2007)认为分层方法可以提供更好的解决方案。基于他们的观察，本文提出的多蚁群算法是一个分层的方法。
文献中提出了许多混合两种不同方法的启发式算法，Tuzun和Burke (1999)提出了一个两阶段禁忌搜索（TS）的方法。一个阶段寻求一个良好的设施配置，而另一个得到一个良6好的路径配置。Wu等人(2002) 提出了一种混合的方法和模拟退火（SA）分解方法来解决多个车辆类型和数量有限的车辆的多仓库位置的路径选址问题。Lin等人(2002)提出了一种基于门槛接受（TA）启发式方法和SA协助制作香港账单寄送的设施选址决策，车辆调度和负载决策。
Albareda-Sambola等人(2005)提出了另外一个两阶段TS启发式算法来解决车辆没有强制约束的LRP，Wang等人（2005）提出了一个两阶段混合启发式算法，其中将LRP分解为选址问题和车辆路径问题。在选址阶段，应用TS来获得设施选址的布置。对于每个选定的设施选址，车辆路径问题由蚁群算法（ACO）在路径阶段解决。Bouhafs（2006）提出了一种混合算法，其结合了SA和蚁群系统（ACS）来解决CLRP。一个良好的设施配置最先由SA构造，再由ACS应用到建设基于设施配置的路径问题。这两个ACO相关的启发式算法构造路径问题并将信息反馈到设施选择阶段。
Prins和他的同事们对LRP实施了不同的启发式方法。Prins等人（2006）结合了贪婪随机自适应搜索程序（GRASP）和路径重连来对约束路径选址问题开发一种二阶段算法。在第一个阶段，GRASP和一个学习过程实现了仓库选择。第二个阶段是使用路径重连生成新的解决方案。后来Prins等人（2006）提出了一种与人口管理结合的文化基因算法（MA|PM）来解决相同的问题。Prins等人（2007）提出了一个合作的方法，结合拉格朗日松弛和粒子化禁忌搜索（GTS）来解决CLRP。一个选址子问题中的算法交替由拉格朗日松弛法解决，GTS解决一个多点仓库的VRP。Duhamel等人（2010）提出了一种结合进化的位置搜索的GRASP（GRASP x ELS）来解决CLRP。
Barreto等人（2007）在一个时间序列启发式算法中整合了几种层次的和非层次的聚类技术。Marinakis和Marinaki（2008）提出了一种混合粒子群最优化算法（HybPSO），其结合了粒子群最优化算法（PSO），多阶段邻域搜索-贪婪随机自适应搜索程序（MPNS-GRASP），扩大邻域搜索（ENS）和路径重连这几类技术来解决LRP。最近，Yu等人（2010）提出了一种模拟退火算法来解决LRP。由文献的基准实例来看，平均而言，Yu等人（2010）和Duhamel（2010）等人的方法是最有效率的算法。
在文献中，LRP一般被认为是一个确定性的情况。少数的研究已经提出了随机性版本的LRP，Berman等人（1995）在随机性LRP方面提供了不错的调查。
3．CLRP的多蚁群最优化方法
本节将介绍那些用来解决CLRP的算法。所提到的多蚁群最优化方法（MACO）是基于蚁群系统（ACS）启发式上的。蚁群系统（AS）是由Dorigo等人（1996）最先提出的蚁群算法。随后，许多蚁群算法的变种已被广泛开发和应用到组合最优化问题的领域。可用的ACO算法的描述和相关文献的回顾都可以在Dorigo 和Stutzle（2004）这里得到。
多蚁群的概念最先由Gambardella等人（1999）提出，用于解决有时间窗口的车辆路径问题（MACS-VRPTW）。两个蚁群被设计来先后解决两个不同目标函数的最优化问题：第一个蚁群用来使车辆的数量最小化，第二个蚁群使路程距离最短。我们的多蚁群算法采用一个对不同蚁群有不同转换规则的分层蚁群算法结构。上层结构面向选址子问题，下层结构面向MDVRP子问题。同时下层结构被进一步分解为用户分配和车辆路径的子问题。上下层结构的协调通过全局信息素的更新规则来实现。
3.1 基本结构
要解决CLRP，首先要确定哪些仓库是打开的，其次每个客户有且只有一个打开的仓库，并为客户确定传播途径，这个解决方案需要用到以下三个特别的蚁群。第一个蚁群是用来定点——确定地点，接着客户们将由第二个蚁群分配给每个所选设施位置——客户分配，然后每个既定选址的VRP将由第三个蚁群决定，这三种蚁群算法将不停重复知道满足条件为止。此外，三种不同的信息矩阵和信息素更新规则分别用于为每个蚁群记录信息素信息。
如图1所提出的多蚁群算法的伪代码，该算法包括三个内部循环。主循环（6到25行）会一直重复直到到达了CLRP的迭代数量，内循环（8到17行）重复至等于蚁群（b）的数目，第三个循环（11行）是用于暗中为线路优化蚁群。每只蚂蚁要为所选地点找到最佳路径，当获得迭代最好的蚂蚁时，局部搜索将有两种途径：嵌入和移动（18到19行）。最后，当所有蚂蚁都找到了解决方案，全局信息素将更新（24行）。
算法1：针对CLRP的多蚁群算法
- Procedure MACO()
- Begin
- Set_Parameters;
- Initialize_pheromone_matrix;/* Initialize the pheromone matrices, */
- :=;/* Set initial global-best cost() */
- While (termination criterion is not met)
- :=;/*iteration-best cost()*/
- for h:=1 to b do /* Construct LRP solutions */
- Location_selection();
- Customer_Assignment();/* based on the selected location */
- VRP();/* based on the customer assignment */
-
Local_Pher
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[147571]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
