价格选择多配送中心车辆调度问题

1、带有价格的选择性多配送中心车辆调度问题摘要：耐用品行业的企业偶尔推出以旧换新或回购活动，通过客户诱发更换购买。由于这一结果，在这期间使用过的产品快速的在经销商处积累。我们研究这样的公司，其目的是收集其经销商核心的逆向物流问题。在核被检测到的地方建立了搜集中心，公司的目的是优化车辆离开搜集中心的路径，到达每一个经销商，然后回到同一个中心。我们假设经销商对于它们的核心不是免费的，而是有一个保留价格。因此，如果由公司宣布的收购价超过了经销商的保留价格，那么积累在经销商的内核才能收购回来。但是，公司没有义务来访问所有的经销商;车辆被分派到一个经销商只有当它是有利可图的才这样做。我们专注的问题成为经典的

2、多配送中心车辆调度问题（ MDVRP ），其中每访问一个经销商与毛利及收购付出的代价相关。为解决这个问题我们制定两个混合整数线性规划（ MILP ）模型，我们把它称为选择性MDVRP定价。由于该问题是NP难题，我们提出了一种禁忌搜索启发式方法来解决中型和大型的实例。与国家的最先进的商业求解器解决混合整数规划模型的比较，启发式的方法更好一些。关键词：逆向物流、有选择的多配送中心车辆路径、收集、定价、启发式搜索1. 引言环保意识的制造业，废物减量和产品回收已经作为在过去的二十年中环境可持续性的替代手段出现。这促使研究人员和从业者把重点放在其包括正向供应链和逆向供应链的闭环供应链中。逆向供应链管理包

3、括了收集，检验，分类被消费者使用过的产品并作适当的恢复。有效地处理这组活动的一个方面是解决网络设计问题，以确定要被打开的设施的数量和位置，并发现这些设施和需求节点之间的产品的流动。多数网络设计模型采用线性或非线性混合整数规划的方式，并采用商业求解器或启发式方法求解。在这种类型的模型中，位置决定只用于设施的收集，检查和再制造业的运作。也有文章专注于以协调的方式处理正向和反向的信道分配问题。因此，设施自己操作的产品，以满足使用的产品，消费者从收集到的需求和反向流量转发流量作出决定。最近，Akçal 等人（2009 年） 和Aras 等人（2010 年）对这两种类型的文件做了全面的阐述。所

4、涉及的产品回收公司的关键问题之一是使用的产品收购所述的指（2003）。这的确是产物回收的第一活动，并触发恢复系统的其它活动。可以通过使用回购运动和为产品持有人提供它们向金融奖励增加的数量和质量的回报。接受废物流中的所有最终用途产品不是大多数公司的可行战略，因为这些产品的高百分比将导致质量较差，并且因此将无法恢复。因此,采用积极的方法和实现产品收购战略,提供相应的回购价格是公司从事产品复苏的关键。有几篇论文，其中明确地纳入使用的产品采集。第一项关于在激励为基础的集合建模也考虑到了网络设计的操作问题的研究是Boyac等人做出的（2008年）。作者开发的连续选址模型用于收集网络通过引入一个下车的战略

5、。该产品的回报率取决于到位，网络的可访问性，以及对所提供的财政补贴的策略。返回的最终用户决定是一个实用程序基于的选择模型捕获的。一个分析框架，提出以确定每个设施，并提供给最终用户的最优财政奖励的收集区域的最佳尺寸，使收集的利润是根据落客和卡车收集策略最大化。Aras and Aksen (2008) 分析了为激励和距离相关的回报的一个无容量限制的收集中心选址问题（ CCLP ）。该产品持有人决定是否参与回购活动由前往最近的收集中心（ CC）和依赖于所用产品的质量状态下的财政奖励的距离影响。两种混合整数非线性规划模型，拟为CCLP的固定费用和p-中位。同一 CCLP 的 p-中位版本被认为是 A

6、ksen等人（2009）研究的，根据拾取集合政策在其中车辆偏离收集中心、访问客户区，和把收集使用产品带回来。其目的是确定收集中心的位置，金融激励水平以及负载组合车辆的数量。这两篇论文，作者利用基于禁忌搜索解决方案程序。最近Aksen等人（ 2009）提出了一个双层配方的框架，描述了政府（领导者），从事收集和回收业务公司之间（跟随者）的补贴协议。该文研究两种可供选择的政策。在扶持政策方面，政府用金钱奖励（补贴）的方式促使该公司实现一个目标收集率。在立法政策方面，另一方面，政府强制要求公司的部分收集目标利率。作为回报，公司保证阈值经济效益。在这两种情况下，政府的目标是尽量减少每收集到的项目应支付的

7、补贴，而该公司的目标是利润最大化。它们表明，在相同的盈利能力和收集的水平，在立法政策下，政府支付较低的补贴。在本文中，我们着重研究在收集网络中的车辆调度问题。一个收集和逆向物流的车辆路径问题的极好来源是 Beullens 等人研究的（2004 年）。他们详细描述了各种版本的经典车辆路径问题（ VRP ）的特性。我们认为所面临的涉及二手产品收购的公司出现的情况如下。该公司已经开设了多家合作中心与无限的存储容量。它采用回升的政策，收集使用过的产品，被称为内核，在经销商处积累作为以旧换新宣传活动的结果。在这些运动中，消费者用他们自己的旧产品购买新产品时会获得优惠的价格。这个折扣也被称为贸易中的回扣和

8、经销商通常通过对新客户提供以旧换新退税，应用价格歧视政策加快他们的购买决策（ Ray等人，2005 ）。由于诱导以旧换新回扣有通过再制造业务产生的收入或成本节约的潜力用于产品的逆向流动，该公司希望通过轴承全部收集相关的成本从经销商处收集它们，也就是说，运营成本车辆和运输核从经销商到社区中心。由该公司提供的收购价使得经销商愿意让旧产品回流。经销商有不同的保留价格，并且他们同意只有当企业的收购价超过了他们的保留价格才出售他们的核心。对核心较高的收购价格降低了单位收益，但在同一时间增加了交易商愿意出售的核心的意愿。需要注意的是由该公司提供的收购价对所有经销商是相同的，因为定价歧视对于经销商而言被认为

9、是一个不公正的态度。此外，交易商可以很容易地在彼此之间分享企业的定价信息。该集合是通过为每个车辆分配给CC的一个相同容量限制车辆组成的车队。关于可被分配给一个CC车辆的数目没有限制。车辆必须背离，来访多家经销商后回到同一CC。该公司的目标是使集合操作尽可能获利。，由于从芯收集得到的零件和部件的再制造，节约的生产成本是公司收入的一个来源。公司的成本是核心的收购和经营车辆产生的成本。公司不得不决定分配给每个顾客的车辆数和分配给经销商的车辆的任务，车辆的路线，以及采购每个核心所花费的价格。车辆路线不必包含所有的经销商。如果从一个经销商处收集核心不赚钱，公司不会往该供销商发送任何车辆直到当所提供的收购

10、价大于或等于他的保留价格时他准备卖掉他的核心。我们将此问题作为''选择性多配送中心的车辆路径问题定价“ ，并记为SMDVRPP 。最相似的问题，在研究中我们是通过超等人引入了团队定向问题（ TOP）（ 1996），多个旅游最大集合问题 （Butt and Cavalier, 1994年） 是引进异构车辆顶部的变体，和Gueguen （ 1999）提出的有时间窗的选择性的VRP（ SVRPTW ）提出的集成了额外的容量和时间窗约束。这将在下一节中提到，这两个问题都属于更广泛的带利润（ VRPP ）的车辆路径问题。然而，只存在一个仓库服务选定的客户。尽我们所知，VRPP的多配送中心

11、问题尚未在研究之内。事实上，古典MDVRP （不含利润）推广了VRP使用超过1仓库或中心节点。各配送中心经营着自己的车辆提供服务的一组客户。MDVRP的目标是为每个配送中心设计的车辆路线，使访问所有的客户的车队行驶的总距离最小。各配送中心的车辆不能共享，每一辆车必须回到各自的出发点。我们本文中的SMDVRPP涉及到一组当作配送中心，一组作为客户节点经销商的社区中心，以及固定经营成本的不限数量的车辆。有与每个客户拜访（拜访经销商在我们的情况下）相关的利润。因此，我们的论文的主要贡献是引进SMDVRPP的，可以被看作是一个多配送中心的VRPP问题。此外，定价也考虑在内，这样的收购价至少不亚于走访经

12、销商的预订价能够带回来经销商的旧产品。尽我们所知，以前定价问题不在VRPP的考虑范围内。对于这个问题，我们提出了两种混合整数非线性规划（MINLP ）的方法，这是线性化，以产生它们的混合整数线性规划（ MILP ）版本。如果从核心单位节约成本足够高，如果经销商的保留价格都等于零，这个问题显然降低到经典多车辆途程问题（ MDVRP ），它被证明是NP问题（ Lenstra和Rinnooy kan,1981）。这意味着SMDVRPP也是NP-hard问题。大量实例证明，通过求解MILP与商业求解器不能有效地解决SMDVRPP。因此，我们采用了基于禁忌搜索原理的启发式求解方法。本文的其余部分安排如下

13、。选择性车辆路径问题的简要文献回顾在第2节规定。问题定义和两个数学编程在第3节给出。所提出的启发式求解过程的详细说明第4节。第5节报告其结果和运算测试。最后，第6节提供了一些结论。2. 文献综述在本文中，我们专注于一个集合问题，叫SMDVRPP ，这是面对参与产品回收的公司提出的。一些收集中心（CCS ）已经已经打开，包括所使用的产品检验和分离，以确定他们的下一个目的地，如再制造工厂，回收中心，或处置场。该公司主要从事用容量限制车辆从经销商到收集中心的核心运输。除了额外的要求，即要为每个核心支付收购的费用， SMDVRPP属于它不需要访问所有客户（经销商在我们的问题）的MDVRP类。因此，我们

14、的文献综述，主要包括对VRP符合利润的研究，这是最适合我们的工作。关于参观所有客户的路由问题的论文很多，而与利润相关的路由问题的论文却很少。在后者中，客户送达和车辆路线被确定，以便优化给定目标函数。虽然来访的所有客户提高了收集到的总收入，访问某些客户（边际收益减去边际成本）的边际利润可能低于零取决于手头的路由规划。在这种情况下，总利润可以改善，如果这些客户被排除在外。Feillet等人（ 2005）阐述带利润的旅行商问题（TSPP)。TSPP就是没有必要访问所有客户的一般的旅行商问题（TSP ）。关联的每个客户那里是已知的先验利润。TSPP 可以作为离散求解双准则优化问题，其中的两个目标是最大

15、化利润和尽量降低旅游成本。另外，也可以以限定的目标的目标函数和其他作为约束之一。在一个版本中，这被称为在文献中的定向问题（OP），有选择性的TSP（ STSP ），或最大集合问题（MCP），其目的是所收集的利润的最大化，使得总行驶成本（距离）不超过上限。命名为奖品收集TSP （ PCTSP ）另一个版本是关于确定巡演的最低总行驶成本，其中收集损益奖金大于下限。存在TSPP的第三个版本叫赚钱之旅问题（ PTP） ，其目标是最大化的收集总利润和总行驶距离的成本之间的差额。Feillet等人（ 2005）提供现有TSPP文学的一个很好的调查。他们的调查列出了各种建模方法，精确启发式求解方法。TSPP

16、的多个车辆的扩展是VRPP。多车版的OP ，这里的车辆被假定为无容量限制，而且对每一个参观时间限制，就是所谓的团队定向问题（ TOP）。Chao等人对TOP问题做了较早的研究。作者提出了一个五步启发式类似于确定性退火来解决这个问题。Butt和Cavalier (1994)从高中招收足球运动员的多个旅游最大的收集问题（ MTMCP ）来定义TOP问题的。他们提出了一个贪婪的旅游建设启发式算法。Butt和Ryan (1999)在价格分支的基础上为MTMCP问题制定了一个确切的算法。Tang和Miller-Hooks (2005)用禁忌搜索启发式嵌入自适应存储过程解决了TOP问题。ARCHETTI等

17、人（ 2007）提出了一个广义的两个变种的禁忌搜索算法和变邻域搜索算法。Boussier等人（2007年）用新分支策略和几个加速技术制定了另一个价格分支的算法。Ke等人（ 2008）用蚁群优化（ ACO ）的方式阐述了TOP问题。ARCHETTI等在（2007）提出了两个可变算法，一个是广义的禁忌搜索算法和一个是变邻域搜索算法。Boussier等（2007年）制定的是另一个基于新分支的战略和加速技术的分支和价格算法。柯等人（2008）在top中阐述了蚁群优化（ACO）的方式。最近的两部作品之一是在top由ARCHETTI等人完成的，作者研究的TOP的容量版本和提出确切的和启发式的程序，他们还研

18、究了PTP的延伸，其中一队可用容量限制的车辆。其它工作是由于Vansteenwegen等（2009年）完成。作者提出的一种算法结合了一个引导本地搜索方法但不同于本地搜索的启发式和多样化的过程，这有助于开拓更广泛的解空间。3.模型公式在我们提出基于SMDVRPP的两个MILP模型之前 ，我们列出了描述问题的中所做的假设，在节点之间的行进距离d ij i和j是已知的，其中节点是CC和经销商的位置。核心的数量由经销商i所拥有，而且这个企业熟知它的预定价格。当统一收购价格W采用一个大于或等于pi的单元核心来提供给经销商时，那么他会拥有经销商销售的所有核心。每个所收集核心产生的收益R，代表了使用产品的剩

19、余价值，这种产品可以通过再制造或回收而获得。该公司可能还没有决定从经销商i甚至wpi中收集核心，也就是说，即使该经销商愿意给内核。是这种情况时，经销商获得的总收益并不能够赔偿拜访他的额外成本。用同类有着容量Q的车队来进行共同的收集，每单位的距离对操作车辆进行收费，有一个可变成本C2和一个固定的成本C1。每个经销商可以通过最多一辆车被访问，也就是说拆分收集是不允许的，此外，在车辆必须收集它访问经销商的所有核心。对于最后一个必要假设的条件就是 q P 最大值ai.。如果q < 最大值ai，这些有（AI> Q）核心数量的经销商不会访问，哪怕是有利可图。每辆车必须启动并在到其指定的CC完成

20、其运行。它不能在另一个CC卸载和重新调度。每个CC可以运行无限数量的车辆。该公司的目标是从收集的核心中获得的最大化利润总额中减去回购成本，经营成本和差旅费所组成的车辆的集合总成本。对于SMDVRPP我们建立第一个模型称为SMDVRPP-1，其利用米勒 - 塔克 - 泽林（MTZ）的子路消除约束（卡拉等人，2004），以及在这些约束中使用的ui变量紧界限,第二模型SMDVRPP-2是基于连续流动的变量和Gavish - 格雷夫斯单个商品流约束（Gavish与Graves，1978）。在这两种配方，IC表示一组CC位置，ID表示集合经销商位置，在¼ICID中，由于参数是常见的两种配方，我

21、们总结它们的定义表1中。3.1.SMDVRPP-1在此模型中的变量定义如下：请注意， Ui为只需要编写解除米勒 - 塔克 - 泽林（ MTZ ）子路消除制约。根据这些变量和参数提出如下数学规划问题：表1.在模型中使用的参数（1）（19） Subject to ; ;；目标函数 （1） 是被计算作为总收入减去总采购成本和营运车辆的成本生成的最大化的利润。约束 (2) 及 (3) 确保经销商可以被访问至少一次。约束 (4) 保证进入和离开一个经销商位置或收集中心车辆的数量（零个或一个）必须是相同的。约束 (5)可确保在两个收集中心间没有车辆约束（ 6 ）中指定的用于汽车的总容量必须足以运送收集芯。

22、约束（7）满足该经销商被分配到最多一个收集中心。如该交易商分配给收集中心约束条件（ 8 ）和（ 9 ）确保经销商必须由车辆被访问。约束（10）和（11）一起意味着，如果两个经销商由车辆连续访问的，那么这些经销商必须被分配到相同的收集中心。约束（12）确保所提供的购买价格为每个核心必须大于或等于所访问的商的最大的保留价格。回想一下，公司的政策是不使经销商之间的存在价格歧视。约束（13）是解除MTZ子路消除约束，这连同Ui变量的下界和上界一起使用。约束（ 14 ）为Ui确定了一个下界简单的说就是车辆从经销商i离开之后的负荷必须至少等于从经销商i加上访问经销商i之前从经销商j收集的数量之和。如果车辆

23、来自收集中心和经销商i之间，然后第二个约束在此消失。约束（15） - （17）都在规定Ui的上界。约束（ 15 ）表示，如果车辆行驶经销商从i到经销商j ，那么车辆的剩余容量（q-Ui）从经销商i离开后必须足以收集经销商j，即q-Uiaj。如果车辆在经销商i后到达收集中心，那么Ui就有上限约束，即Uiq。约束（ 16 ）保证，如果经销商i在收集中心之后被访问，那么，离开经销商i之后的载重量Ui不能超过ai。如果经销商i不是第一个被访问的经销商，那么可获得上界。约束（ 17 ）在性质上（ 15 ）相似，但它们纳入Desrochers 和Laporte (1991)提出的升降系数（q-maxjaj

24、-ai）。因为目标函数中的双线性YikW的问题，所以该公式是一个MINLP或特定的混合整数双线性模型。双线性既不凹陷，也不凸，因此涉及他们的问题时商业解算器不能保证全局最优。双线性YikW可以如下进行线性化。首先，我们观察到，Yik 0,1和W0 ， maxjD Pj。接下来，我们定义一个辅助变量Vik= YikW并引入以下几组约束：;用Vik来替换目标函数（1）中的YikW并添加了（20）（21）约束条件使得MILP与目标函数等效。；需要注意的是的Vik最小和最大可能值分别为零和maxjD Pj。Yik=0，意味着Vik= 0，因为Yik=VikW。这确保了约束条件（ 21 ），因为Yik=

25、 0 使这种约束的右侧W-maxjD Pj0 ，这意味着约束（ 21 ）是多余的。因此，由约束（20）和目标函数（22），可得Vik= 0。当Yik=1时，约束（21）变成VikW。由于优化的取值是最大化，Vik=W是一个最佳值。这是由Vik的定义获得的，即Vik= YikW当Yik=1。应用线性化过程是由Al-Khayyal和Falk （ 1983）证明的，用来为在给定的矩形区域提供下估计最紧密的凸的双线性函数。因此，该MILP问题可以通过国家的最先进的商业MILP求解器如CPLEX解决。3.2.SMDVRPP-2另一种MILP方法可以通过定义连续流变量FIJ那些以书面Gavish - 格雷

26、夫斯单一商品流动的限制（ Gavish与Graves ， 1978）用于解决我们的问题。这些流动变量代表由经销商i运到经销商j的量。保持其他变量和参数是相同的，新的SMDVRPP -2的线性化给出如下：；限制条件（2）（3）（4）（5）（6）（7）（8）（9）（10）（11）（12）（21）；约束条件（ 24）是对每个经销商iD 写入的流量平衡约束。约束（ 25 ）保证，如果车辆从经销商或收集中心i到另一个位置j处，从i到j的运输量Fij不能大于（q-aj）。换句话说，离开i处后的装载能力必须能够满足j处的装载能力。当j为收集中心时，对于jC由于aj=0,这些约束简化为Fijq。约束（26）简

27、单地说，i和j之间的车辆负载应至少等于从i中收集的核心数量。当i时收集中心时，就得到一个非负性约束（Fij0）。约束集（ 24 ）-（ 26 ）消除了子集就像在SMDVRPP- 1中增加MTZ约束一样。4. 解决方法由于SMDVRPP是和MDVRP一样困难的NP-hard问题，非常难以用商业混合整数线性规划求解器来获得合理的解决方案。因此，启发式算法的发展是有益的。在MDVRP的启发式算法中，禁忌搜索（TS）已经被（Renaud 等人，1996 ；Cordeau等人，1997）证明是非常有效的。通过这一事实的启发，基于TS原则我们也设计一个启发式程序。禁忌搜索算法是通过在一个解决方案到另一个解

28、决方案之间的迭代进行解空间的探索。当st+1不比st优化时禁忌机制到位，以防止程序在解之间循环。一个防止循环的简单的方法是回到以前遇到过解决方案，但这样做禁止的过程通常需要过多的记录。相反，过去的解决方案或移动过去的某些属性被认为是禁止的，这些解决方案或移动拥有这些属性不可能考虑到以后的k次迭代。这种机制通常把短期记忆的数目k称为禁忌的持续时间或禁忌列表的大小。其他功能，如多样化和集约化也往往被利用。多样化的目的是为了确保在搜索过程中解空间不会被限制在有限部分。它可以跟踪过去的解决方案和经常进行移动的惩罚。这通常被称为长期记忆。在最好的解决方案周围进行贪婪局部搜索。我们提出了一个富人区的TS

29、（ TS- RN）启发式的SMDVRPP模型。TS- RN是加上战略波动，也就是说，我们也承认这些解决方案，其中一个或多个旅行团违反车辆容量约束。我们称这些为容量不可行的解决方案。在这种解决方案的目标价值计算，我们乘的总的产能过剩（总结超出车辆的通行能力而进行的内核数量在所有不可行之旅）与动态变化的处罚，并添加所产生的不可行性成本总的旅行距离。在每次迭代中，在TS -RN算法探讨了一些当前解决方案的周边解决方案，包括那些不可行的，并选择其中最好的为最高目标，价值计算作为新的当前解。该算法的关键步骤如下：初始解生成方法邻里结构和相关禁忌条件新的当前解决方案的选择分配并更新惩罚值的战略性振荡的过程

30、终止条件4.1.产生一个初始解最初的解决方案是把所有经销商都放入单个旅游经销商序列中按其指数的排序位置形成的。也就是说，在这次巡演中，第一个经销商首先到来，第二个经销商第二个到来。这次巡演连接到具有最小索引的收集中心。请注意此最初的解决方案是几乎可以肯定是不可行的 ；因此，其客观的价值将为产能过剩承担各个惩罚成本。4.2.邻域结构及禁忌条件附近的结构或所谓的TS -RN的移动而影响迭代过程，被指定为当前解决方案的轨迹。在我们的执行中存在两种类型：路径的移动和经销商选择的移动。有7种具体的移动方式是1-0移动， 1-1交换， 2-2交换， 2 - 选件，链互换， 1 - 分裂，以及跨巡演交流。经

31、销商选择的动作是加1，加2，减1，减2。下面我们讲解以及一个可视化表示的路由移动，其中经销商和收集中心分别由圆形和方形表示。1-0移动：给定两个经销商，第一个是从当前位置移除，并在第二个之后（图1和2 ）被插入1-1交换：给定两个经销商，交换他们的位置（图3和4 ）2-2交换：给定两个经销商，第一个和它的后继者换用第二个（图5和图6 ） 。2 - 选择：由于在相同的巡演二级经销商，这两个圆弧与他们的继任连接它们被删除后，经销商连接，其继任人接，终于第一次经销商的继任者，第二经销商之间的链被逆转（图7）链交换：由于在不同的旅游二级经销商，从每个经销商各自的链上的行的最后，交易商互换（图8）。1

32、- 分裂：给定一个交易商在现有的巡演，从收集中心直至包括经销商保留链条，而巡演的其余部分作为一个新的巡演。新的路线可以启动在同一收集中心（图9），或者它可以被分配到另一个收集中心（图10）。1 - 跨线总是会增加线上的总数目。请注意，根据三角不等式，1 - 分裂不能降低总行进距离，如果新的游被分配到相同的收集中心作为现有游，它可能减轻由于产能过剩导致的不可行性。图1. 1-0移动图2.1-0不同旅行线上移动图3.1-1相同线上交换图4.1-1不同线上交换图5.2-2相同线上交换图 6.2-2不同线上交换图7.2-O相同线上选择图8.2-O不同线上链交换混合交换（ITE）：该邻域结构有三种情况案

33、例一.A链的经销商是从一个给定的线中提取并插入一个新的线上拥有相同的或其他的收集中心如图11 。像1-分裂，在ITE移动这种情况下，增加了线上的参与数量。案列二.A链的经销商在给定的线上从当前位置移动到属于相同或不同的收集中心做另一次游览。这种情况示于图12 。案例三.任意大小分属两个不同链上的经销商交换。如图13图9.1-相同收集中心分裂图10.1-不同收集中心分裂图11.ITE案例一图12.ITE案例二图13.ITE案例三添加- 1 ：对不包括在线上的经销商所有可能的插入位置进行检查，经销商插在最佳位置。最佳位置，要么是一个有希望使当前解决方案的目标价值最高增幅（利润总额） ，或者如果没有

34、这样的位置存在，那么它使其中一个下降的客观价值最少。此举实际上相当于旅行商问题的最廉价的插入规则。添加- 2 ：对不包括在线上的经销商所有可能的插入位置进行检查并给予经销商都插在继承对方的最佳位置上，它被定义为中的添加- 1移动的解释。此举相当于应用于对经销商最便宜的插入规则。删除1 ：线上的经销商从线上被删除，它的前和后继续连接。删除2 ：将线上的给定经销商和他的继任者是从线上删除，他的前身和继任者后面的继续连接。TS- RN算法利用禁忌的条件来执行解空间不同区域的探索。为此，每当解按一定的邻域结构更新时禁忌状态与该结构相关联。严禁覆盖禁忌条件，除非在最好的可行的目标函数值Zbest立即改善

35、得以实现。禁忌状态被解除的禁忌持续时间j的结束。在我们的算法中，我们使用禁忌持续时间在区间 7,24 独立问题规模的随机决定。与所有11个邻域结构相关的禁忌条件列于表2。表2.采用邻域结构相关的禁忌条件列表 虽然我们提出了大量的不同的移动，可能的情况是，并非所有的移动都能产生高品质的解决方案。只有其中的一些可以实现，特别是表2中的，如1-0移动， 1-1交换和2-2交换。出于这个原因，我们产生了一些举措组合，并在本文探讨测试情况下它们的表现。4.3.选择一个近似的方案作为下一步的初始方案在每次的TS-RN迭代时，当我们依靠使用的调度方案我们搜索当前方案的领域N ðSt Þ，

36、以设法找到下一个调度方案St+1时，我们充分地探索领域结构，除了Inter-tour Exchange。换言之，领域N ðSt Þ的候选子集N ðSt Þ被充分地探索，领域N ðSt Þ在五条路径调度中是等价的。由于计算的难度，对案例b、c中的国际商贸交易中的调度问题的领域只进行了部分探索。另一方面，案例a的领域全部被探索。事实上，当其他的领域结构不能提供一个比当前方案St更好的Rt的时候，ITE才会被执行，两者优劣的比较基础是包含不可行惩罚函数的目标函数值。为了更好地理解在关于ITE的上两个案例中的部分搜索过程，我们首先给出下面3个

37、定义：（1）节点与目的地的距离：节点N1和目的地T的距离表示为N1 R T,是节点N1与与之相近并包含在节点T中的节点N2之间的距离。我们用Dist(N1, T).表示该距离。（2）到节点最近的距离：到节点N1的最近距离是不包含N1的其他目的地到N1距离中最小的距离。我们用N1 R TÃ来表示该距离。（3）最近的目的地组：在T中与各单个节点距离最近的目的地组，我们用T（T）来表示这样的目的地组。例如，让目的地T只包含N1，N2，N3三个节点，让最近的一个N1为T,另外两个N2,N3记为T,然后，T(T)将成为T ,T ”.注意，在T(T)中的T并不意味着也在T(T)中。有了上述三个定

38、义，使解释关于ITE的两个案例中的局部搜索过程有了可能。从选择的链中给定目的地T，被检测的这些目的地只能是最近目的地组T中的对象，被称为T ðTÞ。也就是说，对于目的地T 2 St来说，足以决定和检查目的地组T ðTÞ中的路径。当Inter-tour Exchange中的案例b、c的领域调度在当前方案中被详细的探索时，就没有必要考虑T ðTÞ中的其他路径了。 此外，对于T1，T2来说，假如T2 在 T ðT 1 Þ 中， T1在 T ðT 2 Þ中，然后，在案例C中，当ITE的另一个目的地领域被

39、探索期间，不论何时，其中一个目的地被考虑时，为了节省计算时间，没必要核对T1。 最后需要说明的应作出有关TS -RN算法的多样化规则。当我们在探索候选领域的最优方案时，我们不但记录了邻域中最好的方案Rbest，同时也记录了最坏的结果Rworst，用最低的利润减去不可行的惩罚成本。让Rworst表示邻域中最坏的方案。现在，如果Rbest是无效的，意味着对于现方案St来说，它的利润正好和不可行惩罚成本相等，进而下一现行方案St+1是最差方案。然而，如果Rbest并非是无效的，St+1就会转向最优。从St到Rworst而不是Rbest的跳跃，在一定意义上，是由分散算法的搜索造成的。通过这个多样化的方

40、案，我们可能打破关于在多个局部最优解都有相同的目标值的循环。4.4.为了战略上的调整来更新惩罚函数值正如前面提过的，在每次迭代中，TS -RN算法探索了一系列的方案，根据车辆容量限制的因素，这些方案有的可行，有的不可行。选择惩罚不可行方案的惩罚参数值的最主要的基本原理是为了确保可行方案和不可行方案都具有相似的可能性成为邻域搜索中的最优方案，然后成为下一阶段当前方案的可行方案。这种方法增加了对解空间探索的多样性。很显然，太高的惩罚函数值会使算法无法无法访问不可行解；而太低的惩罚函数值则没有办法区分各种可行解。因此，惩罚函数的值需要进行动态的改变以尽可能的保证一定数目的可行解与不可行解都可以作为当

41、前方案而被访问。对于一个被给定的迭代，一个不可行方案变成一个最优的邻域方案，并被选作下一阶段当前方案所需要的次数或者这种不可行方案的数目都被记录下来了。如果不可行方案的比例高于60%，则惩罚函数值需要增加。如果比例小于40%，则惩罚函数值要减小。如果不可行方案的比值保持在40%-60%之间，则惩罚函数值保持不变。通过增加惩罚函数的步长来执行惩罚函数的更新。换句话说，如果惩罚函数值需要增加，则表达式为：=惩罚值 + 惩罚步长；反之，则为：= penaltyValue À penaltyStepSize。惩罚步长的大小不是恒定的，有如下四种情况：1. 如果惩罚值必须增大并在前面的控制就增

42、加，然后惩罚步长加倍并加到惩罚值上。2. 如果惩罚值必须增加并在前面的控制下降，那么惩罚步长减半加到惩罚值上。3. 如果惩罚值必须被减少，在先前的控制被降低，然后惩罚步长加倍，并从惩罚值中减去。4. 如果惩罚值必须降低，并在前面的控制就增加，则刑罚步长减半，并从惩罚值中减去。需要注意的是，每次的惩罚值被更新时 numInfeasible参数复位为0。惩罚值更新过程如图1算法在附录A中，其中t表示当前迭代次数。4.5终止条件条件1.有两种类型的终止条件是受TS- RN的影响。我们只要其中任何一个得到满足便终止算法。非改善迭代的最大数量限制（最大非限制数）。这个条件限制了该算法在此期间，最佳可行解

43、Sbestdoes没有改善的连续迭代的次数。条件2.时间限制（ CPU时间限制）。它决定了所允许的最大CPU运行时间。5. 计算结果 在这里，我们先介绍我们是如何产生的随机问题的实例。然后，我们划定的替代移动的组合，在我们的TS -RN启发式实验中计算包含三种解决方法的性能比较的结果。由CPLEX 11.2解决SMDVRPP -1和SMDVRPP -2的模型与所选择的移动组合来实现我们的启发式TS- RN。最后，通过TS -RN一些基准实例的比较来充分研究MDVRP，以评估其性能。通过为收集中心（C=1,2,3,4,5）分配五个不同的价值观，和为经销商的数量（D=10,20,30,40,50,

44、60,70,80,90,100）分配十个不同的值，我们得到40个实例其中每个实例被标记为（C,D)。注意的是，当经销商的数量较少时，也保持收集中心较少的数量。例如当D=20时，C=1,2。收集中心和经销商的位置坐标（ X，Y）是在区间 0 ，500 上的一个离散均匀分布采样。位置之间的移动距离DIJ使用欧几里德距离计算。每个经销商的预订价Pi在文献 5 ，7.5内均匀分布的随机变量抽样。每个经销商的核的数量是在区间 5,15 的离散均匀分布生成的。固定车辆运行成本c1等于100和每行驶距离可变交通工具成本C2被取为1。车辆容量q被设定为在该经销商的核心数量的10倍，即q = 10maxi ai

45、 = 150的最大数目。每单位核心的收入r等于15 。值得一提的是，在随机情况下，我们要注意不能取得实例的最好的解决方法是访问所有的经销商和收集所有的内核。在这种情况下，SMDVRPP将减少到经典MDVRP。TS- RN被编码在Java和与Java Server虚拟机编译的有16 GB的RAM和两个Intel四核至强3.2 GHz处理器的计算机上。对于所有的移动配置， TS -RN的参数值如下：惩罚控制计数= 100 ，惩罚值= 0 ，惩罚步长= 1 ，最大非限制数 = 2000 ， CPU时间上限= 15分钟。5.1选择最好的组合 我们定义一个组合为C0包括以下移动：添加-1，添加-2，删除

46、-1，删除-2,1-分裂，2-O选择和链转换。注意，前四个为经销商的移动选择，我们正在处理一个选择性的路径问题,并不是所有经销商都必须访问,经销商移动选择动作是很重要的,因此它们都包含在基本组合。其他组合在表3中给出，C15包含本研究中使用的所有组合。通过运行TS- RN不同的移动组合， C9平均利润为1116.29是40个实例中被发现的最好的移动组合。组合C15和C10分别以1049.35和1048.69的平均利润排第二和第三。我们用MDVRP基准实例来评估TS- RN的性能，C9是否在上SMDVRPP上有类似的问题由于针对SMDVRPP的TS- RN启发式算法不考虑对车辆游览时间的约束问题

47、，即最大行程时长的限制，我们仅选择那些没有这样的约束条件的MDVRP实例。因此，我们已实施的TS -RN 10 MDVRP测试实例的数据文件，可以在VRP网络（ http:/neo.lcc.uma.es/radi-aeb/WebVRP ）和加拿大分销管理研究的网站上（ http:/neumann.hec.ca/chairedistributique/data ）查到。表4 ，包括每个实例得到的最好的目标函数值，由TS- RN和从最好的目标函数值的百分比偏差所获得的客观价值的结果。这样观察到的TS- RN的精度是比较满意的。因此，在我们的进一步研究中我们采用C9组合和令人满意的TS- RN。表3

48、.TS- RN考虑到的组合表4.验证TS -RN性能的MDVRP实例5.2该解决方案的对比 在表5中，我们提出的结果，作为用于解决SMDVRPP实例3的方法的准确度和效率的基础。“ LB ”表示对应于每一种方法所得到的最好的可行解决方案的利润。此值表示在实例上的考虑最佳利润的一个下界。“ UB ”，另一方面，表示SMDVRPP -1和SMDVRPP -2的模型内由CPLEX发现为3小时或等价10800 S中的允许时限内的上限。“NOD”代表拜访经销商的数量。 CPLEX只能为三个实例（1,10 ），（ 1,20） ，（2 ，20）获得的最优解。在其他情况下，最佳的利润在LB和UB的值之内。表5中的第一个实例达到零值，为LB和UB无论是解决方法。这表明收集的十个经销商的任何一个核心都是不赚钱的。在SMDVRPP - 2模型下，一些LB值都是零，这意味着CPLE