《考虑时间窗的多车场多车型车辆调度路径优化探究》（论文）

II绪论1.1研究背景及意义随着移动互联网的快速发展，品牌制造商的线上销售渠道所占比重逐渐增加，其物流需求也随之呈现出小批量、高频次、多样化、定制化的特点。传统合同物流企业如何适应顾客需求的变化，为品牌制造商提供更加个性化、定制化、更高效率的服务，在竞争激烈的斗争中脱颖而出，是企业管理者和学术研究者在新的竞争背景中主要关注的问题。合同物流（ContractLogistics）是物流企业与有货源的制造销售企业通过签订一定期限的物流服务合同的方式，利用物流企业自有资源或整合社会仓储、干线、配送等资源，为有货源企业提供全部的或一部分的定制化物流服务，满足有货源企业的物流需求。近年来，物流行业的同质化问题严重，竞争不断加剧，利润空间日渐稀薄，主要表现在客户差异化需求不断发展，以服务于品牌制造商线下销售渠道为主的传统物流企业面临着市场份额不断被挤压的挑战。这种内忧外患的局面加剧了传统物流企业的经营压力，仅仅依靠传统单一的线下销售渠道越来越无法满足客户的要求。因此，很多合同物流企业纷纷寻求降本增效、转型升级的路径与突破口，希望打破现有的天花板，让企业保持长青，满足品牌制造商日益差异化的物流服务需求，为其提供更加高效的定制化物流服务，是物流企业发展的主要方向。基于品牌制造企业向线上等多种渠道转型的趋势背景，物流需求也随之发生了变化，对物流服务的质量和效率提出了更高的要求，其需求差异性特征主要表现在：传统线下业务类型大多为ToB业务，主要面对品牌制造商的各级经销商，货物调配批量较大，需求量较为稳定；线上业务面向客户范围广，订单较为随机，需求呈现小批量多批次的特征，需要较高的响应速度和运输效率。由于线上与线下对物流服务的需求不一，品牌制造商的电商渠道与线下渠道分立，导致传统合同物流服务商的份额被挤压。因此在当前竞争背景下，为提高合同物流企业同时为线上渠道和线下渠道服务的能力，保证市场份额不被挤压，需要其提高自身物流服务能力，实现降本增效，品牌制造商的差异化需求，对合同物流企业产生的新的要求主要体现在：（1）针对品牌制造商货物运输批量较为随机的特点，物流企业需要提高运力协调的能力，对不同批量的运单进行整合，合理的调配车辆，规划运输路径，提高运输配送的效率，实现降本增效；（2）利用合同物流企业所具有的干线运输、仓储配送及一体化管理优势，为品牌制造商提供端到端的全程供应链解决方案，利用城市配送中心等仓储资源及高效精准的运输配送能力，提高品牌制造商的订单响应能力；（3）品牌制造商的末端客户对于配送时间的要求更加严格，需要合同物流企业精准控制各级运输网络的运输时间，以免延误货物的末端配送。本文以从品牌制造商到城市配送中心的二级运输网络的车辆调度和路径优化问题为切入点，围绕品牌制造商的个性化需求，为物流企业提高运输效率，改善物流服务运作能力，提供可行方案与建议。1.2国内外研究现状车辆路径问题（VehicleRouteProblem，简称VRP）是1959年由RamserJH和DantzigGB[1]提出的，一直被国内外许多学者所探讨。其基本情况描述为：针对一组有运输需求的客户和一定数量的车辆，规划出合理的车辆运输路线，使车辆能够以一定顺序到达所有客户点，满足客户需求，并在一定约束条件下，使运输总成本最小或运输路径最短。VRP问题作为物流供应链研究中的重要一环，目前已得到较多研究。前期研究主要是围绕算法的求解以及优化开展，随着VRP问题研究的深入，许多学者开始结合实际中存在的问题，考虑更加接近实际的约束条件，主要包括考虑装载量（CVRP）、配送时间窗（VRPTW）、多车型（HFFVRP）以及多车场（MDVRP）等，此外还有学者将客户满意度也纳入研究范围，为车辆的智能调度与路径优化的现实工程提供了理论基础。1.2.1考虑装载量的路径优化问题CVRP问题的主要约束条件是要求车辆所配送的订单或客户的货物重量或体积不能大于该车辆的装载上限，同时每个订单的运输执行只能由一辆车完成，且所有车辆只能都完成取货或者都完成送货，是车辆路径问题中最基本的类型。在VRP问题研究早期阶段，各学者以车辆装载量为约束，建立车辆路径优化模型，基于遗传算法、禁忌搜索算法、模拟退火算法等算法进行求解，结果显示对于特定模型求解各算法均具有较好的求解效率和效果。李琳等人[2]针对电子商务市场环境，建立了带能力约束的车辆路径优化模型，并使用改进的禁忌搜索算法进行求解与算例测试。李军[3]以最小化运输费用为目标函数建立了车辆调度模型，并设计了一种免疫遗传算法，对比了该算法与传统遗传算法的结果。R.Tavakkoli[4]等建立了一种需求可拆分的考虑装载约束车辆路径问题模型，通过提高车辆装载率来减少使用的车辆总数，并通过模拟退火算法进行模型的求解。阎庆和鲍远律[5]设计了一种具有记忆功能的遗传算法和模拟退火算法相结合的混合算法，以此求解车辆路径物流配送问题。严蓉[6]研究了区域内干线物流的运输网络，提出通过改变车辆运输的规则，增加车辆途径分拨中心停靠功能来提高车辆的装载率。向婷[7]等人设计了一种先分组后路径的聚类算法，先根据邻近原则进行分组，通过车辆负载对客户数量对客户进行组合和拆分，最后使用蚁群算法规划每组客户的线路。朱丽娟[8]考虑了二维的货物配载问题，建立了新型的货物配载与车辆路径组合优化模型，并采用改进遗传算法进行求解，用MATLAB求解了实际中的相应问题。1.2.2考虑配送时间窗的路径优化问题在现实运输配送中，时间窗是车辆配送常常需要考虑的问题，许多学者将配送时间窗作为其模型中的主要约束条件。在研究中，时间窗主要有硬时间窗、软时间窗和模糊时间窗三种。硬时间窗要求配送车辆必须在规定时间段内到达，否则将不接收货物，具有固定性；软时间窗具有一定的灵活度，车辆在时间窗以外的范围到达也能够接收货物，但需要受到一定的惩罚，更加符合实际中客户对时间窗的要求；在实际生活中，顾客的服务时间窗存在多个时间段，对车辆到达时间具有模糊性，相较前两种情况，模糊时间窗更接近现实情况，因此具有更高的研究价值。许珮[9]考虑了硬时间窗和车辆装载能力约束的限制，建立了以最小化运输成本和车辆等待服务时间为目标的双目标VRPTW模型，使用遗传算法进行求解，并考虑不确定性因素，建立了对应的鲁棒模型。李啸麟[10]分析了电动车作为物流配送车辆的车辆路径优化问题，建立综合运输成本的硬时间窗多车型车辆路径优化模型。何小锋[11]设计了量子蚁群算法，求解带硬时间窗的车辆路径问题，使用设定人工蚂蚁的转移概率、改变信息素更新等方式提高算法的搜索能力。段雪凝[12]建立了带时间窗的冷链物流车辆路径问题优化模型，优化目标是总配送成本最小和配送准时性最高，并进行了实例求解。KohlN等人[13]建立了VRPTW模型，用拉格朗日松弛算法得到了问题下界，并用分支定界法进行求解。JufangBao等人[14]改进了混合遗传算法，设计了物流路径优化模型。范厚明等人[15]研究了带软时间窗的同时集配货车辆路径问题，设计了混合粒子群算法进行求解并验证。Kaabachi等人[16]研究了考虑时间窗、车辆配载以及车辆总数等约束的多车场车辆路径问题，构建了以总成本。油耗量以及二氧化碳排放量为最优目标的多目标函数模型。闫芳等人[17]同时考虑了时间窗约束与客户满意度两个因素，将服务时间作为度量客户满意度的标准，优化目标为总成本最小化和客户满意度最大化，构建了多模糊时间窗的车辆路径组合优化模型，并引入惩罚因子，最后使用粒子群算法进行了求解。曹庆奎等人[18]建立了基于时变交通流的多模糊时间差路径优化模型，并设计了改进伊藤算法进行求解，随后得出成本最小及顾客满意度最大的车辆调度方案。1.2.3考虑多车场多车型的路径优化问题在企业实际的物流配送中，车场或仓库的数量可能不止一个,所使用的配送车辆型号往往不是单一的，所以衍生出针对多车场多车型的车辆路径问题。多车场多车型的路径规划问题，包含了多种车型，多个车场两个约束，相比于其他约束条件更为复杂，目前与这方面相关的求解算法还不够成熟。肖燕等人[19]考虑了VRP问题中的车型、载重、配送时间窗等限制条件，建立了多车场多车型的车辆调度组合优化模型，并使用C-W节约算法和动态规划算法进行求解。孙会龙[20]分别构建了单车场和多车场两种VRP模型，运用遗传算法通过实例对模型进行求解，与实例中的原有方案进行对比，优化方案明显降低了配送成本。张源凯[21]研究了网上超市“一地多仓型”订单分配的影响因素，根据订单的一单多品特性、配送的相关能力约束建立了运筹学优化模型。陈呈频等[22]针对多车场、多车型的车辆调度问题构建了优化模型，并使用多染色体遗传算法进行了优化求解。Gan等人[23]研究了各种车型数量不确定的情况下的多车型车辆路径问题，并利用粒子群算法进行了求解。兰奇[24]研究了考虑车型类别的VRP问题构建了相应模型，设计了算例并使用遗传算法通过CPLEX进行求解。Desrochers等人[25]提出了一种基于连续路径融合的节约算法用于HFFVRP问题的优化求解，在迭代过程中通过加权匹配的策略选择最好的融合路径。Zhen等人[26]研究了以最小配送时间为目标，考虑时间窗的多车场车辆路径问题，解决了最后一公里配送中的实际问题，并提出了一种基于粒子群算法和遗传算法的混合算法进行求解。JianLi等人[27]研究了带时间窗的多车场车辆路径问题，考虑了时间窗、通行能力、路线运输时间、各车型数量等约束条件，建立了以最小总成本为目标的整数规划模型，并提出了一种具有自适应局部搜索的混合遗传算法。Mancini[28]研究了多车场多车型多周期的车路路径问题，提出了一种针对MDMPVRPHF的混合整数规划公式，并提出了一种基于自适应大邻域搜索（ALNS）的数学方法，其中定义了不同的破坏算子。Salhi等人[29]针对多车场多车型的VRP问题，提出了有效的可变邻域搜索方法，除了适应现有的邻域和局部搜索算子外，还引入新的功能，节省了近80%的CPU时间。除了考虑装载量、时间窗、多车场和多车型这些约束条件，目前许多学者在客户及员工满意度对车辆调度及路径规划的影响上也进行了相关研究，但相比其他约束条件，基于满意度的车辆路径研究目前还不太成熟。雷健锋[30]引入“客户重要程度”作为客户满意度权重系数，构建了基于客户满意度的VRP模型；孙尧针[31]考虑了买卖双方的满意度，建立了基于双方满意度的物流车辆路径优化模型；江雨燕和吴恒成[32]建立了基于员工和客户满意度的路径优化模型，并将满意度进行了量化，用模拟退火遗传算法进行求解，得到了较优的结果；李慧丛[33]设计使用了员工满意度金额客户满意度的模糊隶属函数，并将其作为目标函数，建立了VRP模型。1.3主要研究内容本文基于合同物流企业的干线运输网络，实现存在差异化需求的多个客户之间以及多配送中心之间的货物调配，寻找车辆调度与路径规划的最优方案。通过查阅相关文献及前人研究成果，近几年国内外对于VRP问题的研究多集中在末端配送优化上，以此提高末端物流效率，打通最后一公里，增加顾客满意度。然而对于干线运输的车辆调配与路径优化研究相对较少，在当前线上线下渠道需求差异化问题严重的背景下，运单的货物量较为随机，需要将多个运单组合运输，而人工调配可能会导致车辆运力的浪费以及运输成本的增加。其次，研究数据表明，目前我国的公路运输业务占总体物流费用约70%，在当前激烈的行业竞争形势下，合同物流企业实现干线运输的降本增效对于提高其自身行业竞争力显得尤为重要。基于此，本文结合合同物流企业干线运输流程，考虑了时间窗、车型限载、等约束条件，研究了多车场多车型的货物取送车辆调度与路径优化问题。通过分析各约束条件，以最小化运输成本和超时惩罚成本为目标，建立了研究问题的数学模型，并利用改进后的遗传算法进行求解，最后基于中外运华北公司的企业背景模拟了一个小型算例，用Matlab对模型和算法进行实现，给出了算例的最优车辆调度和路径规划方案。本研究的难点在于不仅考虑了车辆到客户点取货的过程，而且考虑了车辆取货之后将货物送到指定的配送中心的过程；不仅要在选择使用何种车型进行货物的运输，而且需要在各配送中心各车型数量有限的情况下，决策从哪个配送中心调配车辆才能实现路径最小化；不仅需要考虑车辆限载的约束，整合部分运单，规划到达客户点的运输取货顺序，而且需要考虑回到配送中心送货的先后顺序。1.4论文组织结构本文主要利用遗传算法来解决合同物流企业干线运输网络的车辆调配与路径优化问题，提高自身线上线下销售渠道一体化物流服务运作的能力，以满足具有差异化需求的各品牌制造商，论文结构共包含五章：第一章绪论，介绍了本文研究的背景和意义，提出了在时间窗和车辆限载等约束条件下，考虑多车场多车型的货物取送路径优化问题，以此作为本文的研究内容，并对其他学者做出的在各种约束条件下的车辆路径优化问题的研究进行了总结与分析。第二章为研究模型的设计与构建，根据制造企业差异化需求的特点，设计了考虑时间窗和货物取送的多车场多车型的车辆路径优化数学模型，以最小化运输成本和超时违约成本为目标，构建目标函数，并根据实际情况提出约束条件。第三章为算法的选择与设计，本章首先介绍了常用的几种算法并简略地分析了其优缺点，由于本文模型约束条件较多，模型较为复杂，因此选择了遗传算法进行求解；并根据研究问题约束和模型特点对遗传算法进行了合理的调整改进，设计了一种二段编码方式，实现优化问题的求解。第四章为算例分析，设计了符合本文模型特点的算例，参考中外运华北公司干线运输流程对算例参数进行设定，并利用Matlab编程实现了模型和算法，求出了算例的最优方案。第五章总结与展望，总结了本文研究内容与成果，以及本研究的创新点和存在的不足，并指出在该方向上可进一步研究的内容。车辆运输调度问题描述及模型设计2.1问题描述本文研究问题基于合同物流企业从品牌制造商到城市配送中心的货物干线运输流程，研究了考虑从多个配送中心进行车辆的统一调配，实现不同运单的组合运输。如下图2-1所示，合同物流企业货物调配一般存在三级运输网络，一级运输网络是从品牌制造商运送到对应城市配送中心，二级运输网络是配送中心之间的货物调度，三级运输网络是从配送中心到末端顾客的城配运输。本文研究合同物流企业的一级干线运输网络，为其车辆调配与路径优化提供现实指导意义。具体运作流程为由客户订单生产货物调度订单，从多个配送中心中选择合适车型的车辆并规划最优路线进行货物的调度运输，取货点为品牌制造商指定的仓库或供应商，送货点为根据客户需求所分配的配送中心。图2-1合同物流企业三级运输网络示意图本模型的优化目标主要考虑以下几个方面：（1）合理调度车辆，规划运输路径，以减少运输总成本，实现物流企业的降本增效，提高核心竞争力；（2）整合运输差异化需求运单，合理安排运力，实现运输效益的最大化，防止旺季时运力短缺；（3）通过时间窗以及惩罚参数的设置，限制货物送达指定配送中心的时间，保证后续城配运输的正常进行，提高干线运输效率。综上所述，本模型研究问题可具体描述为：某合同物流企业在某地区拥有多个配送中心（车场），分布在该地区中的各个城市，每个配送中心均拥有多种车型的车辆若干，配送中心之间实行一体化管理，因此不同配送中心之间的车辆可以任意调度，即从某配送中心出发的车辆可以回到任意一个配送中心。当收到客户（品牌制造商或供应商）的调度运输任务时，可从任一配送中心中调用企业内任意车辆资源，前往客户点取货，并调配到指定的配送中心，完成货物的干线运输。同时配送中心对货物送达的时间具有较为严格的要求，若货物无法按时送到相应配送中心，则会影响货物后续的城配运输。其中客户的位置坐标以及货物量是已知的，配送中心的位置坐标、车辆的车型、限载量是已知的。该研究问题不仅需要确定每个客户应从哪个配送中心调配车辆，以及应由哪种车型的车辆进行运输，同时还要考虑客户取货的先后顺序，以及货物返回到达配送中心的顺序，最终目标是在考虑客户时间窗、车辆限载等一系列约束条件下，找到总成本最小的路径优化方案。2.2智能调度模型设计2.2.1模型假设基于以上问题描述，在进行问题的研究以及模型的构建之前，首先对该研究问题进行进一步研究假设：（1）车辆运输的路径都起于配送中心，终于配送中心，且配送中心位置固定，车辆由合同物流公司统一进行调度管理，不同配送中心之间的车辆可随意调度；（2）每个运单都有明确的货物信息，各个运单的取货点以及送货点（对应的配送中心）的位置坐标已知，且运输货物的重量和体积已知；（3）假设不同车型车辆的行驶速度一致，运输时间只与运输路径长度有关；（4）不同种类的货物可以混装运输，且每种运输货物都不限制车型，即在装载容积和重量的限制内，每种车型都可承运任何货物；（5）运输处于理想状态，不考虑因天气或道路施工等意外突发因素所造成的时间上的延误或车辆的破损，以及所造成的的风险与损失；也不考虑道路载重限行或车牌号限行等其他因素的影响；（6）本模型只考虑车辆，不考虑司机的相关约束条件，如司机可开的车型、状态、上下班时间、工作时长等，只要车辆处于闲置状态，就可以承运货物。2.2.2相关参数及变量说明P{1,2,……,M,M+1,……,M+N}客户及配送中心点集合，其中前M个为客户编号，后N个为配送中心编号；T{1,2,……,K}车辆集合，其中K为车辆总数，且每个配送中心的车辆编号是连续的；E=ddijGk车辆k的限载重量（k=1,2,……,K）LkCkCkqi点i的货物重量（i=1,2,……,M）li点i的货物体积（i=1,2,……,M）v为货车的行驶速度，假设货车始终保持匀速行驶；tik货车k到达节点isi节点iETi节点i决策变量如下：aijkuik基于以上参数符号的设置，该车辆路径问题的数学描述如下：某物流企业有N个配送中心，每个配送中心内各自停放着多种车型的车辆，所有车辆的总数为K。车辆需要从配送中心出发去往M个客户点装配货物，最后将货物送到指定的配送中心。该模型所要解决的问题是在满足约束条件下，寻求一个最优车辆调度和路径规划方案，将M个客户分配给N个配送中心中的具体车辆，同时确定每辆货车的行驶路线，使运输总成本最低。2.2.3目标函数该模型以总成本最小化作为优化目标，从运输成本、固定成本以及时间窗惩罚三个基本模块进行衡量，然后根据实际需求，加上需要考虑的相关因素，逐一进行分析并构建该模型的目标函数。（1）运输成本本模型假设不同车型的货车单位距离的耗油量不同（不考虑空驶和满载时的货车耗油量区别），货车在两个节点i和j之间运输时，会产生油费、过路费等可变运输成本，这些成本会随着货车行驶距离的增加而增加，现假定该成本与行驶距离成正比，不同车型产生的单位距离运输成本不同，因此需要考虑货车车型以及运输路径长度，以衡量运输成本，表示如下：（2）固定成本固定成本指车型不同的货车使用时所产生的不变成本，如车辆折旧、货车维护费等，只跟车型以及车辆是否使用有关，与车辆行驶路径无关。固定成本表示公式如下：（3）时间窗惩罚成本在货物进行调配时，物流企业对运输时间的控制有较为严格的要求，若货车晚于期望时间到达配送中心，则会对货物城配运输的安排产生影响，可能会导致货物城配运输无法按时送达，造成违约，因此在此对货物的干线运输设置一个软时间窗，若车辆无法按时将货物送至相应配送中心，则需要付出较大惩罚成本，数学表示如式（2-3），其中q为惩罚系数。P(则总惩罚成本为：因此，最小化总成本的目标函数为：minF=min2.2.4约束条件结合实际情况，该模型存在如下几个方面的约束条件：约束(2-6)与(2-7)保证了每个客户点都能被服务，且只能被服务一次，限制车辆装货过程一次完成，避免重复作业；约束(2-8)为路径平衡约束，确保车辆若有到达某节点的路线，则对应会存在由该点发出的路线；约束(2-9)确保了车辆k在客户点取货之后能够送到相应的配送中心，其中i’为客户点i对应的配送中心；约束(2-10)为所有车辆的总数量约束，每个配送中心拥有的不同车型的车辆数量有限，在车辆调度的过程中要使各配送中心实际使用的车辆数目低于配送中心所拥有的车辆数；约束(2-11)为货车装载重量限制；约束(2-12)为货车装载容积限制；约束(2-13)确保时间平衡，若车辆经过路径(i，j)，则到达j节点的时间应为到达i节点的时间加上在i节点的服务时间以及(i，j)路径间的货车行驶时间；约束(2-14)与(2-15)为决策变量约束。

第三章算法选择与设计3.1算法选择许多学者在针对车辆调度与路径优化问题的研究上使用了多种算法并对算法进行了适当的改进。用于求解组合优化问题的算法大致可分为精确算法和启发式算法两类，根据不同种类的车辆路径问题的特点和相关约束条件，设计并使用寻优性能较强、运算相对简便、效率较高的算法对于求解优化VRP问题具有关键性价值。目前研究较多且发展较为完善的算法主要有以下几种。3.1.1精确算法精确算法指的是利用线性和非线性规划的数学技术，描述物流体系中的数量关系，通过有限次的计算得到优化问题的最优解，做出最佳决策。精确算法一般计算复杂度较高，通常只适用于求解小规模的问题，在较大规模问题上不可避免地会出现指数爆炸的问题，且求解时间长，效率低，适应力较差。因此在实际工程中并不适用。而1979年，Lenstra和Kan[34]证明了车辆路径规划是一个NP-hard问题，精确的求解组合优化问题的全局最优解对于具有一定规模的问题是不容易实现的。3.1.2启发式算法启发式算法（HeuristicAlgorithm）无需进行精确的数学规划运算，也不需要或者只需要少量与问题有关的先验信息，使之满足所设定的约束条件，就能够适应不同领域的优化问题求解，并且能够较为有效的得到组合优化问题的最优解，是一种基于直观或经验构造的算法，在实际的工程或应用中具有较大的使用价值，成为了解决车辆路径问题的重要方法。求解车辆调度与路径规划问题的常用启发式算法有构造启发式算法、两阶段启发式算法和智能化启发式算法。其中智能化启发式算法又称现代化启发式算法，在求解组合优化问题上比其他算法具有更好的求解性能，因此许多学者将其运用于车路路径规划的问题求解中，下面的表3-1中对比介绍了几种常见的智能化启发式算法。表3-1常用启发式算法介绍与对比算法名称原理优点不足适用性模拟退火算法模拟固体退火过程，利用随机化处理技术搜索目标函数最小时的能量状态按一定的概率在一个较大的搜索空间里寻找最优解，可避免过早收敛到某个局部极值点。搜索优化所消耗的时间较长，效率较低，结果不一定为最优值适用于改进已知配送路线禁忌搜索算法引入禁忌表，可记录已搜索过的局部最优点，下次搜索时不再搜索这些点跳出局部最优解，更容易实现全局最优要求较高的初始解质量适用于较大规模问题蚁群算法模拟蚁群搜索食物，释放信息素，通过对信息素的更新找到最短路径具有正反馈、协同性的特点；易与其他算法结合求解变量需要不断调整，搜索效率低，易陷入局部最优适用于多目标优化问题粒子群算法模拟鸟群捕食行为，粒子飞行过程即为个体的搜索过程，通过跟踪个体极值和全局极值搜索最优粒子算法规则简单，容易实现；精度高；收敛快处理离散的优化问题效果不佳，容易陷入局部最优多用于求解连续空间的优化问题遗传算法利用生物进化思想，通过不断迭代优化，保留适应度值更大的个体，生成种群最优解全局随机搜索；具有鲁棒性；求解效率高易陷入局部最优适用于大规模车辆路径优化问题遗传算法对于问题的具体领域不具有依赖性，对于求解过程中的任意形式的目标函数与约束条件限制都可找到合适的处理方法，较为适用于大规模的车辆路径优化问题，因此基于本文模型多变量多约束的特点，结合目前已有的研究基础，选择采用遗传算法并根据本文模型特点和约束对其进行适当的调整，来进行本文的车辆调度与路径规划模型的求解并利用Matlab进行仿真计算，以中外运为参考，模仿其货物调配干线运输流程，在组合客户需求订单的基础上，寻求车辆调配与路径规划最优方案。3.2遗传算法设计遗传算法仿照了遗传学的相关理论以及生物学家达尔文提出的进化论，通过自然选择的进化过程而形成的求解方法，被广泛应用于车辆路径研究领域，主要有五个要素：染色体编码与解码、种群初始化、适应度函数、遗传算子（包括选择、交叉、变异等）以及控制参数。前人研究证明，传统遗传算法在求解简单的车辆路径规划问题上具有很好的效果，但对于本文中多车场多车型的VRP问题，由于存在配送中心和车型两个约束，且研究了往返取货和配送到指定配送中心两个流程，传统遗传算法较难实现。因此本文在前人针对多车场多车型的车辆路径优化问题的研究基础上，根据模型设定的约束条件，对传统遗传算法作出合理的调整与改进，具体流程及相关设计如下。3.2.1编码与解码对于车辆路径问题，编码是影响其生成最优解的关键因素。由于本模型中同时考虑了多配送中心和多车型的约束，且包含了取货收货的顺序限制，传统的二进制编码或顺序编码方式难以准确表达出取货与送货以及订单与车辆的对应关系。陈呈频等人[22]在求解多车场多车型问题中，提出了一种可行有效的多染色体遗传算法，每一条染色体表示一辆车，这种编码方式非常直观，车辆与车场及客户一一对应，能够将复杂的对应关系简单化，但其存在的不足是多染色体会导致后续选择交叉变异等遗传操作十分复杂，且当存在多辆车时，染色体的数量也随之增加，导致染色体数量繁多，运算量增大。本文基于自然数编码方式，设计了一种二段编码方式，以实现客户与制定配送中心，及车辆与客户的对应。假设存在M个运单，K辆车。该编码方式分为两个阶段，第一个阶段实现了运单的货物取送调配的对应关系，编码为1到2M的自然数排列，长度为2M，解码时，将大于M的数字全部减M，这时编码中的数字全为1到M，且每个数字出现了两次，第一次出现的数字表示运单取货，第二次出现的数字表示运单到达对应配送中心。例如当存在6个运单，3辆车时，第一段编码长度为12，如（547681213109211），解码时，编码变为（541626134325）。第二个阶段表示运单与车辆的对应关系，编码长度为M，表示M个运单，每个位置的数字为随机的1到K，表示该位置的运单由车辆k配送（k=1,2,…,K）。解码时，根据车辆k出现的位置，对应由该辆车运输的运单，再在第一段编码中找到该运单对应出现的顺序，即为车辆k的运输路径。在上段的举例中，第二段的编码的长度应为6，如（233212），表示运单2、3由车辆3进行配送，再对应第一段编码，找到运单2、3的顺序，为（2332），表示车辆2的运输路径为：到客户点2取货，到客户点3取货，到客户点3指定的配送中心卸货，到客户点2指定的配送中心卸货。3.2.2种群初始化遗传算法通过群体搜索对比的方式找寻最优解，因此在搜索前需要生成由若干染色体组成的初始种群。初始群体是遗传的起点，种群增大可减少陷入局部最优解的概率，但同时也会导致运算量的加大，降低求解效率。此外，若初始种群的分布较为均匀，也有利于算法跳出局部最优。本文采取了随机生成初始种群的方法，以保证种群的均匀分布。3.2.3适应度函数适应度值是评价染色体优劣的重要指标，染色体的适应度值越大，被选择留下和“繁衍”下一代的可能就越大。由于本文模型的目标函数为最小化总成本，与适应度值变化的趋势不一致，因此采用如下式(3-1)的方式计算适应度值，对目标函数进行合理的转化。其中Fi是第i条染色体对应的目标函数值，即总成本，fi为第3.2.4选择算子选择算子是将适应度较高的染色体从父代种群中筛选出来，进入子代种群的关键因素。本文采用轮盘赌策略进行染色体的选择操作。轮盘赌方法利用各染色体适应度所占总适应度值的比例大小进行随机选择，决定是否保留到子代种群。其具体过程如下：计算每个个体适应度值fF=（2）计算每个个体被选中的概率；（3）计算各染色体的累计概率；（4）在[0,1]之间随机生成一个数a，当a≤G13.2.5交叉算子由于染色体前后两段的编码方式并不相同，不能直接进行染色体的交叉，因此需要先将染色体按长度分为2M与M两段。对于第一段编码，基于其编码长度较长且没有重复数字的特点，为了使交叉过程尽可能完全，选择采用定位交叉方法（Position-basedCrossover，简称PBX），具体操作流程如图3-1所示，随机选择父代染色体A、B，将A、B分别分为两段编码iA、jA、iB、jB，针对iA、iB两段编码，随机选择几个基因位置，位置可以不连续，将iA选中的基因按照固定的位置复制到子代染色体第一段编码iC中，删除iB中iA被选中的基因，剩下的基因按顺序填入iC中，对iB被选中的基因也重复相同的步骤，分别产生子代染色体C、D的第一段编码。对于第二段编码，由于具有许多重复的数字，无法使用PBX方法执行交叉操作，且数字组成较为简单，因此直接生成一个随机数，在随机数的位置将jA、jB分成两段，然后交叉互换，生成jC、jD。分别将C、D的两段编码进行组合，得到完整的子代染色体C、D，完成了父代的交叉遗传。图3-1交叉操作过程示意图3.2.6变异算子个体发生变异的概率较小，变异算子主要作用是维持种群中染色体的多样性，防止过快达到收敛。与交换操作一样，在变异操作中，也需要将染色体按编码方式的不同分为两段。第一段编码采取两点互换法，在iA中随机选取两个基因点位置，将这两个位置的基因交换位置从而得到新的个体。如图3-2所示。对于第二段编码，在jA中随机选取一个基因，并生成一个[1,K]的随机数，将被选中基因替换为该随机数。得到变异后的iA’、jA’后，将其组合，成为新的子代染色体A’。图3-2两点互换法操作过程示意图3.2.7终止条件遗传算法通过种群的随机搜索寻找最优解，需要设定一个算法终止条件，在算法运行到满足终止条件后则停止演化运算。本文通过设置最大迭代次数来控制算法的终止，以此可以有效控制算法运行时间，以免出现由于算法无法收敛而不能停止运行的现象。第四章算例分析4.1算例背景及相关参数设置为验证本文模型及算法的可行性和有效性，现基于中外运华北公司一级运输网络货物干线运输的背景，设置合适的算例。中外运华北公司的配送中心地理位置集中于河北、河南、北京、天津等华北地区，其客户分布于全国各地，依托丰富的物流资源以及先进的管理系统，为客户提供优质的一体化物流全链路服务。假定中外运华北公司现有15个来自全国各地不同客户的运单，其需求批量大小不一，为充分利用运力资源，需要整合各个运单，规划最优路线。现参考经纬度坐标位置，设定客户点横坐标范围为70-140，纵坐标范围为20-55，其中每1单位坐标代表100km；基于以上范围限制，选取了位于天津、石家庄、河南三个城市的配送中心，随机生成15个客户点坐标，形成小型的运输网络，位置坐标如下表4-1所示，编号A、B、C为配送中心，1-15为客户点。假设各客户之间的交通运输网络是完全连通的，各点之间的运输路径长度等于坐标间的直线距离。即若两个客户点i、j的位置分别为（xi,y表4-1配送中心及客户点位置信息编号横坐标纵坐标编号横坐标纵坐标A1153878642B11740813048C11334912550191291010546210626111053631023012984041142213894351122314125436119261511635现需要从3个配送中心调配车辆，按照一定顺序前往到客户点取货，再将货物运输到指定的配送中心，运单信息如表4-2所示。该算例限制了每个运单到达指定配送中心的最晚时间，超时惩罚系数为40元/小时，货车在每个客户点装载货物以及在配送中心卸货的时间都为2小时。假定在该时间点上，3个配送中心共有9辆处于闲置状态的货车，包含5.2、6.8、7.7三种车型，在初始状态车辆及车型的分布、相关限载及成本耗费信息如表4-3所示，三种车型的平均速度都为65km/h。为得到该算例车辆调度与路径规划的最优方案，现利用Matlab对上述模型与改进后的遗传算法进行了编程，并以上述算例的数据作为基本变量输入程序，实现了算例的最优方案求解。其中为保证具有较好的计算效果及求解效率，设置基础实验参数如表4-4。表4-2运单信息客户编号货物重量（吨）货物体积（立方）指定配送中心时间窗（以出发时间为基点）16.1111.71A7天（168h）内送达24.135.15A7天（168h）内送达38.4313.54A8天（192h）内送达47.4510.56A8天（192h）内送达53.436.55A8天（192h）内送达610.5418.44B8天（192h）内送达72.124.23B8天（192h）内送达85.337.67B7天（168h）内送达96.6710.56B7天（168h）内送达102.115.43C7天（168h）内送达119.4316.76C7天（168h）内送达125.446.13C8天（192h）内送达138.7614.37C8天（192h）内送达145.209.88C8天（192h）内送达154.559.65C7天（168h）内送达表4-3车辆及车型信息车辆编号所属车场所属车型额定载重（吨）额定容积（立方）固定成本（元）单位距离可变成本（元/km）1AI10179001.22AII133010001.53AII133010001.54BI10179001.25BII133010001.56BIII154011001.87BIII154011001.88CII133010001.59CIII154011001.8表4-4遗传算法相关参数设置相关参数参数值种群规模200交叉概率0.8变异概率0.2最大迭代次数5004.2结果分析由于遗传算法是通过随机搜索寻求最优解，因此Matlab程序每次运行的结果都不一定一致。现使用配置为Inteli5，2.3GHz处理器，2GB显存容量的笔记本电脑进行十次运行试验，取最优的试验结果如下：15个运单的运输总成本为56511.42元，车辆使用总数为8辆。十次试验中程序运行时间都在60秒以内，收敛时迭代次数在100-250之间，证明使用本文改进后的遗传算法能够有效规划不同需求运单的车辆调度及运输路线，且该算法效率较高，运行时间与结果都较为稳定。十次试验中最优解的具体车辆调配与路径规划方案如表4-5所示，每辆车辆的装载量及各条线路的成本组成如表4-6所示，得到的最优运输路径规划图如图4-1所示。遗传算法迭代图如图4-2所示。表4-5最优车辆调度及路径规划方案车辆编号运输路径1A—9—B3A—10—13—7—C—B4B—15—C5B—14—8—B—C6B—1—3—A7B—6—2—A—B8C—5—4—A9C—11—12—C表4-6各线路车辆装载量及运输成本组成车辆编号货物总重量（吨）货物总体积（立方）行驶距离（km）配送时间（h）固定成本（元）运输成本（元）惩罚成本（元）线路总成本（元）16.6710.56284275900341104311.21312.9924.036761181100010142.81011142.8144.559.6582624900991.3601891.36510.5317.55380910310005713.5806713.58614.5425.25545414411009817.36010917.36714.6723.59449712011008094.7009194.70810.8817.1129318110004396.9005396.90914.8722.8932468911005843.5106943.51图4-1最优运输路径规划图图4-2遗传算法迭代图第五章总结与展望本文通过查阅国内外车辆路径优化问题相关研究文献及资料，结合物流运单需求差异化的背景，以及合同物流一级运输网络干线运输的特点，建立了考虑时间窗及车辆配载的多车场多车型的货物取送车辆调度及路径规划问题，并利用改进后的遗传算法进行求解。本文设计的多车场多车型车辆路径问题相对于其他路径问题更加贴近实际情况并且具有通用性和普适性，通过运单信息，与配送中心当时的车辆闲置情况，即可进行车辆调度与路径的规划，且具有较高的寻优效率，解的质量与稳定性较高。本文研究的创新点在于在考虑时间窗的多车场多车型的车辆路径优化问题的研究基础上，加入取送货对应关系的问题，基于配送中心的一体化车辆调配管理，实现了不同配送中心之间的货物运输一体化与运力协调，而不仅是局限于以一个配送中心为起始点进行货物运输，从而减少运力资源的浪费，满足品牌制造商的线上线下渠道物流协同。其次，本文基于该模型提出了一种二段编码方式，能够准确表示出取货与送货的对应关系以及车辆与运单的对应关系，改进了传统遗传算法，为后续学者研究多车场多车型的车辆路径规划问题提供参考。同时，本文在研究中也存在一些不足之处，首先，本文在一些假设前提上简化了实际情况，一方面，将在客户点或配送中心装卸货物的时间设为了一个定值，而没有根据货物量的多少来计算装卸货物的时间，另一方面，没有考虑货车司机长途运输的休息时间，也没有考虑货车空驶与满载时的耗油量区别。其次，本文只考虑了需求量小于车辆限载量的运单，需要组合运输的情况，设定了一个客户点的货物只能由一辆车进行装载，而在实际情况中，往往存在需求量非常大，需要多辆车进行拆分配送的情况。随着对车辆路径规划问题研究的逐渐深入，许多学者将越来越多的限制因素加入模型，在以后的研究中，可以从以下几个方面入手：（1）本文在模型的求解中，选择使用了改进的遗传算法进行求解，在以后的研究中，可以尝试使用其他多种算法进行求解，找到寻优效率更好的算法；（2）考虑对货物量较大的运单进行拆分配送的多车场多车型车辆调度问题；（3）在本文研究的运输模式下，车辆往往需要先从配送中心空驶前往第一个客户点，在后续研究中，可以考虑将这部分运力有效运用，研究车辆往返运输的路径优化问题。

参考文献G.B.Dantzig,J.H.Ramser.TheTruckDispatchingProblem[J].ManagementScience,1959,6(1).李琳,刘士新,唐加福.B2C环境下订单配送问题的模型与算法[J].东北大学学报(自然科学版),2009,30(11):1554-1557.李军.基于免疫遗传算法的物流配送车辆路径优化问题研究[A].中国优选法统筹法与经济数学研究会.第九届中国管理科学学术年会论文集[C].中国优选法统筹法与经济数学研究会:中国优选法统筹法与经济数学研究会,2007:5.R.Tavakkoli-Moghaddam,N.Safaei,M.M.O.Kah,etal.ANewCapacitatedVehicleRoutingProblemwithSplitServiceforMinimizingFleetCostbySimulatedAnnealing[J].JournaloftheFranklinInstitute,2005,344(5).阎庆,鲍远律.新型遗传模拟退火算法求解物流配送路径问题[J].计算机应用,2004(S1):261-263.严蓉.区域干线物流的运输网络优化研究[D].浙江理工大学,2018.向婷.求解车辆路径问题的智能算法研究[D].西华师范大学,2017.朱丽娟.物流配送中心货物配载与车辆路径组合优化研究[D].武汉理工大学,2012.许珮.带时间窗的物流配送中心车辆路径优化问题[D].北京邮电大学,2017.李啸麟.G公司多车型电动物流车配送路径规划研究[D].北京交通大学,2019.何小锋.量子群智能优化算法及其应用研究[D].上海理工大学,2014.段雪凝.带时间窗的冷链物流车辆路径多目标优化问题研究[D].东北大学,2014.KohlN,MadsenOBG.Anoptimizationalgorithmforthevehicleroutingproblemwithtimewindowsbasedonlagrangianrelaxation[J].OperationsResearch:TheJournaloftheOperationsResearchSocietyofAmerica,1997,45(3):395-406.JufangBao,TiangangCai,ZhongheJiang.ResearchonVehicleRoutingProblemwithSoTimeWindowsandDistributionTimeConstraintsofVehicles[J].FutureInformationTechnoloandManagementEngineering,2010:205-208.范厚明,刘文琪,徐振林,等.混合粒子群算法求解带软时间窗的VRPSPD问题[J].计算机工程与应用,2018,54(19):221-229.KaabachiI,JrijiD,KrichenS,etal.Animprovedantcolonyoptimization