牵引车和半挂车路由问题的影响减轻二氧化碳的排放量

文摘

的公司排放最小化的车辆路径问题(VRP)是至关重要的企业实践。关注的牵引车和半挂车路由问题完整的卡车任何两个终端之间的网络,本文提出了一个数学规划模型以最小化的目标每ton-kilometer排放。模拟退火(SA)算法来解决practical-scale问题。评估算法的性能,一个下界。计算各种问题生成的随机实验和一个现实的实例。结果表明,该方法是有效的,该算法可以在一个可接受的计算时间内提供合理的解决方案。

1。介绍和问题描述

随着商品需求的增长,运输体积迅速增加。门到门运输,使用最广泛的模式是公路运输。然而,公路运输对环境有负面影响,因为土地使用、能源资源消耗,等等。公路运输占近80%的总能源需求从运输1]。化石燃料是主要的运输和能源在化石燃料的燃烧排放。运费占主导地位的模式运动,公路运输占最大的份额freight-related排放(2]。道路货运的百分比排放相比,整个交通行业从1985年到2007年,中国在29%和34%之间3]。越来越多的吨每年释放到环境和道路货物运输吗排放很可能继续增长。最近的货运的研究不仅关注成本最小化和利润最大化的货运公司也在碳减排,加强公司的企业社会责任4]。

燃料消耗是最昂贵的运输过程的可变成本道路货运企业(5]。卡车和公路网络的有效利用变得越来越重要。与昂贵的网络基础设施的修改,优化路由策略已经被证明是更有效的提高网络容量(6]。优化车辆路径的数量可以减少卡车和利用网络更好的通过减少车辆运动。优化问题一直得到广泛的研究文献中,称为车辆路径问题(VRP)。VRP和它的各种扩展一直是研究最多的一个组合优化问题,由于问题的复杂性和广泛应用7,8]。

的能量和的最小化排放的VRP是一个相对近期的话题的研究工作。VRP-related研究,旨在最小化总燃料消耗是相当罕见9]。郭(9)提出了一个模型来计算总时间VRP的燃料消耗。SA算法。实验结果表明,可能存在一种之间的权衡燃料消耗、运输时间和运输距离。Pradenas et al。10)提出了一个数学模型对有时间窗车辆路径和回程。分散搜索(SS) metaheuristic最小化同类车辆的排放的温室气体是设计和实现。实验结果表明,车辆路径的环境影响相关车辆利用率,运输的装载在客户,和客户之间的距离。

一般来说,所使用的各种类型的汽车企业。通过宪法模式的自治和自治11),车辆可以分为两种主要类型:汽车卡车和组合。一辆卡车,一辆单机制,有其固定的自治和自治和两个部分是不可分割的部分。结合的类内车辆卡车和卡车与半拖车或卡车拖拉机拖拉机半挂车组合结合完整预告片。在VRP的一些扩展,结合车辆,尤其是使用拖车(VRP)通常被忽视的特性,被认为是。我们学习的一种变体combination-vehicle路由问题,拖拉机半挂车组合利用。我们称之为VRP的变体(TSRP)拖拉机和半拖车路由问题。随着全球变暖的担忧增加,减少排放正成为重要的交通工具。减少燃料消耗将越来越影响了蚁群。不同于其他文学,我们的目标是尽量减少燃料消耗的TSRP通过考虑车辆类型及其利用率。

纸的TSRP具有以下特点。(1)拖拉机的拖拉机半挂车组合可以将独立的半拖车。拖拉机不能装载货物,只有用于半拖车。时间/分离半拖车附加到拖拉机在位置通常是大大低于时间加载/卸载所有货物在半拖车,所以拖拉机TSRP利用率较高。(2)运输服务提供者服务客户订单从一个仓库的数量。发货仓库之间发生和皮卡/交付订单的位置,和仓库之间。整车(TL)或不到卡车(LTL)货物可能存在。卡车被认为在VRP适合LTL发货。适合TL TSRP,半拖车。(3)拖拉机和半拖车运输比单机制提升为更节能的卡车运输(12]。如前所述,Ierland et al。13),排放因子,它可以被定义为人均排放ton-kilometer(单位:g/ t-km),是一个典型的指数来描述排放道路货物运输的影响。(4)TSRP的的一个重要应用是多级货运分销系统的概念(例如,城市物流和多通道货运系统),货运到达一个中央仓库和运输进一步卫星设施由更大的车辆,然后运费是由更小的车辆为最终客户。如何有效车辆路线问题的操作在两个水平在文献中被称为Two-Echelon车辆路径问题(2 e-vrp) (14),广义车辆路径问题(GVRP) [15),或者two-echelon同源化生产location-routing问题(2 e-clrp) (16]。牵引车和半挂车的组合具有较高的平均负载和高利用率的拖拉机,这使得它可行的使用在出货量很大的水平或TL。

我们建议的TSRP loaded-semitrailer流网络。有两种类型的终端网络:一个中心仓库和一些卫星设施。在一开始,所有的拖拉机定位在中央仓库,而卫星设施loaded-semitrailers等待发送。拖拉机或所有车辆(车辆是一个拖拉机拉一个半拖车)产生和终止在中央仓库。一个齐次舰队组成的拖拉机和半拖车服务终端之间的流量需求。拖拉机可以拉一个loaded-semitrailer,也可以单独运行。loaded-semitrailers假定TL。TSRP的目的是确定每个拖拉机拖拉机和路线的数量减少每ton-kilometer排放。

有一些特性来区分TSRP现有路由问题研究。首先,我们扩展了应用程序的背景牵引车和半挂车组合TL运输多级货运的分销系统。的应用TSRP不同于牵引车和半挂车组合应用的文献,这叫做滚装的车辆路径问题(RRVRP)。其次,TSRP综合指数,也就是说,ton-kilometer人均排放的目标。它不同于大多数vrp的单一指数(例如,总距离、总成本等)的目标。在实践中,统计数据人均排放ton-kilometer可用于校准TSRP的实验结果。第三,TSRP的节点可以发送多个loaded-semitrailer和节点和连接弧必须参观了不止一次。一个节点可能出现不止一次在同一个解决方案的路线。

TSRP起源于现实很感兴趣区域级的TL运输卡车在中国的业务和多级货运分销系统。我们的目标是开发一个解决方法TSRP和演示的效果减排。本文组织如下。下一节介绍了相关文献。数学模型和一个下界TSRP开发部分3。部分4提出了解决问题的启发式算法。计算实验中所描述的部分5。最后,给出了结论和未来的工作部分6。

2。文献综述

在本节中,我们将概述的贡献combination-vehicle TSRP地址路由问题。

VRP研究迄今为止被认为尤其是卡车,卡车和拖车的组合。卡车和拖车路由问题(TTRP)已经提出了几十年。TTRP,异构机群组成的卡车和卡车和拖车服务组合的一组客户。每个客户有一定的需求,卡车和拖车的能力是决定性的。一些客户必须提供只有一辆卡车,而其他客户可以提供通过卡车或车辆。TTRP的目的是找到一组路线与最小距离或总成本,这样每个客户参观路线。曹国伟(17)区分三种不同类型的路线在TTRP解决方案:一个纯粹的卡车路线(PTR)一辆卡车服务所有客户没有使用拖车,纯粹的车辆路线(PVR),所有客户服务与耦合的拖车卡车,和一个完整的车辆路线(表格),其中至少一次在一辆卡车的拖车是分开客户和卡车继续卡车subroute服务客户的一个子集。

Semet和Taillard18]和Gerdessen [19]研究了TTRP在1990年代。Semet和Taillard18]和Caramia Guerriero [20.给了一些真实的TTRP应用程序。Gerdessen [19)延长了VRP拖车的车辆路径问题和调查的最佳部署舰队货车挂车组合。朔伊尔(21)提出建设启发式TTRP以及禁忌搜索算法。谭et al。22)提出了一种混合多目标进化算法解决TTRP。林等。23]提出了一种模拟退火(SA) TTRP启发式。Villegas et al。24通过使用混合metaheuristic]解决了TTRP。的扩展TTRP, Villegas et al。25)提出了两个metaheuristics解决单一卡车和拖车路由问题与卫星仓库(STTRPSD)。考虑可用的卡车和拖车的数量被限制在TTRP林et al。26放松机队规模约束和开发了一个SA启发式求解放松卡车和拖车路由问题(RTTRP)。林等。27)提出了一个SA启发式求解时间窗的卡车和拖车路由问题(TTRPTW)。最近,Derigs et al。28)结合本地搜索和大型社区搜索metaheuristic解决TTRP有/无荷载传递和TTRP /没有时间窗口。计算测试基准实例表明,该方法至少竞争最先进的方法TTRP没有时间窗口。

TTRP,每个拖车卡车相关可以由一个独特的,而且只有这个卡车是允许负载转移到预告片。卡车的数量通常比预告片。那个(11),描述了VRP的预告片吧(VRPTT)没有固定的货车挂车任务。TTRP显然VRPTT的一个特例。此外,Pureza et al。29日)解决VRP和时间窗和多个交付男人(VRPTWMD)允许交货很多男性是分配给每个路线。两种解决方案的方法提出了基于禁忌搜索和蚁群优化。使用额外的交付的影响男性路线规划评估的计算实验。如果关于交付男性卡车,VRPTWMD成为TTRP当只有一个送货人。

有一些变异的VRP考虑牵引车和半挂车组合。这些变异包括RRVRP等等。出现在文学,RRVRP当拖拉机移动大型拖车之间的位置生成一个高容量的浪费建筑工地和处理设施。在基本RRVRP,只有一个仓库,所有的拖拉机都位于一个开始。有一个处理设施完整预告片倾倒和空的拖车可以戴上或从库存。在一天结束的时候,所有拖拉机回到仓库,拖车可能保持在客户位置或处理设施。问题是分配去的拖拉机拖拉机和找到路线不超过一个给定的最大持续时间,减少非生产性空车返回时间旅行以及之间的拖拉机拖拉机使用的数量。

博丹et al。30.]研究了RRVRP仓库和处理网站和客户需求分为四个类型。他们定义了RRVRP作为不对称车辆路径问题的结合与本包装问题。提出了启发式方法来解决一些在RRVRP基准问题。Derigs et al。31日)解决了RRVRP结合本地搜索和大型社区搜索由两个相对简单的控制和parameter-free /——可怜metaheuristic控制程序。王寅et al。32]介绍了随着时间的推移RRVRP windows (RRVRPTW)。RRVRPTW的目标是最小化所需的拖拉机的数量和他们的总时间。基于LNS迭代启发式方法组成的构造算法,提出了几种改进算法。Baldacci et al。33)模拟了多个处理设施和多个库存地点RRVRP (M-RRVRP)作为时间约束车辆路径问题油印。

还有其他变体有关牵引车和半挂车组合路由问题。大厅和Sabnani34)的研究路线,由两个或两个以上的部分和两个或两个以上的停在一辆拖拉机的路线。基于预测控制规则路线生产力发展决定何时释放拖拉机。弗朗西斯et al。35解决了multiresource路由问题(MRRP)与灵活的任务。两个资源(拖拉机和拖车)执行任务运输装载和空的设备。程等。36)提出了一个模型,一个钢铁厂找到的拖拉机和半拖车运行路线运输距离最小化的目的。Derigs et al。37)提出了两种方法解决车辆路径问题的多种用途拖拉机和拖车。李等人。38)研究了拖拉机和半拖车unit-flow网络路由问题,和一个启发式算法被用来决定拖拉机的数量和每个拖拉机的路线。

在文献中,combination-vehicle路由问题近年来越来越热。TTRP应用的背景类似于蚁群的,也就是说,城市物流或其他交付过程。事实上,一个城际长途运输层是必要的完善城市物流或其他运载系统。散装运输大量货物城市之间可以实现规模经济,通过使用大容量车辆。尽管使用牵引车和半挂车组合被认为是由RRVRP文学,RRVRP应用主要局限在废物收集业务。因为高利用率的拖拉机,拖拉机和半拖车组合比单机制提升为更节能的卡车。还有另一个变体的RRVRP当应用程序背景成为城际长途运输运输。所有的工作中我们回顾了在文学,小的工作已经完成TSRP我们前面所述。考虑的问题目前的研究涉及到合并TSRP排放最小化。此外,运输企业可以拒绝客户订单因为服务订单是不可能的或服务订单的成本太高了。

3所示。模型公式

TSRP模型的基本假设是(我)所有loaded-semitrailer流要求提前知道。问题是静态的。空半拖车交流将被忽略。(2)Loaded-semitrailer流需求可以产生任何两个终端之间。在中央仓库,传入的半拖车的数量等于输出半拖车的数量;即中央仓库平衡流动。(3)一些loaded-semitrailer流的要求可能被拒绝。交通服务水平是基于流的百分比要求得到满足。(iv)不得超过一个给定的时间间隔。为了平衡路线长度、路由必须超过给定minimization-time。 If a satellite facility is already in a route, it cannot be reinserted in the same route. (v) All tractors are assigned to the central depot where they must return to after each route. Routes must start from and end at the central depot. Each tractor leaves from and returns to the depot exactly once. (vi) The TSRP deals with TL and does not consider cross-docking options.

TSRP可以制定如下。

让是一个有向图顶点集和吗,电弧集。顶点0 ()是中央仓库和其他顶点()(例如,)对应于卫星设施。Loaded-semitrailer任何两个终端之间流动: 在哪里表示,有loaded-semitrailers需要运输来。

和决策变量。如果th拖拉机从来,;否则,。如果th结合车辆(即加载。,拖拉机牵引一个loaded-semitrailer)从来,;否则,。

的燃料消耗th拖拉机从来。的燃料消耗th组合加载车辆运行来。的运行时间是th拖拉机从来和平均速度。的运行时间是th组合加载车辆运行来和平均速度。拖拉机的值班时间每天。

目标函数是

的约束 ;;;;;是一个整数和最大是拖拉机的总使用。

目标函数是人均排放的ton-kilometer TSRP,排放系数(常数)和吗loaded-semitrailer运费的重量。

约束(3)和(4)保证货物流总需求满足一定比例(),而任何终端的需求是受人尊敬的。约束(5)和(6)保证任何拖拉机从中央仓库和终止在中央仓库。约束(7)保证卫星设施不能保留任何拖拉机。约束(8拖拉机的限制(即。,running-alone tractor and tractor attached in combination vehicle) passing by a certain arc. Constraints (9)保证流平衡中央仓库。约束(10)禁止非法段路线。约束(11)保证拖拉机的运转速度。

约束(12)和(13平衡的路线长度的限制,(),(是一个数量有限)的上下极限利用率拖拉机的值班时间,分别。是拖拉机的停留时间在中央仓库。是拖拉机的附加/分离的总时间在卫星设施。影响卫星设施包括一个路线的数量。当一个路线包括卫星设施和拖拉机的附着在卫星设施/分离时间,,在那里。

尽管制定的决策变量是二进制,路线决定。约束(5)~ (10)建议的路线是由连续的弧线拖拉机或通过加载车辆组合。我们表示终端路线的序列,在那里中央仓库吗卫星设备。

一般来说,高效精确的算法来解决我们这里提出的模型尺寸不存在现实的问题。因此,这种模型只能通过启发式解决获得次优解的先验未知的质量。在这种情况下,它是有用的发现下界估计的质量解决方案由启发式发现。如果导数模型的变量和约束条件数量明显低于那些在原始模型中,导数模型预计将在更短的时间内解决。这个导数模型解决发现的客观值上下界解决原始模型(39]。如果我们放松路线长度约束(12)和(13)在上面的模型中,目标函数和约束(3)~ (11)可以作为另一个模型新配方(表示加快,可以解决小规模的实例。加快的解决方案也可能是一个实例的最优解,如果它满足放松一段时间约束。我们使用这个下界来比较部分提出的启发式的表现4。

此外,TSRP模型的目标函数是显著影响两个部分:一个和其他。当约束(3)和(4)方程和满足需求的百分比是100%,目标函数是影响前的部分。如果任何部分航线loaded-semitrailer运输,也就是说,对所有,,,目标函数达到最小值。最低建议作为加快的基准。

4所示。启发式算法

三种类型的算法用于解决VRP [40]。第一类包括精确算法耗时。第二种类型由等经典启发式的贪婪,本地搜索,和放松。第三类包括基于一些metaheuristic的启发式规则。这样metaheuristics或框架来构建启发式SA,禁忌搜索、遗传算法、可变邻域搜索,等等。高计算成本的具体方法和表现不佳的大问题都涉及,目前的研究集中于随机算法能产生可行的,但不一定是最优解在有限的时间5]。SA算法是一种常用的metaheuristics,已成功地应用于解决VRP的几种类型。出于TTRP SA的成功(例如,(26,27]),因此选择基于SA的启发式算法来解决TSRP。

SA使用一个随机搜索方法,搬到附近的解决方案。如果更好的社区解决方案被确定在搜索从当前的解决方案,此举将被接受和当前解决方案将被更好的社区解决方案取代。然后继续附近寻找一个更好的解决方案。此外,SA将接受搬到一个更糟的社区解决方案有一定概率逃离局部最优。公认的概率是基于两个参数,温度逐渐降低,目标函数之间的区别这两个解决方案。初的搜索、移动的接受概率较高。当接近尾声的搜索过程中,接受了此举的概率更小。一般来说,初始温度,冷却功能,最终温度会影响SA的结果。

4.1。社区和初始解

Braysy和Gendreau [41)表示,本地搜索中起着非常重要的作用的metaheuristics VRP的设计。迭代局部搜索算子改进解决方案,探索它的邻居。TSRP模型表明,路线是由连续的弧线。任何的约束(5)(10段)保证一些要求的路线,而路线长度约束(12)和(13)保证整个路线的要求。我们把约束(12)和(13)作为最重要的因素决定一个解决方案的社区。

拖拉机的每天值班时间()取决于司机团队的值班时间。司机的值班时间(用)由驾驶时间,附加/分离时间()和停留时间(在终端)。如果司机的数量分配给每个拖拉机,。当运输终端之间的距离和是和平均速度之间的运行时间和是。约束(12)和(13)被重写为

vehicle-kilometer (v-km)是最重要的指标,为企业评估车辆和司机的性能。当有卫星设施路线,,平均速度越慢,因为拖拉机/车辆频繁进入和离开了码头,一个缓慢的速度是允许的。平均速度(用)被认为是一个递减函数。如果拖拉机的值班时间的利用率是100%,线路的运行时间。然后,车辆的v-km /司机。v-km将减少和增加。因此,路线包括有限插入卫星设施。我们列举卫星设备的数量在一个路由搜索完全找到所有航线满足约束(14)。当线路包括至少1和最多卫星设施,有潜在的路线选择,这也构成了社区。

与蚁群或TTRP每个去除伴随着一个插入,可能会决定一个删除,而不是继续插入我们的问题。这部分的解决方案仍然是可行的,当需求满意比例保持比最低()。通过引用传统的破坏和修复框架,我们把整个路线为操作单位。有三种类型的操作符。(我)路线从当前摧毁运营商解决方案。(2)删除路线从当前解决方案通过摧毁操作符,另一个途径是插入一个修复算子。删除路由记录社区和仍然是一个候选人路线的修复算子。(3)路线可能会克隆自己好几次了。《纽约时报》是由卫星的最大需求决定设施包括路线。克隆操作符是一种特殊类型的修复算子。实际规模的实例的结果部分5显示克隆算子的效果。

初始解的生成,我们计算测试显示一个类似的结论,科埃略et al。42]。最初的解决方案没有显著影响总体解决方案的成本和运行时间。因此,我们随机生成初始解。

4.2。SA启发式

拖拉机的数量(或路线在解决方案的数量)是未知的,但它是一个重要的参数。拖拉机拉很可能不止一个独立半拖车的路线。表示的平均数量运输loaded-semitrailers路线上,是一个重要的基准拖拉机的数量。拖拉机的数量应该是有限的整数。我们的实验结果表明,该人均排放ton-kilometer可以减少加上或者减去额外的拖拉机。建议的SA启发式TSRP并不需要拖拉机的数量作为一个客观的价值。与此同时,计算测试证明它是可行的。通过选择随机SA过程开始线路的初始解表示最大的整数是小于或等于封闭的号码。在每个迭代中,目标函数是用来评估顺序的解决方案满意的比例是货运需求。当满足货运需求的比例达到SA过程发现,nondominated解决方案拖拉机的数量。如果满足货运需求的百分比小于的路线在前解决方案()被放大,次()和SA过程开始路线。最后,拖拉机的数量决定。

SA过程中运行两个阶段。在第一阶段,nondominated解决最小数量的拖拉机。在第二阶段,先后ton-kilometer人均排放的最小化当前数量和拖拉机的数量增加了每一个时间一个预定义的停止准则(例如,见了面人均排放ton-kilometer停止减少)。

初始温度,最终温度,玻耳兹曼常量用于概率函数,最大迭代次数,和冷却机制调整的迭代的数量是由特定的首先。概率函数用于SA过程决定拖拉机的数量是不同的,对SA过程决定TSRP的最终解决方案。前者主要考虑满足货运需求的百分比,而后者认为同步的比例满足货运需求和流动每ton-kilometer排放。像郭提出的9),我们的股价模型还包括每个迭代被冷却的温度,这是不同于一般SA一定数量的迭代之间进行冷却。我们使用一个100年的初始温度,最终温度1和SA的迭代次数= 100000(小规模随机下一节的实例)或4500000(在下一节的现实实例)。冷却机制调整是基于迭代的数量。终止条件时停止算法的迭代次数达到最大,温度变得1。

5。计算研究

因为我们之前没有意识到任何TSRP最小化测试实例ton-kilometer人均排放,提出的模型和算法进行了测试在一系列小规模的实例生成的随机和一个现实的实例。我们的计算实验进行了两部分。首先,小规模的实例被用来显示模型和启发式的功效。我们也校准解决方案方法在小规模的实例解释部分5。1。其次,我们有一个现实的实例上运行启发式不同中央仓库位置解释部分5。2。重点在于总结一些校准方法寻求紧密parameter-free metaheuristic通过小规模实例生成的随机。指的校准方法,SA启发式算法可以生成高质量的解决方案在相对短的时间与一些参数调优。

5.1。小规模的实例

提出TSRP模型和SA启发式评估的小规模测试问题网格图。几个参数被认为是在创建的问题卫星设备节点的数量(C_n);loaded-semitrailers每颗卫星设备的数量;中央仓库的位置;卫星的位置设施;拖拉机和半拖车的参数(例如,燃料消耗,loaded-semitrailer货物重量,速度,等等);任意两个节点之间的距离;距离的路线。

小规模的实例分为四组根据卫星设备的数量。小规模的实例是由随机的方式如下。使用Matlab中的“随机”函数。通过随机(“规范”,1 1 5 5),随机生成数组。我们选择一个随机的最低位置数组作为中央仓库和其它C_n-卫星设施位置的数组。任意两个终端之间的距离计算的空白行和列。“随机”功能使用十次,每组包括十个实例。“随机”功能也用于确定loaded-semitrailers终端的数量。

拖拉机半挂车组合,可以加载30吨,最大限度地满足节能的要求”的监管监督车辆燃料消耗”(编号11/2009法令运输部的中华人民共和国(MOTPRC)),是用于运输货物。所选代码的类型组合是“CQ4254HTVG324V”或“ND4251B32J7。“燃料消耗是每100公里18公升柴油拖拉机单独运行和32升柴油每100公里运行组合。假设:之间的差距相邻的行或列的随机阵列50公里;的加载因子loaded-semitrailer是60%;速度是50公里/小时;跨越的距离大约是650公里;和满足货运需求的比例不小于85%。

测试问题详细表1。列1 - 9显示测试问题,矩形区域,loaded-semitrailers的总数,平均loaded-semitrailer所有卫星设施,的方差loaded-semitrailer所有卫星设施,中央仓库之间的最小距离和卫星设备,中央仓库之间的最大距离和卫星设备,任何两个终端之间的平均距离和方差分别为任意两个终端之间的距离。

获得下界,提出的整数规划模型(加快)部分3已经实现并使用LINGO11解决。的解决进程加快了拖拉机的数量作为前提;也就是说,。为一个实例计算下界加快时,我们可能会发现一个更好的价值在计算实验。为加快寻找可行解中,拖拉机的数量是手动调整。此外,拟议的SA算法在MATLAB R2010b编码和在电脑上运行的AMD Athlon X2 (tm) 2.10 GHz双核ql - 65在Windows 7旗舰(32位)和2 GB的RAM。并给出了计算结果表2。

当不切实际地存在情况下,终端和loaded-semitrailer流的分布满足所有约束,这样任何段路线loaded-semitrailer运输,ton-kilometer人均排放将达到最小值。根据我们的假设,最低是48.53克/ t-km。因为大多数情况下很难满足idealistical要求,人均排放ton-kilometer加快将大于48.53克/ t-km。我们计算的百分比差距或。结果表明,平均比例差距加快和理论最低是4.72%。72.5%的40个测试实例百分比低于5%的差距。

是显示在表2,解决方案人均排放ton-kilometer通过拟议中的SA启发式接近下限。RAND5-8,某些情况下,如RAND5-4 RAND6-8, RAND7-1, RAND7-2, RAND7-4, RAND7-6, RAND8-1,启发式解决方案之间的差距和加快不到1%。所有40个测试实例,最大的百分比差距启发式解决方案,加快是14.20%,平均比例差距是2.79%。87.5%的40个实例百分比低于5%的差距。

值得注意的是,一个中央仓库的位置可能会影响比例差距。实例的百分比差距超过5%的中央仓库位于与区域的边界。

5.2。一个现实的实例

现实的实例研究的主要目的是评估的适用性发达启发式实际规模问题。

运输公司在中国的山东省,只是叫SDEXP,是我们计算研究的对象。SDEXP由山东省17个分支机构分布在17个城市(图1)。SDEXP雇用数以百计的单一机组卡车运输货物在2007年之前,山东省道路货运市场约1.25%的份额。随着政策鼓励和推广发行的牵引车和半挂车组合MOTPRC第11个五年计划时期(2006 ~ 2010),SDEXP计划逐步用牵引车和半挂车组合代替单一机组卡车。

我们抽象SDEXP的交通网络图,其中节点表示城市和弧表示每两个城市道路基础设施连接。假设任何城市节点可以被视为一个中央仓库和其他城市节点卫星设施。表3给出了每两个城市之间的距离。SDEXP预计货物流任意两个城市之间每天在表4。

拖拉机半挂车组合采用小规模的实例是用于现实的实例。假设加载因子loaded-semitrailer是50%;速度是80公里/小时;和需求满意的货物流的比例不小于80%。每100公里油耗是17升柴油拖拉机独自运行,40升柴油每100公里运行。跨越的距离是影响司机的值班时间。根据SDEXP的经验,一个司机的平均每天值班时间是8.5小时。拖拉机和两个司机可以连续工作不超过17.0小时24-consecutive-hour时期。卫星设备的附加/分离时间2/3小时,和中央仓库的停留时间是2个小时。。。

假设任何一个候选人的17个城市SDEXP仓库中部城市,有17个场景分类的中央仓库的位置。令人满意的解决方案在表17的场景5。当城市位于不同空间区域和各种货物流,分别被视为中央仓库,令人满意的解决方案的性能明显不同。我们使用“拖拉机数量”、“连续拖拉机燃油消耗的比例,”和“人均排放ton-kilometer”来分析解决方案的性能。

在一个近似的水平满足货运需求的比例,拖拉机的需要的数量大约是64不同的中央仓库位置和WH除外。拖拉机的平均数量是货运需求总量的1/4左右。

存在一个关系需要拖拉机的数量和平均loaded-semitrailer路线。由于loaded-semitrailers的数量是由满意运费的百分比决定需求,拖拉机数量越少(或路线号码),加载越半拖车的路线。当loaded-semitrailers的数量和跨越的距离决定,拖拉机数量越多,更多的燃料消耗的比例拖拉机单独运行。结果符合上述两个关系(图2)。SA启发式是稳定解决现实的实例。

根据开发的方法和因素政府间气候变化专门委员会(IPCC),排放燃料消耗成正比,所以排放的解决方案可以快递运输的可变成本。Escobar et al。43]和Hashemi Seifi [39)指出,运输成本往往决定的影响定位一个仓库,反之亦然。我们的结果显示一个类似的结论。中央仓库解决方案不同的城市有不同的每ton-kilometer排放。中央仓库附近城市研究中心的空间范围(例如,助教,LW, JNA,和ZB)有相对较好的解决方案。除此之外,城市中心仓库位于济青高速公路(JNA-ZB-WF-QD线)有良好的解决方案,包括更多的loaded-semitrailers路线和低水平的每ton-kilometer排放。事实上,交通经济带济青高速公路山东贡献了约40%的GDP和30%以上的山东公路货运量在最近的5年。这是暗示的ton-kilometer人均排放的解决方案不同的中央仓库的城市不仅由中央仓库的位置,而且影响交通流的经济关系。

评估的结果不同国家人均排放ton-kilometer。例如,Ierland et al。13)指出,卡车排放因子是155 g/荷兰t-km;欧洲环境局(44)指出,平均水平排放62 ~ 110 g在欧盟成员国/ t-km公路运输;李等人。3)指出,平均水平排放100 g之间波动/ t-km和132克/ t-km从1985年到2007年在中国。我们调查了一些2009年SDEXP点对点运输和发现排放因子从100克不等/ t-km 180克/ t-km,平均是135 g/ t-km。我们realistic-instance研究表明,提供的车辆调度TSRP承诺减少道路货物运输排放。

结果的有用和有意义的SDEXP选择中央仓库的位置,配置拖拉机和路线,以减少排放。

6。结论和未来的工作

本文讨论了拖拉机和半拖车路由问题和缓解的效果排放,承诺与应用程序在多级freight-related货运分布系统和整车道路减排。一个数学规划模型以最小化的目标人均排放ton-kilometer牵引车和半挂车的路由问题,提出了完整的卡车任何两个终端之间的网络。SA启发式提出解决这个问题的一个现实的大小。验证提出的启发式,设计的一个下界。启发式算法是测试不同类型的问题。结果表明,该启发式在合理的计算时间内提供高质量的解决方案。中央仓库位置的影响和货运流分布解决方案质量也是探索。总之,该算法可以提供健壮的解决方案。

对于未来的研究,它将会是很有趣的测试的效率和有效性提出TSRP模型及其在各种实例解决方案方法。一些有效的启发式TSRP也可以提出。此外,注意可以关注TSRP的扩展,例如,TSRP时间窗和TSRP车辆路径的其他货运配送系统的水平,这是至关重要的正确实用的可行性。

利益冲突

作者宣称没有利益冲突有关的出版。

承认

这项工作得到了国家自然科学基金的研究资助中国(没有。71202016)。这种支持。

引用

1. GFEI”,提高车辆燃油经济性在东盟地区,”2010年,http://www.globalfueleconomy.org/Documents/Publications/wp1_asean_fuel_economy.pdf。视图:谷歌学术搜索
2. a·c·麦金农和m . i Piecyk”测量有限公司₂排放的道路货物运输:回顾英国体验”,能源政策,37卷,不。10日,3733 - 3742年,2009页。视图:出版商的网站|谷歌学术搜索
3. h·李,y, j . Zhang和t . y . Wang”道路货运交通二氧化碳排放趋势和政策在中国,“能源政策57卷,第106 - 99页,2013年。视图:出版商的网站|谷歌学术搜索
4. d . y .林和k·h·Ng协作回程路由的影响在货运行业的碳减排,”交通研究D部分,17卷,不。8,626 - 628年,2012页。视图:出版商的网站|谷歌学术搜索
5. r . Banos j .奥尔特加·c·吉尔·A·费尔南德斯·托罗,“模拟annealing-based并行多目标的方法与时间窗车辆路径问题,“专家系统与应用程序,40卷,不。5,1696 - 1707年,2013页。视图:出版商的网站|谷歌学术搜索
6. x j . Zhang z s .他z,他和l . Rayman-Bacchus“概率路由策略无标度网络,”自然史一,卷392,不。4、953 - 958年,2013页。视图:出版商的网站|谷歌学术搜索|MathSciNet
7. g . Laporte“五十年的车辆路径”,交通科学,43卷,不。4、408 - 416年,2009页。视图:出版商的网站|谷歌学术搜索
8. r . Baldacci、p·托斯和d维哥”车辆路径的算法中的最新进展。”4、,5卷,不。4、269 - 298年,2007页。视图:出版商的网站|谷歌学术搜索|Zentralblatt数学|MathSciNet
9. y郭”,使用模拟退火,以减少燃料消耗时间的车辆路径问题,“计算机与工业工程卷,59号1,第165 - 157页,2010。视图:出版商的网站|谷歌学术搜索
10. l . Pradenas b Oportus,诉Parada”缓解温室气体排放与回程车辆路径问题,“专家系统与应用程序,40卷,不。8,2985 - 2991年,2013页。视图:出版商的网站|谷歌学术搜索
11. m .那个”应用程序的车辆路径问题,预告片吧,”欧洲运筹学杂志》上,2012年。视图:出版商的网站|谷歌学术搜索
12. h .问:李陆和y”,牵引车和半挂车运输对减少公司的影响₂在中国发射,”中国第七届先进交通论坛(AFTC 11),毛b . h, s . j .杨和l·l·杨。,pp. 232–237, The Institution of Engineering and Technology: Systems Science and Transportation Development, Beijing, China, 2011.视图:出版商的网站|谷歌学术搜索
13. e . v . Ierland c Graveland, r . Huiberts“环境经济分析的欧洲主要港口鹿特丹的新铁路,“交通研究D部分,5卷,不。3、197 - 209年,2000页。视图:出版商的网站|谷歌学术搜索
14. v . c . Hemmelmayr j . f . Cordeau, t . g . Crainic”一种自适应大型社区搜索启发式Two-Echelon在城市物流车辆路径问题,“电脑和运筹学,39卷,不。12日,第3228 - 3215页,2012年。视图:出版商的网站|谷歌学术搜索|MathSciNet
15. p c .流行,即卡拉和a·h·马克,“新的广义车辆路径问题的数学模型和扩展,“应用数学建模,36卷,不。1,第107 - 97页,2012。视图:出版商的网站|谷歌学术搜索|Zentralblatt数学|MathSciNet
16. c . Contardo诉Hemmelmayr, t . g . Crainic”低和上界two-echelon生产location-routing问题,“电脑与行动研究,39卷,不。12日,第3199 - 3185页,2012年。视图:出版商的网站|谷歌学术搜索|MathSciNet
17. i m .曹国伟”卡车和拖车的禁忌搜索方法路由问题,“电脑和运筹学卷,29号1,33-51,2002页。视图:出版商的网站|谷歌学术搜索|Zentralblatt数学
18. f . Semet和大肠Taillard”,解决现实生活中的车辆路径问题有效地使用禁忌搜索,“《运筹学第41卷。。4、469 - 488年,1993页。视图:出版商的网站|谷歌学术搜索
19. j . c . Gerdessen”与拖车车辆路径问题,”欧洲运筹学杂志》上,卷93,不。1,第147 - 135页,1996。视图:出版商的网站|谷歌学术搜索|Zentralblatt数学
20. m . Caramia和f . Guerriero牛奶不相容约束集合问题。”接口,40卷,不。2、130 - 143年,2010页。视图:出版商的网站|谷歌学术搜索
21. 朔伊尔,“卡车和拖车的禁忌搜索启发式路由问题,“电脑和运筹学,33卷,不。4、894 - 909年,2006页。视图:出版商的网站|谷歌学术搜索|Zentralblatt数学
22. k . c . Tan黄懿慧咀嚼,l·h·李,“混合多目标进化算法求解卡车和拖车车辆路径问题,“欧洲运筹学杂志》上,卷172,不。3、855 - 885年,2006页。视图:出版商的网站|谷歌学术搜索|Zentralblatt数学|MathSciNet
23. s . w .林诉f . Yu, s . y .周”解决卡车和拖车路由问题基于模拟退火启发式,”电脑与行动研究,36卷,不。5,1683 - 1692年,2009页。视图:出版商的网站|谷歌学术搜索|Zentralblatt数学
24. j·g . Villegas c·普林斯c . Prodhon A . l . Medaglia和n . Velasco”掌握的进化路径链接卡车和拖车路由问题,“电脑与行动研究,38卷,不。9日,第1334 - 1319页,2011年。视图:出版商的网站|谷歌学术搜索|Zentralblatt数学
25. j·g . Villegas c·普林斯c . Prodhon a . l . Medaglia n•贝拉斯科,“掌握/盾和多头进化的本地搜索单一卫星仓库、卡车和拖车路由问题”人工智能技术的工程应用,23卷,不。5,780 - 794年,2010页。视图:出版商的网站|谷歌学术搜索
26. s . w .林诉f . Yu, s . y .周“在卡车和拖车路由问题,“专家系统与应用程序,37卷,不。1,第903 - 899页,2010。视图:出版商的网站|谷歌学术搜索
27. s . w .林诉f . Yu, c . c . Lu”卡车和拖车的模拟退火启发式路由时间窗口的问题,“专家系统与应用程序,38卷,不。12日,第15252 - 15244页,2011年。视图:出版商的网站|谷歌学术搜索
28. 美国Derigs, m . Pullmann,沃格尔,“卡车和拖车路径问题,启发式和计算经验,“电脑与行动研究,40卷,不。2、536 - 546年,2013页。视图:出版商的网站|谷歌学术搜索
29. 诉Pureza、经纪人莫拉比托r、m . Reimann“车辆路径与多个毫无二致:VRPTW建模和启发式方法,”欧洲运筹学杂志》上,卷218,不。3、636 - 647年,2012页。视图:出版商的网站|谷歌学术搜索|Zentralblatt数学|MathSciNet
30. l·博丹a . Mingozzi r . Baldacci, m .球”rollon-rolloff车辆路由问题。”交通科学,34卷,不。3、271 - 288年,2000页。视图:出版商的网站|谷歌学术搜索|Zentralblatt数学
31. 美国Derigs, m . Pullmann,沃格尔,“短注意运用一个简单的LS / LNS-based metaheuristic rollon-rolloff车辆路由问题,“电脑与行动研究,40卷,不。3、867 - 872年,2013页。视图:出版商的网站|谷歌学术搜索
32. j .王寅,我。金,金,“rollon-rolloff废物收集和时间窗车辆路径问题,“欧洲运筹学杂志》上,卷224,不。3、466 - 476年,2013页。视图:出版商的网站|谷歌学术搜索
33. r . Baldacci l·博丹,a . Mingozzi”多个处理设施和多个库存位置rollon-rolloff车辆路径问题,“电脑和运筹学,33卷,不。9日,第2702 - 2667页,2006年。视图:出版商的网站|谷歌学术搜索|Zentralblatt数学
34. r·w·霍尔和v c . Sabnani”控制车辆调度循环路线货运服务终端,“交通研究部分,36卷,不。3、257 - 276年,2002页。视图:出版商的网站|谷歌学术搜索
35. ·弗朗西斯·g·m·张,k . Smilowitz”提高了建模和解决方法multi-resource路由问题,“欧洲运筹学杂志》上,卷180,不。3、1045 - 1059年,2007页。视图:出版商的网站|谷歌学术搜索|Zentralblatt数学
36. b . y . r . Cheng梁,m·h·周”的车辆调度优化钢铁工作基于半挂车运输、交换”中南大学的技术杂志》上,17卷,不。4、873 - 879年,2010页。视图:出版商的网站|谷歌学术搜索
37. 美国Derigs, r . Kurowsky,沃格尔,“解决一个实际的车辆路径问题有多个使用拖拉机和拖车和规章在航空货运司机引起公路支线服务,“欧洲运筹学杂志》上,卷213,不。1,第319 - 309页,2011。视图:出版商的网站|谷歌学术搜索
38. h·李,y, j . Zhang和t . y . Wang”解决牵引车和半挂车路由问题基于启发式方法,”数学问题在工程文章ID 182584卷,2012年,12页,2012。视图:出版商的网站|谷歌学术搜索|Zentralblatt数学|MathSciNet
39. d . s . h . Hashemi和a . Seifi”低和上界location-arc车辆容量约束路由问题,“欧洲运筹学杂志》上,卷224,不。1,第208 - 189页,2013。视图:出版商的网站|谷歌学术搜索|MathSciNet
40. 美国Almoustafa、美国哈纳菲和n . Mladenović”新的精确方法对于大型非对称distance-constrained车辆路径问题,“欧洲运筹学杂志》上,卷226,不。3、386 - 394年,2013页。视图:出版商的网站|谷歌学术搜索|MathSciNet
41. o . Braysy和m . Gendreau”有时间窗车辆路径问题,第一部分:路线建设和局部搜索算法,”交通科学,39卷,不。1,第118 - 104页,2005。视图:出版商的网站|谷歌学术搜索
42. l·c·科埃略,j . f . Cordeau g . Laporte”在多车inventory-routing一致性。”交通研究C部分,24卷,第287 - 270页,2012年。视图:出版商的网站|谷歌学术搜索
43. r . j . w . Escobar Linfati, p .托斯”的两阶段混合启发式算法生产location-routing问题,“电脑与行动研究,40卷,不。1,第79 - 70页,2013。视图:出版商的网站|谷歌学术搜索|MathSciNet
44. 欧洲环境局运输crossroads-TERM 2008:指标跟踪运输和环境在欧盟,”技术代表、办公室官方出版物欧洲经济共同体,卢森堡,2009。视图:谷歌学术搜索

版权

版权©2013李红旗等。这是一个开放分布式下文章知识共享归属许可,它允许无限制的使用、分配和复制在任何媒介,提供最初的工作是正确引用。