文摘

不同的城市交通流(如乘客旅行,货运分布,和废物管理)是传统分别由相应的专用车辆(sv)。多用途车辆(MV)是一种新型的汽车概念,可以使不同交通流的顺序共享通过改变所谓的模块,因此理论上提高城市交通的效率通过利用更高的汽车。在这项研究中,一个变种的提货和发货时间窗的问题是建立描述顺序共享问题考虑多个仓库的MVs和sv特性,部分充电策略,舰队规模。MVs可以改变他们的负载模块进行所有项目类型,也可以由sv。为了解决路由问题,一种自适应大型社区搜索(ALNS)与新问题特定的启发式算法。拟议中的ALNS小型15日测试情况和评估使用商业MIP的能手。结果表明,该算法效率,能够生成健壮的和高质量的解决方案。我们研究ALNS算法通过分析收敛的性能和选择概率的启发式解决方案破坏和修复操作符。15日大型实例,我们比较结果纯SV,纯粹的MV,和混合舰队,这表明MVs的引入可以允许更小的舰队,同时大约保持纯SV的总旅行距离一样。

1。介绍

日益增长的城市交通带来挑战。以斯德哥尔摩为例,它面临着交通拥堵的问题(1),确保可靠的运输随着人口数量的增加(2]。与此同时,西姆斯等人。3)指出,除非运输排放可以强烈与GDP增长,增加运输活动可能超过所有的缓解措施,以减少全球运输的温室气体排放。作为一个潜在的解决方案,Savelsbergh和Woensel4和洛杉矶等。5)强调整合的重要性和/或协作运输。

交通需求往往大大不同空间和时间。概要文件的需求根据不同类型的交通工具。图1显示了一个示例需求分布不均的多种运输类型。乘客流峰值在早晨和晚上,而货运需求集中在白天,回收是完全分布式的早晨。

客运、货运和回收运输业务目前由单独的舰队的不同类型的车辆。这些专用车辆(sv)可以运输物品只有一个类型的。当一种需求很低,利用相应的车辆变得不那么有效,因为他们袖手旁观或运行填充率较低,而车辆其他需求类型的能力可能不足。陈和李6和刘et al。7]讨论了类似的nonmodular车辆未充分利用。各类SV是专门为特定的需求类型,因此不能有效地进行项目的其他类型。例如,汽车为乘客有足够的席位,这只允许几个包裹在小储藏室或席位。一些车辆不能够携带物品的任何其他类型(例如,使用车辆对废物进行人)。

多用途车辆(MVs)的概念,从而改变他们的加载模块专用站运输物品的多种类型,同时保持传动系和其他部分,示意图如图2。鉴于目前的自主汽车的快速发展,未来MVs可能自动(即。,没有驱动程序)。如果没有,汽车出租车司机应该位于固定组件。

操作一个舰队包括MVs的总成本是车辆的固定成本,可变成本的总旅行距离,和模块变化成本变化。MVs顺序能够共享车辆,从而可能增加车辆的利用率,达到降低总体成本更少的车辆固定成本和可变成本的路线更灵活的选择。在图的例子1,部分MV舰队可能运输乘客和浪费,分别在早上高峰。然后,MVs货运在白天可以改变。在晚上高峰之前,MVs可以改变运输人。早上MVs用于回收峰值以后还可以运送乘客和货物。因此,MVs少于sv可能要求城市交通。

未来的城市交通应该可持续应对全球变暖的挑战。努力在发展电动汽车一直致力于这样的野心。因此,我们假设所有未来电动车辆。然而,即使电动汽车环保在行动,制造电动汽车仍将导致许多排放。高利用率的MVs理论上可以解决这个问题在一定程度上通过使用更少的车辆。

从MVs的角度,模块需要额外的距离为来访的改变。幸运的是,如果MVs电气,这个缺点将被克服因为增加电动汽车的行驶距离不会引起过度的排放。因此,电动MVs可以享受更灵活的路由选择和高利用率没有显著增加排放。

虽然各种形式的共享流动系统被广泛研究(见[8),小研究一直致力于连续的共享问题。在最近发表的一项研究Hatzenbuhler et al。9),作者提出一个时间窗口和顺序提货和发货问题共享。作者认为顺序的操作共享MVs导致机队规模的减少,为旅客和货运的服务请求可以维护。我们将扩展它通过引入混合舰队包括SV和MVs研究从当前的纯SV舰队过渡到纯MV舰队或混合舰队。进行数值实验将填补上述研究空白,增强理解MVs在未来城市交通系统的影响。

理解MVs的潜力,有两个重要问题:1)什么是最合适的车辆(即特征。,一个纯粹的MV舰队或混合舰队包含sv和MVs) ?和2)如何计划路线和舰队配置(即。,有多少汽车应该使用每种类型的)?为了回答这些问题,一种自适应大型社区搜索(ALNS)算法的开发,这是能够确定的最佳路线和舰队配置。然后我们比较纯粹的SV操作的最佳解决方案,使用混合舰队纯MV操作和操作。

本研究的贡献可以概括如下:(我)我们所知,我们是第一个考虑混合舰队,MVs提货和发货问题,出现问题的数学公式。(2)我们整合方面的多个仓库,部分充电策略,舰队规模,包括MVs和sv和混合舰队。(3)我们提出一个有效ALNS算法提出的问题,引入了新的机制来处理MVs。(iv)我们验证的结果进行了比较,提出了启发式的表现从一个精确的算法的解决方案。(v)我们表明,混合舰队可以提高场景的解决方案获得纯sv不均的几种类型的需求。纯MV舰队和混合舰队可能导致更少的车辆,而总旅行距离与SV舰队。

研究的其余部分组织如下。部分2文学评论相关工作。部分3提出问题并给出它的数学公式。部分4介绍了提出ALNS算法。结果和表演ALNS运营商显示的部分5紧随其后的是讨论。部分6包含的结论,未来可能的应用和研究方向。

2。文献综述

2.1。提货和发货的时间窗口问题

广泛研究的一个变体车辆路径问题(VRP)是PDPTW。PDPTW,一组车辆运输路线确定这样一组请求服务至少用给定的车辆(成本10]。PDPTW使用异构车队驻扎在多个仓库,以满足一组预先确定的运输要求。每个请求由一个拾音器位置、交货地点和一定数量的物品,应该是运输。请求的上车时间和交付时间应由两个时间窗口的位置。目标函数可能包括车辆和各种变量的固定成本运营成本(见[11])。

dial-a-ride问题(DARP)是一种变异的PDPTW运输物品的人,因此更侧重于服务质量和方便乘客11,12]。更全面的评论,我们感兴趣的读者参考文章PDPTW [13]和DARP [12,14]。

2.2。结合不同类型的交通工具

在城市交通中,不同类型的物品在异构的运营商。大多数研究在联运讨论两种类型的项的组合在同一车辆,主要可分为两类:单层和双层模型。

在单层模型中,车辆可以同时运输货物和乘客交货点。李等人。15]介绍了一种新型的模型称为搭载一乘问题(SARP)基于dial-a-ride问题。SARP,货物和乘客乘坐出租车。

至于双层模型,第一层通常描述预定的运输方式,如公共汽车和火车,其多余的空间可以用来运送货物。在第二层,较小的车辆运输货物或乘客最终目的地。因此,严格的同步传输点的每一层是必要的(8]。

2.3。机队规模和Mixed-Fleet问题

舰队规模和mixed-fleet (FSM)提出的问题是第一个黄金et al。16]在VRP的研究中,多种类型的车辆(不同容量、范围等)是可用的和舰队的规模是无限的。Hiermann et al。17]介绍了电动机队规模和混合蚁群和时间窗口(E-FSMFTWs)和充电站,认为充电时间和地点的选择。

2.4。部分充电

电动汽车(EVs)迅速发展在过去的十年。然而,电动汽车出现问题如长时间充电和充电站位置不足。因此,优化电动汽车已成为一个重要的和及时的研究课题。

康拉德和Figliozzi18)被认为是充电车辆路径问题(GVRP),它允许电动车充电在选择客户的位置。Erdoğan和Miller-Hooks19)提出了一个绿色车辆路径问题,提出了一个数学公式与充电站。电动汽车充电站的可以完全充电一个预定义的时间。然而,时间窗口和容量约束并不认为他们的问题。施耐德et al。20.]介绍了电动有时间窗车辆路径问题(E-VRPTW)和基于GVRP充电站,充电的时间取决于剩余电力当电动车到达充电站。时间窗和容量约束也被认为在E-VRPTW求婚。格等。21]讨论了电动皮卡和交付时间窗口的问题,扩展了PDPTW充电站。

2.5。自适应大型社区搜索

ALNS,首先引入了Ropke和Pisinger22),是一种启发式算法组成的竞争subheuristics调整频率的选择根据他们的历史表现。ALNS已广泛应用,证明有效的求解一般蚁群。Ropke和Pisinger22)应用ALNS PDPTW最著名的解决方案和改进基准实例。李等人。23)为SARP ALNS算法提出了李et al。15)和实例证明了其有效性产生真正的出租车轨迹和基准DARP的实例。Hiermann et al。17)解决了E-FSMFTW利用branch-and-price和一种自适应大型社区搜索使用嵌入式本地搜索和标签过程强化。他们提出的算法的有效性是由新创建的组基准实例证明E-FSMFTW和现有的单一车辆类型使用一个精确的基准方法。Keskin和Catay24)提出了一个创新的ALNS EVRP-PR,引入了新的充电站的删除和插入机制。基准实例的计算结果表明,提出的方法是有效的和高质量的。

3所示。方法

3.1。模型描述

在这项研究中,我们考虑一个混合舰队包括MVs和几种类型的sv的加载模块MVs可以切换专用改变车站运输任何项目类型的sv。整个车队被假定为电动。每辆车可以部分或全部在充电站充电。每个capacity-limited车辆从一个仓库和返回到仓库的起源。请求,包含几种类型的物品上车地点,交货地点,和时间窗口,由混合舰队服役。作为一个示例,图3显示一个由车辆路线。汽车有两个乘客请求和充电站的充电电池。在访问改变车站,它服务于一个运费请求并返回相同的仓库的起源。

我们的目标是找到最好的车辆配置的混合舰队,这些车辆的路线网络组成的客户点(提货和发货点),充电站,改变电台,和仓库实现整体最小成本包括车辆的固定成本、可变成本总旅行的距离,改变成本的变化。问题可以被看作是一个变种的提货和发货问题时间窗口(PDPTWs)中定义的文献综述。我们称它为multi-depot皮卡和交付时间窗口的问题,部分充电策略,舰队规模,和混合的专用车队和多用途车辆。

3.2。数学问题公式化

在本节中,我们提出的问题的数学模型。术语和参数显示在表中1。在这个模型中,所有点除了仓库只能访问一次。因此,多个副本的变化站和充电站被添加到网络允许多个访问一个站。可以访问每个重复一次,重复的数量足够大,覆盖的最大可能的访问数量变化或充电站。区分到达时间、加载和电当车辆开始和结束在仓库,我们添加一份仓库仓库不同于仓库。鉴于仓库,仓库顶点 表示开始仓库和仓库顶点 表示最后仓库。MVs必须空负荷之前进入一个变化。

有两种类型的车辆。一个是MV,另一个是SV包含三种类型的车辆。条目的请求类型可以由SV或MV相应的车辆类型。尽管MVs可以运输物品多种类型在不同的时刻,MV的类型被定义为项目的类型,它可以携带在一个特定的时刻。

让表示网络中所有的点表示类的车辆(即。,0为SV) MV和1。我们定义了二元决策变量等于1如果车辆类携带物品的类型 ,沿弧旅行 为 ,和来源于仓库 。否则,变量是0。让表示请求的所有类型。我们定义了二元决策变量跟踪项目的要求在车辆路线。它等于1如果车辆携带物品的要求当到达这一点 ,和0。考虑到请求 , 表示其和提货点 表示其交货地点。

3.3。目标制定

目标函数(1)最小化车辆的总成本包括固定成本和可变成本的距离成正比。第一和第二项表示sv和MVs的固定成本,分别。车辆的固定成本包括购买成本和劳动成本(例如,驱动程序和包装如果有的话)平摊到每个旅行。第三和第四项代表sv和MVs,带来的可变成本。可变成本包含每个距离单元的能源消耗的成本。第五项代表改变成本,与模块的数量成比例变化。它的参数是显示在表的意义1。

3.4。约束

在本节中定义的模型特征。与仓库相关的约束和混合舰队都是基于提出的配方Salhi et al。25),认为多个仓库和蚁群混合舰队。我们通过使用变量扩展配方跟踪运动的项目车辆路线和介绍MVs的特点,改变电台,和充电站。

约束(2)和(3)确保每个小点是由相应的车辆类型。约束(4)保证每个充电站可以访问所有车辆最多一次。约束(5)- (7)执行模块改变站可以通过MVs专门访问了。约束(8)确保MVs不能开车从仓库到变化。流保护为客户分和充电站是由约束(9)。约束(10)确保流变化的保护站。约束(11)保证车辆访问改变站,必须改变其载体类型。是一个足够大的参数条件的约束。约束(12)避免self-circles所有点。约束(13)和(14)确保车辆返回相同的仓库,他们离开。约束(15)- (18)防止车辆直接从仓库到仓库。约束(19)定义了二元决策变量。

以下的一组约束记录请求的携带状态:

约束(20.)定义的初始情况仓库开始,保证所有车辆清空他们的访问结束前仓库和改变。约束(21)通过请求的状态来如果不拿起或交货 。约束(22)确保车辆收集物品拾取点的请求。约束(23物品)保证车辆在交付点的请求。约束(24)确保交货点后必须提供其相应的提货点。约束(25)定义了二元决策变量。

最后一组约束记录到达时间,精力,和负载。跟踪能源使用,决策变量被定义为能量水平当车辆到达意义 。决策变量被定义为车辆离开时的能级充电站吗 。充电的电力是( ),它遵循定义首次引入Keskin和Catay [24]。决策变量记录车辆访问点的时候 。

在该模型中,每个类型的SV和MV有不同的能量存储能力,每个能量单位,充电时间和能源消耗单位距离。当表达参数的车辆类型,我们使用索引的{1,…代表MVs}代表SV类型和0。决策变量描述当前的剩余容量的 。

约束(26)定义了仓库和客户点的时间窗口类型。约束(27)和(28)描述客户点时间变化和变化,分别。约束(29日)和(30.)考虑时间变化在充电站MVs sv,分别。约束(31日)确保车辆离开充电站的能级的能量水平高于车辆到达的时候。约束(32)和(33)保证能量水平不超过最大能量的能力离开充电站时对应的车辆类型。约束(34)和(35在充电站)描述能量变化MVs sv,分别。约束(36)和(37)描述能源消费从仓库到其他点MVs sv,分别。约束(38)描述了在客户点负载变化,变化,和充电站。约束(39)和(40)描述了负载变化对MVs sv,当离开仓库。

4所示。自适应大型社区搜索

本节详细说明了ALNS算法提出的问题。部分4所示。1该算法的概述。部分4所示。2定义了过程生成最初的解决方案。部分4所示。3探讨了序贯策略共享。部分4所示。4讨论了部分充电策略。部分4所示。5描述解决方案的评价。部分4所示。6,4所示。7,4所示。8,4所示。9介绍客户破坏(CD)运营商,客户维修(CR)操作符,站摧毁(SD)运营商,分别和站维修(SR)运营商。

4.1。解决方案一代

拟议中的ALNS显示在算法的伪代码1。在第一步中,创建一个初始解(见部分4所示。2)。然后,该算法迭代破坏和修复当前的解决方案。对于每次迭代,如果新解决方案(即不是能源可行。,nonfulfillment of energy constraints), the station insertion algorithm Greed (see section4所示。9)应用于得到一个能量可行的解决方案。

接受或拒绝新的解决方案是基于模拟退火(SA)的方法:让和分别是新的解决方案和当前的解决方案。如果小于 ,在哪里模型的目标函数加负载点球吗和时间的惩罚(定义的算法2),新解决方案被接受为当前的解决方案。否则,新的解决方案可能仍然被接受的概率 。每一次迭代后,温度冷却速率乘以最好的解决方案将被更新,如果新解决方案到目前为止是最好的。初始温度保证第一个新的解决方案比当前的解决方案将被接受的概率为0.5。如果小于如果和为零,新的解决方案将被更新为最佳解决方案。不可行的解决方案有更好的将被接受为当前的解决方案,从而增加ALNS的灵活性。

分析函数包含的目标模型解决方案+负载的处罚和一次罚款相应的参数和 ,分别见算法2。 担保的实现负载限制。 确保完成的时间窗口。新的解决方案总是能源可行的算法1。因此,惩罚不需要电力。输出 , ,和SA中被利用的方法。

ALNS算法的结构是基于Keskin和Catay提出的算法24),这是证明有用的车辆路径问题的充电站。迭代的充电站后每个运营商迭代运算符的破坏和修复请求。

当选择摧毁操作员和维修在每个迭代中,我们使用一个轮盘赌选择。这种机制是Ropke和Pisinger提出的22]。所示的算法1、迭代分为段的长度和分别为客户和充电。的概率选择一个操作符在一段在前面的部分取决于它的重量(例如, )。特别是,操作员的重量在段是 ,在哪里是轮盘赌的参数,代表了操作员的使用在段期间 ,和运营商的分数吗在段期间 。对于每次迭代,分数的选择算子是增加了 , ,或 ,的分数如果迭代生成迄今为止最好的解决方案,改善当前的解决方案,或根据公司标准接受糟糕的解决方案。

每个客户/充电后段,客户的分数和重量/充电运营商重置。重置的段 ,如果操作员不是在这个细分市场中选择(也就是, ),这个操作符的重量下一段 将 。小的值 保证不接近零,这样每一个操作员可以选择,即使他们有坏表演一段。

4.2。初步解决方案

在初始解的生成,请求被处理根据他们的类型。相同类型的所有请求,一个请求是随机选择的基本请求生成一个车辆。一开始选择仓库,这样只增加了至少这个飞行器携带基本的要求。请求被随机分配到一个MV或SV。然后,剩下的请求将被插入到最佳位置,考虑时间和负载的可行性。请求可能早些时候访问次优先级顺序插入。如果不可能插入任何剩余请求车辆,基于一个请求生成一个新的车辆随机选择从剩下的请求。请求插入和车辆生成过程不断重复,直到所有剩余的这种类型的请求被插入。然后对所有类型的过程。最后,车站插入算法(见部分4所示。9)执行最初的解决方案可行的能源约束。

4.3。序贯策略分享

顺序不允许共享车辆同时携带不同类型的项目。新的变更站时可能会需要将请求插入车辆和至少一个不同类型的请求。相反,现有改变电台可以当删除请求的相邻点双方属于同一类型。在应用破坏和修复运营商,该算法检查每两个连续的客户点。然后,如果两边的两个客户点不是同一类型的,改变站添加最低距离增量是插入。如果两个客户点是相同类型的,改变站从解决方案中删除。

然而,新的更改电台插入执行车辆路线后,破坏和修复运营商一直应用。插入站增加了额外的旅行距离变化的路线,这是最初没有考虑应用破坏时和维修操作符。因此,矩阵等价的距离尽可能直接的距离加上额外的旅行距离(见方程(41)使用为了额外的旅行距离融入路线,因此正确地更新成本值。

如果两个点不相同的类型,其等效距离是一样的距离两个点为端点通过最近的变化。否则,他们直接距离等价的距离是一样的。

4.4。部分充电策略

Keskin和Catay24]表明:“如果存在一个最优解,使得电动车离开仓库的电池部分指控,然后同样的EV离开仓库完全充电也是最佳的完全充电电池以来得宝不推迟起飞时间的电动车。“因此,车辆从一个完全充电电池在我们提出的算法。

我们提出一个简单的和最优部分充电策略,避免违反任何时间窗口。自充电时间随充电能量,在获得能源的可行性解决方案,我们的算法在每个车站设置充电能量最小值,这确保了电动汽车到达下一站/仓库空电池。

4.5。汽车类的赋值和解决方案评估

在提出问题,有种sv和一种MV。车辆的目的非常重要,因为每一种车都有不同的能力,最大的能源容量,充电速度和能源消耗的速度。在算法2计算目标函数和车辆的目的是改变了基于评价结果。

4.6。客户摧毁运营商

客户销毁删除或移动运营商客户请求。(我)随机的位置:在当前的解决方案,一个数字点的选择包括客户点,改变电台,和充电站。然后,请求包含所选客户点删除。(2)路径:灵感来自Demir et al。26),一个请求是随机选择的。然后,站和请求与至少一个点在提货点之间的序列和预选的请求的交货地点是删除。(3)最大距离:灵感来自Keskin和Catay24),的请求最大距离增量,计算车辆的总距离减去总距离去除后,删除。在这里,意味着请求的总数,是一个随机数从0到1,是一个参数随机性的影响。(iv)肖:灵感来自Ropke和Pisinger22),这个操作符的想法是删除类似的请求。两个请求 ,相似的定义如下: 在哪里到达的时间点吗 。方程(42)认为差异在两个传感器之间的距离和到达时间点和两个交付点。最大相似度的两个请求删除。(v)随机车辆:一个随机车辆选择和删除。(vi)对:两个请求选择和删除。原来的车辆(即的信息。,the vehicle from which each request is removed) is swapped between those vehicles.(七)Cross-swap:两辆车都是随机选择的。所有点空负载,当被访问,记录。每辆车的路线分为两部分根据一个随机的记录点。每辆车的后一半路线连接到前面一半的其他车辆路线。最后,进行一次可行性检查断裂点到仓库的两辆车,删除了请求包含可行不可行点,直到所有剩余请求时间。(八)交换:两个请求都是随机选择的,他们的提货点和交付点交换。因此,不删除请求。

4.7。客户维修操作

客户维修操作符插入请求删除销毁操作符。最好的位置插入一个请求被定义为位置导致最低的距离增加而带来的其他职位。插入请求带来的距离增加定义如下: 在哪里和的意思是前面的点和下一个点,分别。(我)原始车辆:请求的插入顺序首先是随机打乱。然后,每个请求插入删除原来的车辆,在最好的位置。如果请求的原始车辆不存在破坏运营商之后,它将被插入到一个随机车辆。(2)国米车辆:过程类似于第一个修复算子。唯一的区别是,插入认为所有车辆之间的所有位置。(3)新的车辆:操作员后生成车辆和插入请求相同的方法在初始解的生成。(iv)随机插入:车辆被插入的顺序是随机打乱了。请求按最早的可能的访问时间插入排序。然后,每个请求的列表是按订单插入车辆内的最佳位置,考虑到时间和负载的可行性。如果所有剩余请求不能插入到汽车,未来汽车将被考虑。如果还有剩余的请求,所有车辆都被认为是,运营商新汽车将这些请求执行。

4.8。站摧毁运营商

车站摧毁运营商用于消除或移动充电站的解决方案,这可能会提高总体性能通过移除效率低下或调整他们的位置。四个运营商实现。固定数量充电站的选择破坏了运营商,除了低效的访问操作。(我)后最糟糕的用法:运营商提出的Keskin和Catay24),这个操作符的目标是利用电池尽可能多。因此,充电站按能级时访问。充电站中能量最高的水平。(2)低效的访问:我们提出一种新的破坏充电站运营商。充电,车辆需要访问充电站,增加总疏散距离。因此,避免与短充电停止大量增加是合理的。提出操作符类的充电站充电量比距离增量站和计数站与零充电金额的数量 。然后,第一 站被删除。(3)随机站:充电站是随机移除以多样化的解决方案。(iv)随机游走:充电站然后向前或向后移动一个位置选择车辆的路线。

4.9。站维修操作

车站修复运营商利用使被插入充电站电动可行的解决方案。有三个运营商实现,都是基于Keskin和Catay [24]。(我)贪婪:这个操作符检查路线从一开始就得宝。一次点是访问-电池状态,充电站是插入到这个点和之前的点之间的弧,至少距离增量。如果插入弧不是可行的,前面的弧。(2)比较:这个操作符检查第一点与消极的电池状态和访问看着弧前这一点。如果最近的可行的弧插入之前有一个不可行的电弧或可行之前插入更多的距离增加,充电站的最小距离增量是插入到弧。否则,前面的电弧被认为是相同的方式。(3)最佳电弧:一旦一个点是访问-电池状态,点之间的所有弧和前面的车站或仓库。带来的增量最小距离的插入一个充电站计算可行的弧线。车站在电弧产生增量插入最短的距离。

避免特殊情况,没有可行的弧之间的最后一站/仓库的访问与消极的电池状态,我们假设一个相对大量的车辆能源能力实验。

5。数值实验和分析

为了验证我们提出ALNS算法,15小实例解决使用ALNS和解决Gurobi是7.5.2。这两种方法的结果为每个实例。问题是解决了使用一个8核i7 - 8700 3.20 GHz CPU的计算机。除了数值结果,我们记录和分析运营商和客观的选择概率值的优化运行。最后,15个大型案件由纯SV测试比较结果,纯粹的MV,或混合舰队。

5.1。参数调优

调优方法的启发,Ropke和Pisinger22),Demir et al。26],和Keskin Catay [24)来测试每一个设置的参数,提出了只有1500执行ALNS 20次迭代。然后,平均20试验记录的客观价值。最后,最好的设置平均客观价值选择的参数数值实验在本研究的其余部分。一次只有一个参数是不同的,同时保持其他默认值如果不调整或调整值。我们根据订单表调优参数2。人造九请求与三种类型的实例用于调优。表2显示参数调优结果的细节。最好的参数值以粗体表示。我们设定一个高的冷却速率0.995的第一个1500次迭代收敛快而手动调整冷却速率为0.999 - 5实验使程序导致良好的性能在整个迭代。

5.2。小型实例

我们有15手动创建的实例。表3显示一般信息的请求数量,充电站的数量,仓库,为每个实例和改变电台。至于请求向量,到位向量代表有多少请求的每个类型 。实例有不同数量的充电站,改变电台,仓库,请求,请求类型,以确保实例表示一组不同的可能场景。sv和MV的固定成本是随机选择的范围(2000、4000),使我们的项目能够缩短路线和更少的车辆之间的权衡。MV的固定成本会高于一切,一些或所有的建模SV类型。位置、时间窗口,大量的顾客点,从实例和车辆容量也不同实例增加多样性。

每个实例被提出解决ALNS 5倍和MIP算法解算器。ALNS的最大迭代次数设置为10000,以防1-13,15000例14,20000 15。在表3, 充电站的数量,仓库,分别和改变电台。 意味着时间找到最好的解决方案。 意味着时间完成所有迭代。表示时间获取精确的最优解的算法。表示的平均百分比ALNS算法获得的结果偏离最优解MIP获得的解算器。记录多少次ALNS达到最优解在5试验。

如表3所示, 情况下1-13小于1秒,这表明该算法可以达到一个很好的解决方案很快。的 1 - 15的病例,除了最后一例小于2.5秒,这表明该ALNS通常具有稳定和快速计算时间在同样的停止条件。比较 和 与所有情况下,因此,我们可以表明,该ALNS是有效解决问题。

同时,最多有0.71%的平均偏差为所有15例。ALNS达到最优解为所有5试验11 15例。虽然ALNS陷入局部最优解,以防10,偏差很小。因此,ALNS生成的高质量的解决方案。

5.3。运营商分析

分析运营商实现在这项研究中,我们L90-3实例上运行该算法(见5.4中详细的实例描述)。就像前面提到的4、迭代分为固定长度的片段和概率选择一家运营商在一个段前部分取决于它的性能。数据4和5显示目标曲线,选择概率部分为客户和运营商,分别。堆叠柱形的组件在一个段代表运营商在这段的概率。

看客户摧毁运营商在图4(一)目标开始下降之前,运营商Cross-swap的概率和随机车辆增加,而运营商交换的概率,一对,和肖减少。同时,运营商最大距离和路径保持他们的概率。算子的概率随机位置先增加,然后下降,之后又增加。客观价值下降,运营商的概率最大距离、路径和Cross-swap主导而算子的概率随机车辆不断减少。此外,运营商随机位置、肖一对,和交换仍在低概率在整个优化,表明优化表现不佳。

考虑到客户维修操作图4 (b),原来的车辆和国米车辆低概率在整个优化,表明贫穷的可能性提高客观价值。下降前的目标,该算法试图生成许多新的车辆证明增加概率的随机插入操作员新车而保持一个高概率的同时。客观价值减少后,操作者随机插入生成主导和更少的新车。

减少目标图5(一个),车站破坏的概率算子随机漫步不断减少而其他三个运营商份额大约相等的概率。目标开始下降后,运营商低效的访问占主导地位,而其他三个运营商在波动的概率相对较低。最后的优化,所有四个运营商份额大致相等的概率。

在图5 (b),前三站实现修复运营商概率约等于目标开始减少。随后,运营商对于大多数优化振荡,直到回到平等的份额。

在ALNS,我们应用传统运营商和问题特定的操作符。在传统的运营商,最差的距离和路径经常选择在优化,性能优越。问题特定的运营商Cross-swap、随机插入和低效的访问显示良好的性能,同时对执行最据报道选择概率。

5.4。大型病例

评估的有效性的综合城市交通MVs给定请求时间分布不均匀,我们创建三个基础实例。每种类型在所有基础实例的请求,他们的时间窗口白天都集中在特定的时间段来模拟不同类型的需求,这是分布不均。这三个基础实例的请求总数的30岁,50和90。请求的总数是分为三个类型的物品。基本实例翻译9、14和7请求,分别为3项类型,虽然基础实例预示有17个,16日和17日请求,分别。基础实例L90包含30为每种类型的请求。三个基地的实例有相同的时间窗口的分布如表所示4。

在表4左边的箭头表示一个时间窗口的提货点。右边的箭头表示一个时间窗口交货点。1型的时间窗口是集中在上半年的一天。时间窗口2型有两种代表早晚高峰的乘客。3型覆盖整个白天的时间窗口。不同类型的请求需要在不同时期(即服役。分布不均,时间窗不同的需求类型)。

研究性能的纯sv,纯MVs,混合车辆,该程序可以稍微修改,以获得解决方案纯MVs和纯sv除了混合车辆。考虑纯SV舰队,一个足够大的价值可以转让的固定成本MVs,这样不会利用MV。对于纯MV舰队,所有车辆可能被分配在MVs算法2。

与此同时,MV的固定成本是一个重要的因素,决策者考虑舰队配置。为简单起见,我们假设所有SV类型有相同的固定成本 。此外,我们创建了两个不同的情况下对MVs基于他们的固定成本。一种情况假设MVs等于固定成本sv和其他情况假定MVs略高固定成本为1.2 。控制其他因素,所有sv和MVs具有相同参数的充电性能,能量容量和体积容量。

如表5和图6显示,这三个基础实例计算与不同的车辆特征和MV的成本结构。每个实例使用50000次迭代计算3次,最好与整体解决方案的目标是显示。程序使用相同的参数设置如表所示2除了大80年延伸的长度调整客户运营商分数来满足最大迭代时间更长,有更多的请求。我们记录的总旅行距离,客观价值,为每个实例和车辆配置。

在相同的实例(即固定成本结构。,L30-1 to L30-3, L50-1 to L50-3, and L90-1 to L90-3), MVs and mixed vehicle fleets can improve the objective value by 5-15% compared to SVs. At the same time, fewer vehicles are utilized in pure MV and mixed vehicle fleet solutions. The introduction of MVs (i.e., both mixed fleet and pure MVs) implies fewer vehicles and lower objectives if the same fixed costs are assumed.

在实例L30-4 L30-5 L50-4 L50-5, L90-4 L90-5,客观价值的改善在L30-2 L30-4远小于,L30-3, L30-5。纯MV舰队甚至有一个客观价值高于SV舰队在预示和L90。然而,混合车辆仍然可以改善客观价值相比SV舰队当MV比SV固定成本略高。这是令人惊讶的,但增加的一个潜在的解释客观值大规模实例与纯MV舰队和固定成本(即增加。L50-4 L90-4)可以潜在需求的模式。更多的客户请求在一个特定的区域,客户的时间和空间差距越少点。因此,请求越均匀分布在这个区域。自MVs操作的好处主要源于分布不均的有效整合需求在时间和/或空间,更高的需求密度潜在中和这个操作MVs的优势。然而,车辆总数的舰队,混合和MV, sv相比可以减少。

至于旅行距离,总有关于请求的数量没有明显的趋势,舰队特点,MV成本结构给出结果。作为一个可能的解释,更少的车辆需要更多的旅行距离虽然MVs支持更灵活的路线。因此,更少或更多的总距离取决于之间的敌对关系更灵活的路线和更少的汽车。然而,相比纯sv(即。,L30-1, L50-1, and L90-1), the total distances of other instances have not changed more than 5%.

分析的实例,可以看出MV和混合车队利用更少的车辆服务请求。这是真实的场景和你相等或更高的固定成本为sv MVs比。引入MVs(即。,both mixed fleet and pure MVs) brings improvements in terms of the objective value and fleet size, if MVs have the equivalent fixed cost as SVs. When increasing the fixed costs of MV by 20% compared to SV costs, the objective value of pure MVs rises or decreases less than the situation of equal fixed costs. However, the mixed vehicle fleet can still reduce the objective value in such a situation. At the same time, MVs do not significantly change the total distance. Namely, the MVs improve the objective mainly by fewer vehicles.

6。结论和未来的工作

本研究探讨MVs提货和发货问题特性的多个仓库,混合舰队,和部分充电策略。问题的数学公式,提出了一个高效的ALNS算法。此外,我们提出新的启发式运算符和策略为了适应问题特定的特征变化引起的电台和部分充电。

在几个数值实验中,我们表明,该ALNS小规模的情况下可以找到解决方案和高品质高效的时间。我们显示概率的变化提出了运营商在整个迭代一个运行和分析它结合目标曲线。通过大规模的情况下,混合舰队可以减少总成本相比,sv MVs场景中具有相同或更高的固定成本而sv。MVs会导致小舰队规模的纯MVs或混合舰队,但几乎没有正面或负面影响的总旅行距离。的改善带来的客观MVs主要来源于车辆少。

解决问题的算法并不局限于我们的提议ALNS。一些最具代表性的计算智能算法是有前途的,比如蚁群优化(27,28),人工蜂群算法(29日,30.],帝王蝶优化[31日,32),和哈里斯鹰优化(33]。

MV是一个有前途的方向更高效的城市交通系统通过允许更少的机队规模虽然总旅行大约保持距离。当过渡从当前sv MVs舰队,舰队将会有很长一段时间,sv和MVs共存。同时,sv可能在某些方面比较优势。例如,一些sv在某种类型的运输项目是有效的。因此,sv的共存,从长远角度MVs仍然是可能的。该模型可以帮助决策者在产品化阶段和/或sv和MVs的共存。混合车辆分析表明,过渡对MV是有益的因为sv的共存和MVs带来减少客观价值和机队规模。因此,交通系统可能已经在产品化阶段改进。纯MVs也可能是未来的趋势,如果他们有一个更低的固定成本而sv。

提高模型的实用性和通用性,未来的研究方向是进一步研究额外的大规模数据集情况下使用真实的需求。另一个未来的研究方向的动态需求考虑提出的问题,以便决策者可以动态地接受或删除请求。

至于MVs方面,不同的选项MV的操作在将来的研究中可以考虑。即有可能MVs异构能力、速度、或其他vehicle-related参数。此外,MVs没有能够传输各种类型的项目。例如,一些MVs可能只是乘客和货物之间进行切换,有些车辆可能只是货物之间的切换和回收。两种类型之间的灵活变化可能更可行的在更短的时间和可能已经导致效益。

数据可用性

使用的数据来支持本研究的发现可以从相应的作者。

的利益冲突

作者宣称没有利益冲突。