采用奇偶点图上作业法的快递配送路径优化研究.pdf
《采用奇偶点图上作业法的快递配送路径优化研究.pdf》由会员分享,可在线阅读,更多相关《采用奇偶点图上作业法的快递配送路径优化研究.pdf(3页珍藏版)》请在咨信网上搜索。
1、2023 年第 4 期山东交通科技-113-112-方法所得的结果是可行解而非最优解,还需进行优化。优化原则:(1)图上的每条边最多只能有1条重复边;(2)图上任何一个圈中,重复边的总权不能超过这个圈总权的1/2,当同时满足这两个原则时,便是最优解。3 以某区域为例优化快递配送路径3.1 区域概况研究范围为某市下娄小区及其工业区区域,配送区域东起开元北街至下丰塘、陶店村;北至诚信大道、南至商城大道,全长1.7km,宽1.4km,每日快递配送量在5070件,主要在东边的开元北街右边的商家、下娄小区、银海路两边商家、下丰塘、陶店村等地派件,配送区简图见图1,因陶店村与下丰塘村每次配送都有固定点,不
2、用送到每家每户,故这两个村仅作为两个点,便于优化与计算。诚信大道陶店村下丰塘商城大道下娄小区开元北街图 1 配送区示意图3.2 配送路径优化3.2.1 问题描述将邮递员所配送的区域看作一个赋权无向图,把所要走的道路当做边,长度表示权,在这个赋权无向图中找出一条起始点相同的链,该链中包含每条边至少一次,同时链中总权数最少。将以距离为衡量标准,通过奇偶点图上作业法,规划一条使邮递员走过尽可能短而又能完成配送任务的路径。3.2.2 假设条件(1)研究区域只包括下娄小区的外围靠近道路的顾客,不包括下娄小区内部的、不靠近道路的顾客。(2)为方便计算而且不失结果的真实性,图1中边的权值由实地距离按一定比例
3、尺换算成一定数值。(3)所有快递收件点基本都在工厂门卫处,而工厂大门都在道路两边,所以邮递员只要走过所有街道就能完成配送,图1的顶点仅仅为了方面说明,不代表收件点。3.2.3 优化方法因为每日配送快递的道路是随机的,所以最优道路并不是固定的,而且每条道路每天有快递的频率是不一样的,因此对于有快递频率高的道路和频率低的道路,采取不同的办法处理。对于快递频率高的街道,采用奇偶点图上作业法算出最小值,对于不常出现快递的街道,则寻找与低频率街道相邻的高频率街道,当走过高频率街道的同时正好走到该高、低频率街道相连的顶点时,在该低频率街道上走个来回。例如,假设V1至V2,V2至V3是通过奇偶点图上作业法算
4、出来的最优路径,而V2至V16是低频率街道却恰好当天有快递,则该部分最优路径是V1至V2,V2至V16,V16至V2,V2至V3;若当天没有V2至V16道路的快递,则不需往返此街道。此方法所得结果虽然不是最优的,但结果具有一定的通用性,而且对邮政员来说,这个方法更容易接受。3.2.4 概率统计为了区分是高频率道路还是低频率道路,首先对每条边编号,然后统计一个月(22个工作日)内各街道有快递的天数,见图2、图3。图 2 配送区内各街道编号图 3 各街道配送天数统计配送天数/d25201510501 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
5、21 22 23 24 25 26 27 28 29 30 31 32 33 34 35编号可以看出,编号5、8、10、14、19的街道属于低频率街道;其余均为高频率或者较高频率的街道。3.2.5 路径优化方案为了方便研究,给区域简图标上顶点 V 1、V2V23,并且为每条边附上权值,图中虚线表示低频率街道,实线表示高频率街道,见图4。采用奇偶点图上作业法的快递配送路径优化研究卢立红,高 苏(山东省交通科学研究院,山东 济南 250031)摘要:介绍了路径优化问题的研究现状,基于某营业点物流配送路线上的相关资料和数据,采用奇偶点图上作业法对该区域的配送路径进行优化,通过对比路线的距离和配送时间
6、,得出更加合理的配送路线,实现降低配送成本及提高服务质量的目标,同时对其他配送区域的优化提供有效的参考。关键词:邮政;路径优化;奇偶点图上作业法中图分类号:F615文献标识码:AStudy on optimization of delivery path of express delivery using operation method on parity point mapLU Lihong,GAO Su(Shandong Transportation Institute,Shandong Jinan 250031 China)Abstract:Theresearchstatusofpat
7、hoptimizationproblemisintroduced,theadvantagesanddisadvantagesofpostallogisticsareanalyzed,andthenbasedontherelevantdataanddataonthelogisticsdistributionrouteofabusinesspoint,thedistributionpathinthisareaisoptimizedbyusingodd-evenpointmap.Bycomparingthedistanceoftherouteandthedistributiontime,obtain
8、amorereasonabledistributionroute,achievethegoalofreducingthedistributioncostandimprovingtheservicequality,andprovideeffectivereferencefortheoptimizationofotherdistributionareas.Key words:postalservice;pathoptimization;operationmethodonodd-evenpointmap0 引言随着电子商务的快速发展,快递行业也迎来高速发展时期,但巨大的机遇也伴随着相应的挑战。经济的
9、发展使人们不再满足于低质量快递服务,而是更加倾向于高质量的服务,这迫使快递公司不得不做出改变、转型升级,而如何做好过渡是整个快递行业所面临的难题。通过科学的方法对快递最后几公里的合理配送进行研究,对建成普惠城乡、服务优质的快递服务体系具有重要意义。1 研究现状上世纪五十年代,车辆路径问题(VRP)首次被提出,随后国内外专家学者经过几十年的研究,取得了大量科研成果。人工智能和启发式方法为解决大规模、多目标车辆调度问题提供了新思路,其中动态规划法、遗传算法被用于优化车辆调度问题,蚁群算法可解决旅行商问题与指派问题1-3。由于快递配送受路况、天气影响,收件人的数量和分布也具有不确定性,从业人员的素质
10、有待进一步提高等情况,容易造成快递配送路径固定、配送时间长、成本高等问题,限制了快递行业的进一步发展。因此,优化配送路径可以降低成本、提高服务水平,提供一个多赢的局面。2 奇偶点图上作业法奇偶点图上作业法最早由管梅谷提出,用于解决快递员如何用最短的距离投递完所有快递再回到邮局的问题4-5。顶点表示顾客签收快递处;边指两点间的路径;权表示两点间的距离;次是顶点上边的数目,奇点是次为奇数的点,偶点是次为偶数的点。若邮递员所要配送的区域中道路所组成的图中没有奇点,那么快递员就可从起点出发走遍所有道路再回到起点,但大多数情况下会存在奇点,使得快递员会或多或少地重复走某条或者某几条道路。因此,在某些道路
11、必须重复走的情况下,重复走哪些道路使总路径最短,是所要研究的重点。奇偶点图上作业法的原理:在任何图中,奇点的个数一定是偶数,将所有奇点随机两两配对,然后把每对奇点间沿着图中存在的边相连,并在原图中加上相连的链,使所有奇点变为偶点,从而新图便不存在奇点,就能从起点出发走遍所有的边再回到起点,而两奇点间加上的相连的链即重复边,该收稿日期:2023-01-11作者简介:卢立红(1994),女,山东日照人,硕士研究生,工程师,研究方向为交通规划。2023 年第 4 期山东交通科技-113-112-方法所得的结果是可行解而非最优解,还需进行优化。优化原则:(1)图上的每条边最多只能有1条重复边;(2)图
12、上任何一个圈中,重复边的总权不能超过这个圈总权的1/2,当同时满足这两个原则时,便是最优解。3 以某区域为例优化快递配送路径3.1 区域概况研究范围为某市下娄小区及其工业区区域,配送区域东起开元北街至下丰塘、陶店村;北至诚信大道、南至商城大道,全长1.7km,宽1.4km,每日快递配送量在5070件,主要在东边的开元北街右边的商家、下娄小区、银海路两边商家、下丰塘、陶店村等地派件,配送区简图见图1,因陶店村与下丰塘村每次配送都有固定点,不用送到每家每户,故这两个村仅作为两个点,便于优化与计算。诚信大道陶店村下丰塘商城大道下娄小区开元北街图 1 配送区示意图3.2 配送路径优化3.2.1 问题描
13、述将邮递员所配送的区域看作一个赋权无向图,把所要走的道路当做边,长度表示权,在这个赋权无向图中找出一条起始点相同的链,该链中包含每条边至少一次,同时链中总权数最少。将以距离为衡量标准,通过奇偶点图上作业法,规划一条使邮递员走过尽可能短而又能完成配送任务的路径。3.2.2 假设条件(1)研究区域只包括下娄小区的外围靠近道路的顾客,不包括下娄小区内部的、不靠近道路的顾客。(2)为方便计算而且不失结果的真实性,图1中边的权值由实地距离按一定比例尺换算成一定数值。(3)所有快递收件点基本都在工厂门卫处,而工厂大门都在道路两边,所以邮递员只要走过所有街道就能完成配送,图1的顶点仅仅为了方面说明,不代表收
14、件点。3.2.3 优化方法因为每日配送快递的道路是随机的,所以最优道路并不是固定的,而且每条道路每天有快递的频率是不一样的,因此对于有快递频率高的道路和频率低的道路,采取不同的办法处理。对于快递频率高的街道,采用奇偶点图上作业法算出最小值,对于不常出现快递的街道,则寻找与低频率街道相邻的高频率街道,当走过高频率街道的同时正好走到该高、低频率街道相连的顶点时,在该低频率街道上走个来回。例如,假设V1至V2,V2至V3是通过奇偶点图上作业法算出来的最优路径,而V2至V16是低频率街道却恰好当天有快递,则该部分最优路径是V1至V2,V2至V16,V16至V2,V2至V3;若当天没有V2至V16道路的
15、快递,则不需往返此街道。此方法所得结果虽然不是最优的,但结果具有一定的通用性,而且对邮政员来说,这个方法更容易接受。3.2.4 概率统计为了区分是高频率道路还是低频率道路,首先对每条边编号,然后统计一个月(22个工作日)内各街道有快递的天数,见图2、图3。图 2 配送区内各街道编号图 3 各街道配送天数统计配送天数/d25201510501 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35编号可以看出,编号5、8、10、14、19的街道属于低频率街道;其余均
16、为高频率或者较高频率的街道。3.2.5 路径优化方案为了方便研究,给区域简图标上顶点 V 1、V2V23,并且为每条边附上权值,图中虚线表示低频率街道,实线表示高频率街道,见图4。采用奇偶点图上作业法的快递配送路径优化研究卢立红,高 苏(山东省交通科学研究院,山东 济南 250031)摘要:介绍了路径优化问题的研究现状,基于某营业点物流配送路线上的相关资料和数据,采用奇偶点图上作业法对该区域的配送路径进行优化,通过对比路线的距离和配送时间,得出更加合理的配送路线,实现降低配送成本及提高服务质量的目标,同时对其他配送区域的优化提供有效的参考。关键词:邮政;路径优化;奇偶点图上作业法中图分类号:F
17、615文献标识码:AStudy on optimization of delivery path of express delivery using operation method on parity point mapLU Lihong,GAO Su(Shandong Transportation Institute,Shandong Jinan 250031 China)Abstract:Theresearchstatusofpathoptimizationproblemisintroduced,theadvantagesanddisadvantagesofpostallogistics
- 配套讲稿:
如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。