文摘
本文探讨了协作车辆路径问题在城市圈物流网络(Co-VRP-URLN) COVID-19流行病。根据城市分布的特点和交通的限制对中国在此期间,本研究主要考虑的常见分布模式顺序交换通过城市的外环,然后解决了车辆路径问题的分布,它属于一种特殊multidepot时间窗车辆路径问题。根据问题的定义,建立了multicommodity流对应的整数规划问题,和可变邻域搜索算法详细设计来解决这个问题。算法的有效性是一个标准的例子,验证了联合分布的好处是显示通过改进标准的例子。最后,比较不同的配送中心的影响。结果表明,该模型可以显著提高分销效率在城市交通的限制下。
1。介绍
本研究主要关注的问题集中城市共同配送车辆路线规划,其目的是评估一个潜在的城市联合分布模型下COVID-19流行病。城市配送体系,配送中心(DC)通常位于城市的郊区,而客户都在城市。货物进入城市后,他们将被送到配送中心的临时存储或组合。从运输工具的角度来看,尽管大卡车相对经济的交通工具,由于城市交通法律法规的限制下COVID-19流行,他们通常不直接进行上门配送服务,但卸载货物的配送中心。那么中小型配送车辆进行最后的城市配送服务。
对于执行最后一步的载体来说,它需要做的是完成分配效率。具体来说,一个团队负责分发产品和组织适当的驾驶路线下不同数量的货物不同的客户的需求。我们的目标是满足客户的需求,实现这些目标是最短的距离,最少的成本,和最少的时间消耗在一定的约束下,这被称为车辆路径问题(VRP)。
然而,与其他交通运输活动相比,城市“最后一英里”的利润分布较低,所以运营商更渴望找到进一步的降低成本的方法。满足客户服务水平的前提下,联合分布是最有效的方法之一。运营商参与共同配送可以减少车辆使用的数量和距离的顺序交换和整合和汽车共享,以便降低成本,获得更高的效益。另一方面,联合分布也会带来交通堵塞等社会福利救济和减少污染以及法规下COVID-19流行病。
在城市地区,一种新的基于环网分布法是新兴的。结合联合分布,一种新的城市共同配送车辆路径问题是诞生了。有别于传统的车辆路径问题,航空公司可以通过城市交换订单“外环道路使用重型卡车,然后分发它们。图1显示了一个简单的例子。可以看出,由于地理分散的配送中心,通过城市的郊区交换订单已经有效地合并)(一些公共客户,客户之间的距离和相应的商品分销出发点是缩短,和减少车辆在城市的分布。与此同时,汽车的数量可能会减少使用,产生一定的经济效益和社会效益。
本文研究的困难这种车辆路径问题的模型和算法。在未来的研究中,作者将在以下几个方面作出努力:(1)给出一个正式的问题描述和通用数学模型,(2)简要介绍可变邻域搜索算法来解决模式,(3)设计算法的具体细节,和(4)验证本研究通过数值实验的可行性。
2。文献综述
当前文学研究的主要贡献的联合分布下的车辆路径问题集中规划如下:(1)提出了联合分布模式,建立新的分销网络。(2)与特殊约束条件建立相应的模型和设计的算法来解决这个问题。研究结果可以指导联合分布的实现在一定程度上的目的,实现评价的影响共同配送模式。其中,根据联合分布的实际场景,它可以分为两个基本类型根据运输任务形式(主要是指不同的货物装卸的地方):一对一的运输模式和one-many-one运输模式。每种类型包含相应的联合分布模式和相应的车辆路径问题,下面详细描述。
2.1。一对一的模式
一对一意味着每一批货物将给定的起点(装载点)和终点(卸货点)。需求分布成对出现,可以分为两个子分类。
2.1.1。车辆只能提供一批货物
在卡车装载运输,刘等人。1)提出了一个multidepot弧路径问题能力约束。目标函数是最小化空车辆的距离,和一个两级贪婪算法旨在解决大规模实际问题。埃尔南德斯和Peeta2)被认为是联合分布问题的需求确定但联盟是时间的运输能力。最小费用流模型建立和修剪算法设计的一个分支。一般颤抖et al。3)研究了一种弧路径问题没有容量限制下的联合分布,和一些客户想要由指定的运输公司。根据这些条件,作者建立了一个整数线性规划模型,并设计了一个分支切割算法来解决这个问题。水系等。4]和Kuyzu [5)定义了托运人的合作问题,建立了电弧模型覆盖问题,并指出,最基本的弧覆盖模型可以通过多项式时间解决。扩展后的共同弧覆盖问题,一些特殊的协议合作伙伴,问题变成了np困难问题。该算法使用列生成和分支界限法准确地解决问题。
2.1.2。车辆可以加载超过一批货物
对于这些问题,戴笠和陈6,7),分别设计了拉格朗日松弛算法和弯管机分解算法来解决这些问题。翁和徐8),分别设计了两种基于拉格朗日松弛启发式算法和弯管机分解为一类multihub弧路径问题随着距离的约束。林(9)被认为是一种新型的联合分布,在车辆被允许交换货物中间的和反复使用。建设性的启发式算法基于插入算子的设计。
2.2。One-Many-One模式
One-many-one意味着加载点的商品都是起点的车辆(仓库或院子里),而其他点卸载点。这种模式是城市分布的主流方式,如快递和超市分布。与一对一运输相比,有更多的共同配送模式在这种运输方式下,主要通过汽车共享或分享。
这种联合分布的评价模式中,学者们发现,联合分布反映了良好的灵活性的影响下的动态环境。当外部环境(如的体积分布和交付)波动,通过合作可以有效地避免资源的浪费。斯派格和咀嚼10)模拟的食品市场在德国,在一个公共配送中心成立,成立一个联合分布网络的重要节点。然后,他们建立了一个多级分销网络的工厂分布center-customers。本文大量带有时间窗车辆路径问题模型考虑能力约束、订单交付、最大操作时间和外包。模型分解为几个VRP的子和蚁群算法旨在解决它。最后,由离散事件仿真测试方法,结果表明,联合分布随机和动态条件下具有良好的性能。Quintero-Araujo et al。11]还讨论了收入的联合分布与随机需求和供应链发现,收入增加了7.3%。Yilmazb [12)建立了一个马尔可夫决策过程模型来评估操作小规模托运人的不确定环境下联盟和指出,尽管联合分布通常可以带来可观的收益,及时受益分布将大大影响联盟的稳定性。
共同配送可以带来经济效益和社会效益,如减少道路拥堵、噪音污染,废气污染。因此,政府部门也积极支持运输企业的合作,特别是在市内的水平分布。Perez-Bernabeu et al。13]的结果相比multidepot车辆路径问题后联合分布的联合分布前常见的车辆路径问题,这表明碳排放将会显著降低。党的et al。14)建立了库存路径问题(IRP)模型的联合分布的环境。模型考虑了保质期,能源使用(碳排放)和产品需求的不确定性。结果表明,降低成本在4%和24%之间,和碳排放降低了8% - -33%。对于合作IRP问题,Fardi et al。15)使用鲁棒优化方法研究类似的问题。
3所示。问题描述和数学模型
在此背景下,城市环网的联合分布的车辆路径问题研究(协作车辆路径问题在城市圈物流网络,Co-VRP-URLN)。在这个问题上,有几个航空公司的运营车辆准备服务相同的城市在每个配送中心(CDC)。每个运营商获得一批订单交货需求从自己的托运人。在交付周期的开始,这些货物已经存储在自己的配送中心。每个订单对应一个客户,订单的收入,地理位置,对商品的需求,服务时间,服务时间窗口(困难)。当他们单独分配,成本是车辆固定成本和汽车驾驶成本。为了降低成本,航空公司形成一个联合分布联盟和分享他们的订单信息:运营商可以提供一些订单为分销合作伙伴。因为本文的研究是基于城市的环分销网络,配送中心的货物可以重新分配,通过城市“外环的流动。“决策中心的优化目标是重新分配决定的订单和车辆路径,实现最小成本或最大的收入。约束如下:(1)车辆容量限制;(2)车辆从配送中心和回到配送中心;(3)时间窗约束(如果早期等);(4)每个客户提供一次,只有一次。此外,考虑以下:(1)假设货物转移过程完成之前,第三方运输公司配送周期的开始(如晚上)或直接卸到其他配送中心通过重型车辆进入城市之后,这些额外的成本操作(称为重新定位)被称为转移成本。与城市配送车辆相比,运输车辆负载在这个过程中越来越便宜。为方便以后的研究中,它仅仅是假定成本是直接与交通容量和距离成正比。(2)没有限制汽车的数量,但每辆车有固定成本。(3)假定操作车辆的航母都在同一配送中心。(4)配送车辆的模型都是相同的;即每单位容量和成本都是一样的。(5)货物相互兼容;也就是说,他们可以用同一辆车。
根据图论的问题可以被定义为一个有向图 。描述的参数和符号表1。
根据上面的描述,可以构造的数学模型: 酸处理
目标函数(1)是最小化总成本,包括运输成本的配送车辆,外环的转移成本。和固定车辆成本。
约束(2)意味着每个客户只能由一辆车;约束(3)是车辆流平衡约束。
约束(4)规定,每辆车必须回归原来的配送中心;约束(5)是流出限制商品的配送中心。
约束(6)意味着满足每个客户的需求;约束(7)确保配送中心的流量平衡。
约束(8)意味着商品配送中心之间交换只能通过外环,进行米是一个足够大的实数。
约束(12)和(13)表明,交付车辆必须满足时间窗约束;约束(14)表明,道路网络的货运流必须是负的。
约束(15)是一个0 - 1变量的约束。
这个问题是车辆路径问题的变体,因此它也是一个np难问题,通过启发式算法来解决。在许多启发式算法,针对成功应用蚁群的变邻域搜索算法,该方法采用设计这个问题的算法。
此外,这里给出的是一个普遍问题描述和数学模型,而且没有一种货物运输的具体场景,但是这个模式仍然可以扩展到一些应用场景在城市分布。公共配送中心的一个例子,它代表承运人从起点开始,其交易行为发生在同一点。对应模型,设置配送中心坐标相同的点,并设置转移成本为0。另一个例子,在超市分布,可能会有公共客户(如图1),这意味着超市服务要求不同的运营商。模型,对应客户的坐标点可以设置为同一点。然而,如果有新的需求约束,如返回的快递需求,相应的模型需要修改。
4所示。算法原理
可变邻域搜索(VNS)是一个简单但强大的metaheuristic算法。首次提出Mladenovic和汉森16]。它的核心思想是系统并定期改变社区在本地搜索的过程中,以提高算法的搜索能力。关键在于社区的设计结构和局部搜索的策略。到目前为止,可变邻域搜索求解整数规划取得了极大的成功,整数规划,非线性规划。可变邻域搜索可以应用于许多领域,迅速增加,如定位问题,调度问题,车辆路径优化问题,网络通信设计、聚类分析、人工智能、可靠性、几何问题,总体规划的问题。
变邻域搜索是一个启发式算法,从而改变社区不断在局部优化的过程中,跳出局部优化。所谓的邻居只是其他点附近的一个给定的点的集合。在距离空间,社区通常定义为一个给定的点为中心的圆,在组合优化问题,社区中的节点通常被定义为一组问题域转换得到的每个节点在特定问题域与给定的转换规则。
变邻域搜索是基于以下定理:(1)局部最优值在一个社区不一定是当地最优值在另一个社区。(2)全局最优值是当地最优值在所有可能的社区。(3)对于很多问题,局部最小值在不同的社区很近。
变邻域搜索的基本过程如下:从一个初始解,生成社区解决方案根据目前社区结构紧张,和一个新的本地搜索解的社区解决方案;如果新的解决方案是比历史最优解,使用新的解决方案作为当前解决方案继续在附近搜索结构;否则,下一个邻居了,重复上述过程,直到达到最大迭代次数或一代又一代的最大最优解不更新或设定时间限制。
的框架中所示的典型的变邻域搜索算法是算法1。
|
简而言之,盾意味着当无法找到更好的解决方案在当地社区,它将跳转到下一个邻居继续搜索;附近找到一个更好的解决方案时,它会跳回到第一个社区和重新开始搜索。此外,本地搜索算法的搜索策略通常包括第一最好改善和改进。前者意味着,在解决的过程中,如果新的解决方案是比当前的解决方案,目前的解决方案是更新的新的解决方案,再进行迭代搜索,直到当前无法优化的解决方案,并作为最终的最优解。后者意味着,在解决的过程中,目前的解决方案是遍历的所有社区解决方案,和解决方案最大的改进范围是最终的最优解。一般来说,前者是高质量的,后者是在解决时间短。
5。算法设计
5.1。解决方案的代表
与传统车辆路径问题相比,本文还处理车辆的问题从不同的配送中心,这是类似于多个仓库的车辆路径问题。下面的代码定义来表示的结构解决方案: 意味着一辆车我从直流h和拜访客户 按顺序,然后返回h。所有客户数据在所有代码(图只出现一次,一次2)。
此外,当是设置为相同的配送中心,这意味着汽车吗不转让。该算法可以直接应用于普通有时间窗车辆路径问题。在数值实验中,算法的有效性将受到考验。
5.2。代的初始解和终止条件
初始解的质量影响了算法的效率。本文的结果之前每个载波的分配联合分布作为初始解决方案。这最初的解决方案提供了一个良好的上界,从而加快算法的收敛。当联合分布前解决车辆路径问题,最初的解决方案是简单地设置为每个客户有一个车。
终止条件时将停止搜索最优解还没有更新迭代一定次数后或当最大CPU时间。
5.3。摇晃
震动过程首先选择一个预定义的社区结构以某种方式,然后改变了当前解决方案根据社区结构来生成一个新的跳出局部最优的解决方案。Co-VRP-URLN涉及多个路径。根据其特点,晃动的过程被定义为两个子路径的插入或汇兑。插入:两条路径,和 ,从当前的解决方案是随机选择,子路径的长度吗从被选中,然后插入吗(图3)。汇兑:两条路径,和 ,从当前的解决方案是随机选择,子路径的长度吗从子路径的长度从然后选择交换(图4)。
值得注意的是,插入可以被视为一种特殊的交换;一个选定的子路径的长度为0,所以他们可以在编程相结合。此外,由于允许不可行解的存在性,没有必要判断操作是可行的。他们根据不同的操作分为不同的社区,不同长度的路线选择,和不同来源的路线(可分为同一配送中心和不同的配送中心)(图4)。
5.4。本地搜索
本地搜索被定义为两个或三个路径参与振动优化各自的路径。本地搜索中最耗时的部分整个VNS算法和质量很大程度上决定了最终的解决方案。因此,时间和质量应该考虑在本地搜索算法的设计。本文提出了两种局部搜索方法。首先是对本地搜索使用盾,第二个是正确的方法来解决这个问题。
5.4.1之前。盾
路径优化的经典启发式优化算子k- opt用作社区结构,代表的交换k边的流动路径。大量的数值实验表明,3-opt比2-opt的局部最优解和4-opt比3-opt略好,但这需要太长时间。此外,还是选择算子是3-opt算子的一个子集,可以在更短的时间内获得类似的质量解决方案。因此,2-opt算子和,或者选择算子选择本地搜索的社区结构。preexperiment之后,第一个改进策略是采用加快搜索速度。
5.4.2。准确的解决方案
本地路径的优化也是一个旅行推销员问题时间窗口(TSPTW)。模型描述如下:
酸处理
虽然TSPTW也是一个np难问题,考虑能力约束摇晃时,路径不包含太多的客户。因此,解算器可以用来获得上述问题的最优解在很短的时间内。应该注意的是,获得最优解时,编码应根据最优解的格式安排。
的目标函数 酸处理
可以看出,模型组成的(25),(17)- (22)和(26)- (29日)相当于原来的模型,是一种linear-integer编程。实现本地搜索,当道路上的点的数量很小,准确的算法,当数量大,使用盾。
5.5。验收标准的解决方案
验收标准确定的解决方案是接受下一次迭代。在这个算法中,大都市的标准模拟退火算法用于选择的解决方案进入下一次迭代。标准可以接受糟糕的解决方案有一定概率,避免过早陷入局部最优。中所示的标准是方程(30.),随机数在区间[0,1];初始温度是 ,每隔一代更新根据是什么 ; 是可设置的散热系数。
6。数值实验
6.1。例如建筑
由于没有具体的数据,这个问题,有必要构建一个示例。基于标准的例子有时间窗车辆路径问题(VRPTW)所罗门在1987年提出的相应的改进,以及一系列的测试数据集,用于测试该算法的有效性,并联合分配的好处是解释说。这个例子可以从所罗门的官方网站下载(来源:http://web.cba.neu.edu/%7Emsolomon/problems.htm)。
客户点的地理位置和时间窗口给出了所罗门的标准数据集。地理位置分为三类:R, C,和RC, R代表随机和C代表集群。三个类别对应随机分布,聚集分布,和混合分布的客户点,如图5。每个类提供了三种不同大小的数据集的25日,50和100个客户。考虑到联合分布的影响不明显,如果很少有客户,和太多的客户会影响计算速度,本节将使用的数据集50个客户点与适度规模。此外,考虑到城市分布主要是随机分布,通常有严格的时间窗口,本文选择“r102-50”类R作为基本的例子和构造的基础上,客户分布和时间窗口。
在所罗门的每个示例数据集的位置只给一个配送中心;根据的需求这一问题,我们需要设计一些合理的配送中心的位置。因此,一个简单的方法来确定配送中心的位置,提出了如下:首先,所有客户点的质心计算,和客户的距离最远的点对点作为半径的一个圆。最后,一些点圆选择配送中心的地理位置,和客户随机分配到一个运营商以同样的概率。此外,客户之间的距离和欧氏距离计算配送中心,配送中心之间的距离是根据圆的弧长计算。
三大运营商(a, b和c)为例,设计三种方式选择配送中心,代表三个配送中心的分布形式,远近,和附近X,Y,Z分别。具体来说,在课堂上X(a, b, c)固定在0°、120°、240°,分别;在课堂上Y(a, b, c)固定在0°、150°和210°;最后,在课堂上Z(a, b, c)固定在0°、60°、300°,分别。三种类型的配送中心的例子如图6。为了进行足够的数值实验,10个不同的作业进行随机分配的客户点,共有30例子。使用“米- - - - - -N”来表示与类别的例子米和电话号码N。例如,“X1”代表类的一个例子X没有。1。
6.2。参数设置
参数设置包括模型输入和算法superparameter设置。模型的输入是根据实际情况,合理设计和算法的superparameters由preexperiment决定。在本节中使用的参数设置如表所示2。
6.3。标准数据集的实验结果
为了测试算法的有效性,实验是进行标准VRPTW问题,而最著名的解决方案(noble)。注意,车辆费用不包括在标准VRPTW问题,因此需要修改模型中输入。
具体来说,首先,为了测试算法的稳定性和减少实验误差,10进行数值实验12反应类50个客户点的例子在所罗门的标准数据集。最坏的结果,最好的结果,平均结果记录下来。车辆的平均使用量也,这是表达的最好,AVG,最坏的情况下,和KAVG分别。其次,三个结果与已知最优解人。计算使用一般比较方法:(SOL-BKS) /溶胶×100%,其中溶胶是该算法获得的结果,并比较结果为空白K,差距最好的,差距AVG,差距最糟糕的,分别。表3给出了实验结果。
可以看出,12例,平均误差百分比该算法获得的结果是2% - -6%;最优性能的算法,最优解为R101 R104、和R108问题,和最大误差3.54% (R107);表现最差的百分误差是5% - -9%,这仍然是在可接受的范围之内的。
一般来说,与已知最优解的比较表明,该算法可以更好地接近最优解,甚至达到最优解在某些例子,显示了算法的有效性,以及从平均性能和表现最差的结果,该算法还具有良好的稳定性。因此,将该算法应用于该模型的结果应该更可靠。
6.4。评估联合分布
接下来,该算法应用于这个问题,结果之前和之后的联合分布比较所构造的例子。稳定的结果,每个例子是仍然计算10倍,平均值作为最终结果。实验结果包括配送总成本(成本),所需的车辆(K),和路径长度(DIS)承运人的联合分布,以及配送总成本(成本),所需的车辆(K),路径长度(DIS)和转移成本(反式)联合分布,以及它们之间的比例差距(差距)。的结果X,Y,Z情况如表所示4- - - - - -6,分别。
6.4.1。成本分析之前和之后的联合分布
表中的结果表明,该联合分布能够带来相当理想的成本降低。降低成本的X,Y,Z病例的35.16%、32.61%和29.95%,分别。不同的成本降低百分比而言,三种类型的计算情况下的车辆成本降低了28.86%,29.15%,和18.75%,分别和运输成本降低了48.24%,42.87%,和26.34%,这表明,通过联合分布,使用车辆和运输距离整个联盟的进一步优化,不仅可以产生经济效益,但也带来社会效益,减少配送车辆和分布的距离。
从成本的角度比例,表7显示了平均成本和每个成本源的比例之前和之后的联合分布。每个成本源的比例以更直观的方式图7。
它可以发现,汽车成本的比例从55.26%上升到58.08%,而距离成本的比例从44.74%下降到38.58%,表明运输成本效益更多的联合分布。可以理解,随着客户需求的总量不变,将会有一个强大的下限限制汽车的数量保存,和优化运输距离相对更加灵活。它可以调整根据配送中心的地理位置和转移客户的位置点,所以有更多的空间优化。在以下三种例子横向比较分析配送中心分布的影响。
6.4.2。直流分布的影响分析
的例子X,Y,Z表示配送中心从分散到集中的变化。图8显示下降之间的关系和示例。
它可以发现最分散的配送中心(类X)可以带来最大的成本降低。然而,当配送中心相对集中(类Z),联合分布带来的利润不如由分散的分布(类X和类Y),这是更符合期望本文的开头,因为分散的配送中心可以缓解长途运输行为在一定程度上。由于商品的组合和一定数量的商品,汽车成本降低的比例相对比较相似。此外,它应该指出,表演类X和类Y非常相似,这意味着,在分销联盟,没有必要有一个更好的效果,当所有的配送中心都是相对分散。类似的配送中心之间的转移成本相对较低,可近似视为相同的公共配送中心的订单可以有效地合并和加载,相当于两个局部最优解。如果它成为一个全局最优的解决方案,将减少相应的成本。换句话说,不同的配送中心分布有利于降低成本,可能会促进分销联盟的形成。
一般来说,整个联盟的成本可以大大降低城市共同配送的“环”网络通过少量的转移成本,包括减少车辆使用和运输距离,将产生良好的经济效益和社会效益。
7所示。结论
本文提出了一个新的研究问题和基于联合分布的方向:Co-VRP-URLN。的导数multidepot车辆路径问题和多级车辆问题。本文建立了混合整数线性规划的np难问题。根据变邻域搜索算法的框架(VNS),解决方案表示,健身的计算方法,初步解决方案生成策略和终止条件,犹豫不决社区结构,和方法,两种局部搜索策略和解决方案验收标准设计。通过数值实验,验证了算法的有效性和稳定性。与此同时,共同配送成本的变化在不同的配送中心配送条件评估。结果与预期的结果基本上是一致的,符合城市分布的特点。
每个航空公司的车辆路径规划和顺序选择取决于本身而不是收集所有信息通过“决策中心”统一规划。未来的研究将进一步探索分布式联合分布,也就是说,合作的前提下不完整的信息共享。
数据可用性
数据可在http://web.cba.neu.edu/∼msolomon / problems.htm。
的利益冲突
作者宣称没有利益冲突。