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

基于运行路径和客户整体满意度的车辆调度问题实证分析TOC\o"1-2"\h\u30845摘要 1134731.绪论 2123511.1研究背景及意义 2291761.2国内外研究现状 22581.3本文的主要工作 4167582.运营网络问题理论分析 6145472.1运营网络优化研究 6256592.2车辆配载问题相关理论 7149692.3车辆路径问题相关理论 9183223.数学模型的建立 12259193.1运营网络综合优化分析 1281883.2建立综合优化模型需要考虑的问题 12195573.3模型的确定 13106184.求解算法设计 16170864.1遗传算法 1679634.2非支配排序遗传算法NSGA-Ⅱ 1693394.3总结NSGA-Ⅱ的优劣 20194905.案例分析 21225975.1项目基本情况 21274595.2结果分析与讨论 2325646.总结 2527838（1）理论分析工作 2529963（2）数学模型的建立与算法的设计 2616997（3）分析案例 26132参考文献 27摘要随着国家经济从高速度发展转向高质量发展，物流企业的作用开始凸显，作为物流企业需要更好地优化运营网络，降低成本。物流企业运营方式的优化变成了学者们研究的重点。配送是运营网络中重要一环，是优化的重点内容，配送时的车辆路径问题和车辆配载问题是配送的两个关键问题，同时企业在优化的同时，也要考虑到客户的满意度。本文将运营网络中的车辆配载问题、车辆路径问题和客户满意度问题综合考虑，达到同时优化的目的。本文的研究重点包括：（1）建立车辆路径问题、车辆配载问题与客户满意度问题的综合优化模型。（2）作为多目标函数，引入非支配排序遗传算法，对问题进行求解。（3）借助河北某交通运输集团案例，对模型的实用性与算法的有效性进行验证。本文首先阐述了国内外车辆路径问题、车辆配载问题的研究现状，还阐述了车辆路径问题、车辆配载问题的相关理论。其次，将车辆路径问题、车辆配载问题与客户满意度建立联系，确定优化思路，设定以车辆行驶总路径最短、客户满意度最高为目标函数，车辆配载作为约束条件的数学模型，针对模型特点设计用于求解的非支配排序遗传算法。最后将模型应用到某交通运输集团的配送问题中，将优化后的路线与满意度方案与现在应用的方案进行对比，结果显示优化后的方案车辆运行总路径最短，客户整体满意度最高，从而降低了物流企业运营成本，是一种优化的方案，也证明了数学模型的实用性和算法的有效性。本文只把车辆配载问题作为约束条件，车辆配载问题在后续的工作中，需要进一步的探讨。关键词：车辆路径问题；客户满意度问题；车辆配载问题；非支配排序遗传算法1.绪论1.1研究背景及意义十三五期间，我国五年内的年均GDP增量为6.7%，经济在高速度发展。十四五我们提出了更高的要求，我们经济要转型，对于政府而言，政府加速放管服，简政放权，构建服务型政府，创新管理手段与管理方法，打造智慧政府，政府服务企业，为企业提供政策扶持，提供绿色通道，吸引投资。对于企业而言，企业需要转型，需要不断地内部优化，需要创建自己的特色产业，避免同质化竞争。2020年最热的中兴华为事件，告诉了我们，我们企业需要打造核心技术，不然就会出现卡脖子问题，社会应该构造鲶鱼效应，让企业之间互相竞争。共同进步。自春秋战国时期，既有“三军未动，粮草先行”之说，如何高效且有序运输物料自古以来就是人们关注的热点问题。一次统计局调查显示，国家公布的社会化物流成本约占GDP总值16%左右。全中国的制造业一年的利润还没有到达18%，我们整个社会化物流行业成本17.8%，这个数字我们国家对比于欧美国家高出了大概10%[1]，由此可见物流行业有竞争，但是更有机遇，企业需要好的完整的运营网络，需要最优的运营网络。为了在激烈竞争的市场环境中更好地生存和发展，物流企业需要不断优化运营网络，以京东为例，京东是注重资产的企业模式，在全国范围内有约166个仓库，整个企业大约有10万员工。京东会在全国各地交通要塞设置自己的配送中心，选择送货的最优路线，让车辆的路径达到最优，车辆的载重率达到最大，这样可以使经济达到最优，如此的运营网络与物流模式大大提高了企业的公信力，推出的京东物流与隔天达也提高了人民的生活体验感，由此可知物流运营网络的重要性。物流运营网络由各个子部分组成，配送中心选址、配送线路、车辆配载等，其中车辆路径问题是一个NP难问题，近年来，随着网络电商的迅速发展，运营网络优化又变成了一个热门话题，运营网络成为了工业工程、物流工程、运筹学、和计算机等多个交叉学科的重点研究内容[2]，国内外研究大都是研究三个子部分，整体研究物流运营网络比较复杂繁琐，鉴于此现象，我想将结合考虑这几个子部分，给出一个优化解，具有理论意义，也有实际意义。1.2国内外研究现状通过查阅文献可以发现，国内外直接研究企业运营网络问题，往往比较复杂繁琐，所以我将该问题拆分为几个子问题，包括车辆配载和车辆路径，在子问题上深入分析，给出最优解。1.2.1车辆配载问题关于车辆配载，通过研究可以发现，该问题主要涉及到车辆、货物、配送中心和客户。车辆要考虑到车辆的类型，车辆的载重和容积，还有车辆运行的时间，在进行模型建立过程中，往往要考虑到车辆的载重不能大于车辆的额定载重，车辆的容积不能大于车辆额定的容积，车辆使用应保证容积与载重率最大。车辆运行时间直接决定了客户的体验感，如果客户有优先级有要求，需要在车辆运行时间上加以控制，车辆配载问题还涉及到车辆的类型以及车辆的来源途径，是否为自用或外包公司租赁。车辆配载问题还涉及到货物问题，货物的类别、是否易碎易燃、是否有特殊处理要求，货物的体积与重量也是车辆配载问题中应该重点考虑的因素。配送中心对车辆配载也起着决定性作用，因为配送中心是车辆配载的起点，配送中心的数量和位置也决定了车辆配送的方式，决定了对客户是一对一配送还是一对多配送，或者是多对多配送。车辆配载问题与集装箱的装箱问题都是一类问题，最终的优化目标都是希望能够使载重和容积的利用率达到最大，从而降低成本，提高收入。车辆配载问题始于国外，自上世纪四十年代起，随着行业的崛起，萌生了相应的需要，国内外研究人员对此做了大量的相关研究，研究的重点也都是建立车辆配载的数学模型和不断优化算法，期望找到最优的解决方案。近几年，关于车辆配载问题的国内研究主要是根据特定问题，设置不同的约束条件进行建模，再根据案例选择合适的算法进行求解。研究成果主要有：周颖[3]研究了铁路零担货物，做了一个数学模型关于车辆额定载重和额定容积的车辆配载0-1规划模型，目标函数是车辆净载重和车辆容积最大，并通过设计算法进行求解，这种方法也有一定的缺陷，它无法求解规模较大的问题；刘小群等[4]以优化待装货物的大小和数量为出发点，建立了数学模型，建立了一个静态和动态容重比的模型，这个模型可以用来解决不同种类的货物的装车问题。王玲玲等[5]以客户需求为数学模型设计的出发点，将客户需求列为最高的优先级，建立了单车多品种货物采集模型，并通过动态规划的方法对模型求解，这种模型也有缺陷，它无法求解大规模问题。孙黎宏[6]建立了一个多目标函数的模型，他分析总结了多车型配载的七个制约条件，同时解决问题时引入了层次分析法。朱丽娟[7]优化了货物配载模型和车辆路径模型，将二者组合设计算法，在遗传算法的基础上进行改进，带入案例进行分析，具有实际意义。李小玲[8]优化遗传算法，代入案例进行分析。综上可见，国内外对于车辆配载问题的研究已经很多，国外主要从维度出发解决问题，国内主要从特定问题出发，我们建立的模型也各不相同，比如有的把单车配载作为优化目标、还有的把多车配载作为优化目标、有的把多品种货物配载作为优化目标、还有的把不同箱型不同包装的配载作为优化目标。在算法的设计中大同小异，一般算法还是会选择于现代启发式算法，很多人在研究时候，还是对基础的算法进行改进优化，再编写程序完成优化。1.2.2车辆路径问题关于车辆路径问题，又可以将其称为车辆调度问题，车辆调度问题主要涉及到车辆、配送中心、客户和道路。车辆主要需要考虑到车辆的类型，车辆的装载能力，车辆使用的成本，如司机的工资和装卸搬运的费用等。车辆路径问题中，配送中心需要重点考虑的关键一环，配送中心中有车场，车场作为车辆行驶的起点和终点，涉及到车辆在完成工作后是否返回问题。网点是车辆服务的目标之一，它涉及到接受服务的顺序同时还有对配送时间的要求。道路是构成车辆路径问题的重要一环。道路是由节点、线路构成，节点中还包括了配送中心和客户，路线问题涉及到了运行时间、运行距离和运行费用等。随着社会的进步，需要考虑越来越多的实际问题，学者越来越多的研究了车辆路径问题，世界各地的学者们针对现在存在的不同的问题，针对这些问题建立数学模型，并设计、优化算法进行求解。国外从上世纪八十年代开始，Bodin[9]等人就开始以满载集送货一体化为研究对象，优化车辆路径的问题；Ganesh[10]等改进了启发式算法，他们以优化集送货一体化为目的，对模型设计了种群搜索式算法，解决了这种车辆路径问题；William[11]以多货点车辆路径为研究内容，为数学模型设计了多阶段混合遗传算法，解决了这种问题。Pisinger[12]等建立数学模型，以带有载重限制的、时间窗的、多车场的开放式的问题为研究内容，建立模型，解决了此类车辆路径问题，并通过通用启发式算法，求解数学模型。国内研究车辆路径问题，大概始于上世纪八十年代，根据社会存在的一些实际问题，学者们开始研究各种不同的的车辆路径问题。李兵等[13]建立了模型，解决了客户需求动态变化的车辆路径问题，并改进了节约法，随机生成了数字，设计了算例验证了模型；邹彤等[14]建立了数学模型用以解决不确定的车辆数并带时间窗的问题，同时选择遗传算法求解问题；李宁等[15]建立了数学模型，对模型设计了粒子群算法；张晨[16]针对随机需求的单车辆的车辆路径问题，建立了数学模型，并设计了算法对该数学模型模型进行求解，引入了一个近似动态规划算法；祝毅鸣等[17]将一个随机动态问题作为研究对象，针对这种车辆路径问题，设计了算法，并且通过MATLAB运行程序。和现在存在的其他方法相比，这种算法的收敛速度和精度更好，节约时间，并且更可靠。刘兴和货国光[18]很好的解决了一个问题，这个问题是关于随机路径，解决这个车辆路径问题使用了禁忌算法。曾凡超[19]等设计了一种改进的双种群遗传算法，用来解决车辆路径问题。由此可见最近这些年年来，国内外关于车辆路径问题的研究主要是建立数学模型，同时寻找解决问题的最优算法，算法多数运用的都是遗传算法，研究内容大多都是根据实际案例进行分析，考虑到企业拥有车辆的数量、客户有多种多样的需求等，建立了数学模型求解问题，解决的问题从最短时间和最短路径两个方面入手，可以更好地满足我们日常生活的需要。1.3本文的主要工作1.3.1本文的主要内容将运营网络分成车辆配载和车辆路径问题，优先设计车辆路径问题，辅助设计车辆配载，客户满意度，最后几个部分到一起综合优化，合成为运营网络。通过研究运营网络，设计算法，以某交通运输集团有限公司为例，整理数据，验证算法同时分析其相关业务及存在的问题，阐述优化物流运营网络，验证前期数学模型合理性，综合优化，提出改进方案。第一部分，是文章的绪论。首先第一个工作是分析本文研究的时代背景及时代意义，总结了国内外研究的现状，同时对本文要研究的内容进行了梳理。第二部分，是理论分析。分析了车辆配载和车辆路径问题的相关理论，总结理论。第三部分，建立模型。首先本文通过分析车辆配载与车辆路径、客户满意度之间的关系，确定了一个综合优化思路，本文分别选择了车辆配载、车辆路径和客户满意度三个模型作为综合优化模型的整合目标，通过整合相关参数和变量、完善约束条件和目标函数，建立一个综合的优化模型。第四部分，案例应用部分。改进算法，编写MATLAB程序。针对某交通运输集团存在的问题，应用本文建立的数学模型和改进的算法对车辆配载、车辆路径和客户满意度问题综合优化，目的要验证模型的实用性和算法的有效性。本文最后，对本文工作内容进行一个总结，同时指出希望改进之处。

1.3.2本文的技术路线首先通过文献查询了解相关基础资料的收集，本文明确了研究背景和意义，了解研究现状及应用的主要内容和方法；然后对国内外的相关理论进行分析，找到合适的方法；然后建立数学模型、同时设计改进算法；使用MATLAB编写程序，本文用某交通运输集团配送的实例，对设计出来的模型的实用性和算法的有效性进行相关验证，本文的技术路线如图1-1所示。图1-1技术路线

2.运营网络问题理论分析本章从运营网络整体、车辆路径、车辆配载进行相关理论分析。2.1运营网络优化研究一个运营网络，应该有供应商、有物流配送中心、有客户，其中涉及到很多个环节，一般涉及到运输、货物储存、装卸搬运和包装，一个完整的运营网络应该是从供应商取得货物，在物流配送中心将货物集中、货物存储、分拣货物配送货物、货物装车配载货物、货物配送运输，最后送到客户手里，车辆再回到配送中心，形成一个闭合的回路。[20]运营网络的每一个步骤都有大量的成本，不断优化运营网络可以提高收益，运营网络流程如图2-1所示。图2-1运营网络流程图（1）集货与传统的送货方式相比较，如今物流配送中心的优势之一就是可以集货，将有相同需求的客户分为一类，发挥规模优势，集货如果分配合理，可以减少成本，集货的合理性会影响配送中心后续的工作收益。（2）储存储存是物流网络的重要一环，对物流配送配送中心来说，合理的储存是有好处的，比如储存可以保管货物，可以为货物提供场所和环境。合理的储存可以调节供需，比如风扇在夏天供不应求，而在冬天很少有人买，合理的储存可以弥补供需之间的时间差。储存可以调节价格，一些货品会因为断货而飞速涨价，合理的储存可以调节市场价格。储存可以调节货物的运输，比如一些物品体量很大，一次无法运输，这时就需要储存来进行调节和衔接。合理的储存会影响物流运输过程的整体效果。（3）分拣配货分拣是指物流配送中心会根据客户的要求、客户的所在地区、客户的属性等将货物从储存区挑选出来，运到配货区。配货区要对分拣区分拣出的货物进行检查、包装、贴标签，准备发货。合理的安排分拣与配货可以降低成本，提高收益。（4）车辆配载车辆配载问题是物流运营网络的核心内容，需要注意到车辆额定的载重量和额定的容积，为了运输安全，我们要求货物的重量和体积均不能超过车辆的额定的载重量和额定的容积，车辆配载还应该考虑让使用的车辆数目最小，这样可以有效的降低成本，对于特殊的商品，还需要考虑配送的条件，对于不同客户，还应该考虑客户的优先级以及客户的需求，优化车辆配载问题可以降低物流运营成本。（5）车辆路径车辆路径问题是物流运营网络的核心内容，一般来说车辆路径问题根据需求可以考虑车辆行驶距离最短或者车辆行驶时间最短。车辆路径问题涉及到了车辆运行产生的费用，如车辆的折旧费，车辆的油耗费，车辆的保险费，车辆的维修保养费以及司机的费用等，合理的选择车辆路径是物流运营网络中关键的一环，需要不断的优化路线，降低运营成本，从而提高收益。（6）送达服务送达服务是关键一环，送到客户手上的同时需要了解客户对本次服务的满意度，一旦发现运营途中存在问题，应该及时与客户沟通协商解决，这个部分直接接触客户，对物流企业形象的影响至关重要。（7）回程完成整体的配送任务，车辆会返回车场，形成一个闭合的回路，一般来说车辆回程都是空车，产生的一切费用都需要企业承担没有营收，所以应当尽量选择最短路径回配送中心，减少空载行程，降低配送成本。如果返回配送中心途中经过运营网点，也可以考虑回程路上运送货物，增加车辆的利用率，达到收益最大的目的。上述配送流程为物流运营网络的经典流程。不同的企业不同的配送中心运营方式不同，与模型还有些许出入，分析运营网络流程时还需结合案例实际进行。2.2车辆配载问题相关理论2.2.1车辆配载问题描述车辆配载问题实际上可以理解为一个0-1背包问题，问题描述为有一个大小容积固定的背包，现在有形状不同，重量不同的若干物品，需要放入背包，如何放可以使得背包的利用率最大，这样的问题就是0-1背包问题。[21]在车辆的配载问题中，就可以理解为有一辆容积载重固定的车，有若干体积、重量不同的货物需要放入车中，如何放可以使车辆的容积利用最大，载重利用最大，这样的问题就是车辆配载问题。描述为：一个配送中心中有型号相同的汽车若干，有大小不同，重量不同的货物，企业提出要求，要给这些车辆和货物安排一个合理的装载货物的顺序，寻找约束条件，不断优化目标函数，得到最优解。2.2.2车辆配载问题构成要素（1）货物货物是制约车辆配载的关键因素，货物的体积与重量约束了车辆的使用，体积与重量均不能超过车辆的额定容积与额定载重，根据货物的性质还需要考虑货物是否需要特殊处理，需要特殊包装。（2）车辆车辆是车辆配载的核心内容，车辆的额定载重和额定容积影响到最后的收益与成本，车辆的种类和车辆的数量也是建模中需要考虑的问题，车辆是否为企业所有还是为外包公司租赁，都是要考虑的内容。车辆使用数量的多少影响到产生成本的多少，比如需要考虑的车辆折旧费用、车辆保险、付税费用、司机人员的工资以及装卸搬运费用等。（3）配送中心配送中心是车辆装卸货物的场所，配送中心车位的多少影响到装配货物的时间，配送中心的数量决定了车辆运输的时间长短，也决定了车辆配送的方式，一个配送中心对一个客户或者对多个客户，多个配送中心对一个客户或者多个配送中心对多个客户，都是不确定的，是我们需要考虑的问题。（4）客户客户的需求影响了车辆配载的顺序，客户享有的优先级直接影响到车辆配载顺序的前后，客户对货物的时间和需求量的要求，都影响到车辆配载。（5）目标函数车辆配载问题是有多个目标函数，目标函数的设定可以是车辆的额定容积最大，车辆的额定载重最大，车辆使用数量最小。同时车辆配载是一个NP难问题，在建立数学模型时，一般目标函数要求不同，有的问题求最大值，比如载重利用率及容积利用率，有的要求最小值，比如车辆使用的数量。在寻找算法求解时会很困难，因此可以将额定载重率进行转换，转换为未使用的载重率和容积率最小，这样就可以将目标函数统一为单目标函数，大大降低算法设计的难度。（6）约束条件主要有几个内容是车辆配载问题的约束：车辆的额定载重、额定容积、客户对货物配送时间、货物的承压能力约束、货物装载顺序、货物放置方法等。我们的目标是构建一个可以解决案例问题的数学模型，需要做的工作有设计优化算法。2.2.3车辆配载问题的分类

随着经济的发展和行业的需求，从上世纪出现车辆配载问题起，国内外学者对车辆配载问题就开始了各个角度的研究，常见的几类车辆配载问题如表2-1所示。表2-1车辆配载问题分类依据问题类型车辆配载问题货物装载维度一维问题车辆使用数目最小二维问题考虑货物重量和体积约束三维问题考虑车辆和货物的要求客户对配送的要求有需求优先级问题考虑客户对货物送达时间的要求无需求优先级问题不考虑客户对货物送达时间的要求车辆的单多车型单车型的配载配送时装载货物的车辆类型相同多车型的配载配送式装载货物车辆类型不同车辆的数量单车配载问题配送货物时一辆车进行装载多车配载问题配送货物时多辆车进行装载优化目标单目标问题装载时优化目标只有一个多目标问题装载时优化目标有多个研究时往往都是以上问题组合优化，得到不同的车辆配载模型。2.3车辆路径问题相关理论2.3.1车辆路径问题描述车辆路径问题也可以说有一个卖货的人，要前往全国各地推销自己的产品，他需要经过要去的城市，再回到自己的原点，如何走才能使自己的行程最短，这就是一个旅行商问题[22]。结合到车辆路径问题，就是一辆车要前往全国各地的城市送货，途中会路过各个网点，最后回到配送中心，如何行驶才能使车辆的行程最短，就是一个车辆路径问题。2.3.2车辆路径问题构成要素（1）配送中心配送中心是车辆路径问题的关键，配送中心中有停车位，配送中心的车场是车辆运送货物的起始和结束。（2）网点车辆由配送中心出发，会经过很多个网点，网点的位置决定了车辆的路线，途中经过的网点越多，产生的成本越小，收益越高，如何能够合理规划路线经过更多的网点是车辆路径问题中需要重点考虑的因素。。（3）车辆车辆是构成车辆路径问题的决定性因素，车辆涉及到车辆的种类，种类不同的车额定载重量与额定容积不同，在设计路线经过运营网点时，额定容积和额定载重量影响到车辆是否还有空余空间装填货物，是否有必要经过该网点，在优化路径问题上，车辆种类是核心因素。不同车辆还会产生不同的成本，比如不同车辆的百公里油耗不同，保养费用维修费用不同，车辆的购买费用不同等。（4）客户客户是影响车辆路径问题的核心因素之一，客户优先级的不同影响车辆的路径，如客户对配送时间有要求，客户选择的服务类型，客户的需求量等，都影响车辆的路径选择。（5）道路道路是车辆路径的核心要素之一，道路连接起了各个网点，道路的好坏也影响到了货物配送路线选择，反映到模型中，道路运行的距离长短直接影响配送时间，影响运行产生的费用等。（6）目标函数车辆路径问题的目标函数一般从以下几个角度出发，包括车辆路径产生的总费用最低，费用包括过路过桥费、油耗使用费、车辆由于行驶磨损产生的车量折旧费，以及车辆的维修保养费等；车辆路径的距离最短，车辆路径的长短直接影响到最终的收益；客户服务水平最高，客户有优先级，有的客户对货物时间有要求，有的客户对货物的运量有要求。（7）约束条件车辆路径问题中的约束条件有：满足车辆最大行驶距离，满足客户对货物送达时间窗的要求，车辆有最大的装载能力，客户有优先接受服务的权利，车辆的数量一般也是有限的，一些客户对货物的规格有相应的要求，应该考虑在内。2.3.3车辆路径问题的类型随着经济的发展和行业的需求，从上世纪出现车辆路径问题起，国内外学者对车辆路径问题就开始了各个角度的研究，常见的几类车辆路径如表2-2所示。表2-2车辆路径问题分类依据问题类型问题描述配送任务分类特征纯送货、取货问题纯送货问题、纯取货问题只对这个客户进行送货或取货，没有往返送取结合问题车辆既要对该客户点送货同时也在该客户点进行集货车辆载货状况货物满载配送时，车辆的额定载重小于货物的配送量，需要一辆以上的车辆完成任务货物非满载配送时，货物的配送量小于车辆的额定载重，多个客户的需求可以用一辆车满足车场数量一个车场客户配送用了一个车场多个车场客户配送用了多个车场车辆和车场的联系开放式问题完成任务后车辆不需要返回起点封闭式问题完成任务后车辆需要返回起点运送货物类型单品种货物配送的货物是同一种货物多品种货物配送的货物是不同的货物目标数量单目标问题让某一个目标函数达到最优解多目标问题考虑让多个目标同时达到最优研究时往往都是以上问题组合优化，得到不同的车辆路径模型。

3.数学模型的建立本章分析了车辆路径与车辆配载之间的关系，同时引入客户满意度，通过完善目标函数和约束条件，建立一个综合的优化模型，解决实际问题。3.1运营网络综合优化分析3.1.1运营网络与客户的联系在2.1中，我们已经初步讨论了一个完整的物流运营网络，其中车辆配载问题与车辆路径问题都是核心问题[23]，车辆配载过程中，涉及到车辆的使用，车辆路径问题中也涉及的车辆的使用，于是通过车辆，我们就将二者建立了联系，一个物流运营网络优化的成功与否与客户之间也有必要的联系，优化运营网络除了要考虑企业的成本费用外，也要考虑到客户的满意度。设计运营网络，要综合考虑这些问题，需要符合实际的案例。车辆路径问题与车辆配载问题是我们优化运营网络的抓手，通过客户的满意度来衡量运营网络优化情况，综合考虑问题，建立数学模型，设计算法，结合实际案例进行讨论，确定模型的可行性，解决运营网络中存在的不合理情况，从而降低成本，提高满意度。3.1.2综合优化思路对于运营网络的优化，有三种优化思路，一种是以车辆配载问题为主，通过节约算法优化运输路径；一种是以车辆路径问题为主，设计一条最优路线，将路线与客户满意度建立联系；一种是综合分析车辆路径问题和车辆配载问题与客户满意度三者之间的关系。（1）车辆配载问题为主以车辆配载问题为主，有多个目标函数，比如货物载重不能超过额定载重，货物体积不能超过额定容积，车辆使用数目最少，多目标函数问题有的求最大值，有的求最小值，同时需要考虑运输路径问题。这种设计思路作为多目标函数问题，统一目标函数较困难，设计算法较为困难，同时考虑到优化路径，最后求得的解限制在一定的范围内，不能很好的解决案例问题。（2）车辆路径问题为主以车辆路径问题为主，目标函数可以考虑设计车辆运行成本最低或者车辆总行驶路径最短，同时考虑客户的因素，比如客户对配送时间和货物量的要求。这种设计思路没有考虑到车辆的最大配载能力，设计出的最优解无法满足普遍需求，不能很好的解决案例问题。（3）车辆路径、车辆配载与客户满意度设计两个目标函数，一个目标函数为车辆行驶总路程最小，一个目标函数为客户总满意度最高，同时将车辆配载作为约束条件，要求车辆的货物总重量不能超过车辆的额定载重量。这种设计思路很好地解决了车辆路径问题与车辆配载问题之间的联系，同时又考虑到客户的实际需求，可以很好地解决案例问题，从而寻找到最优解。本文将采用第三种优化方式，结合案例建立数学模型，设计算法解决实际问题。3.2建立综合优化模型需要考虑的问题车辆路径问题是NP难问题，车辆配载问题同样也是NP难问题，我们还引入了客户满意度，单独求解这些问题都比较繁琐，将三者组合起来解决更是增加了问题的难度，模型之间会产生一些问题，互相制约或者影响，所以在设立综合模型的时候需要考虑一些问题。（1）目标函数单独优化车辆路径模型或者车辆配载模型，需要考虑到车的载重率，容积率，车的行驶路程与费用等，客户满意度需要考虑时间问题，综合优化时选择以车辆总路程最短和客户满意度最高作为目标函数。（2）约束条件将车辆载重作为车辆的约束条件，在后续设计算法时，可以有效的降低复杂程度。考虑车辆路径问题与客户满意度问题时，两个目标函数整体建模时也要考虑到两者共有的约束条件。（3）统一参数变量两个目标函数进行设计时，要将涉及到的参数变量进行统一，避免在后续设计算法时会因为参数变量不统一造成结果出现误差，不具有实用性。3.3模型的确定3.3.1模型描述在第二章分析了车辆路径问题与车辆配载问题涉及到的理论知识，同时在第三章开篇也提到了综合优化思路，本文所研究的车辆路径问题、车辆配载问题以及客户满意度问题所涉及到的范围为：一个配送中心、单车型、车辆闭环运送、以时间为约束条件的客户满意度。可以具体描述为：从一个配送中心出发多辆车向多个门店送货，每个门店的位置确定，车辆的类型相同（车辆的额定载重和额定容积相同），每辆车的参数已知，选择合适的配送路线，使车辆不超过额定载重和额定容积，让车辆行驶总路程最短，送到门店后，评价客户总满意度。3.3.2模型假设和符号说明（1）模型假设环境模型在以下的环境中建立：①配送路线是一条闭合回路；②门店的位置是确定的。③车辆的型号一致；④客户评价指标一致；⑤货物类型不做要求。（2）模型中涉及到的参数及变量xijuijSiDiLktiyiv表示车辆行驶速度3.3.3车辆路径目标函数的确定通过第二章的理论分析，通过参阅大量的文献，车辆路径问题的模型建立目标函数一般从两个方面优化，一个是总成本最小，一个是总路程最短，结合案例，选择总路程最小的目标函数作为本文目标函数。本文的车辆路径问题描述为：某车场有车k辆，车辆要从车场为客户送货，表示为从客户i处行驶到客户j处，在充分利用车辆的情况下，使得行驶总路程最短。对模型中的参数定义：k为车辆编号，k=1,2…k；i和j均为客户编号，客户也可代表为两个地点；i=1,2，…N，j=1,2，…N；xijk表示车辆k从客户i处驶至客户j处；min（3-1）对目标函数解释如下：式（3-1）表示车辆行驶总路程最小。3.3.4客户满意度目标函数的确定将客户满意度与时间建立一个联系，如果配送时间越短，那么客户的满意度就越高，如果配送的时间越长，那么客户满意度越低，同时随机给了每个客户一个满意度的值。对模型中的参数定义：Si表示服务客户i的满意度；tmax（3-2）对目标函数解释如下：式（3-2）表示客户总满意度最高。3.3.5约束条件的确定对模型中的参数定义：Di表示客户i的货物需求量；Lk表示车辆k的额定装载量；yii（3-3）t（3-4）k（3-5）j（3-6）i（3-7）j（3-8）x（3-9）y（3-10）对约束条件的解释如下：式（3-3）表示在每条线路上，车辆服务的所有门店的货物总重量不超过车辆的额定装载量；式（3-4）表示车辆k到达门店j的时间；式（3-5）表示一辆车服务一个门店；式（3-6）（3-7）表示到达每个门店的车辆的唯一性；式（3-8）表示车辆从配送中心车场出发，完成配送任务后再返回配送中心车场；式（3-9）（3-10）表示决策变量对0、1的约束。

4.求解算法设计4.1遗传算法遗传算法起源于上世纪，一经提出就收到了全世界各个行业学者的注意，因为它可以解决很多问题，经过了近半世纪的发展，遗传算法如今已经变成了很典型的智能优化算法，在车辆路径的优化问题上得到了广泛的使用[24]。遗传算法的基本思路是首先要有一个初始的种群，里面包括一定数目的个体，个体的编码方式有很多种，一般都会采用二进制或者自然数编码。总的来说遗传算法就是对初始的种群个体不断地循环迭代寻找一个最优的解，在每一轮的循环过程中，算法都将被选择的个体进行交叉、变异，产出新的子代，父子两代种群，一起合并成为下一轮循环的初始种群，如此循环往复，不断的优化，不断地适应环境，直到达到条件，停止迭代，并从当前的种群中找到最好的解。遗传算法有以下的特点：（1）全局性遗传算法可以同时对整个群体的所有个体进行评估，相比于其他算法对单个的初始个体进行跌倒优化，全局搜索的能力更强，范围更广，能够避免陷入到一个地方反复求最优解，导致结果不具有普适性。（2）随机性类似于基因的遗传变异有一定的概率，遗传算法的交叉变异也是在一定的概率下进行的，相比于其他算法更具有随机性，在求解时更容易获得最优解。（3）普适性遗传算法的适用问题多种多样，遗传算法的应用范围更广。遗传算法是通过初始种群的不断迭代从而得到最优解，一般计算流程如图4-1所示。图4-1遗传算法基本流程4.2非支配排序遗传算法NSGA-Ⅱ典型的遗传算法一般面向的问题是求解单目标函数，当有多个目标函数需同时需要解决的时候，我们一般采用非支配排序遗传算法NSGA-Ⅱ。Deb等[25]于本世纪初发表了一个带有精英策略的、非支配排序的遗传算法，这种算法被命名为第二代非支配排序遗传算法，自此学者们开始将该方法用于许多领域的研究并取得了很好的效果。NSGA-Ⅱ主要有以下几个内容，精英策略、采用拥挤度和拥挤度比较算子，和快速非支配排序算法，这几个方式综合改进了个体选择的过程。图4-2NSGA-Ⅱ基本流程4.2.1pareto解一个目标优化问题和多个目标优化问题，理论上还是有许多不同之处。如果只有一个目标函数，我们寻找最好的解，这个解要好于其他的解,一般都是全局的最大或最小,即全局最优解。但是如果问题存在了很多目标时，因为目标之间存在冲突，没有办法比较，所以就很难找到一个解，使所有的目标函数同时达到最优，对于多目标优化问题，我们通常会有一个解集，这种解被叫做非支配解或帕累托最优解，定义如下[26]：对于最小化多目标问题，n个目标分量fi(i=1,…，n）组成的向量fX=(f当且仅当，不存在决策变量Xv∈U，v=fXv=∀4.2.2Paerot支配关系对于最小化多目标问题，n个目标分量fi(i=1,…，n）组成的向量fX当且仅当，对于∀i∈1，…，n，都有fiX当且仅当，对于∀i∈1，…，n，有fiXu＜fi

4.2.3快速非支配排序算法、拥挤度估计、精英策略开始我们设定种群为p，我们需要通过算法计算p中的两个参数np和Sp，包括每个个体p，这里的np是个体数，是种群中支配个体p，一个种群中，被个体p支配的个体集合称为Sp。整个种群都遍历过后，这两个参数复杂度的总计算是O（拥挤度估计可以保证种群多样性，为了得到种群中的特定解，需要得到他周围的解的拥挤度估计，这点两侧的两个点的平均距离就是我们要根据这些目标函数计算的内容，如图4-3所示。精英策略是保留父代中优良个体，让其直接进入到子代，目的是防止获得的帕累托最优解丢失。精英策略会选择算子，按三个指标，由父代Ci，和子代Di，合成的种群Ri图4-3拥挤度估计4.2.4算法流程算法流程如图4-4所示。第一步：生成随机个体并通过选择算子选出包含N个个体的初始种群P0第二步：对初始种群中的个体，执行交叉和变异操作，生成子代种群Q0，其个体数为N第三步：合并两个种群，令R0=P0∪第四步：利用快速非支配排序对种群分层得到个体的序值，对于同层的个体利用小生境算子（即NSGA-Ⅱ的拥挤距离算子）计算个体密度值，并基于序值和密度值对合并后的R0进行修剪，得到下一轮循环的初始种群P1，其个体数为第五步：判断程序是否已经达到迭代终止的要求，若是，则对种群进行分层，输入第一层的个体；如果不是就转第二步。图4-4算法流程解释图4.3总结NSGA-Ⅱ的优劣NSGA-Ⅱ优势：（1）快速非支配排序法的提出，降低算法的计算难度和复杂度。（2）算法中出现的拥挤度和拥挤度比较算子，可以代替需要指定共享半径，才能实现的适应度共享策略，同时在快速排序后的同级比较中，可以作为胜出标准，可以使准帕累托域中的个体放大到整个帕累托域，同时使其可以均匀分布，有效的保持了种群的多样性。（3）算法提出了一个精英策略，可以有效的扩大采样空间。算法将父代种群、与其产生的子代种群一起组合，让其共同竞争，产生下一代种群，这样的做法有利于保持父代中的优良个体进入下一代，同时通过对种群中所有个体分层存放，可以让种群中的最佳个体留存，可以迅速的提高种群水平。NSGA-Ⅱ劣势：（1）在高维多目标优化中，由于维度较高，拥挤度策略作用低。（2）非支配解在种群中比例增加，会导致搜索过程缓慢。

5.案例分析本章以某交通运输集团为例，对本文建立的数学模型和设计的遗传算法进行验证，验证模型的可靠性与算法的有效性。5.1项目基本情况5.1.1背景介绍某交通运输集团是一家物流企业，方便了人们的生活，满足了社会的需求，对国家的贡献很大，如今某集团已成为集多领域业务为一体的大型综合性物流企业。社会在发展，时代在进步。京东物流、顺丰物流等物流公司如雨后春笋般蓬勃而出，迅速发展，如今在满足了物流运输网点遍布全国的基本需求后，人们对物流服务提出了更高的要求，比如要对时间，对运输安全提出要求，如此的社会发展方向要得到满足，企业就要不断进步，因为不进则退，公司就需要不断地创新，需要优化运营网络。5.1.2运营现状某交通运输集团车辆为同一型号的货车，车辆有最大行驶里程，运送货物结束后要返回到车场，方便统一调配管理。目前，某交通运输集团的主要货车信息的相关参数如表5-1所示。表5-1车辆相关参数车辆类型车辆数量（辆）额定载重（t）货箱尺寸长宽高（mm）额定容积（m³）载货最大使用里程（km）货车5144000*2000*200014200企业运营网络配送的工作流程大致为：先确定客户所在地点，根据客户的需求和地点进行配载、装车，按着给定的线路送到客户处，车辆再返回配送中心，其工作流程图如5-1所示。图5-1某交运集团物流作业流程该物流企业从配送中心向附近30家门店进行配送，其中原点是配送中心所在的位置，其余1到30号为门店的分布图，具体门店坐标如表5-2、5-3、5-4、5-5、5-6、5-7所示。表5-2门店1到门店5的坐标门店12345x3.69377.770565.876655.586325.3680y69.907789.090395.929154.721613.8624表5-3门店6到门店10的坐标门店678910x76.01782.755735.099530.524761.2413y14.929440.750884.071725.428281.4285表5-4门店11到门店15的坐标门店1112131415x73.616014.949839.181235.646951.7050y24.352592.926434.998419.659525.1084表5-5门店16到门店20的坐标门店1617181920x56.749275.374922.082054.376252.4078y61.604547.328835.165983.082858.5264表5-6门店21到门店25的坐标门店2122232425x13.00899.519839.869176.779527.2308y54.972391.719428.583975.720075.3729表5-7门店26到门店30的坐标门店2627282930x46.821417.904960.101320.407640.4765y38.044556.78217.585425.395053.0797在该企业中，随机选取5辆车查看运行路线，5辆车的运行路线如表5-8所示。表5-8优化前的车辆路径车辆编号路径10-22-6-3-16-11-30-7-28-020-17-14-8-5-29-21-030-25-27-26-19-15-1-23-040-2-4-18-24-13-9-050-20-10-12-0如表5-8所示这5条现行的运营路线，车辆运行总路程为1532公里，客户满意度为1.2272×109。5.2结果分析与讨论本文采用MATLAB编写程序，验证模型的可靠性和算法的有效性，参考文献中一般都会确定一个初始种群数目，这个数目值一般都会取在50-2000之间，首先设置数目为10，快速验证结果是否符合要求，曲线趋势是否正确，然后再将初始种群数量设置为1000，进行实验。种群初始化的时候，根据算法方案让1000个个体作为初代染色体。本文设定最大的迭代次数为100，若在100代时模型没有像预期一样收敛或者收敛的效果不如预期理想，则我们要修改迭代次数，迭代次数经过修改后，要再一次运行程序。通过多次实验，多次取值，得到了如下的程序运行结果，见图5-2、5-3、5-4，分别为总行驶公里数变化趋势图、客户总满意度变化趋势图以及优化后的车辆路径图，对变化趋势进行相应描述，对客户满意度趋势进行相应描述，对路径进行相应分析，得出了优化后的数据与方案。图5-2车辆行驶总路程的变化趋势图从图5-2中我们可以发现，迭代最初的时候，优化后的曲线斜率变化速度比较快，但是当迭代次数不断增加，迭代过程的累加，迭代后的曲线斜率逐渐变的平缓，实验在迭代到第50代时，曲线开始收敛到该车辆行驶总路程问题的最优解。分析过程我们可以知道，开始我们得到的解相对较差，但是随着迭代次数的增加，进化过程的进行，我们设计的遗传算法会自动寻优机制，指导搜索过程向着目标更好的方向逐渐收敛，进而逼近最优，从41代左右后，可以看出问题解的波动性开始逐渐相对稳定，同时在第50代搜索到了上述最优解，车辆行驶总路径的优化结果为630.54。图5-3客户总满意度的变化趋势图从图5-3中可以看出，优化刚刚开始的时候，优化曲线的变化率比较快，在第40代收敛到该问题的最优解。在迭代到第8代到第18代的时候，总满意度在0.65×1010到1.1×1010左右波动，在第20代的时候，有一个非常迅速的跃升，随着迭代次数的增加，进化过程的进行，我们设计的遗传算法开始自动寻优机制，指导其搜索过程向着目标更优化的方向进行收敛，得到的解逐渐逼近最优，自40代左右后，问题解的波动性开始趋于相对平稳，同时在第40代时搜索到了上述问题的最优解，最后客户总满意度的优化结果为1.48×1010。

图5-4优化的车辆行驶路径图配送中心根据30个门店的需求选择5辆车进行配送，生成了5条配送路径，如表5-9所示。表5-9优化后的车辆路径车辆编号路径10-4-24-17-11-6-28-15-26-020-20-16-10-3-19-8-30-030-13-23-14-29-5-9-040-18-7-21-27-050-1-2-22-12-25-0如表5-9所示，优化后的车辆路径车辆总行驶公里数为630.54，对比表5-8中5条车辆路径车辆行驶的总公里数1532，减少了901.46公里，对比表5-8中客户满意度1.45×1010，优化后的客户满意度为1.48×1010，客户满意度提升了0.03×1010，优化前后车辆行驶总公里数降低，客户满意度增高，说明了模型的可靠性、以及算法的有效性，模型可以解决实际问题。6.总结在物流运营网络中，车辆路径问题是影响物流企业收入关键因素之一，将车辆路径问题与车辆配载问题关联，同时将客户满意度作为衡量标准，为实际案例提供了解决方案，具有实际意义。本文主要做了以下几个方面的工作：（1）理论分析工作文章做了大量的理论分析工作，首先分析了企业运营网络的运营流程，并指出运营网络中影响收益的几个因素，并对相关构成要素深入分析。其中关于车辆配载问题，分析了车辆配载中的要素，关于车辆路径问题，也分析了车辆路径问题中的要素。（2）数学模型的建立与算法的设计文章建立了多目标函数的综合优化数学模型，将车辆路径问题与客户满意度问题作为目标函数，将车辆配载问题作为约束条件，构建的数学模型简洁美观，富有实用性，能够解决实际问题。（3）分析案例文章引入某交通运输集团实例，对模型的可行性进行检验，对某交通运输集团实例进行分析，根据其现有网点对车辆路径进行优化，寻找总路程最短、客户满意度最高的方案。

参考文献[1]景晶.关于我国社会化物流体系的构建.决策和信息.2008,12:31-32.[2]宋亮.面向物流行业的车辆路径问题数学建模与近似算法设计：（博士学位论文）.深圳：哈尔滨工业大学，2018.[3]周颖.零担货物配装模型与算法研