考虑多仓库异构车型的公共自行车调配优化.pdf
《考虑多仓库异构车型的公共自行车调配优化.pdf》由会员分享,可在线阅读,更多相关《考虑多仓库异构车型的公共自行车调配优化.pdf(14页珍藏版)》请在咨信网上搜索。
1、第 39 卷第 1 期2024 年 2 月系 统 工 程 学 报JOURNAL OF SYSTEMS ENGINEERINGVol.39 No.1Feb.2024考虑多仓库异构车型的公共自行车调配优化李一鸣1,孙卓2(1.大连海事大学航运经济与管理学院,辽宁 大连 116026;2.大连海事大学交通运输工程学院,辽宁 大连 116026)摘要:针对公共自行车系统中站点库存量不均衡,设置多个仓库和使用多种类型货车调配等特点,研究多仓库异构车型的调配路线优化问题.基于用户需求刻画站点库存量的非线性惩罚函数,构建以站点库存量惩罚和货车行驶时间最小为目标的优化模型,并设计聚类路径算法进行求解.该算法通
2、过k-means聚类对站点网络进行划分,然后对划分的网络进行重新建模,基于启发式规则对模型进行求解.最后,通过数值算例验证模型和算法的有效性,阐明多仓库和异构车队在企业调配管理上的灵活性以及需求满足上的高效性,为企业系统运营提供有效调度规划方法.关键词:多仓库;异构车型;公共自行车;路线优化;聚类路径算法中图分类号:F253.4文献标识码:A文章编号:10005781(2024)01003414doi:10.13383/ki.jse.2024.01.003Public bike repositioning optimization with multiple depots andmultipl
3、e heterogeneous vehiclesLi Yiming1,Sun Zhuo2(1.School of Maritime Economics and Management,Dalian Maritime University,Dalian 116026,China;2.College of Transportation Engineering,Dalian Maritime University,Dalian 116026,China)Abstract:Public bike-sharing systems have the characteristics of the unbala
4、nced station inventory,multipledepots,and multiple heterogeneous vehicles.This paper investigates the static bike repositioning problem withmultiple depots and heterogeneous vehicles.Describing the user demand based on the nonlinear penalty func-tion of station inventory,a mixed-integer nonlinear pr
5、ogramming model is proposed to minimize the weightedsum of operational time and nonlinear penalty function,and a cluster-first route-second algorithm is designedto solve it.The cluster-first route-second algorithm decomposes the station network by k-means algorithm,then the reduced network is re-mod
6、eled and solved based on heuristic rules.Numerical results illustrate theeffectiveness of the model and algorithm,the flexibility of multiple depots and heterogeneous vehicles,and theefficiency of demand satisfaction.Our model can provide an effective repositioning method for operators.Key words:mul
7、tiple depots;multiple heterogeneous vehicles;public bike;routing optimization;cluster-firstroute-second algorithm收稿日期:20201230;修订日期:20230118.基金项目:国家自然科学基金资助项目(61304179;71831002);教育部人文社会科学研究青年基金资助项目(19YJC630151);辽宁省自然科学基金资助项目(2020HYLH32);大连市科技创新基金资助项目(2020JJ26GX023);辽宁省社会科学规划基金资助项目(L19BGL011).第 1 期李一
8、鸣等:考虑多仓库异构车型的公共自行车调配优化351引引引言言言随着城镇化进程的不断加快,交通拥堵和环境污染等问题愈发严重.公共自行车作为国家大力提倡的低碳交通出行模式,是解决最后一公里,城市拥堵和环境污染等问题的重要途径.自从2008年杭州建立第一个公共自行车系统以来,公共自行车系统在我国得到迅猛发展,截止2016 年初,我国共有118个城市拥有公共自行车系统1.公共自行车具有出行灵活、准时性高和低碳环保等优点.作为城市综合交通的组成部分之一,公共自行车能够有效解决人们的中短距离出行,并且能与公交、地铁等长距离出行方式优势互补.随着公共自行车系统的飞速发展,相关问题日益凸显且亟待解决.倪康康等
9、2对于公共自行车系统发展现状进行分析,指出由于人们使用公共自行车的出行需求差异,使得公共自行车系统内的自行车分布存在不平衡.即有些站点内停满了自行车,有些站点内却没有自行车.这使得用户出现借车难和还车难等问题.为解决此类问题,相关运营商需要利用货车对系统内的自行车进行重新调配,来满足用户的使用需求.这类问题被称为公共自行车调配问题或公共自行车重新配置问题(bike repositioning problem,BRP).有关此类问题的研究分为静态和动态两种.当运营商对公共自行车的调配主要发生在夜间,且忽略此时用户的使用需求时,该问题被称为静态公共自行车调配问题(static bike repos
10、itioning problem,SBRP)37.当运营商认为站点内的自行车需求与时间密切相关,且调配行为可以发生在一天当中的任何时间,该问题被称为动态公共自行车调配问题(dynamic bike repositioning problem,DBRP)7.关于公共自行车调配问题的相关研究,大部分学者集中于SBRP.在模型设计方面,已有研究主要以运营成本、时间成本和用户需求等指标作为目标函数.比如最大程度满足用户需求8,最小化货车的旅行时间9,10,最小化总行驶距离11,12和最小化系统运营成本13,14等.除此之外,相关学者通过添加各种操作约束,使得模型更贴近实际.Datner等9提出站点仅能
11、被拜访一次的路径约束.Chemla等10把站点对用户需求的满足设置为硬约束条件.Erdogan 等13将用户需求松弛为区间形式,只要站点库存量在该区间内,即可满足用户需求.Bulhoes等15在约束条件中考虑了路面状况、交通法规和地形等要素.Huang等16提出站点目标库存量的短期预测函数,并用该函数来替代约束条件中的站点目标库存量参数.Tian等17用任务流窗口约束来替换传统的时间窗约束,并以此来限制货车访问站点的顺序.在SBRP中也存在不同的研究方向,Li等18和徐国勋等19考虑不同自行车类型对货车调配路线的影响,并设计混合遗传算法和混合禁忌搜索算法进行求解.Ho等20考虑多种货车车型条件
12、下的调配路线问题,并设计大规模邻域搜索算法进行求解.Li等21考虑最佳用户激励机制下的调配路线问题,将用户调配自行车进而获得奖励的行为,描述为非线性弹性需求函数,并以此构建了一个非线性非凸的混合整数规划模型,之后通过双层VNS算法完成模型的求解.Zhang等22同时考虑站点间的自行车调配和坏车回收,以总成本最小为目标构建了一个混合整数规划模型,并设计自适应禁忌搜索算法进行求解.You等23设计了一个两阶段启发式算法对公共自行车调配问题进行求解,第一阶段确定每个站点的库存量、装载量和卸载量,第二阶段确定货车的具体行驶路径.在SBRP的求解算法上,Forma等24提出了三步数学启发式算法,首先通过
13、节约算法对站点网络聚类,划分出子网络.然后计算子网络中的货车调配方案.该算法的聚类过程存在波动性,会出现子网络仅包含一个站点的情况.Wang等25提出了最近邻路径算法,其中聚类过程使用的是最近邻算法对站点进行聚类,但作者在该算法中设定了子网络中的站点数量仅为6 到7个站点,使得部分货车的装载空间没有得到充分利用.本文在上述文献的基础上提出了聚类路径算法2631,在站点网络的划分上,选取高效的数据挖掘算法k-means,对站点网络进行分区,同时设计了启发式规则,结合子网络的站点数量,货车数量和货车容量,枚举不同的子网络和货车的组合方案,通过对不同方案进行求解,最终获得高质量的满意解.通过对现有文
14、献的整理,发现对于SBRP的研究.除了Liu等32以外大部分是基于单一仓库或单一货车车型的假设.部分研究会考虑多仓库或异构车型中的某一种情况,但很少会同时考虑以上两者.在现实生活中,由于站点网络较为庞大,单仓库的公共自行车系统往往需要配备更多的货车,这大大增加了管理和运营36系 统 工 程 学 报第 39 卷成本.所以大部分公共自行车网络中往往存在多个仓库,如CitiBike和LimeBike等.同时,公共自行车从业者表示由于各个站点需要调配的自行车数量不同.调度员会采用不同的货车车型组合,来完成站点的装卸需求.所以,对于SBRP的研究是需要同时考虑多仓库和异构车型两种情况32.本文拟解决问题
15、如下,1)构建公共自行车调配模型.针对复杂场景下的自行车分配不均衡情况,设计站点库存量的非线性惩罚函数,通过量化用户需求分布,来指导运营商的调度规划策略.2)考虑多仓库场景.针对运营商布置多个仓库进行调配的情况,设计多仓库站点网络约束,增大运营方案设计空间.3)扩展配送货车类型.针对异构货车精准调配的优势,设计对应变量和约束,使路线规划贴合需求及降本增效.为了使问题更贴近实际情况,本文研究多仓库异构车型情况下的调配路线优化问题,以站点库存量的非线性惩罚函数和货车行驶时间的线性加权最小为目标,建立了一个混合整数非线性规划模型.该模型充分考虑了公共自行车调配所面临的实际情况,例如在多仓库情况下货车
16、行驶路径的差异,以及在不同货车数量和容量的情况下,货车对于站点的访问顺序及装卸量等.为了便于模型求解,本文利用Raviv等33,34提出的线性化概念,对含有非线性目标函数的模型,进行分段线性化.基于站点网络的特点,将原问题分解为聚类、重新建模和求解三个子问题,并设计了聚类路径算法进行求解.最后,以实际公共自行车站点网络为例进行货车调配路线优化设计,取得了较好的结果,揭示了仓库数量和异构货车组合对运营商调配策略的影响关系.同时,实验结果表明,本文的模型和算法具有合理性和有效性,能够为公共自行车系统的调配路线优化提供理论支持.2多多多目目目标标标SBRP优优优化化化模模模型型型2.1问问问题题题描
17、描描述述述与与与假假假设设设在公共自行车网络中,每个站点配备有一定数量的自行车和锁桩.随着用户对于公共自行车的不断使用,导致站点内的自行车数量发生变化.有些站点停放的自行车过多,导致锁桩不够用,而有些站点内却没有自行车.为了方便用户的使用,运营商需要利用货车在固定时段(比如夜间)对网络中的自行车进行调配.而货车的调配路线以及在每个站点的装卸量,则是需要运营商提前确定的.以往的货车调配路线优化研究,大多是基于单一仓库和单一货车车型的假设.而现实生活中的公共自行车网络往往存在多个仓库,且运营商在对站点间的自行车进行调配时,往往会采取多种货车车型的组合方案,来满足站点的装卸需求.为了使研究问题更贴近
18、实际情况,本文研究多仓库异构车型情况下的调配路线优化问题.以图1为例,对问题进行说明.图 1货车路径图Fig.1Problem illustration图1是一个小型多仓库的公共自行车网络,该网络由两个仓库和五个站点组成.其中,运营商派出了两第 1 期李一鸣等:考虑多仓库异构车型的公共自行车调配优化37辆不同车型的货车对网络中的自行车进行调配.绿色虚线表示的是容量为10的货车的调配路线.红色实线表示的是容量为20的货车的调配路线.直线上的黑色数字表示货车的行驶时间,以秒为单位.每个点旁边的正负标号表示货车在该点装卸的自行车数量,正号表示装载,负号表示卸载.第二个仓库旁边带括号的蓝色数字表示货车
19、到达该点的时间,由货车的装卸时间和行驶时间组成.为了方便模型的构建和求解,需设定如下假设条件:1)仓库有部分自行车和存放自行车的空间.2)仓库既可以装载也可以卸载.3)每个站点可以被多辆货车拜访.4)允许货车在出发或是返回时,车上装载自行车.2.2符符符号号号说说说明明明在建模过程中使用的符号如表1所示:表 1变量名称及定义表Table 1Symbols in definition集合定义ND仓库的集合Ns站点的集合V货车的集合N所有点的集合,N=ND NsP装载站点的集合,i Ns|s0i sliD卸载站点的集合,i Ns|s0iqiv+1 M(1 xijv),i N,j Ns,i=j,v
20、V,(17)xijv 0,1,i,j N,i=j,v V,(18)yPiv0,i P ND,v V,(19)yDiv0,i D ND,v V,(20)yijv0,i,j N,i=j,v V,(21)si0,i N,(22)qiv0,i N,v V,(23)第 1 期李一鸣等:考虑多仓库异构车型的公共自行车调配优化39式(1)以站点惩罚成本与带权重的运输成本之和最小化为目标函数,站点的惩罚成本可通过对应的惩罚函数33,34计算获得,且惩罚函数仅与站点内的自行车库存量相关;式(2)式(4)表示经过调配之后仓库和每个站点内的自行车库存量,其中,装载站点的自行车库存量等于该站点的初始库存量,减去货车在
21、该点装走的自行车数量,卸载站点的自行车库存量等于该点的初始库存量,加上货车在该点卸下的自行车数量;式(5)和式(6)表示货车在站点i装载或卸载的自行车数量,其中,装载量等于货车访问该站点后与访问该站点前,车上自行车数量之差,卸载量等于货车访问该站点前后车上自行车数量之差;式(7)和式(8)表示货车在仓库装载或卸载的自行车数量;式(9)和式(10)表示货车在站点内装载或卸载自行车的数量不能超过站点内自行车或空余锁桩的数量;式(11)确保货车的总装载量和总卸载量相等;式(12)限制货车的容量,即货车上的自行车数量不能超过货车的最大容量;式(13)限定货车的出发仓库;式(14)为货车的流守恒条件,即
22、货车访问了某站点,则必须离开该站点;式(15)表示一辆货车访问某一个站点最多一次;式(16)限定货车装载、卸载和行驶的总时间不能超过该货车的最大调配时间;式(17)消除子回路35,作用为消除货车行驶路径中产生的子回路;式(18)式(23)为非负,整数和01变量约束.由于式(1)中惩罚函数fi(si)不是线性的,本文利用分段线性化方法33,34将fi(si)分段线性处理为函数fi(u),同时设定如下参数biu和aiu,其中i 1,2,.,Ns和u 0,1,.,Qi 1,并给出求解公式为biu fi(u+1)fi(u),aiu fi(u)biuu,其中aiu和biu分别代表线性化函数的截距和斜率.
23、为了实现对目标函数的完全线性化,仍需定义如下的决策变量,gi表示每个站点的惩罚值(gi等价于惩罚函数fi(si).本文用下面线性化之后的式(24)来代替原来非线性的式(1),即MiniNsgi+i,jN,i=jvVtijxijv,(24)同时在模型中加入线性化的约束(25)giaiu+biusi,i Ns,u 0,1,.,Qi 1.(25)因此,非线性的式(1)线性化为式(24)和式(25).为了缩小解空间,加快计算速度,本文添加了如下有效不等式约束yPiv6min(s0i,Kv)jNxijv,i Ns,v V,(26)yDiv6min(Qi s0i,Kv)jNxijv,i Ns,v V,(2
24、7)yPiv+yDivjNxijv,i Ns,v V.(28)式(26)式(28)通过限制装卸变量的取值范围,来缩小解空间,其中式(26)表示货车在站点的装载量要小于该站点的自行车数量或货车容量;式(27)表示货车在站点的卸载量要小于该站点的空闲锁桩数量或货车容量;式(28)确保货车进入站点一定会发生装卸操作;因此,新的混合整数规划模型就由式(24)和式(2)式(23)和式(25)式(28)组成.3求求求解解解方方方法法法公共自行车调配路线优化问题已被证实为NP-Hard问题6,尚不存在多项式时间算法.相较于传统的旅40系 统 工 程 学 报第 39 卷行商问题和车辆路径问题,SBRP要更为复
25、杂.因为在货车的调配过程中,SBRP不仅需要考虑货车的行驶路径,同时要考虑货车装卸自行车的数量.这个额外的装卸变量会增大解空间,进而增加求解难度.在问题规模较小的时候,可以使用商业优化软件CPLEX求解.随着问题规模的变大,商业优化软件无法在规定的时间内求解出精确解.故本文针对所研究问题的特点设计了聚类路径算法.首先,将原问题分解为三个子问题,分别是聚类、重新建模和求解.聚类是通过k-means算法,基于一定特征将大规模站点网络分解为多个较小的站点网络.然后,对每个较小的站点网络进行重新建模,更新参数.最后,基于一定启发式规则,利用CPLEX对小规模站点网络模型进行求解.重复迭代上述过程,输出
- 配套讲稿:
如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。