采用奇偶点图上作业法的快递配送路径优化研究.pdf

2023 年第 4 期山东交通科技-113-112-方法所得的结果是可行解而非最优解，还需进行优化。优化原则：（1）图上的每条边最多只能有1条重复边；（2）图上任何一个圈中，重复边的总权不能超过这个圈总权的1/2，当同时满足这两个原则时，便是最优解。3 以某区域为例优化快递配送路径3.1 区域概况研究范围为某市下娄小区及其工业区区域，配送区域东起开元北街至下丰塘、陶店村；北至诚信大道、南至商城大道，全长1.7km，宽1.4km，每日快递配送量在5070件，主要在东边的开元北街右边的商家、下娄小区、银海路两边商家、下丰塘、陶店村等地派件，配送区简图见图1，因陶店村与下丰塘村每次配送都有固定点，不用送到每家每户，故这两个村仅作为两个点，便于优化与计算。诚信大道陶店村下丰塘商城大道下娄小区开元北街图 1 配送区示意图3.2 配送路径优化3.2.1 问题描述将邮递员所配送的区域看作一个赋权无向图，把所要走的道路当做边，长度表示权，在这个赋权无向图中找出一条起始点相同的链，该链中包含每条边至少一次，同时链中总权数最少。将以距离为衡量标准，通过奇偶点图上作业法，规划一条使邮递员走过尽可能短而又能完成配送任务的路径。3.2.2 假设条件（1）研究区域只包括下娄小区的外围靠近道路的顾客，不包括下娄小区内部的、不靠近道路的顾客。（2）为方便计算而且不失结果的真实性，图1中边的权值由实地距离按一定比例尺换算成一定数值。（3）所有快递收件点基本都在工厂门卫处，而工厂大门都在道路两边，所以邮递员只要走过所有街道就能完成配送，图1的顶点仅仅为了方面说明，不代表收件点。3.2.3 优化方法因为每日配送快递的道路是随机的，所以最优道路并不是固定的，而且每条道路每天有快递的频率是不一样的，因此对于有快递频率高的道路和频率低的道路，采取不同的办法处理。对于快递频率高的街道，采用奇偶点图上作业法算出最小值，对于不常出现快递的街道，则寻找与低频率街道相邻的高频率街道，当走过高频率街道的同时正好走到该高、低频率街道相连的顶点时，在该低频率街道上走个来回。例如，假设V1至V2，V2至V3是通过奇偶点图上作业法算出来的最优路径，而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 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）摘要：介绍了路径优化问题的研究现状，基于某营业点物流配送路线上的相关资料和数据，采用奇偶点图上作业法对该区域的配送路径进行优化，通过对比路线的距离和配送时间，得出更加合理的配送路线，实现降低配送成本及提高服务质量的目标，同时对其他配送区域的优化提供有效的参考。关键词：邮政；路径优化；奇偶点图上作业法中图分类号：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:Theresearchstatusofpathoptimizationproblemisintroduced,theadvantagesanddisadvantagesofpostallogisticsareanalyzed,andthenbasedontherelevantdataanddataonthelogisticsdistributionrouteofabusinesspoint,thedistributionpathinthisareaisoptimizedbyusingodd-evenpointmap.Bycomparingthedistanceoftherouteandthedistributiontime,obtainamorereasonabledistributionroute,achievethegoalofreducingthedistributioncostandimprovingtheservicequality,andprovideeffectivereferencefortheoptimizationofotherdistributionareas.Key words:postalservice;pathoptimization;operationmethodonodd-evenpointmap0 引言随着电子商务的快速发展，快递行业也迎来高速发展时期，但巨大的机遇也伴随着相应的挑战。经济的发展使人们不再满足于低质量快递服务，而是更加倾向于高质量的服务，这迫使快递公司不得不做出改变、转型升级，而如何做好过渡是整个快递行业所面临的难题。通过科学的方法对快递最后几公里的合理配送进行研究，对建成普惠城乡、服务优质的快递服务体系具有重要意义。1 研究现状上世纪五十年代，车辆路径问题（VRP）首次被提出，随后国内外专家学者经过几十年的研究，取得了大量科研成果。人工智能和启发式方法为解决大规模、多目标车辆调度问题提供了新思路，其中动态规划法、遗传算法被用于优化车辆调度问题，蚁群算法可解决旅行商问题与指派问题1-3。由于快递配送受路况、天气影响，收件人的数量和分布也具有不确定性，从业人员的素质有待进一步提高等情况，容易造成快递配送路径固定、配送时间长、成本高等问题，限制了快递行业的进一步发展。因此，优化配送路径可以降低成本、提高服务水平，提供一个多赢的局面。2 奇偶点图上作业法奇偶点图上作业法最早由管梅谷提出，用于解决快递员如何用最短的距离投递完所有快递再回到邮局的问题4-5。顶点表示顾客签收快递处；边指两点间的路径；权表示两点间的距离；次是顶点上边的数目，奇点是次为奇数的点，偶点是次为偶数的点。若邮递员所要配送的区域中道路所组成的图中没有奇点，那么快递员就可从起点出发走遍所有道路再回到起点，但大多数情况下会存在奇点，使得快递员会或多或少地重复走某条或者某几条道路。因此，在某些道路必须重复走的情况下，重复走哪些道路使总路径最短，是所要研究的重点。奇偶点图上作业法的原理：在任何图中，奇点的个数一定是偶数，将所有奇点随机两两配对，然后把每对奇点间沿着图中存在的边相连，并在原图中加上相连的链，使所有奇点变为偶点，从而新图便不存在奇点，就能从起点出发走遍所有的边再回到起点，而两奇点间加上的相连的链即重复边，该收稿日期：2023-01-11作者简介：卢立红（1994），女，山东日照人，硕士研究生，工程师，研究方向为交通规划。2023 年第 4 期山东交通科技-113-112-方法所得的结果是可行解而非最优解，还需进行优化。优化原则：（1）图上的每条边最多只能有1条重复边；（2）图上任何一个圈中，重复边的总权不能超过这个圈总权的1/2，当同时满足这两个原则时，便是最优解。3 以某区域为例优化快递配送路径3.1 区域概况研究范围为某市下娄小区及其工业区区域，配送区域东起开元北街至下丰塘、陶店村；北至诚信大道、南至商城大道，全长1.7km，宽1.4km，每日快递配送量在5070件，主要在东边的开元北街右边的商家、下娄小区、银海路两边商家、下丰塘、陶店村等地派件，配送区简图见图1，因陶店村与下丰塘村每次配送都有固定点，不用送到每家每户，故这两个村仅作为两个点，便于优化与计算。诚信大道陶店村下丰塘商城大道下娄小区开元北街图 1 配送区示意图3.2 配送路径优化3.2.1 问题描述将邮递员所配送的区域看作一个赋权无向图，把所要走的道路当做边，长度表示权，在这个赋权无向图中找出一条起始点相同的链，该链中包含每条边至少一次，同时链中总权数最少。将以距离为衡量标准，通过奇偶点图上作业法，规划一条使邮递员走过尽可能短而又能完成配送任务的路径。3.2.2 假设条件（1）研究区域只包括下娄小区的外围靠近道路的顾客，不包括下娄小区内部的、不靠近道路的顾客。（2）为方便计算而且不失结果的真实性，图1中边的权值由实地距离按一定比例尺换算成一定数值。（3）所有快递收件点基本都在工厂门卫处，而工厂大门都在道路两边，所以邮递员只要走过所有街道就能完成配送，图1的顶点仅仅为了方面说明，不代表收件点。3.2.3 优化方法因为每日配送快递的道路是随机的，所以最优道路并不是固定的，而且每条道路每天有快递的频率是不一样的，因此对于有快递频率高的道路和频率低的道路，采取不同的办法处理。对于快递频率高的街道，采用奇偶点图上作业法算出最小值，对于不常出现快递的街道，则寻找与低频率街道相邻的高频率街道，当走过高频率街道的同时正好走到该高、低频率街道相连的顶点时，在该低频率街道上走个来回。例如，假设V1至V2，V2至V3是通过奇偶点图上作业法算出来的最优路径，而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 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）摘要：介绍了路径优化问题的研究现状，基于某营业点物流配送路线上的相关资料和数据，采用奇偶点图上作业法对该区域的配送路径进行优化，通过对比路线的距离和配送时间，得出更加合理的配送路线，实现降低配送成本及提高服务质量的目标，同时对其他配送区域的优化提供有效的参考。关键词：邮政；路径优化；奇偶点图上作业法中图分类号：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:Theresearchstatusofpathoptimizationproblemisintroduced,theadvantagesanddisadvantagesofpostallogisticsareanalyzed,andthenbasedontherelevantdataanddataonthelogisticsdistributionrouteofabusinesspoint,thedistributionpathinthisareaisoptimizedbyusingodd-evenpointmap.Bycomparingthedistanceoftherouteandthedistributiontime,obtainamorereasonabledistributionroute,achievethegoalofreducingthedistributioncostandimprovingtheservicequality,andprovideeffectivereferencefortheoptimizationofotherdistributionareas.Key words:postalservice;pathoptimization;operationmethodonodd-evenpointmap0 引言随着电子商务的快速发展，快递行业也迎来高速发展时期，但巨大的机遇也伴随着相应的挑战。经济的发展使人们不再满足于低质量快递服务，而是更加倾向于高质量的服务，这迫使快递公司不得不做出改变、转型升级，而如何做好过渡是整个快递行业所面临的难题。通过科学的方法对快递最后几公里的合理配送进行研究，对建成普惠城乡、服务优质的快递服务体系具有重要意义。1 研究现状上世纪五十年代，车辆路径问题（VRP）首次被提出，随后国内外专家学者经过几十年的研究，取得了大量科研成果。人工智能和启发式方法为解决大规模、多目标车辆调度问题提供了新思路，其中动态规划法、遗传算法被用于优化车辆调度问题，蚁群算法可解决旅行商问题与指派问题1-3。由于快递配送受路况、天气影响，收件人的数量和分布也具有不确定性，从业人员的素质有待进一步提高等情况，容易造成快递配送路径固定、配送时间长、成本高等问题，限制了快递行业的进一步发展。因此，优化配送路径可以降低成本、提高服务水平，提供一个多赢的局面。2 奇偶点图上作业法奇偶点图上作业法最早由管梅谷提出，用于解决快递员如何用最短的距离投递完所有快递再回到邮局的问题4-5。顶点表示顾客签收快递处；边指两点间的路径；权表示两点间的距离；次是顶点上边的数目，奇点是次为奇数的点，偶点是次为偶数的点。若邮递员所要配送的区域中道路所组成的图中没有奇点，那么快递员就可从起点出发走遍所有道路再回到起点，但大多数情况下会存在奇点，使得快递员会或多或少地重复走某条或者某几条道路。因此，在某些道路必须重复走的情况下，重复走哪些道路使总路径最短，是所要研究的重点。奇偶点图上作业法的原理：在任何图中，奇点的个数一定是偶数，将所有奇点随机两两配对，然后把每对奇点间沿着图中存在的边相连，并在原图中加上相连的链，使所有奇点变为偶点，从而新图便不存在奇点，就能从起点出发走遍所有的边再回到起点，而两奇点间加上的相连的链即重复边，该收稿日期：2023-01-11作者简介：卢立红（1994），女，山东日照人，硕士研究生，工程师，研究方向为交通规划。-115-卢立红，高 苏：采用奇偶点图上作业法的快递配送路径优化研究-114-基于双层规划模型的共享单车差异化定价问题研究马 骏1，李永昌2（1.济南职业学院汽车学院，山东 济南 250103；2.山东省交通规划设计院集团有限公司，山东 济南 250101）摘要：共享单车已成为城市慢行的重要模式，为了缓解高峰时期的供应短缺，加快平峰时期的周转率，本文提出了共享单车的差异化定价策略。通过建立共享单车票价的双层规划模型，使用基于粒子群优化的全局定价模型求解算法，实现了出行者的广义出行成本最小化和共享单车企业经济效益最大化的目的。关键词：共享单车；差异化定价；双层规划模型；粒子群优化算法中图分类号：U491文献标识码：AResearch on differentiated pricing of shared bicycle based on Bi-level programming modelMA Jun 1,LI Yongchang2（1.Automobile College of Jinan Vocational College,Shandong Jinan 250103 China;2.Shandong Provincial Communications planning and Design Institute Group Co.,Ltd.,Shandong Jinan 250101 China）Abstract：Sharedbicycleshavebecomeanimportantmodeofurbanslow-moving.Inordertoalleviatethesupplyshortageduringpeakperiodsandspeeduptheturnoverrateduringpeakperiods,thispaperproposesadifferentiatedpricingstrategyforsharedbicycles.Byestablishingabilevelprogrammingmodelofsharedbicycleticketpriceandusingtheglobalpricingmodelsolutionalgorithmbasedonparticleswarmoptimization,thegoalofminimizingthegeneralizedtravelcostoftravelersandmaximizingtheeconomicbenefitsofsharedbicycleenterprisesisachieved.Key words:sharedbicycle;differentiatedpricing;bilevelprogrammingmodel;particleswarmoptimizationalgorithm0 引言共享单车为城市绿色出行提供了便捷，但随着共享单车的发展，其在使用和经营方面的弊端也日益显现。早晚高峰对共享单车需求的不平衡影响了居民出行质量和满意度，其次，租金作为主要的收入来源，也越来越无法满足企业日益增加的投入成本。目前共享单车的定价策略大多采用统一的收费方式，但不同时期对共享单车的需求具有高度的灵活性。根据共享单车需求随时间的周期性变化引入差异化定价策略，该策略可以调节共享单车的供需关系，缓解高峰时期的供应短缺，引导旅客的客流分布。1 国内外相关研究概述差异化定价的基本原理是拥堵定价理论，该理论最早由剑桥大学的A.c.Pagou于20世纪20年代提出，研究了在现有交通供给规模下，如何通过经济手段控制和调整道路总需求，使交通量在时间和空间上重新分配，缓解供需失衡的矛盾。彭赓等1通过构建两阶段Hotelling双寡头竞争模型提出了共享单车平台最优定价策略。秦进等2以高速铁路客票总收益最大化为目标构建优化模型，研究高速铁路客票差异化定价与坐席分配的联合优化决策方法。廉天翔和徐猛3从平台运营角度研究了共享停车位的预订和分配问题，构建了共享停车位预约和分配的0-1整数规划模型，针对不同停车需求进行差异化定价分析。冰雪4考虑共享电动汽车运营商效益和站点供需平衡情况，以分时段上下阈值作为定价关键变量，建立共享电动汽车差异化定价模型，实现运营商收益整体最优。2 共享单车时空出行特征分析本研究样本包含49万条共享单车骑行数据，包括脱敏后用户ID、自行车ID、自行车类型、自行车使用开始时间、自行车骑行起点和终点。这些数据基于用户完全自发的行为，可以更客观地反映出行的行为特征和时间要求。2.1 共享单车出行时间特征分析根据一周24h订单分布变化趋势统计，工作日收稿日期：2023-02-12作者简介：马骏（1995），女，山东潍坊人，硕士研究生，研究方向为交通规划。的时间是1min。由图5计算出总距离L1=0.657km，由图6计算出总距离L2=0.642km，由图7算出总距离L3=0.641km。由1200的比例尺算出实际距离，L1=13.14km，L2=12.83km，L3=12.82km，各方案从时间角度具体对比结果见表1。表 1各配送路线时间配送距离/km开车时间/min红绿灯 时间/min配送时间/min总时间/min方案一13.1440.03.3360103.33方案二12.8338.54.0060102.50方案三12.8238.53.3360101.83由表1得出，经过奇偶点图上作业法优化的路径在时间上相差不大，但比未优化的配送的时间短，一般而言，邮递员配送时间大概在150180min。上述是针对特定区域的快递配送的路径优化，经过优化缩短了邮递员的配送距离，减少了配送成本和提高了配送效率，但也存在一定的局限性，当出现低频率道路有需要配送的快递或者高频率道路没有需要配送的快递的特殊情况时，该路径并非最优，这是由快递本身的不确定性造成的。对于这些不常见的特殊情况，需要根据实际情况重新优化。4 结语针对邮递员快递配送存在的盲目投递、走重复路线等问题，对某区域内的快递分布做出统计，先以配送总距离为衡量标准，按照奇偶点图上作业法的原理和优化原则，得出最合理的配送路径；然后以时间为衡量标准，结合区域的路况和配送的实际情况，算出每条路线的配送总时间，经过多次优化，得出最合适且能让邮递员容易接受的配送路径。参考文献：1 王红艳.基于粒子群算法的物流路径优化方法研究J.电子设计工程,2020,28（17）:61-65.2 安智敏,闫显亮,徐毅.基于蚁群优化神经网络的路基沉降量预测J.山东交通科技,2023（1）:96-97,136.3 蒋丛萃.大数据背景下的电子商务物流配送路径优化算法J.现代电子技术,2020,43（19）:130-133.4 王邦兆,陈永清,王海军,等.中国邮递员问题奇偶点图上作业法最优标准的商榷J.价值工程,2018,37（36）:258-259.5 袁威威.欧拉图在配送线路中的应用J.大庆师范学院学报,2017,37（3）:62-64.图 5 初步优化后配送方案一图 4 配送区示意图12V159V1425V13910132020101014524V1228V11V3V17V232020201818V41262327V10V18V19183024191925V918131417V20V21V5V62326V7V8V2V12125V13V122020191924V112020191918181818231323242530V2V14V3V15V1027V9V8V171417V16V4V5V626V7由图 4 可知，存在 V3、V4、V6、V7、V9、V12、V14、V20共8个奇点，让其随机按图中存在的路线两两相连，见图5，虚线表示邮递员需重复走的路线，经过第一步优化后图中均为偶点，则可通过一笔画完成。经检查，发现图 5 满足第一个优化原则，却不满足第二个优化原则，其中圈（V16,V5,V6,V17）与圈（V13,V14,V11,V12）中重复边的权值大于对应圈总权值的一半，故还需要优化。通过进一步优化调整，所得结果见图6，重复距离比图5减少了15km，但仍不是最优方案，圈（V17,V6,V7,V8）还可以继续进行优化。图 7 最终所得配送方案三图 6 二次优化后的配送方案二通过优化得到最终配送方案见图7，经检查，该方案既满足第一个优化原则，也满足第二个优化原则，最优路径：V1V13V14V1312V11V14V11V10V9V8V17V8V7V6V17V6V5V16V5V4V3V2V3V15V16V17V10V15V14V2V1。当编号为5、8、10、14、19的低频率道路有快递时，在走到该道路附近时重复走该道路。3.2.6 优化结果为方面计算，做如下假设：（1）假设配送车的平均速度是20km/h。（2）配送区域在V1、V3、V4、V7处有4处红绿灯，其中红灯60s、绿灯30s，配送车遇到红灯的概率为2/3，遇到绿灯的概率为1/3，假设配送车在每个红绿灯处等待时间为40s。（3）该区域每日的快递数量在5070件，假设每日的快递量为60个。（4）假设快递员在门卫处等待顾客签收V16