PDF.
研究文章|开放获取
牛云云，杨泽华，陈平，肖建华那 “一种涉及燃料消耗约束的现实世界开放式车辆路由问题的混合动力禁忌搜索算法“，复杂那 卷。2018年那 文章ID.5754908那 12 页面那 2018年． https://doi.org/10.1155/2018/5754908
一种涉及燃料消耗约束的现实世界开放式车辆路由问题的混合动力禁忌搜索算法
摘要
外包物流运作到第三方物流在过去几年中引起了更多的关注。然而，在外包物流背景下，很少有论文分析了燃料消耗模型。这个问题涉及比传统的开放式车辆路由问题（OVRP）更复杂，因为燃料排放的计算取决于许多因素，例如车辆的速度，道路角度，总负载，发动机摩擦和发动机位移。我们的论文提出了一种绿色开放式车辆路由问题（GOVRP）模型，具有用于外包物流运营的燃料消耗约束。此外，提出了一种混合动力禁忌搜索算法来处理这个问题。考虑到外包物流在中国的货运运输中发挥着越来越重要的作用，在基于中国的实际道路数据进行了实验。通过对成本组件的统计分析将开放路线与封闭路线进行比较。与封闭式路线相比，开放路线将总成本降低18.5％，燃油排放量降低了近29.1％，潜水员降低了13.8％。还研究了不同车辆类型的效果。在所有60级和120节点的情况下，使用轻型车辆的平均总成本是最低的。
1.介绍
许多发展中国家都面临着两个问题:如何降低经济成本和如何发展环境友好型社会。因此，研究人员和具有综合物流专业知识的公司倾向于采用新的运输模式来应对这些问题。将物流业务外包给第三方物流，可以提高货物运输的资源利用率和操作效率，从而降低成本。它在货物运输中发挥着越来越重要的作用。在这种情况下，公司可以从其他公司租用车辆来运送货物。车辆不需要像往常一样返回公司。它们通常被描述为开放式车辆路径问题(OVRP) [1］．与车辆路径问题(VRP)相比，OVRP模型中的路径是开放的;参见图1．
OVRP是NP-hard [2]，因此通常采用启发式或元启发式方法来处理[3.]，如禁忌搜索[4.，以社区为基础的搜索[5.，粒子群优化算法[6.，蚁群优化[7.，或进化计算[8.］．混合成血管算法也被设计用于解决OVRP [9.］．此外，研究了几种OVRP的变体，以模拟具体的实际问题。有时间窗的OVRP (OVRPTW)由[10以模拟多产品报纸的投递。多仓库OVRP (MDOVRP)最早由[11]模拟新鲜肉的分布。引入了解耦点（OVRP-DP）的开放式车辆路由问题[12来描述由多个运营商执行的开放路由。研究需求不确定的OVRP，以处理不确定的客户需求，避免需求不满足或增加额外的运营成本[13］．然而，在过去研究的模型中，很少有考虑燃料和碳排放影响的公式[14］．本文是对这一研究方向的贡献。
碳排放和货物运输对环境有危险的影响。如何将燃油消耗降到最低成为一个热门话题。在[15比较了6种燃料消耗模型，分析了影响道路运输碳排放的几个因素。在[16]，引入污染路径问题(PRP)来评估VRP的温室气体排放。通过PRP模型，可以将每条道路消耗的总能量直接转化为温室气体排放。参考 [17]被认为是异构的车队并扩展了PRP模型。参考 [18[]综述了绿色货运问题的最新研究进展。
这项研究是由中国北京的一个真实问题推动的。随着物流外包在我国货物运输中发挥越来越重要的作用，许多公司都从第三方物流中租用车辆。产品交付客户后，车辆不需要返回车厂。每条路线从车站出发，最后到达一个顾客。这些公司正面临着将燃油消耗成本和司机工资等总成本最小化的问题。
本文的主要贡献总结如下。(1)在OVRP背景下进行油耗分析;建立了绿色开放式车辆路径问题(GOVRP)模型。为了优化模型中的燃料排放成本，我们将综合模态排放模型(CMEM)引入到OVRP模型中，并对OVRP进行扩展，以计算温室气体排放量为目标。(2)提出了一种包含多种邻域搜索策略的混合禁忌搜索算法。提出了一种改进的最近邻启发式算法(mNNH)来求得初始解。在寻找合适的初始解时，考虑了载荷和距离两个因素。然后设计了四个邻域搜索算子来生成当前解的邻域。(3)基于中国北京地区客户的真实地理数据进行实例计算实验。从降低总成本的角度分析了开放路线和车型的影响。
2.GOVRP的数学模型
CMEM由[19那20.来计算燃料排放。在本节中，我们将CMEM引入到OVRP中，并建立了GOVRP的数学模型。的燃料消耗(公升)车辆类型由[21] 在哪里 那 那 , 是约束。是总车辆重量，是距离，还是为车辆速度。三个方面分别称为发动机模块、重量模块和速度模块。表示法及其默认值列在以下两个表中[17那22］．表中列出了车辆的常用参数1．不同车型的具体参数见表2．
|
|||||||||||||||||||||||||||||||||||||||||||||||||||
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||
让 是客户和仓库的集合，让 是弧的集合。节点0表示仓库，因此客户集是 ．表示车辆的容量。变量意思是顾客的需求 ．变量到节点的距离是多少到节点 ．变量电弧上的总流量是多少 ．GoVRP的数学模型定义如下：
公式(2) - (5.)描述govvrp的目标，其中术语(2) - (4.)计算总燃油消耗成本和期限(5.)衡量司机的总工资。更具体地说,为每升燃油排放成本，条款(2) - (4.）计算发动机模块，重量模块和速度模块引起的燃料消耗成本。表示在路线上花费的总时间是最后被服务的顾客。
二元变量如果有车辆在弧上行驶，则等于1 ；否则,等于0.约束（6.) - (9.)确保每一位顾客只接受一辆车辆的服务，而且只接受一次。车辆不返回被驱逐出境。如果是最后服务的客户，约束(8.)可以写成 ．否则，可以写成 ．约束（10） 和 （11)定义流。二元变量等于1吗 速度 ．
3. Hybrid Tabu搜索GOVRP的算法
在本研究中，设计了一种包括若干邻域搜索策略的混合动力禁忌搜索算法来解决GoVRP。该算法的流程图如图所示2．详细步骤列出如下。
步骤1。初始设置包括初始化一个空禁忌列表和一个空候选列表，创建一个初始解决方案，将该初始解决方案设置为迄今为止的最佳解决方案。采用改进的最近邻启发式算法(mNNH)求得初始解。我们将在本节详细说明3.1．
步骤2。如果停止条件满足，搜索过程将停止，并返回最佳解决方案。否则，它会转到Step3.．
步骤3。利用四种有效的邻域搜索算法，从一个当前解到邻域中可接受解的每一步探索解空间。对于当前解决方案的每个邻居 那通过速度优化算法，根据[23］．
步骤4。检查邻近的解决方案是否需要禁忌元素。我们搜索最佳解决方案并更新候选列表。
第5步。如果最好的本地候选者比当前最佳解决方案更好，请更新当前最佳解决方案。将本地最佳解决方案添加到禁忌列表中。然后，转向步骤2．
在本文中，停止条件是最大迭代次数 ．当我们的算法被迭代时，算法终止。
３．１．最初的解决方案
我们使用改进的最近邻启发式算法(mNNH)来获得初始解。在寻找合适的初始解时，mNNH考虑了负载和距离两个因素。在运输系统中，车辆可以减少服务客户后装载 ．我们定义 在哪里定义为未路由的客户集。
MNNH根据以下步骤构建一个接一个路由。第一条路线始于未经证明的客户 那可以通过以下等式来计算： 然后,我们计算在当前节点之间和其他未解除的节点。我们选择最新的节点如果当前路径不违反车辆容量约束，则为下一个节点。我们更新当前节点然后用同样的方法搜索下一个节点。当没有客户可以分配给路由时，就会启动一条新的路由。当所有客户都已经路由完毕时，流程将停止。该算法被描述为算法1．
|
||||||||||||||||||||||
３．２．附近搜索
当前解决方案的邻居首先由四个邻域搜索算子得到。在此过程中，他们不能像以前一样违反能力限制。然后，根据[23］．
（1）随机操作员（RO）．它从解中随机选取一个节点，然后随机为其找到一个可能的位置。
（2）高成本节点改进操作员（HCNIO）．如图所示3.时，操作员尝试重新分配成本高的节点 那因为前一个客户和后一个客户之间的总距离最长。客户可计算如下: 在哪里是前面的客户和是以下客户
我们计算节点的最佳可能位置基于 在哪里 插入节点的开销是多少客户之间和客户和 是当前路由客户的集合。
（3)短途航线改进运营商(SRIO)．操作员试图通过重新分配属于这些路线的节点来组合或删除这些短途路线。一个阈值设置为计算路由长度。只有当路由长度小于阈值时 那该路线中的节点可以重新分配给其他位置。该过程可以在图中说明4.（ ）.首先删除较短路由中的弧，然后将隔离节点分配给其他较长的路由。
每个未路由节点的最佳可能位置亦由(19）.通过使用(20.)，选择最合适的客户反复插入路线中。未路由的节点将被逐个插入到当前路由中。
（随机路径改进算子．当前解决方案中的每条路径都有机会被摧毁。在这种情况下，应该重新分配该路线的客户。每个节点的最佳位置是由(19）.然后通过使用(20.）反复。所有其他无义的客户将逐一插入序列。如图所示5.，圆点椭圆中包含的两条路线被破坏;这些路线中的节点被重新分配到可能的位置。
对于当前解决方案的每个邻居 那设置每条路线的最佳速度。根据(23，最佳速度是
4.计算分析
实验数据来源于北京客户的真实地理距离。生成了三个包含10、20和30个客户的较小类和四个包含60、80、100和120个客户的较大类。每个类包括10个实例。本研究涉及的所有客户如图所示6.．算法参数值在表中给出3.．
|
||||||||||||||||||||||||||||||
4．1.目标对最小TD、最小FEC和最小DC的影响
采用最小TD(总距离)、最小FEC(燃油排放成本)和最小DC(司机成本)三个不同的目标分别最小化总距离、燃油排放成本和司机成本。我们得到的解决方案在每个绩效衡量中有不同的成本组成部分，并分析了不同目标的效果。实验在10个节点、20个节点和30个节点的实例中使用轻型车辆进行。报告十次运行后收集的每个实例的平均结果;见表4.那5.,6.．列显示总距离(TD)，执行时间(ET)，燃料排放成本(FEC)，司机成本(DC)，总成本(TC)，和CO2排放(CE)。表格7.展示每堂课的平均成绩。
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
平均10节点类，燃料排放成本占总成本的约30％。对于20个和30节点类，燃油排放成本占总成本的约26％。二氧化碳排放随着客户的数量而增加。只考虑客观的驾驶费导致最多的二氧化碳排放和最贫困的总成本表现。只考虑燃料排放只能通过最低二氧化碳排放，但总成本较高。最小TC作为目标产生最低总成本和最短总距离。
4．2.开放航线的影响
在本小节中，我们将与封闭路线的开放路线的总成本进行了比较。还通过使用轻型车辆在较小的实例类上进行实验。在表中列出了超过十次运行的封闭路线的平均结果8.．每个班的平均成绩报告在表中9.为了说明开放路线的效果。如表所示9.在所有情况下，开放航线降低了18.5%的总成本，其中燃料排放成本降低了近29.1%，潜水员成本降低了13.8%。
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
4.3。结果更大规模实例
以最小TC为目标，对四组最大的样本进行了实验。超过十次运行的结果被报告在表中10通过使用轻型车辆。符号BS，MS，WS，SD和ET分别代表了最佳解决方案，平均解决方案，最坏的解决方案，标准偏差和执行时间。如表所示10，总成本随着客户数量的增加而增加。
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
4.4。不同车辆类型的结果
在60节点和120节点的实例上，使用不同类型的车辆进行了实验。在这个小节中，分析的重点是哪种类型的车辆最适合使总成本最小化。具体车辆参数如表所示2．表格中列出了不同车辆类型的结果11和12．在这两类的所有实例中，使用轻型车辆的平均总成本是最低的。对于120个节点的实例，使用中型车辆的平均总成本增加了4.8%，使用重型车辆的结果增加了23.6%。对于60节点的实例，使用中型车辆的平均总成本增加了7.7%，使用重型车辆的价值增加了28%。
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
5.结论
在这项研究中，考虑到第三方物流燃料排放的影响，将GoVRP作为制定。问题是为车辆构建开放路线，以便使用车辆容量约束来访问所有客户。目的是最大限度地减少燃料排放成本的总成本和驾驶成本。
针对GOVRP实例，设计了一种混合禁忌搜索算法。利用北京地区客户的真实地理数据，对60个实例进行了实验。分析了不同目标下的成本构成，比较了开放航线与封闭航线在降低总成本方面的差异。本文考虑了一个齐次舰队。计算结果表明，车辆类型对总成本有影响，应根据实例的大小进行调整。在未来，可以使用异构车队来最小化总成本。其他类型的OVRP，如OVRPTW和MDOVRP，我们的算法可以通过一些改变来解决。
现在，一些新的计算技术被用来处理复杂的问题。其中一些是受生物启发的模型，如膜启发的进化算法[24-26]及探测机[27］．他们的非确定分布式并行框架已被证明可以提高优化算法的性能[28］．它们中的大多数都可以用来解决现实生活中的问题[29］．我们希望这些算法能够在未来为我们的GOVRP实例获得更多有竞争力的结果。
的利益冲突
作者声明他们没有利益冲突。
致谢
国家自然科学基金项目(no . 61502012, no . 61772290, no . 61373066);北京市自然科学基金资助项目(批准号:4164096);教育部人文社会科学青年基金(批准号:)资助项目:13 yjc630010);天津市科技发展战略研究计划资助项目(批准号:16 zlzxzf00030);以及中国经济协同创新中心。
参考文献
- L. Schrage，“更复杂/现实的路由和调度问题的制定和结构”，网络，卷。11，不。2，pp。229-232,1981。查看在：出版商的网站|谷歌学者
- S. Raff，“车辆和人员的路线和调度:最先进的状态，”计算机与运筹学，第10卷，第5期。2，页63-211,1983。查看在：出版商的网站|谷歌学者
- J.Brandao，“开放式车辆路由问题的禁忌搜索算法”，欧洲运筹学研究杂志，第157卷，第1期3，页552 - 564,2004。查看在：出版商的网站|谷歌学者|MathSciNet
- U. Derigs和K. Reuter，“解决开放式车辆路径问题的一个简单而有效的禁忌搜索启发式算法”，作业研究会杂志，第60卷，第2期12, pp. 1658-1669, 2009。查看在：出版商的网站|谷歌学者
- E. E. Zachariadis和C. T. Kiranoudis，“一个开放的车辆路径问题元启发式，用于检查广泛的解决方案社区，”计算机与运筹学，第37卷，第2期4，第712-723页，2010。查看在：出版商的网站|谷歌学者
- S. A. Mirhassani和N. Abolghasemi，“开放式车辆路径问题的粒子群优化算法”，专家系统与应用第38卷第2期9，pp。11547-11551,2011。查看在：出版商的网站|谷歌学者
- X.-Y。Li, P. Tian, and S. c.h. Leung，“一种混合禁忌搜索的蚁群优化元启发式算法求解开放式车辆路径问题，”作业研究会杂志，第60卷，第2期7, pp. 1012-1025, 2009。查看在：出版商的网站|谷歌学者
- 余s.，丁灿，朱科，“一种基于GA-TS的煤矿物料开放式车辆路径优化算法”，专家系统与应用第38卷第2期8, pp. 10568-10573, 2011。查看在：出版商的网站|谷歌学者
- P. P. Repoussis, C. D. Tarantilis, O. Braysy, G. Ioannou，“开放式车辆路径问题的混合进化策略”，计算机与运筹学，第37卷，第2期3，第443-455,2010。查看在：出版商的网站|谷歌学者
- R. Russell，W.-C.蒋，D. Zepeda，“在报纸物流中集成了多产品生产和分配”计算机与运营研究第35期5, pp. 1576-1588, 2008。查看在：出版商的网站|谷歌学者
- C. D. Tarantilis和C.T.Kiranoudis，“新鲜肉的分布”食品工程学报第51卷第1期1，页85-91,2002。查看在：出版商的网站|谷歌学者
- R. Atefi, M. Salari, L. C. Coelho, J. Renaud，“具有解耦点的开放式车辆路径问题”，欧洲运筹学研究杂志第265期1, pp. 316-327, 2018。查看在：出版商的网站|谷歌学者|MathSciNet
- 李明勇，“具有需求不确定性的开放式车辆路径问题及其鲁棒性策略”，专家系统与应用号，第41卷。7、pp. 3569-3575, 2014。查看在：出版商的网站|谷歌学者
- K. Fleszar, I. H. Osman, K. S. Hindi，“开放式车辆路径问题的可变邻域搜索算法”，欧洲运筹学研究杂志第195卷第1期3，第803-809页，2009。查看在：出版商的网站|谷歌学者
- E. Demir, T. Bektaş，和G. Laporte，“几种公路货运车辆排放模型的比较分析”，交通研究D部分:交通与环境，第16卷，第5期。5, pp. 347-357, 2011。查看在：出版商的网站|谷歌学者
- T. Bektaş和G. Laporte，“污染路径问题”，交通研究B部分:方法论，卷。45，不。8，pp。1232-1250，2011。查看在：出版商的网站|谷歌学者
- C。Koç， T. Bektaş， O. Jabali和G. Laporte，“舰队规模和混合污染路径问题，”交通研究B部分:方法论， vol. 70, pp. 239-254, 2014。查看在：出版商的网站|谷歌学者
- E. Demir, T. Bektaş，和G. Laporte，“绿色道路货运的最新研究综述”，欧洲运筹学研究杂志，第237卷，第2期。3, pp. 775-793, 2014。查看在：出版商的网站|谷歌学者
- M. Barth, T. Younglove和G. Scora，“开发一种重型柴油模态排放和燃料消耗模型，”技术代表UCB-ITSPRR-2005-1，加州道路计划，加州大学伯克利分校交通研究所，加州，美国，2005。查看在：谷歌学者
- M. Scora和G. Barth，“综合模态排放模型(CMEM)，版本3.01，用户指南，”技术代表，2006，http://www.cert.ucr.edu/cmem/docs/cmem_user_guide_v3.01d.pdf.．查看在：谷歌学者
- M. Barth和K. borboonsomsin，“交通拥堵对二氧化碳的真实影响，”运输研究记录， 不。2058，pp。163-171,2008。查看在：出版商的网站|谷歌学者
- 男人，卡车在分销运输，http://www.mantruckandbus.co.uk/en/trucks/start_trucks.html．
- E. Demir, T. Bektas，和G. Laporte，“污染路径问题的自适应大邻域搜索启发式”，欧洲运筹学研究杂志，第223卷，第2期。2, pp. 346-359, 2012。查看在：出版商的网站|谷歌学者|MathSciNet
- 张国栋，“一种近似求解组合优化问题的峰值神经P系统，”国际神经系统杂志，卷。24，不。5，pp。1-16,2014。查看在：谷歌学者
- 张国栋，“基于种群-膜-系统的配电网重构进化算法”，电子学杂志，卷。23，不。3，第437-441,2014。查看在：谷歌学者
- 张学军，“基于皮肤膜的多目标膜算法”，自然计算，第15卷，第5期。4, pp. 597 - 610,2016。查看在：出版商的网站|谷歌学者|MathSciNet
- 徐俊，《探针机》，神经网络和学习系统的IEEE交易第27卷第2期7、pp. 1405-1416, 2016。查看在：出版商的网站|谷歌学者|MathSciNet
- 张国栋，“基于差分进化和组织膜系统的制造参数优化问题求解方法”，中国机械工程，2018,27(11):1234 - 1234。应用软计算，卷。13，不。3，pp。1528-1542,2013。查看在：出版商的网站|谷歌学者
- 张国栋、M. J. Prez-Jimnez和M. Gheorghe，膜计算的现实应用，施普林格，柏林，德国，2017。
版权
版权所有©2018牛云云等。这是一篇发布在知识共享署名许可协议，允许在任何媒介上不受限制地使用、传播和复制，但必须正确引用原作。
