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

自适应内存算法分割交付车辆路径问题

拉斐尔 · E.Aleman· 鑫汇张·

雷蒙德 · 希尔

摘要

抽象拆分交付车辆路径问题 （可拆分） 放宽迫使独特货物交付至客户的路由限制，允许多个车辆以满足客户的需求。分批被用来降低总舰队的成本来满足这些客户的需求。我们提供详细的调查，可拆分文学的和基于一个叫做路线角度控制测量的新型概念可拆分为定义一种新的建设性算法。我们该建设性方法扩展到使用自适应内存的概念，迭代的方法，然后添加一个变邻域下降过程。这三种新方法与通过求解可用可拆分基准问题集确切和启发式方法进行比较。我们的方法发现媲美与现有的方法和我们寻找最近的 21 习题集基准 16 新的最佳解决方案。

关键字：自适应记忆· 车辆路径· 拆分交货· 路线角控制· 启发式· 变邻域下降

1 介绍

的车辆路径问题 (VRP) 或卡车调度，首先制订了丹和 Ramser (1959年) 是一个核心问题在交通运输，物流，和供应链管理。车辆路线问题涉及辆车以固定特征 （即，速度、 容量等） 驻扎在一个中心仓库和一套地理上分散的点 （即，城市、 仓库、 学校、 客户等） 与固定要求。车辆用于访问和充分供应这些点的需求。优化问题是确定哪些客户访问的每个车辆和车辆将按照哪条路线去服务那些分配客户，同时尽量减少，各车队的业务费用，如旅行距离、 气体消耗量和车辆折旧。路线为开始和结束油库、 每一位客户的需求完全由恰有一辆，和由任何路线的需求总量不能超过车辆容量。

在现实中，然而，可能有的宗客户需求超过车辆能力或节省总距离或车辆数目可以通过为客户提供服务与车辆不止一部。拆分交付车辆路径问题 （可拆分） 放松 VRP 限制，允许使用多个车辆以满足客户的需求点和潜在总交货成本降低分裂在车辆中的客户交付 (Dror 和特鲁多 1989年)。可拆分的计算复杂度仍然是 NP 难 (Dror 和特鲁多 1990年)。Archetti 等人 (2005年) 作为特殊情况的车辆有 k 单位能力，可拆分定义 k 可拆分 k isin; Z 。Archetti 等人 (2005年) 研究表明，2 可拆分是在当满足一些特定的条件，在距离，而与 k 问题的多项式时间可解 ge; 3 仍然是 np 难度的问题。Archetti 等人 (2005年) 也表明 2 可拆分可能沦为一个问题可能更小，其中每个客户都有单一需求。

在一个无向图 G 上定义可拆分= （V，E） 地方 V={0，1，...，n} 是组 1 个节点的图和 E= {（i，j） : i，j isin; V，我 lt; j} 是的连接节点的边的集合。节点 0 表示一个仓库在舰队 M = {1，...，m} 的车辆的相同容量 Q 驻防，而其余的节点集 N = {1，...，n} 表示客户。非负成本，通常距离的函数或旅行时间，c_ij是与每一条边 （i，j） 相关联。每个客户我 isin; N 有的 q_我单位的需求。优化问题是确定哪些客户服务的每个车辆和车辆将按照哪条路线去服务那些分配客户，同时尽量减少业务费用的舰队，这样当旅行距离，天然气消费和车辆折旧。

我们建议采用建设性的启发式方法和固定的数量的车辆由未分配的客户按顺序插入下建设解决方案构建初始解的求解方法。序列是按特定的顺序客户的列表。完整的解决方案时，客户的序列被修改基于构造解决方案的特点。一旦确定了一个新的序列的客户，再次执行建设性的启发式方法来找到另一个解决方案。又在此基础上，修改客户的序列，该过程一直重复，直到可以发现没有更好的解决方案。在这种迭代的建设性方法过程中发现的最佳解决方案是然后改进使用变邻域下降 (VND) 过程。据我们所知，这就是第一次变邻域搜索算法来解决可拆分。

2 文献综述

2.1 可拆分的好处

乍一看，人们会相信允许拆分交货的好处是小的当客户要求要么大大小车辆能力或接近车辆容量。在实验研究中，Dror 和特鲁多 (1989年) 表明，是否客户的需求是低的与车辆能力和三角不等式成立 (c_ij le; c_ik c_kj ，对于所有的 i、 j 和 k)，拆分需求好处是实际上很少。相反，当客户的需求是能力的更大，至少 10%的车辆，可拆分解决方案的成本是能力的比 VRP 解决方案的成本低很多。图 1 显示了一个简单的例子来说明允许拆分交货数量的车辆和解决方案成本的潜在好处。在此图中，有 12 名顾客与相同需求 q_我 = 60 对称地分布在半径为 r 的圆中心油库，在车队的容量 Q = 100 位于。最优的 VRP 解如图所示1(a).它采用 12 车辆平均利用率 60%，z 值 = 240r 距离单位。如果允许拆分交付，如图所示，可以提供所有客户的需求1(b) 用 90%的平均利用率与 z 解决方案价值仅 8 车 = 201.4r.

Archetti 等人 (2006b) 可拆分为提供最坏情况分析和表明可以通过允许拆分交货的交货成本节约最是 50%，这一定是紧 (即，存在一个例子中，价值最优车辆路径问题的解决方案双打可拆分的最优解的值）。然而，这种分析，不能洞察客户特征与储蓄达到允许拆分交货之间的关系。

图 1 可拆分的储蓄的插图: （a） VRP 解决方案和 (b) 可拆分解决方案

Archetti 等人 (2008年) 分布环境特有和深入研究的价值和好处的允许拆分交货 （最详细发现到目前为止）。他们研究的重点是确定拆分交付为不同客户的特点，特别是在地理方面的实际影响和客户需求分布。好处，是在: （1） 的路线，和因而车辆，数目减少所需充分供应所有客户的需求和交货费用 （2） 的减少。

Archetti 等人 (2008年) 使用了数学分析，证明可以通过允许拆分交货的路线数目最大减少 50%。此外，他们的分析证实了当平均客户的需求是 50%和 70%的车辆能力之间，需求差异相对较小，可以获得极大的削减。然而，虽然没有，似乎依赖交付成本减少对客户的地理分布，出现存在需求方差依赖。

2.2 现有可拆分算法

精确和启发式算法被用于解决可拆分。虽然精确算法解决保证问题最优解的情况下，他们可以是不切实际用于求解大的情况下，由于所需的计算费用。最大

可拆分解决问题最优解的实例包括 50 客户 (Belenguer 等人2000 年).

有可拆分文献中找到一些确切的方法。Dror 等人 (1994年) 提出了整数规划和描述一种基于有效不等式的新类为可拆分的分枝定界算法。Sierksma 和 Tijssen (1998年) 可拆分适用于建筑物直升机在北海人受雇在这些平台上的乘员组交换为支持离岸平台班车的时间表。他们提出一个覆盖集可拆分为和解决使用单纯形算法和包括一个背包问题和几个 TSPs.列生成技术及其弛豫

Lee 等人 (2006年) 提出了基于确定性动态规划模型和最短路径搜索算法拆分传感器 (mVRPSP) 的多车辆路由问题求解方法。他们基于 mVRPSP 最优解的一些性质，重新确定原始的动态程序找到等效有限行动与最优性无损失的状态空间模型。降阶的模型是与定向的网络，然后求解最短路径问题相关联。该算法用于解决小实例与 4、 5 和 7 的供应商和在所有情况下得到的最优解.

金等人 (2007年) 提出一种迭代的确切方法，被称为两阶段方法与有效不等式 (TSVI) 以找到最优解后有限数量的迭代可拆分实例与平均客户需求大于 10%的车辆能力。他们将问题划分为聚类子问题和为每辆车的旅行推销员问题。在第一阶段，聚类子问题以最佳方式分配客户需求的车辆不考虑距离成本。

通过商业优化规划求解找到穿越的每辆车的最小距离第二阶段，旅行推销员问题。这些距离作为削减添加到原始的聚类子问题。直到没有新的集群可以在第一阶段中找到重复的过程。

其他研究估计问题的界限。Belenguer 等人 (2000年) 计算到可拆分实例基于多面体研究问题和割平面算法的最优解的下限。切割平面算法入手，初始的下限，计算通过求解初值问题制定通过线性编程代码。有效的不平等或削减，是发达国家、 添加到配方，和用于确定算法所得到的解的可行性。任何侵犯的不平等添加到，初步拟定并重复这一过程来计算一个更好的界。如果没有不平等发现违反新解决方案中，切割平面算法将停止，并提供一个最终的下限。金等人 (2008年) 建议列一代能找到下限和迭代的方法来获得可拆分的上限。方法测试使用由 Belenguer 等人的 25 实例 12 (2000年) 包含大客户的需求，如算法并不能有效地解决小平均客户需求的问题。他们建议解决这些实例作为本文介绍车辆路径问题 (CVRPs)，而不 SDVRPs。列一代提高了一些边界的 Belenguer 等人 (2000年).

的启发式算法往往需要解决大可拆分实例。在文献中发现的各种方法包括本地、 禁忌，和分散搜索、 混合办法和模算法。Dror 和特鲁多 (1989年) 提出了局部搜索来解决路由问题与分裂的交货。他们是一种两阶段算法，首先构建可行的 VRP 解和从这如果分批提高初始的 VRP 解生成可行的可拆分解决方案。分批纳入解决方案通过使用2 拆分交换运算符，将邻域创建与所有可能的选择，从路径中删除需求点并将其插入到其组合的备用容量是大于或等于需求的另外两条路线。路线加法例程可能创建新路线尝试消除分裂交付，只要获得总路由成本降低。Frizzell 和 Giffin (1992年) 使用网格网络不可拆分的欧几里得距离。他们使用建设性的方法那簇相邻的客户，然后分配到群集车辆直到群集的未分配的需求小于车辆能力。对于每个群集，阻塞最近邻用于首次分配离车厂客户的需求。如果同一群集中的联合的要求超过车辆能力，阻塞机制产生距离储蓄作为要拆分的需求才是最接近到仓库。Bouzaiene Ayari 等人 (1993年) 建议适应的克拉克和赖特 (1964年) 算法来解决随机需求车辆路径问题和拆分交货。这项研究显然是第一次尝试解决随机车辆路径问题分批。

在第二次的纸，Frizzell 和 Giffin (1995年) 纳入的问题 (SDVRPTW) 的时间窗口。该算法是类似于 Frizzell 和 Giffin (1992年)，但现在客户按车厂和其时间窗的距离。最初的解决方案被更改通过将客户移动到备用路线或通过交换任何两个客户之间分配路线时保存在目标函数的结果。Mullaseril 等人 (1997年) 描述在亚利桑那州的牧场上遇到一个饲料的分布问题。他们研究调度车队繁多，大牲畜饲料分布的问题。这个问题的解决方案战略是适应 Dror 和特鲁多的算法 (1989年)。因为该解决方案必须考虑时间窗，候选名单被修剪到的那些尊重时间窗口约束的路由。为了减轻潜在候选人数目减少， k 拆分交换运算符使用 2 le; k le; M，其中 M 是候选人路线数目生成，通常小于 10。最后，一个路线加改进的方法，但能力和时间可行性进行检查。

由何及斯瓦尔巴禁忌搜索 (2004年) 使用称为重定位分割运算符运算符。算法通过检查客户预先定义的顺序并追加最近开始与建设的初始解非路由的客户对最新的路由客户。禁忌搜索过程中四个街区之间的最佳人选被选择在每次迭代。他们使用标准运算符 (例如，客户搬迁、 客户交流、 和 2 minus; 选择lowast;) 适应可拆分上下文可能消除分裂交付。他们还使用拆分运算符，它使用两条路线，以共享的交付和重新定位内两条路线必须获得总距离减少交付重定位。Archetti 等人 (2006a) 提出了禁忌搜索客户删除从一套线路服务它要么插入到一个新的路由或现有工艺路线具有备用容量。禁忌搜索使用随机的禁忌，从定义的客户数量和当前解决方案中的路由数间隔时间内选择。为了消除k 分裂周期后的禁忌搜索采用改进相。Chen 等人 (2007年) 发展结合混合的整数规划和启动与基于克拉克和赖特初始可拆分解的记录旅行算法的启发式算法 (1964年) 算法。在最初的解决方案中的每个路由，混合的整数规划认为端点和最接近的邻居每个终结点重新配置终结点的需求和最大化总储蓄。终结点重新分配在三个方面: (1) 不会更改;（2） 端点完全删除从其当前的 route(s) 和所有其需求搬到其他的 route(s);(3) 该终结点从其当前的 route(s) 部分中删除，其需求的一部分搬到其他 route(s)。启发式测试 49 问题 Archetti 等人 (2006a)，5 随机问题的 Belenguer 等人 (2000年) 与大客户的需求，和 21 新基准问题和显示要明显胜出算法的 Archetti 等人 (2006a).

涵盖可拆分其他研究包括工作由宋等人 (2002年) 谁采用拆分交货计划，找到报纸代理分配和路由车辆同时交付成本降至最低并降低交货的总延迟时间送报纸。使用了各种算法并获得了储蓄的配送费用的 15%和 40%的延迟时间。诺瓦克 (2005年) 检查取件和派送路由的拆分负载问题，并探讨如何降低成本通过消除约束，车上只有一个可以服务的客户。问题作为动态规划的数学模型和结果表明负荷，至少一半的车辆能力发生拆分负荷最大的利益。刘 (2005年) 提出了一种具有有效不等式的两阶段算法 (金等人2007 年) 和一个分支和价格的方法来解决问题。Wilck 和骑士 (2007年) 研究改良的目标函数，以考虑运营成本的荷载的影响，并可能降低他们。玉等人 (2006年) 考虑拆分交付库存路由问题，并采用拉格朗日松弛和线性规划方法求解。Belfiore 和吉崎康宏 (2006年) 实施一个散点图搜索来解决涉及其他方面的限制，包括异构车辆、 时间窗和可访问性约束应用于在巴西的零售市场。该算法是用于解决在日常基础上所产生的真实场景，并且允许减轻舰队相比，目前的做法，在公司的营运成本。Ambrosino 和 Sciomachen

全文共23048字，剩余内容已隐藏，支付完成后下载完整资料

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