多个仓库的车辆路径问题的背景下,城市交通总量平衡

文摘

multidepot VRP是解决城市交通总量平衡的上下文中。总交通均衡下,multidepot VRP改为GDAP(分组的问题客户+估算OD流量+分配流量)和二层规划用于模型问题,上层模型的地方决定了每个卡车的客户访问和还说卡车去最初的OD(出发地/目的地)旅行,和较低的模型分配道路网络的OD出行。上层模型和较低的模型之间的反馈是遍历OD出行;因此总交通平衡可以模拟。

1。介绍

VRP是一个通用的名称指的是一类组合优化问题中,许多车辆服务客户。车辆离开仓库,服务客户的网络,并返回到仓库完成后的路线。Dantzig和公羊(1959)首次提出这个问题在文献中。VRP通常定义为一个图表 ,在那里 顶点的集合; 电弧集;和 是一个成本矩阵定义结束了吗 ,代表距离,旅行时间,或者旅行费用。VRP在于找到一组路线基于相同的车辆仓库(s),这样每一个顶点是访问一次,同时最小化整个路由成本。

旅游费用(VRP)是一个决定性的影响因素。在早期研究车辆路径问题(1),车辆旅行时间是计算两个节点之间的欧几里得距离(客户或仓库)和一个给定的速度。所有已知的,它不是一个合理的方式使用欧氏距离来计算两个节点之间的旅行时间为实际的车辆路径问题由于道路和时变交通状况的非线性特性。后来,一些研究人员,以满足实际需求,通过对道路网络的最短路径旅行时间代表了成本。后意识到在一个城市道路网络交通流量的变化可能会改变的最短路径,因此两个站点之间的旅行时间,采用动态最短路径上的旅行时间旅行成本,和两个站点之间的旅行成本动态计算相应的时间窗口。

目前,基于局部交通平衡,一些研究计算动态最短路径旅行时间交货时间窗。例如,近年来,一些工作(2)被认为是城市道路网络的实际交通状况真实的车辆路径问题。他们认为,在城市道路网络的交通状况是由其他车辆的OD流量,但不运载工具本身和运载工具会选择路径基于其他车辆的流量平衡。这个方法是理性的运载工具时少量及其对道路的影响可以忽略。然而,如果大量运载工具,和他们的交通可能会影响其他车辆使他们中的一些人改变他们的出行路径,该方法不能得到真正的旅行时间。结果,实际的最优回路/路径旅行时间下局部平衡不能获得(本文循环意味着客户访问序列,和路径意味着序列通过一辆卡车在道路网的链接)。

当仓库的位置/设施和仓库之间的流动和设施需求是稳定的,VRP应该解决静态(先天),而动态。在这种情况下,运输卡车的路由行为类似于其他车辆。同时考虑到交通状况。例如,运输卡车将选择更少的道路交通、和其他车辆可能远离交通的道路严重影响交货和卸载卡车旅行。这意味着道路上的所有车辆和交通流之间的相互作用存在,结果从所有司机的选择自己的道路。然后,对道路旅行时间由链接的能力和相应的交通流量。此外,由于不同的VRP计划将导致不同OD流量的送货卡车,交付回路/路径也与城市交通OD。因此,可以说,交付回路/路径,得到在假设其他车辆不受运输卡车,没有针对实际情况进行了优化。

当运输卡车对道路交通的影响不容忽视,VRP应该被视为一个交通问题在宏观层面而不是在微观层面的物流问题。然后,我们必须从视图设计交付回路/路径交通总量的平衡,即考虑到所有车辆之间的交互。

在现实世界中,运输卡车的现象不影响道路交通在城市已经消失,因为(1)道路容量在大多数大城市(尤其是中国)在临界点一些额外的车辆可能会导致严重的拥堵在某些道路,进一步导致整个城市道路交通模式的变化和(2)快速发展电子商务改变公民的购物行为。网上购物减少个人旅行但增加运货卡车交通。目前,运输卡车已经成为整个城市交通的重要组成部分,如图1(一)和1 (b)。

由于上述原因,VRP问题不仅仅是分配客户送货卡车和旅行路径基于给定的OD流量。应该考虑一个交付和其他车辆作为一个整体,研究他们的路径选择行为。因此,应该采取运输卡车和其他车辆之间的相互作用考虑直接因为交付计划将会改变OD出行道路交通,而OD出行和道路交通反向确定VRP方案。这是一个解决方案的VRP总交通平衡的方法。在这里,“总”交通平衡意味着运输卡车和其他车辆之间的相互作用被认为是直接的。在“总”用户均衡,运输卡车和其他车辆都愿意改变自己的出行路径。

因此,在总交通平衡方面,VRP变得GDAP(分组问题客户+估算OD流量+分配流量),其中“分组客户”是指客户的工作分配给不同的仓库,然后multidepot VRP是解决变成一群single-depot VRP;估计OD流量是指作品的旅行连锁配送卡车被添加到给定的 ;交通分配是指作品更新的OD矩阵被分配到路网。其数学描述显示为

我们认为,交付计划(即是服务于客户的卡车和旅行路径)应该同时解决三个方程得到的。这里,第一个方程是VRP模型,第二个方程是交通分配模型,第三个是连锁的方法把运货卡车旅行到OD矩阵。

我们可以使用上面的二层规划模型问题,运输卡车和其他车辆之间的相互作用。上层模型决定了每辆运货车里面的客户访问和每辆运货车里面的路径,然后我们把这些运输卡车OD旅行到最初的OD矩阵,和较低的模型是一个交通分配模型,发现路径的所有车辆。LM和之间的交互迭代更新OD。因此,总交通道路网络的平衡可以模拟和回路/路径的运输卡车可以在收敛的输出。

剩下的纸是组织如下。节2,我们执行一个文献回顾总结现有的研究,特别是发现他们的缺点。节3和贡献,我们国家的想法。节4,我们的模型结构GDAP算法和设计解决方案。节5,我们做的一个案例研究演示解决方案交付模型的使用过程和结果数据的海洋产品在大连(中国)。节6,我们总结研究,考虑未来的研究。

2。文献综述

2.1。研究蚁群

在过去的三十年里,学术出版物的数量众多的变体的VRP增加了广泛3),包括发展的简要回顾VRP出版于2009年(4]。

Dantzig和公羊后(1959),相当数量的变异VRP的研究,包括(1)VRP硬,柔软,和模糊服务时间窗口(VRPTW);(2)VRP考虑回程(VRPB);(3)VRP考虑最大路径长度(DVRP);(4)定期VRP (PVRP);(5)VRP与多个旅行(VPRMT);(6)分裂配送车辆路径问题(SDVRP)等;(7)VRP最小化排放(5]。Montoya-Torres et al。6]说明VRP变异与图的层次结构2。根据他们的说法,最令人印象深刻的增长的VRP研究是观察到的2006年至2014年间共有103出版物。

因为许多变体的VRP是np难问题,许多研究人员提出解决方案的算法。例如,克拉克和赖特(7)提出了解决Clarke-Wright算法在1964年,这是第一个解决multidepot VRP (MDVRP)一个启发式算法。Cordeau et al。8)描述了一种“禁忌”MDVRP搜索算法。模拟退火(SA)已被吴工作以及解决VRP et al。9];Yu et al。10)提出了一种改进的蚁群优化粗粒度的并行策略,ant-weight策略,MDVRP和变异操作;比达尔et al。11)提出了一个算法框架,成功解决三个车辆路径问题:multidepots VRP,周期性的蚁群,和multidepots周期性VRP;Martonak et al。12)提出了细胞自动机实时蒙特卡罗的对称量子退火方案旅行推销员问题;Crispin和Syrichas13]量子退火算法申请VRP研究量子退火的有效性。Polacek et al。14社区搜索MDVRP]使用变量。Yu et al。15]解决了MDVRP时间窗的两阶段启发式方法。更详细的VRP解算法的文献提出了Montoya-Torres et al。6];林等。16];王等人。17];和Zhang et al。18]。

目前,解决VRP不仅是重要的配电系统的设计在供应链管理,但同样重要的城市固体废物收集、街道清洁,校车路由、路由的销售人员,和快递服务。研究大致可以分为理论论文提供数学公式和精确或近似解的方法和case-oriented论文学术问题。最近,注意力一直致力于更复杂的VRP的变体(通常被称为“富裕”VRP)比经典VRP模型更接近实际分布问题。

也有文献将蚁群在现实背景下考虑旅行时间的动态城市道路网络,因为在城市旅游的速度(或时间)通常白天由于不同堵塞模式上的差异。Malandraki和Daskin19]介绍了混合整数线性规划公式TDTSP和TDVRP将旅行时间函数作为一步的功能。时间旅行时间的一个主要挑战是城市货物车辆路线优化的动作。例如,Ichoua et al。20.)提出了一个模型基于时间旅行速度满足nonpassing属性。Polimeni和Vitetta21)和Cattaruzza et al。22)研究时间方法和认为成本还取决于时间的联系。实际上,对传统动态蚁群,旅行时间的关系被认为是不同的在不同的时间窗口,然后将任务分配给卡车。送货卡车和其他车辆之间的相互作用还没有直接考虑。

谷口和山田23]研究了车辆路径和调度程序使用先进的信息系统和货物运输系统在城市地区。安藤和伊藤24)研究了车辆路径行程时间可靠性的基础上获得的数据探测车辆。康拉德和Figliozzi25]提出交通排队算法和抵达和起飞时间算法量化拥堵时间真实的城市货运的影响分销网络;Deflorio et al。26]应用性能指标比较不同的服务设置,介绍了模拟方法构建的需求;Munuzuri et al。27)认为,模拟城市货物运输是困难的和高度data-demanding并提出一次生成模型实现货物运输的一个叫做矩阵估计一个城市。

内et al。28VRP)引入了一个新的变种,即两级弧时间窗车辆路径问题,通常出现在土耳其军用和民用运输。他们把网络分为三层(工厂、仓库和客户)(即连续和路由操作分为两层。facility-depots和depots-customers之间)。唐et al。29日)提出了VRP模型主题旅行时间可靠性约束。曼奇尼[30.)考虑高峰时段交通拥堵和解决VRP道路上一个真正的网络时间旅行速度由多项式函数表示。尽管困难与这些类型的函数,这种方法更精确地代表拥挤演化行为。然而,这项研究的实际旅行时间计算基于局部交通道路网络平衡不考虑之间的交互直接交付卡车和其他车辆。Chiabaut et al。31日]介绍了一个通用方法预测和评价城市物流的影响在全球运输网络的性能。

现实世界的应用蚁群通常包括两个重要的维度:进化和质量的信息32]。进化与这一事实有关的信息在某些问题的信息规划的执行期间可能会改变路线。质量信息的反映可能的可用数据的不确定性。此外,根据问题和可用的技术,车辆路线可以是静态(先天)或动态设计。

在真实的应用程序中,静态设计更重要的是当层之间的VRP是仓库和设施。在一个小的时间内(如一个月或一个季度),空间分布的仓库/设施,仓库和设施之间的需求流动的城市固体废物收集、街道清洁,校车路由、路由的销售人员,和快递服务可能很难改变。因此一个交付计划可能被用于整个季度或月。这类似于公共汽车交通服务,每日个人旅游需求是相对稳定的,每天公交线路的重新设计和动态调度的公交车一小时并不是必要的。

2.2。研究其他车辆之间的相互作用和交付卡车

谷口et al。33)考虑背景流量和之间的交互的服务卡车物流终端定位终端。他们使用了二层规划模型,上层问题描述的行为计划总成本最小化。低水平的问题描述的行为,每个公司,每个卡车在选择最优物流终端和运输路线。模型明确地考虑网络中交通状况,并成功地应用于一个实际的道路网络Kyoto-Osaka地区在日本。他们只处理定位问题不是VRP问题,因为每个服务卡车运行终端之间只有一个仓库。

谷口的研究人员小组还采用二层规划模型集成供应链网络(SCN),交通网络(TN)的流量平衡。其中,山田et al。34)提出了一个战略运输规划模型设计区际货运TN和货运站发展。低水平是一个多通道多类用户流量分配模型,而行动的最佳组合,在上层问题,确定。山田et al。35)提出了一个供应chain-transport超级网络平衡(SC-T-SNE)模型,六entities-manufacturers的行为,批发商,零售商,货运公司,需求市场,TN用户解释。与TN的行为用户包括送货卡车被合并,该模型允许从内部确定运输成本基于货运公司的决策,以及调查行为变化之间的相互影响在视交叉上核和TN。值得注意的是,交通状况的影响在道路网络实体的行为在每个研究视交叉上核,反之亦然。山田和Febri36)进一步提出了一个离散网络设计问题,假设的SCN-TN交互。他们开发了一万亿年平衡约束的离散优化模型。他们的研究主要是网络规划问题(即。,facility location, link construction) with equilibrium constraints, rather than delivery management. With the OD of TN users, the same as the OD of goods, the truck path choice behavior differs from that in VRP where delivery loop of a truck is a trip chain. Thus, with the same equilibrium constraints, the key issues and model structure are different.

3所示。动机和贡献

当仓库的位置/设施和仓库之间的流动和设施需求是稳定的,VRP应该解决静态(先天),而动态。在这种情况下,运输卡车的路由行为类似于其他车辆。同时考虑到交通状况。例如,运输卡车将选择更少的道路交通、和其他车辆可能远离交通的道路严重影响交货和卸载卡车旅行。这意味着道路上的所有车辆和交通流之间的相互作用存在,结果从所有司机的选择自己的道路。然后,对道路旅行时间由链接的能力和相应的交通流量。此外,由于不同的VRP计划将导致不同OD流量的送货卡车,交付回路/路径也与城市交通OD。因此,可以说,交付回路/路径,得到在假设其他车辆不受运输卡车,没有针对实际情况进行了优化。

当运输卡车对道路交通的影响不容忽视,由于反复出现拥堵和复杂的电子商务商业模式(37),VRP问题应该被视为一个交通问题在宏观水平上而不是在微观层面上的物流问题。然后,我们必须从视图设计交付回路/路径交通总量的平衡,同时考虑到所有车辆和交通之间的交互生成/景点交通区。

在这项研究中我们的贡献如下。

(1)根据总交通均衡分配,将multidepot VRP转换为GDAP(分组的问题客户+估算OD流量+分配流量)的运输卡车和其他车辆之间的相互作用考虑获得交付计划在“总交通平衡。”

(2)解决GDAP上下两层的模型。基于反馈回路的“分组的问题客户确定运送路线-更新OD流量分配OD流量——重组…,“首先客户分为几组和第二组的交付回路/路径获得最初的OD矩阵更新,第三链接的流量计算用户均衡交通分配模型。

(3)在大连开展案例研究与实际数据审核方法和提供一些有用的结果。

(4)评估交付基于不仅计划交货时间也整个道路网的交通状况。

4所示。模型结构

4.1。模型的假设

(A1)研究区域包括连续但不重叠的交通区域,车辆的OD出行除了运输卡车不改变,但起源和目的地之间的路径都不是固定不变的,这将决定基于问题的理论。(A2)每个客户的需求。(A3)仓库的供应数量足够大。(A4)交付循环的长度短于卡车的最大范围。(A5)所有的运输卡车都是一样的类型,与给定的载荷能力。(A6)装卸次交货将被忽略。(A7)每辆车一个卡车相当于3单位。(A8)司机知道道路和尽量选择的旅行时间最短路径。

4.2。上面的模型

变量定义如下: :所有的总交货时间交付卡车th轮分组,即上层模型的客观价值; :0 - 1变量, 意味着车辆通过路径- - - - - -在th轮分组;它是决策变量确定送货卡车的路线,并进一步整个配送网络;是决策变量,它决定了运输卡车的OD出行,两个客户之间的路径将通过降低模型中的问题; :其他车辆的的起源; :的运输卡车的起源(仓库或客户); :所有车辆的的起源, ; :的目的地其他车辆; :的目的地送货卡车(仓库或客户); :的目的地所有的车辆, ; :运货车的设置; :卡车的旅行时间从来在th轮分组; :客户的需求j; :负载能力的卡车k; :从站点交付路径的长度网站j; :的一辆卡车范围最大的旅行; :在仓库送货的卡车的数量r; :(0 - 1)变量, 意味着路径- - - - - -通过链接在一轮的分组。

上面的模型如下:

方程(2)是目标函数,最小化总交货时间,包括旅行时间的卡车;(3)确保交付循环的总需求客户应小于运货卡车的容量;(4)确保一个循环的长度(即交付卡车)的旅行距离应该短于其最大旅游范围;(5)确保运输卡车的时间从仓库开始并返回仓库是相同的,这是0或1。它确保卡车从仓库,最后回到相同的仓库;(6)意味着为每个客户只有一个车从仓库或另一个客户是可用的。确保客户的需求应该由只有一个卡车;(7)确保卡车的数量从每个仓库( )应小于可用的;(8)确保仓库之间的卡车不旅行;(9)是0 - 1变量;(10)代表之间的最短旅行时间仓库和客户或两个客户。

实际上,用于描述道路网络的交通流量。它是获得较低的模型;是交付的OD旅行卡车。它是输入较低的模型。

4.3。较低的模型

使用的变量定义如下: :客观价值,旅行时间的总和所有链接; :旅行时间在联系在th一轮任务; :交通流在链接在th轮任务; :对道路交通流之间的 在th一轮任务; :交通流之间 在th一轮任务; :(0 - 1)变量,如果链接在路径从来在的th一轮任务,是1,否则为0; :自由流动的旅行时间链接一个; :参数(这里 , )。

较低的模型如下:

方程(11)是目标函数;(12),(13)和(14)流约束,确保交通流不应消极保护和满足流。方程(15)是性能函数的联系;(16)是(0 - 1)变量。

5。模型的解决方案

通过迭代计算模型可以解决“分组客户→确定交货计划→改变OD矩阵→分配OD流量→重组客户→⋯。“在这里我们使用网络图3“1 - 5”、“6 - 8”,分别代表客户和仓库,作为一个例子来解释这个解决方案的方法。

5.1。优化配送方案

我们优化固定链接上下文的交付计划的旅行速度multidepot VRP的通用算法(GA)。首先,multidepot VRP转化为几个single-depot VRP通过分组的客户。由于分组,客户集群形成的类型。其次,几个交付计划,分别了好几套single-depot vrp,对应设计客户集群的类型。最后,一群的最佳交货计划single-depot vrp发现通过比较相对应的目标函数的值客户集群的类型。

分组如下工作。

步骤1。计算TMij和TQij从3仓库5客户获取旅行时间向量;为客户j,它是(TM6j,TM7j,TM8j,TQ操作6j,TQ操作7j,TQ操作8j]。

步骤2。找到最小TMij每个客户的j。

步骤3。比较最低的客户与和 ,如果 和 ,然后客户是由仓库6(组1)。否则,分配客户组4,这个集团的仓库为客户尚未确定。

步骤4。分配的客户组4组1 - 3通过枚举方法,和获得l客户集群的类型,例如,类型1:得宝6(客户1、2),得宝7(客户5),和仓库8(客户3、4);类型2:得宝6(客户2),得宝7(客户1、5),仓库8(客户3、4)。
在这里, , 从仓库的最短旅行时间吗对客户的情况下是否考虑运输卡车的影响分别链接的速度旅行,。

交付方案优化如下。

计算年代的所有集群组和比较年代选择最少的价值获得相应的交付计划。的步骤如下。

步骤1。代码和生成初始种群,即车辆路线。

步骤2。检查每个根据约束的可行性。

步骤3。可行的个体,计算他们的健康。

步骤4。执行选择和变异操作。

第5步。确定终止计算。

步骤6。执行交叉和变异操作,并返回到步骤2。

对于每个步骤,详细计算如下。

(1)染色体的设计。设置初始人口规模的可行的解决方案并生成初始种群染色体的如下:

客户在组1 (a)计数th集群类型的分组 ,和随机生成一个数组(组1)组1的客户。

(b)确定仓库6的插入的ID 然后将“6”插入数组1次随机获得一个新的数组(组2)。

(c)“6”添加到数组的头和结束2确保卡车开始和返回仓库6。得到最终的阵列组1(3)数组。

(d)重复上述工作组2和组3。

(e)组的最后阵列组1、2和3依次获取个人设置的初始种群。通过这种方法,个人设置初始种群的产生。

例如,初始种群是由自然编码方法编码,并且每个染色体编码由三个基因片段(基因段1段2段3)基因,也代表组织的代码1,2和3,分别。在染色体中[6 2 1 6 7 4 7 8 3 8 5 8],(6 2 1 6)基因片段1表示,一辆卡车从仓库6依次交付货物到客户2和客户1;7 (7 - 4)基因片段2表示,一辆卡车从仓库7日交付货物客户4并返回到仓库7;(8 3 8 5 8)基因段3代表第一个卡车从仓库8交付货物到客户3并返回仓库8第二卡车货物从仓库8提供客户5并返回仓库8;这就是为什么在这条染色体,8号出现两次。

(2)健身计算。通过计算适应度值(2)。

(3)选择算子。轮盘赌方法用于选择操作基于健身价值 。首先,计算概率 每个染色体;(2)计算累积概率 每个染色体;(3)生成一个随机数 ;如果 ,选择染色体1;如果 ,选择染色体 。

(4)交叉操作。执行交叉在同一基因片段。带染色体——[6 2 1 6 7 4 7 8 3 85染色体B - 8]和[6 2 1 6 7 3 7 8 4 5 8]为例。首先,删除每个配送中心的数量和获得染色体A1 -(1 2 3 4 5)和染色体B2 - (1 2 3 4 5)。其次,确定两个过境点(强调基因位点)。接下来,这两个点之间的基因交换获得染色体A2 - [2133 5]和染色体B2 - [2144 5]。然后改变重复数到失踪数获得染色体A3 -(1 2 3 4 5)和染色体B3 - (1 2 3 4 5)。最后,添加的数字,它代表了配送中心,到原始位置获得染色体A4 -[6 2 1 6 7 3 7 8 4 8 5 8]和染色体B4 - [6 2 1 6 7 4 7 8 3 5 8]。

(5)变异算子。执行一个在同一个基因突变部分,例如,染色体——[6 2 1 6 7 4 7 8 3 858]。首先,确定一个突变点(强调基因位点)。接下来,突变点会变成这组的另一个客户号,[6 2 1 6 7 4 7 8 3 838]。然后,改变重复数到失踪的人数,然后获得[6 2 1 6 7 4 7 85838]。

5.2。OD矩阵估计需求(更新)

确定OD出行运输卡车的基于最优分组模式,然后添加运输卡车的OD出行前OD矩阵。

5.3。分配流量

Frank-Wolfe (FW)方法用于解决模型越低,这是一个普通用户均衡交通分配模型,如下所示。

步骤1(初始化)。集 , 全有全无分配法,获得一组可行流 ,并设置 。

第二步(link-impedance更新)。集 。

步骤3(测向)。全有全无分配法重复与 额外的链接流 。

步骤4 (move-size决心)。解决 获得 。

第五步(更新)流动。一个人 。

步骤6(收敛判断)。如果 ( :一个给定的阈值),停止计算和输出 。否则,设置 ,转到第2步。

本文提出了主模型(上一个)来描述蚁群。上层模型的决策变量 ,这是有限的和离散。在这种情况下,最优解必须存在。实际上,只有降低模型的独特性可以证明(38),而无法保证上层模型的独特性。

6。案例研究

6.1。需要的数据

零售交付的水产品在大连西岗区(中国)用于案例研究。如图4(一)有四个仓库,27日零售商(客户)。27个客户的日常需求表中列出1。交付,水产品和冷保持材料(如冰箱,冰,和海水)必须装载运输卡车;因此,卡车的实际能力(额定)是0.35 t (1 t)。

研究区域分为31个交通区(图4(一)),道路网络图所示4 (b)。其他车辆OD出行矩阵在时间7:30-8:30来自个人旅行调查2011年大连。分配初始公路网OD矩阵,我们可以得到初始链接流和旅行时间 。

6.2。解决方案分析

优化模型的解决方案,即交付计划在总交通平衡,如图5(一个)由不同的卡车/仓库,客户服务是说明了不同形状和颜色的点,分别。所有交付卡车的行驶距离109.7公里和相应的旅行时间是329.1分钟。图5 (b)显示了交货计划交付卡车和其他车辆之间的相互作用时不考虑,即局部交通均衡下的交货计划。在这种情况下,运输卡车的总旅行距离94.8公里,总旅行时间是425.2分钟。虽然计划的距离在总交通均衡长15.7%,它的旅行时间缩短29.2%。因此,我们不能说下的方案获得了部分交通平衡是真正的最优的和不应采用真正的工作。

说明了模型的有效性,我们设置一些场景通过改变OD矩阵和运输卡车的数量,然后分别做敏感性分析。对于构建场景,我们调整车辆OD出行矩阵大连2011年( 一步= 0.2)和运载工具的数量乘以( 步骤0.2)。然后,我们使用 最初的OD流量和 次运输卡车的测试模型,并给出结果,分别。重叠率比较指标(17)的交付回路/路径,这意味着交付循环交通卷的敏感性,和客户不改变服务仓库的比例(18),这意味着交通卷组的敏感性,和总旅行时间()的运输卡车。

指数图所示6。当 或 , 和 。可以看出,交货计划的总交通均衡分配的情况下自由流动的流量是一样的。在这三个案例(即 ,0.2,0.4),总旅行时间()的运输卡车几乎没有变化,运输卡车的回路/路径是完全相同的。

当 , , 。这意味着交付回路/路径的总交通均衡分配的情况下自由流动的流量是不一样的。举个例子,我们可以看到不同的交付回路/路径从仓库1到客户21。总交通均衡的路径的长度较长(2.58公里,图中粗线7 (b)),而路径的长度最短的道路距离一样(旅行时间最短的路径,因为网络是在自由流动情况下)较短(2.34公里,图中粗线7(一));然而,旅行时间13.6分钟,15.3分钟,分别。

当 , , , 和 。在这种情况下,一些客户可能会改变服务仓库。例如,当 、客户8是由仓库3(红色实线在图8),而这是由仓库1路在最短的距离方法(蓝色虚线图8)。总交通均衡下的路径的长度较长(4.4公里),而路径的长度最短的道路距离短(3.0公里)。然而,旅行时间是15.4分钟,17.3分钟,分别。

当 , , , ,和保持不变( 和 )。可能是因为所有的道路已经达到饱和,和司机不能减少旅行时间通过改变路径。虽然之后 送货卡车不改变他们的旅行路径,其总旅行时间()增加得更快。因为在饱和巷道V / C(体积/能力)比率大于1和道路阻抗成指数增加的比例。

基于上述分析,我们可以了解到,交付计划在总交通平衡随着交通量的变化改变。在自由流动的情况下,卡车沿着回路/路径最短旅行距离(或时间)。随着交通量的增加道路距离最短的路径可能不是用最短旅行时间。根据拥塞度,可能成为其他路径最短旅行时间的。因此,交付计划在总交通平衡实用。

此外,交通运输卡车也可以改变其他车辆的旅游行为。为了说明这一点,我们设置一些场景通过设置OD矩阵的其他车辆 和运载工具的数量乘以( 步骤0.2)。然后我们解决了每个场景的模型。

结果如图所示9。可以看出,与其他车辆旅行时间积极与自己的旅行和运输卡车的数量。

在许多中国大城市,为了管理交通,卡车被禁止在早晚上下班高峰时间旅行。在图的信息9,一个城市可以更有效地管理交通的卡车禁止。例如,如果设置25分钟的临界点的平均旅行时间旅行,然后我们得到以下三个分析。

案例1。它是绿色的点在图9,在那里 和 。相应的平均旅行时间是23.9分钟(少于25分钟);因此,没有必要禁止运输卡车的高峰。

例2。这是蓝色的三角形图9,在那里 和 。相应的平均旅行时间是26.4分钟(大于25分钟)。在这种情况下,如果送货卡车禁止出行高峰,所有其他汽车旅行的平均旅行时间将减少到22.3分钟(正确的黑色点如图9),它显示了禁止的有效性和必要性。

例3。红场图9,在那里 和 。相应的平均旅行时间是45.1分钟(远远大于25分钟)。在这种情况下,如果送货卡车禁止出行高峰,所有其他汽车旅行的平均旅行时间将减少到40.6分钟(左边的黑色点如图9),也比25分钟。因此,我们可以说,它不是非常必要禁止运输卡车,因为微小的影响。

此外,与基于局部交通计划平衡可能恶化整个路网的服务水平,造成严重的交通拥堵,因为有些道路在配送路径可能已经大量的交通饱和,和一些运输卡车可能导致严重的交通拥堵。图10显示交付卡车对道路交通的影响。基于VRP计划交付完成后部分交通均衡分配,拥挤在链接1,链接2,和链接3恶化(图10 ())。如果交付是基于交货计划总交通均衡下,拥挤不会发生在链接1、链接2,连接3和整个网络上的交通流更加平衡。它表明,我们的方法是更现实的和有用的,因为它完全使用道路网络。

此外,结果还表明,在总平衡旅游流的情况和旅行速度链接2 1699 pcu /小时和13.4公里/小时。然而,在局部平衡的情况,相应的数字是1746 pcu / h和12.5 km / h,分别。它证明,没有考虑到他们,更多的运输卡车将选择链接2,这将会更加拥挤的运输卡车后加入。因此,局部均衡下的最短路径是假的。

在计算时间方面的解决方案,对部分流量平衡法是13秒和总的流量平衡法是256秒(杯:Core i5, 1.5 G)。很明显,模拟之间的交互之间的所有车辆和交付计划和OD旅行,迭代计算应该做;因此我们的方法计算成本更多时间解决方案。然而,由于GDAP不是一个动态问题,但之前模拟交通总量的平衡与上下两层的模型和不需要实时计算,计算速度和效率并不重要。

7所示。结论

在本文中,我们改变multidepot VRP GDAP,这是另一种方式的设计路线multidepot VRP然后造型城市货物运输。GDAP提出了二层规划模型,和所有车辆的路径选择行为之间的互动和交付计划和OD出行矩阵之间的交互可以模拟。然后multidepot VRP的解决方案是通过混合分组方法,遗传算法,沃尔夫算法。交付方案输出从模型是在总交通平衡,因此是现实的,它可以充分利用道路容量和平衡交通流在整个网络。

与部分交通均衡下的解决方案相比,总交通均衡下的解决方案不仅能缩短交货时间,还有助于避免交通拥挤的道路上接近饱和。为优化MDVRP上下两层的模型具有良好的适应性。可以用它作为进一步研究的参考组合优化问题。

我们建议做进一步的研究的新方法与其他方法比较真实的生活情况。也可以做更多的研究对算法的情况下,装载在卡车不是常数。

方法的限制,(1)很难得到其他车辆的OD;(2)遗传算法无法保证全局最优解决方案的交付计划。

的利益冲突

作者宣称没有利益冲突。

确认

这项研究支持的中国自然科学基金重点项目(批准号71431001),中国青年自然科学基金项目(批准号71402013),人文和社会科学青年基金会中国教育部(14 yjc630010)。

引用

1. n . a . El-Sherbeny和a·纳赛尔”与时间窗车辆路径:准确的概述,启发式和metaheuristic方法,”沙特国王大学——科学杂志》上,22卷,不。3、123 - 131年,2010页。视图:出版商的网站|谷歌学术搜索
2. b她、美国Gnutzmann和e . Sandvoss”基于在线交通信息的动态车辆路径”,交通科学,38卷,不。4、420 - 433年,2004页。视图:出版商的网站|谷歌学术搜索
3. r . Lahyani m . Khemakhem, f . Semet”丰富的车辆路径问题:从分类定义,“欧洲运筹学杂志》上,卷241,不。1、1 - 14,2015页。视图:出版商的网站|谷歌学术搜索|MathSciNet
4. g . Laporte“五十年的车辆路径”,交通科学,43卷,不。4、408 - 416年,2009页。视图:出版商的网站|谷歌学术搜索
5. m . Figliozzi”排放最小化车辆路径问题,”交通研究记录,没有。2197年,页1 - 7,2010。视图:出版商的网站|谷歌学术搜索
6. j . r . Montoya-Torres j·l·佛朗哥,s . n . Isaza h . Felizzola吉梅内斯,和n . Herazo-Padilla”的文献综述与多个仓库,车辆路径问题”计算机与工业工程卷,79年,第129 - 115页,2015年。视图:出版商的网站|谷歌学术搜索
7. g·克拉克和j·莱特”,调度车辆从中央仓库交货地点,”OperationResearch,12卷,不。4、568 - 581年,1964页。视图:谷歌学术搜索
8. j . Cordeau m . Gendreau和g . Laporte”禁忌搜索启发式周期和multi-depot车辆路径问题,“网络,30卷,不。2、105 - 119年,1997页。视图:出版商的网站|谷歌学术搜索
9. c . t . Wu低,j·巴姨,“启发式解决multi-depot location-routing问题,“电脑与行动研究卷,29号10日,1393 - 1415年,2002页。视图:出版商的网站|谷歌学术搜索
10. z z . b . Yu Yang, j . x谢”并行改进蚁群优化multi-depot车辆路径问题,“运筹学学会》杂志上,卷62,不。1,第188 - 183页,2011。视图:谷歌学术搜索
11. t·维达尔t . g . Crainic m . Gendreau n . Lahrichi和w·丽,“混合遗传算法对multidepot和周期性车辆路径问题,“运筹学,60卷,不。3、611 - 624年,2012页。视图:出版商的网站|谷歌学术搜索|MathSciNet
12. r . Martonak g . e .澳网,e . Tosatti“量子退火的旅行推销员问题,”物理评论E,卷70,不。5第2部分,文章ID 057701, 2004。视图:谷歌学术搜索
13. a . Crispin和a . Syrichas“量子退火算法进行车辆调度,”学报2013年IEEE国际会议系统,人,和控制论,SMC 2013英国,页3523 - 3528年,2013年10月。视图:出版商的网站|谷歌学术搜索
14. m . Polacek r·f·哈特尔k . Doerner和m . Reimann”附近一个变量搜索多得宝与时间窗车辆路径问题,“杂志的启发式,10卷,不。6,613 - 627年,2004页。视图:出版商的网站|谷歌学术搜索
15. b . Yu, p·h·金和z z,“两阶段启发式方法求解多中心和时间窗车辆路径问题,“系统工程理论与实践,8卷,不。32岁,1793 - 1800年,2012页。视图:谷歌学术搜索
16. c . c .林j·r·康w . y . Liu和c·c·李,“双门三维容器包装问题在送货上门服务,“亚太运筹学杂志》上,28卷,不。5,601 - 621年,2016页。视图:谷歌学术搜索
17. 你们c . k . Wang, a .宁”实现更好的车辆路径问题的解决方案涉及分裂交付和皮卡使用竞争决策算法,”亚太运筹学杂志》上,32卷,不。4,1550022,22页,2015。视图:谷歌学术搜索|MathSciNet
18. j·张,j . Tang和r . y . Fung)“分散搜索multi-depot车辆路径问题与体重相关的成本,”亚太运筹学杂志》上,28卷,不。3、323 - 348年,2011页。视图:出版商的网站|谷歌学术搜索|MathSciNet
19. c . Malandraki和m . s . Daskin”,与时间有关的车辆路径问题:配方,性质和启发式算法,”交通科学,26卷,不。3、185 - 200年,1992页。视图:出版商的网站|谷歌学术搜索
20. 美国Ichoua, m . Gendreau j·波特凡,“车辆调度与时间旅行时间,”欧洲运筹学杂志》上,卷144,不。2、379 - 396年,2003页。视图:出版商的网站|谷歌学术搜索
21. “a . Polimeni和a .维提塔优化等在时间依赖网络中的节点:成本函数和应用,“优化理论与应用》杂志上,卷156,不。3、805 - 818年,2013页。视图:出版商的网站|谷歌学术搜索
22. d . Cattaruzza n . Absi d Feillet, j . Gonzalez-Feliu“城市物流车辆路径问题,”欧元在交通物流》杂志上》第六卷,没有。1,51 - 79,2017页。视图:谷歌学术搜索
23. 大肠谷口和t .山田,“可靠有时间窗车辆路径和调度对城市物流”学报第一交通网络可靠性国际研讨会(INSTR),2003年。视图:谷歌学术搜索
24. n安藤和大肠谷口”,旅行时间可靠性与时间窗车辆路径和调度,“网络和空间经济学》第六卷,没有。3 - 4、293 - 311年,2006页。视图:出版商的网站|谷歌学术搜索
25. r·g·康拉德和m . Figliozzi”算法的量化影响拥堵时间真实的城市货运的分销网络,“交通研究记录卷,2168年,第113 - 104页,2010年。视图:出版商的网站|谷歌学术搜索
26. f . Deflorio j . Gonzalez-Feliu g . Perboli, r . Tadei”时间窗的影响在城市货运的成本分布服务在城市物流应用,”欧洲交通和基础设施研究杂志》上,12卷,不。3、256 - 274年,2012页。视图:谷歌学术搜索
27. p . j . Munuzuri议会、l . Onieva和j . Guadix”城市货运发货,估计日常车辆的流动”城市规划与发展》杂志上,卷138,不。1,43-52,2012页。视图:出版商的网站|谷歌学术搜索
28. c·i Karaoglan, h . Gokcen”两级弧时间窗车辆路径问题:构造了一个混合整数规划模型和启发式方法,”欧洲运筹学杂志》上,卷230,不。3、539 - 550年,2013页。视图:出版商的网站|谷歌学术搜索|MathSciNet
29. L.-S。唐,W.-M。程,Z.-Q。张,j .梁”与旅行时间可靠性约束车辆路径问题,”国际会议在2007年交通运输工程学报》上,ICTE 2007,页1831 - 1836,中国,2007年7月。视图:出版商的网站|谷歌学术搜索
30. 曼奇尼,“与时间有关的旅行速度车辆在实际道路网络路由和调度:都灵的情况下,“交通研究Procedia,3卷,第441 - 433页,2014年。视图:出版商的网站|谷歌学术搜索
31. n . Chiabaut c·洛佩兹,l·勒克莱尔,“城市货运系统的性能评估使用Multi-use-Lane动脉”美国交通运输研究委员会的会议美国,华盛顿特区,2016年。视图:谷歌学术搜索
32. h . n . Psaraftis“动态规划解决单一车辆多对多直接请求dial-a-ride问题,“交通科学,14卷,不。2、130 - 154年,1980页。视图:出版商的网站|谷歌学术搜索
33. e .谷口m . Noritake t .山田,t . Izumitani”最佳的大小和位置规划公共物流终端”运输研究E部分:物流和运输审查,35卷,不。3、207 - 222年,1999页。视图:出版商的网站|谷歌学术搜索
34. 山田t, b·f·拉斯j·卡斯特罗和大肠谷口,“设计多通道货物运输网络:启发式方法和应用,“交通科学,43卷,不。2、129 - 143年,2009页。视图:出版商的网站|谷歌学术搜索
35. k . t . Yamada Imai、t .中村和e .谷口”供应chain-transport supernetwork均衡模型与货运公司的行为,”运输研究E部分:物流和运输审查卷,47号6,887 - 907年,2011页。视图:出版商的网站|谷歌学术搜索
36. t .山田和z . Febri货物运输网络设计中使用粒子群优化供应chain-transport supernetwork平衡,”运输研究E部分:物流和运输审查卷,75年,第187 - 164页,2015年。视图:出版商的网站|谷歌学术搜索
37. j . f . Ehmke a Steinert, d . c . Mattfeld”高级路由城市物流服务提供商根据时间旅行时间,“计算机科学期刊,3卷,不。4、193 - 205年,2012页。视图:出版商的网站|谷歌学术搜索
38. y谢菲,城市交通网络:平衡分析与数学规划方法美国加州,新世纪,恩格尔伍德悬崖,1985。

版权

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