考虑外协策略的电动车辆路径优化研究.pdf
《考虑外协策略的电动车辆路径优化研究.pdf》由会员分享,可在线阅读,更多相关《考虑外协策略的电动车辆路径优化研究.pdf(8页珍藏版)》请在咨信网上搜索。
1、Computer Engineering and Applications计算机工程与应用2023,59(16)电动车作为一种新能源汽车,以“零排放”的优势在物流行业中备受青睐,尤其是在配送最后1 km中,与传统燃油货运车相比,电动车存在续航里程短的问题,因此在配送过程中会使用充电/换电的方式来提高电动车的续航里程,以完成配送任务。由于换电站的建设成本高昂,且车辆型号较多,电池规格不统一,目前物流企业车辆大多采用充电的方式补充电量。不同于传统燃油车的补能方式,电动车的充电时间较长,基于不同的充电技术和电池容量,通常在18 h之间。这会对后续货物配送的时效性造成严重影响,导致配送成本增加。因此,
2、为了降低电动车辆充电时间对配送时效性的影响,研究考虑外协服务的电动车辆路径问题(electricvehicle routing problems considering outsourcing strategy,EVRPOS)具有重要的现实意义。在考虑利用社会闲散资源进行协同配送的情况下,研究了城市物流中电动车辆配送路径问题。EVRPOS由电动车辆路径问题(electric vehicle routing problems,EVRP)延伸而来,二者均属于组合优化领域的经典问题,也是NP-hard问题。已有学者从多方面对电动车配送路径优化问题进行了研究,取得了丰富的成果。大致分为以下几个方面:一
3、是电动车路径优化问题。Erdoan和Miller-Hooks1考虑的绿色车辆路径问题(green vehiclerouting problem,G-VRP)是最早研究行驶路程中充电问题的论文之一,车队由替代燃油车辆(alternative fuelvehicle,AFV)组成,车辆可以访问充电站以扩大行驶里程,目的是最小化车辆总行驶距离。Schneider等2研究带时间窗的电动车辆路径问题(electric vehicle routingproblems with time windows,EVRPTW),对电动车访考虑外协策略的电动车辆路径优化研究葛显龙1,2,邓诗言11.重庆交通大学 经济
4、与管理学院,重庆 4000742.重庆交通大学 智能物流网络重庆市重点实验室,重庆 400074摘要:针对电动车充电时间较长,影响配送效率的缺点,提出一种考虑外协服务的混合配送策略,在电动车充电间隙将社会闲置运输资源整合到配送过程中。以最小化车辆固定成本、路径成本、时间窗惩罚成本和外协成本为目标,建立混合整数规划数学模型,并设计三阶段求解算法。结合重庆某物流企业进行实际配送案例分析,结果表明提出的外协策略能够减少总配送时间,有效地节约成本。关键词:电动车;路径优化问题;外协策略;三阶段算法文献标志码:A中图分类号:TP18doi:10.3778/j.issn.1002-8331.2205-02
5、98Electric Vehicle Routing Problems Considering Outsourcing StrategyGE Xianlong1,2,DENG Shiyan11.School of Economics and Management,Chongqing Jiaotong University,Chongqing 400074,China2.Chongqing Key Laboratory of Intelligent Logistics Network,Chongqing Jiaotong University,Chongqing 400074,ChinaAbst
6、ract:Aiming at the disadvantages of electric vehicles(EVs)charging time and distribution efficiency,a hybrid distri-bution strategy considering outsourcing service is proposed to integrate the social idle transportation resources into the dis-tribution process during charging time.A novel mixed inte
7、ger programming model is established with minimizing fixedcost,distance cost,time windows penalty cost,and outsourcing service cost.Then,a three-stage heuristic algorithm isdesigned to solve the proposed model.The case study related to a logistics enterprise in Chongqing indicates that the modeland
8、the algorithm are effective and applicable.Meanwhile,numerical experiments show that the proposed distributionstrategy can reduce the total delivery time and effectively save costs.Key words:electric vehicle;routing optimization problem;outsourcing strategy;three-stage algorithms基金项目:重庆市自然科学基金(KJCXZ
9、D2020031)。作者简介:葛显龙(1984),博士,教授,主要研究方向为网络配送与路径优化,E-mail:;邓诗言(1997),硕士研究生,主要研究方向为城市配送。收稿日期:2022-05-16修回日期:2022-10-13文章编号:1002-8331(2023)16-0316-083162023,59(16)问客户点的时间进行约束,提出一个双层目标函数,目的是最小化车辆数量和总行驶距离。Goeke和Schneide3提出了带有时间窗和混合车队的电动车辆路径问题,针对物流企业同时使用电动车和燃油车进行配送的情况,研究了不同目标函数下使用电动车和燃油车进行配送的成本,为企业的配送发展提供了一
10、定的选择依据,具有较强的现实意义。付朝晖等4研究在时变网络下的生鲜产品配送问题,考虑货物新鲜度的变化,以改进蚁群算法分别对开放式和封闭式策略路径进行求解对比,结果表明该开放式策略更优。刘育良等5考虑了负载对能耗的影响,提出了一个现实的能耗模型,可以减少不可行路线的产生。二是电动车的充电策略。Montoya等6研究了非线性充电时间的EVRP,使用分段线性逼近来捕获充电过程的非线性充电行为。结果表明忽略充电函数的非线性性质可能会导致不可行的解决方案,此变体最大程度地缩短了总行驶距离和充电时间。葛显龙等7将充电量定义为决策变量,电动车的充电量由接下来的配送任务决定,而不用每次都充满电,此策略可以降低
11、充电成本以及减少总的配送时间。Desaulniers等8提出四种不同的充电策略,包括单次充电、多次充电、部分充电和完全充电策略,研究表明多次充电和部分充电策略能够降低物流成本。三是电动汽车的充/换电站选址问题。Lim等9基于加油站的选址模型,提出了替代燃油车辆的流量-补能选址模型,并设计三种启发式算法有效求解该模型。Yang等10同时考虑了电动车路径规划和充电站选址问题(electric vehicles battery swap stationslocation routing problem,BSS-EV-LRP),以最小化配送和选址成本。Hof等11使用自适应可变邻域搜索算法来解决BSS
12、-EV-LRP,改善了Yang等10求解的结果。根据以上分析,已有文献将研究重点放在了充电策略和电动汽车的充/换电站选址上,因较长充电时间而造成的配送效率低下问题没有得到解决。为了减轻充电时间造成的影响,一种可行的解决思路是利用社会闲散运输资源配送部分客户,以减少电动车辆因充电而暂停配送造成的时间损失。在实践中,随着滴滴共享模式向物流行业的渗透,通过分享车辆资源实现闲置车辆与货运需求协同的匹配,从而提高了资源的利用率。在学术上,目前已有学者对利用社会闲散资源提升配送效率的相关问题进行了研究。Archetti等12利用社会闲散运输资源配送一些位置较为偏远的客户,其余客户则由专用车队统一配送,有效
13、降低了配送成本。Kafle等13研究了一个混合网络,用卡车将货物从仓库运输到中转点,利用行人或骑自行车的人完成配送任务的最后一步(或取货任务的第一步),避免了传统卡车在城市配送中的低效率。Corts-Murcia等14研究了电动车充电时进行混合配送的问题,在电动车充电间隙,电动车司机采用无人机和自行车等交通工具去配送部分客户,其余客户由司机驾驶电动车进行配送,有效缩短了总配送时间。绕卫振等15对多个企业协同配送过程的成本分摊策略进行了研究,提出了一种新的成本分摊方法,对利用社会闲散配送资源进行协作配送的成本分摊有一定的借鉴意义。已有文献中采用社会闲散运输资源和专用电动车队两种方式共同配送,采用
14、行人、自行车和个人运输车辆等方式配送部分客户以提高效率,社会闲散运输资源在降低配送成本方面有足够的潜力。根据以上分析,本文提出一种外协策略以减轻充电时间对配送时效性的影响,即当电动车位于充电站时,利用社会闲散运输资源如达达配送等方式去配送部分客户。由社会闲散运输资源进行配送的客户称为外协客户。建立以最小化总成本为目标的电动车辆路径问题模型,设计三阶段算法进行求解。最后结合实例对本文提出的模型进行检验和分析。1问题描述存在外协服务的配送网络是一个复杂的物流系统,顾客的配送需求由企业电动车队和社会闲置运输资源共同完成。为界定研究范围,考虑在单一配送中心拥有同质电动车队背景下,客户相关配送信息均已知
15、。规划电动车和社会闲散运输车辆服务所有客户的路径,使得:(1)电动车队的起始点均在配送中心;(2)电动车辆和社会闲散运输车辆速度相同且恒定,未在客户时间窗内将货物送达会产生惩罚成本;(3)每个顾客由电动车或外协方式服务一次;(4)电动车离开配送中心的载重量不超过最大负载;(5)电动车电量低于阈值需前往充电站充电。具体情况如图1所示。由图1(a)所示,8,9;10表示客户点的时间窗为8,9,配送车辆到达客户点的时间为10点。其中车辆达到充电站的时间为10点半,充电时间为1 h,因此离开充电站的时间为11点半。由于较长的充电时间,导致车辆到达客户点5和6时,已晚于其最晚开始服务时间。在图 1(b)
16、中将客户点 5外协,电动车充满电后只服务客户 6,可以在规定的时间窗内将货物送至客户5和6处。显然(a)的时间窗惩罚成本比(b)高,(b)的总配送时间配送中心充电站客户点电动车配送路线外协配送路线8,9;9:30234659,10;1010:3011,12;12:4010,11;12111,12;125610,11;1128,9;9:309,10;10310:3041(a)方案1(b)方案2图1车辆路线图Fig.1Vehicle route map葛显龙,等:考虑外协策略的电动车辆路径优化研究317Computer Engineering and Applications计算机工程与应用202
17、3,59(16)更少,但(b)可能带来更大的路径成本。因此,选择合适的外协客户在降低总配送成本和时间方面有很大的潜力。当不考虑使用外协服务进行配送时,问题就简化为了带时间窗的电动车辆路径问题(EVRPTW)。为了界定研究范围,在建立模型前提出以下假设:(1)车辆离开仓库或充电站时,电池是满电状态;(2)配送车辆的电量损耗和行驶距离成正比;(3)配送车辆的充电时长恒定;(4)每个客户都必须被访问,且只能被访问一次;(5)每个充电站可被多次访问;(6)电动车到达充电站时社会闲散运输资源已经到达充电站,社会闲散运输资源可以即时获取包裹后按照指定的目标进行配送;(7)电动车最多只能访问一次充电站;(8
18、)每条路线最多只能存在一个外协客户。2外协客户选择策略使用外协的方式能否降低成本则取决于减少的时间窗惩罚成本和使用外协服务策略增加的额外配送费用。当减少的时间窗惩罚成本大于增加的额外配送费用,则能够降低总的配送成本。下面为外协客户的选择依据:(j-i-tijzij)lpu(c3-c1)dij,iF,jV(1)(j-lj)lpu(c3-c1)dij,iF,jV(2)约束(1)表示外协前到达客户j的时间晚于最晚时间窗,节约的时间为电动车到达客户j的时间减去外协车辆到达客户点的时间。约束(2)表示外协前到达客户j的时间早于最晚时间窗,则节约的时间为电动车到达客户j的时间减去最晚到达时间。每次访问充电
19、站最多只能外协一个客户,因此选择满足约束(1)和(2)中节约成本最大的客户作为外协客户,以最小化总成本。3建立EVRPOS数学模型3.1符号说明为便于建模,所使用的符号如表1所示。3.2模型构建根据上述分析,以车辆固定成本、路径成本、时间窗惩罚成本以及外协成本最小化为优化目标,建立考虑外协服务的电动车路径优化模型。min(c1kKiVjV,ijxijkdij+c2kKiVx0ik+)iVpui(ti)+c3iFjVzijdij(3)jV,ijxijk+jFzij=1,iV,kK(4)jV,ijxijk1,iF,kK(5)jV,ijxijk-jV,ijxjik=0,iV,kK(6)iVx0ik|
20、K,kK(7)ui-qixijk+Q(1-xijk)uj,i,jV,kK(8)ui-qozio+Q(2-xijk-zio)uj,iF,jV,oV,kK(9)uiQ,iV(10)i+(si+tij)xijk-lN+1(1-xijk)j,i,jV,kK(11)i+tijzij-lN+1(1-zij)j,iF,jV(12)i+ti+tijkxijk-(lN+1+ti)(1-xijk)j,i,jV,kK(13)o+(tio+so)zio+tijxijk-(lN+1+ti)(2-xijk-zio)j,iF,jV,oV,kK(14)pui(i)=epumax(ei-i,0)+lpumax(i-li,0),
21、iV(15)yi-dijxijk+B(1-xijk)yj,iV,jV,kK(16)yi=B,iF(17)0yiB,iV(18)iFzij1,jV(19)类型集合参数变量符号VFVK0,N+1QBqisieilidijtijctepulpuc1c2c3Pciuiyixijkzij说明顾客集合充电站的集合顾客、充电站和仓库的集合电动车集合配送中心车辆最大装载量电池容量顾客i的需求顾客i的服务时间顾客i最早开始服务时间顾客i最晚开始服务时间节点i到j之间的距离车辆从节点i到j的行驶时间电池能量消耗系数在充电站的充电时间车辆早于时间窗到达产生的单位惩罚成本,元/min车辆晚于时间窗到达产生的单位惩罚成
22、本,元/min电动车辆配送单位距离的运输成本,元/km每辆电动车辆的固定成本,元/辆外协配送单位距离的运输成本,元/km单次充电成本到达节点i的时间到达节点i时的剩余载重量到达节点i时的剩余电量如果车辆k从节点i访问了节点j为1,否则为0如果顾客j由外协服务为1,否则为0表1模型中的符号说明Table 1Symbol description in model3182023,59(16)iV,ijxijkiVzij,jF,kK(20)ui,i,yi0,iV(21)目标函数(3)最小化总成本,由电动车辆的路径成本、电动车辆的固定成本、电动车辆违背软时间窗的惩罚成本以及外协成本四部分构成。约束(4)
23、表示必须对所有客户进行一次访问。约束(5)表示对充电站的访问不能超过一次。约束(6)表示电动车辆的流量平衡。车队规模由约束条件(7)表示。约束(8)表示节点的剩余负载。约束(9)表示位于充电站后访问节点的剩余负载,其中协作车辆拜访客户的需求影响剩余的负荷。车辆容量受到约束(10)的限制。对于每个节点的到达时间,必须考虑三种情况:约束(11)表示车辆路线中节点j的到达时间,约束(12)表示通过外协服务访问的顾客j的到达时间,约束(13)和(14)表示在充电站i之后访问的节点j的到达时间。约束(15)表示电动车违背软时间窗的惩罚成本。约束(16)表示节点处的电量约束。而约束(17)表示电动车在访问
24、充电站后其电量更新为满电。约束(18)保证电量非负且不超过电池最大容量。约束条件(19)确定了每次到达充电站可以拜访的外协客户的最大数量。变量x和z之间的关系用约束条件(20)表示。约束(21)是变量的定义域。4设计算法求解EVRPOS问题属于NP-hard问题,精确算法16难以有效求解大规模配送问题,一般采用启发式算法17-22进行求解。考虑外协服务的电动车辆路径问题是在电动车辆路径问题上的拓展,主要区别在于需要在电动车辆配送路线上选择合适的外协客户进行剔除。因此算法思路是先规划电动车辆路径,再剔除外协客户得到所研究问题的解。第一阶段根据节约里程算法23得出初始EVRP解,此时所获得的EVR
25、P解不够精确;第二阶段采用禁忌搜索算法进行搜索优化,提升EVRP解质量;第三阶段根据第二阶段优化后所获得的EVRP解,选择合适的外协客户进行剔除,重新生成配送路径,即考虑外协服务的电动车辆路径问题可行解。采用三阶段算法可以在短时间内有效获得EVRPOS的高质量解。4.1初始解产生(1)编码方法本文采用自然数编码的形式,“051374260”表示EVRP问题的一条配送路线,包含6个客户和1个充电站,其中0表示配送中心,7表示充电站点,其余表示客户。(2)初始解的设计首先采用节约里程算法,得到包含配送中心和所有客户点的TSP解,即使用一辆车从仓库出发,访问所有客户完成配送任务后返回仓库,此时并未考
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 考虑 策略 电动 车辆 路径 优化 研究
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。