基于运行路径和客户整体满意度的车辆调度问题实证分析17000字【论文】

基于运行路径和客户整体满意度的车辆调度问题实证分析 1 2 2 2 4 7 7 8 2 27 28摘要客户满意度问题综合考虑，达到同时优化的目的。本文的研究重点包括：(1)建立车辆路径问题、车辆配载问题与客户满意度问题的综合优化模型。(2)作为多目标函数，引入非支配排序遗传算法，对问题进行求解。(3)借助河北某交通运最后将模型应用到某交通运输集团的配送问题中，将优化后的路线与满意度方案与现在应用的方案进行对比，结果显示优化后的方案车辆运行总路径最短，客户整体满意度最高，从而降低了物流企业运营成本，是一种优化的方案，也证明了数学模型的实用性和算法的有效性。本文只把车辆配载问题作为约束条件，车辆配载问题在后续的工作中，需要进一步的探讨。关键词：车辆路径问题；客户满意度问题；车辆配载问题；非支配排序遗传算法1.1研究背景及意义十三五期间，我国五年内的年均GDP增量为6.7%,经济在高速度发展。十四五我们提出了更高的要求，我们经济要转型，对于政府而言，政府加速放管服，简政放权，构建服务型政府，创新管理手段与管理方法，打造智慧政府，政府服务企业，为企业提供政策扶持，提供绿色通道，吸引投资。对于企业而言，企业需要转型，需要不断地内部优化，需要创建自己的特色产业，避免同质化竞争。2020年最热的中兴华为事件，告诉了我们，我们企业需要打造核心技术，不然就会出现卡脖子问题，社会应该构造鲶鱼效应，让企业之间互相竞争。共同进步。自春秋战国时期，既有“三军未动，粮草先行”之说，如何高效且有序运输物料自古以来就是人们关注的热点问题。一次统计局调查显示，国家公布的社会化物流成本约占GDP总值16%左右。全中国的制造业一年的利润还没有到达18%,我们整个社会化物流行业成本17.8%,这个数字我们国家对比于欧美国家高出了大概10%[1],由此可见物流行业有竞争，但是更有机遇，企业需要好的完整的运营网络，需要最优的运营网络。为了在激烈竞争的市场环境中更好地生存和发展，物流企业需要不断优化运营网络，以京东为例，京东是注重资产的企业模式，在全国范围内有约166个仓库，整个企业大约有10万员工。京东会在全国各地交通要塞设置自己的配送中心，选择送货的最优路线，让车辆的路径达到最优，车辆的载重率达到最大，这样可以使经济达到最优，如此的运营网络与物流模式大大提高了企业的公信力，推出的京东物流与隔天达也提高了人民的生活体验感，由此可知物流运营网络的物流运营网络由各个子部分组成，配送中心选址、配送线路、车辆配载等，其中车辆路径问题是一个NP难问题，近年来，随着网络电商的迅速发展，运营和计算机等多个交叉学科的重点研究内容[2],国内外研究大都是研究三个子部分，整体研究物流运营网络比较复杂繁琐，鉴于此现象，我想将结合考虑这几个子部分，给出一个优化解，具有理论意义，也有实际意义。1.2国内外研究现状通过查阅文献可以发现，国内外直接研究企业运营网络问题，往往比较复杂繁琐，所以我将该问题拆分为几个子问题，包括车辆配载和车辆路径，在子问题上深入分析，给出最优解。关于车辆配载，通过研究可以发现，该问题主要涉及到车辆、货物、配送中在进行模型建立过程中，往往要考虑到车辆的载重不能大于车辆的额定载重，车辆的容积不能大于车辆额定的容积，车辆使用应保证容积与载重率最大。车辆运行时间直接决定了客户的体验感，如果客户有优先级有要求，需要在车辆运行时间上加以控制，车辆配载问题还涉及到车辆的类型以及车辆的来源途径，是否为自用或外包公司租赁。车辆配载问题还涉及到货物问题，货物的类别、是否易碎易燃、是否有特殊处理要求，货物的体积与重量也是车辆配载问题中应该重点考虑的因素。配送中心对车辆配载也起着决定性作用，因为配送中心是车辆配载的起点，配送中心的数量和位置也决定了车辆配送的方式，决定了对客户是一对一配送还是一对多配送，或者是多对多配送。车辆配载问题与集装箱的装箱问题都是一类问题，最终的优化目标都是希望能够使载重和容积的利用率达到最大，从而降低成本，提高收入。车辆配载问题始于国外，自上世纪四十年代起，随着行业的崛起，萌生了相应的需要，国内外研究人员对此做了大量的相关研究，研究的重点也都是建立车辆配载的数学模型和不断优化算法，期望找到最优的解决方案。近几年，关于车辆配载问题的国内研究主要是根据特定问题，设置不同的约束条件进行建模，再根据案例选择合适的算法进行求解。研究成果主要有：周颖[3]研究了铁路零担货物，做了一个数学模型关于车辆额定载重和额定容积的车辆配载0-1规划模型，目标函数是车辆净载重和车辆容积最大，并通过设计算法进行求解，这种方法也有一定的缺陷，它无法求解规模较大的问题；刘小群等[4]以优化待装货物的大小和数量为出发点，建立了数学模型，建立了一个静态和动态容重比的模型，这个模型可以用来解决不同种类的货物的装车问题。王玲玲等[5]以客户需求为数学模型设计的出发点，将客户需求列为最高的优先级，建立了单车多品种货物采集模型，并通过动态规划的方法对模型求解，这种模型也有缺陷，它无法求解大规模问题。孙黎宏[6]建立了一个多目标函数的模型，他分析总结了多车型配载的七个制约条件，同时解决问题时引入了层次分析法。朱丽娟[7]优化了货物配载模型和车辆路径模型，将二者组合设计算法，在遗传算法的基础上进行改进，带入案例进行分析，具有实际意义。李小玲[8]优化遗传算法，代入案例进行分析。综上可见，国内外对于车辆配载问题的研究已经很多，国外主要从维度出发解决问题，国内主要从特定问题出发，我们建立的模型也各不相同，比如有的把单车配载作为优化目标、还有的把多车配载作为优化目标、有的把多品种货物配载作为优化目标、还有的把不同箱型不同包装的配载作为优化目标。在算法的设计中大同小异，一般算法还是会选择于现代启发式算法，很多人在研究时候，还是对基础的算法进行改进优化，再编写程序完成优化。1.2.2车辆路径问题关于车辆路径问题，又可以将其称为车辆调度问题，车辆调度问题主要涉及到车辆、配送中心、客户和道路。车辆主要需要考虑到车辆的类型，车辆的装载能力，车辆使用的成本，如司机的工资和装卸搬运的费用等。车辆路径问题中，配送中心需要重点考虑的关键一环，配送中心中有车场，车场作为车辆行驶的起点和终点，涉及到车辆在完成工作后是否返回问题。网点是车辆服务的目标之一，它涉及到接受服务的顺序同时还有对配送时间的要求。道路是构成车辆路径问题的重要一环。道路是由节点、线路构成，节点中还包括了配送中心和客户，路线问题涉及到了运行时间、运行距离和运行费用等。随着社会的进步，需要考虑越来越多的实际问题，学者越来越多的研究了车化集送货一体化为目的，对模型设计了种群搜索式径问题，建立了数学模型，并设计了算法对该数学对这种车辆路径问题，设计了算法，并且通过MATLAB运行程序。和现在存在种多样的需求等，建立了数学模型求解问题，解决的第四部分，案例应用部分。改进算法，编写MATLAB程序。针对某交通运径和客户满意度问题综合优化，目的要验证模型的实用性和算法的有效性。本文最后，对本文工作内容进行一个总结，同时指出希望改进之处。到合适的方法；然后建立数学模型、同时设计改进算法；使用MATLAB编写程效性进行相关验证，本文的技术路线如图1-1所示。论分析化模型目标函数处理用文献查阅选择图1-1技术路线(1)集货本章从运营网络整体、车辆路径、车辆配载进行相关理论分析。络应该是从供应商取得货物，在物流配送中心将货物集物配送货物、货物装车配载货物、货物配送运输，最后储存客户…图2-1运营网络流程图将有相同需求的客户分为一类，发挥规模优势，集货如(2)储存储存是物流网络的重要一环，对物流配送配送中心来好处的，比如储存可以保管货物，可以为货物提供场所和价，合理的储存可以调节市场价格。储存可以调节货物体量很大，一次无法运输，这时就需要储存来进行调节(3)分拣配货等将货物从储存区挑选出来，运到配货区。配货区要对分行检查、包装、贴标签，准备发货。合理的安排分拣(4)车辆配载和额定的容积，为了运输安全，我们要求货物的重额定的载重量和额定的容积，车辆配载还应该考虑让使样可以有效的降低成本，对于特殊的商品，还需要考虑客户，还应该考虑客户的优先级以及客户的需求，优化(5)车辆路径求可以考虑车辆行驶距离最短或者车辆行驶时间车辆运行产生的费用，如车辆的折旧费，车(6)送达服务意度，一旦发现运营途中存在问题，应该及时与(7)回程完成整体的配送任务，车辆会返回车场，形成一车辆回程都是空车，产生的一切费用都需要选择最短路径回配送中心，减少空载行程，途中经过运营网点，也可以考虑回程路上运送货物，增车辆配载问题实际上可以理解为一个0-1背包问题，问题描述为有一个大小放可以使得背包的利用率最大，这样的问题就是0-1背包问题。(1)货物(2)车辆(3)配送中心(4)客户(5)目标函数(6)约束条件者对车辆配载问题就开始了各个角度的研究，常见的几类车辆配载问题如表2-1表2-1车辆配载问题分类依据问题类型车辆配载问题货物装载维度一维问题二维问题车辆使用数目最小考虑货物重量和体积约束客户对配送的要求三维问题有需求优先级问题考虑车辆和货物的要求考虑客户对货物送达时车辆的单多车型无需求优先级问题单车型的配载多车型的配载间的要求不考虑客户对货物送达时间的要求类型相同型不同车辆的数量单车配载问题多车配载问题配送货物时一辆车进行配送货物时多辆车进行单目标问题多目标问题装载时优化目标只有一个研究时往往都是以上问题组合优化，得到不同的车辆配载模型。(1)配送中心配送中心是车辆路径问题的关键，配送中心中有停车位，配送中心的车场(2)网点途中经过的网点越多，产生的成本越小，收益越高，如(3)车辆车辆是构成车辆路径问题的决定性因素，车辆涉及到车辆的种类，种类不额定载重量影响到车辆是否还有空余空间装填货物，是否有必要经过该网点，在优化路径问题上，车辆种类是核心因素。不同车辆还会产生不同的成本，比如不同车辆的百公里油耗不同，保养费用维修费用不同(4)客户路径，如客户对配送时间有要求，客户选择的服务(5)道路(6)目标函数(7)约束条件者对车辆路径问题就开始了各个角度的研究，常见的几类车辆路径如表2-2所分类依据表2-2车辆路径问题问题类型问题描述配送任务分类特征纯送货、取货问题纯送货问题、纯取货问车辆载货状况货物满载货物非满载货或取货，没有往返车辆既要对该客户点送货同时也在该客户点进行集货重小于货物的配送量，需要一辆以上的车辆完成任务小于车辆的额定载重，多个客户的需求可以用车场数量一个车场多个车场一辆车满足客户配送用了一个车场客户配送用了多个车场车辆和车场的联系开放式问题完成任务后车辆不需要返回起点回起点运送货物类型单品种货物配送的货物是同一种货物多品种货物配送的货物是不同的货物目标数量单目标问题让某一个目标函数达到多目标问题到最优研究时往往都是以上问题组合优化，得到不同的车辆路径模型。本章分析了车辆路径与车辆配载之间的关系，在2.1中，我们已经初步讨论了一个完整的物流运营网络，其中车辆配载问题与车辆路径问题都是核心问题[23],车辆配载过程中，涉及到车辆的使用，车辆路径问题中也涉及的车辆的使用，了联系，一个物流运营网络优化的成功与否与客户之间也有必要的联系，运营网络除了要考虑企业的成本费用外，也要意度来衡量运营网络优化情况，综合考虑问题，合实际案例进行讨论，确定模型的可行性，解决对于运营网络的优化，有三种优化思路，一种是以车辆节约算法优化运输路径；一种是以车辆路径路线与客户满意度建立联系；一种是综合分析车辆(1)车辆配载问题为主这种设计思路作为多目标函数问题，统一目(2)车辆路径问题为主这种设计思路没有考虑到车辆的最大配载能(3)车辆路径、车辆配载与客户满意度设计两个目标函数，一个目标函数为车辆行驶不能超过车辆的额定载重量。这种设计思路很配载问题之间的联系，同时又考虑到客户的实际需本文将采用第三种优化方式，结合案例建立数车辆路径问题是NP难问题，车辆配载问题同样也是NP难问题，我们还引入了客户满意度，单独求解这些问题都比较繁琐，将三加了问题的难度，模型之间会产生一些问题，互相制约或者影响，所以在设立综合模型的时候需要考虑一些问题。(1)目标函数单独优化车辆路径模型或者车辆配载模型，需要考虑到车的载重率，容积率，车的行驶路程与费用等，客户满意度需要考虑时间问题，综合优化时选择以车辆总路程最短和客户满意度最高作为目标函数。(2)约束条件将车辆载重作为车辆的约束条件，在后续设计算法时，可以有效的降低复杂程度。考虑车辆路径问题与客户满意度问题时，两个目标函数整体建模时也要考虑到两者共有的约束条件。(3)统一参数变量两个目标函数进行设计时，要将涉及到的参数变量进行统一，避免在后续设计算法时会因为参数变量不统一造成结果出现误差，不具有实用性。3.3模型的确定在第二章分析了车辆路径问题与车辆配载问题涉及到的理论知识，同时在第三章开篇也提到了综合优化思路，本文所研究的车辆路径问题、车辆配载问题以及客户满意度问题所涉及到的范围为：一个配送中心、单车型、车辆闭环运送、以时间为约束条件的客户满意度。可以具体描述为：从一个配送中心出发多辆车向多个门店送货，每个门店的位置确定，车辆的类型相同(车辆的额定载重和额定容积相同),每辆车的参数已知，选择合适的配送路线，使车辆不超过额定载重和额定容积，让车辆行驶总路程最短，送到门店后，评价客户总满意度。3.3.2模型假设和符号说明(1)模型假设环境模型在以下的环境中建立：①配送路线是一条闭合回路；②门店的位置是确定的。③车辆的型号一致；④客户评价指标一致；⑤货物类型不做要求。(2)模型中涉及到的参数及变量xi;表示车辆k从客户i处驶至j处ui;表示客户i处至j处的距离Si表示服务客户i的满意度Di表示客户i的货物需求量Lk表示车辆k的额定装载量ti表示车辆k到达客户i的时间yi表示客户i由车辆k服务v表示车辆行驶速度3.3.3车辆路径目标函数的确定通过第二章的理论分析，通过参阅大量的文献，车辆本文的车辆路径问题描述为：某车场有车k辆，车辆要从车场为客户送货，表示为从客户i处行驶到客户j处，在充分利用车辆的情况下，使得行驶总也可代表为两个地点；i=1,2,…N,j=1,2,…N;xi表示车辆k从客户i处驶至对目标函数解释如下：式(3-1)表示车辆行驶总路程最小。将客户满意度与时间建立一个联系，如果配送时间度就越高，如果配送的时间越长，那么客户满意度越对目标函数解释如下：式(3-2)表示客户总满意度最高。对模型中的参数定义：Di表示客户i的货物需求量；Lk表示车辆k的额定店的货物总重量不超过车辆的额定装载量；式(3-4)表示车辆k到达门店j的时间；式(3-5)表示一辆车服务一个门店；式(3-6)(3-7)表示到达每个门店返回配送中心车场；式(3-9)(3-10)表示决策变量对0、1的约束。遗传算法起源于上世纪，一经提出就收到了全世界传算法的基本思路是首先要有一个初始的种群，里面包括体的编码方式有很多种，一般都会采用二进制或者自然算法就是对初始的种群个体不断地循环迭代寻找一个环过程中，算法都将被选择的个体进行交叉、变异，种群，一起合并成为下一轮循环的初始种群，如此循环往复，不断的优化，不断地适应环境，直到达到条件，停止迭代，并从当前的种群中找到最好的解。(1)全局性(2)随机性(3)普适性遗传算法的适用问题多种多样，遗传算法的应用范围更广。遗传算法是通过初始种群的不断迭代从而得到最优解，一般计算流程如图4-1所示。图4-1遗传算法基本流程同时需要解决的时候，我们一般采用非支配排序法，这种算法被命名为第二代非支配排序遗传算初始化种群生成第一代子群非支配排序选择、交叉、变异父、子代个体合并生成新父种群选择、交叉、变异Gen小于最大代数?快速非支配排序拥挤度计算选择合适个体组成4.2.1pareto解一个目标优化问题和多个目标优化问题，理论上还是有许多不同之处。如间存在冲突，没有办法比较，所以就很难找到一个解，使所有的目标函数达到最优，对于多目标优化问题，我们通常会有一个解集，这种解被叫做非支对于最小化多目标问题，n个目标分量f:(i=1,…,Vi∈{1,…,n},vi≤uiA3i∈{1,…,n}lvi<ui 4.2.3快速非支配排序算法、拥挤度估计、精英策略开始我们设定种群为p,我们需要通过算法计算p中的两个参数np和Sp,包括每个个体p,这里的np是个体数，是种群中支配个体p,一个种群中，被个体p支配的个体集合称为Sp。整个种群都遍历过后，这两个参数复杂度的总计算是拥挤度估计可以保证种群多样性，为了得到种群中的特定解，需要得到他周围的解的拥挤度估计，这点两侧的两个点的平均距离就是我们要根据这些目标函数计算的内容，如图4-3所示。精英策略是保留父代中优良个体，让其直接进入到子代，目的是防止获得的帕累托最优解丢失。精英策略会选择算子，按三个指标，由父代Ci,和子代Di,合成的种群R;;然后再进行优选，目的是为了组成新的父代种群Ci+10f₂f₁算法流程如图4-4所示。第一步：生成随机个体并通过选择算子选出包含N个个体的初始种群P₀;第二步：对初始种群中的个体，执行交叉和变异操作，生成子代种群Qo.其个体数为N;第三步：合并两个种群，令R₀=P₀UQo,新的种群Q₀中的个体数为2N;第四步：利用快速非支配排序对种群分层得到个体的序值，对于同层的个体利用小生境算子(即NSGA-Ⅱ的拥挤距离算子)计算个体密度值，并基于序值和密度值对合并后的R₀进行修剪，得到下一轮循环的初始种群P₁,其个体数第五步：判断程序是否已经达到迭代终止的要求，若是，则对种群进行分层，输入第一层的个体；如果不是就转第二步。非支配排序拥挤度比较算子C4.3总结NSGA-Ⅱ的优劣NSGA-Ⅱ优势：(1)快速非支配排序法的提出，降低算法的计算难度和复杂度。(2)算法中出现的拥挤度和拥挤度比较算子，可以代替需要指定共享半径，才能实现的适应度共享策略，同时在快速排序胜出标准，可以使准帕累托域中的个体放大到整个帕累托匀分布，有效的保持了种群的多样性。(3)算法提出了一个精英策略，可以有效的扩大采样空间。算法将父代种群、与其产生的子代代，同时通过对种群中所有个体分层存放，可以让种群NSGA-Ⅱ劣势：(1)在高维多目标优化中，由于维度较高，拥挤度策略作用低。(2)非支配解在种群中比例增加，会导致搜索过程缓慢。5.案例分析本章以某交通运输集团为例，对本文建立的数学模型和设计的遗传算法进行验证，验证模型的可靠性与算法的有效性。5.1项目基本情况5.1.1背景介绍某交通运输集团是一家物流企业，方便了人们的生活，满足了社会的需求，对国家的贡献很大，如今某集团已成为集多领域业务为一体的大型综合性物流企业。社会在发展，时代在进步。京东物流、顺丰物流等物流公司如雨后春笋般蓬勃而出，迅速发展，如今在满足了物流运输网点遍布全国的基本需求后，人们对物流服务提出了更高的要求，比如要对时间，对运输安全提出要求，如此的社会发展方向要得到满足，企业就要不断进步，因为不进则退，公司就需要不断地创新，需要优化运营网络。5.1.2运营现状某交通运输集团车辆为同一型号的货车，车辆有最大行驶里程，运送货物结束后要返回到车场，方便统一调配管理。目前，某交通运输集团的主要货车信息的相关参数如表5-1所示。(辆)货车5企业运营网络配送的工作流程大致为：先确定客户所在地点，根据客户的需求和地点进行配载、装车，按着给定的线路送到客户处，车辆再返回配送中心，其工作流程图如5-1所示。图5-1某交运集团物流作业流程该物流企业从配送中心向附近30家门店进行配送，其中原点是配送中心所在的位置，其余1到30号为门店的分布图，具体门店坐标如表5-2、5-3、5-门店1Xy门店6Xy门店Xy门店Xy门店21Xy门店26Xy在该企业中，随机选取5辆车查看运行路线，5辆车的运行路线如表5-8所车辆编号路径12345如表5-8所示这5条现行的运营路线，车辆运行总路程为1532公里，客户本文采用MATLAB编写程序，验证模型的可靠性和算法的有效性，参考文献中一般都会确定一个初始种群数目，这个数目值一般都会取在50-2000之间，首先设置数目为10,快速验证结果是否符合要求，曲线趋势是否正确，然后再将初始种群数量设置为1000,进行实验。种群初始化的时候，根据算法方案让1000个个体作为初代染色体。本文设定最大的迭代次数为100,若在100代时模型没有像预期一样收敛通过多次实验，多次取值，得到了如下的程序运行结果，见5-4,分别为总行驶公里数变化趋势图、客户总满意度变化趋势图以及优化后的车辆路径图，对变化趋势进行相应描述，对客户满意度趋势进行相应描述，对o◎O◎◎0◎aXX000X0X0X000XX00X0XXX00XX00X图5-2车辆行驶总路程的变化趋势图从图5-2中我们可以发现，迭代最初的时候，优化后的曲线斜率变化速度比平缓，实验在迭代到第50代时，曲线开始收敛到该车辆行驶总路程问题的最优着目标更好的方向逐渐收敛，进而逼近最优，从41代左右后，可以看出问题解的波动性开始逐渐相对稳定，同时在第50代搜索到了上述最优解，车辆行驶总路径的优化结果为630.54。图5-3客户总满意度的变化趋势图从图5-3中可以看出，优化刚刚开始的时候，优化曲线的变化率比较快，在第40代收敛到该问题的最优解。在迭代到第8代到第18代的时候，总满意度在0.65×10¹0到1.1×10¹0左右波动，在第20代的时候，有一个非常迅速的跃升，随着迭代次数的增加，进化过程的进行，我们设计的遗传算法开始自动寻优机制，指导其搜索过程向着目标更优化的方向进行收敛，得到的解逐渐逼近最优，自40代左右后，问题解的波动性开始趋于相对平稳，同时在第40代时搜索到了上述问题的最优解，最后客户总满意度的优化结果为1.48×10¹0。图5-4优化的车辆行驶路径图配送中心根据30个门店的需求选择5辆车进行配送，生成了5条配送路径，如表5-9所示。车辆编号路径12345如表5-9所示，优化后的车辆路径车辆总行驶公里数为630.54,对比表5-8中5条车辆路径车辆行驶的总公里数1532,减少了901.46公里，对比表5-8中客户满意度1.45×10¹⁰,优化后的客户满意度为1.48×10¹0,客户满意度提升了0.03×10¹0,优化前后车辆行驶总公里数降低，客户满意度增高，说明了模型车辆路径问题与车辆配载问题关联，同时将(1)理论分析工作文章做了大量的理论分析工作，首先分析了企业运营网络的运营流程，并指出运营网络中影响收益的几个因素，并对相关构成要素深入分析。其中关于车辆配载问题，分析了车辆配载中的要素，关于车辆路径问题，也分析了车辆路径问题中的要素。(2)数学模型的建立与算法的设计文章建立了多目标函数的综合优化数学模型，将车辆路径问题与客户满意度问题作为目标函数，将车辆配载问题作为约束条件，构建的数学模型简洁美观，富有实用性，能够解决实际问题。(3)分析案例文章引入某交通运输集团实例，对模型的可行性进行检验，对某交通运输集团实例进行分析