【《带模糊时间窗的D公司路径优化模型的构建案例分析》8200字（论文）】

带模糊时间窗的D公司路径优化模型的构建案例分析目录TOC\o"1-3"\h\u23054带模糊时间窗的D公司路径优化模型的构建案例分析 1153601.1D公司简介 193521.2D公司生鲜农产品冷链配送现状 1189531.2.1生鲜农产品冷链配送作业情况 1239781.2.2生鲜农产品冷链配送网络分布 4291961.3D公司生鲜农产品冷链配送存在问题 4297012构建带模糊时间窗的D公司路径优化模型 6271242.1基本问题描述 6105032.2模型假设与符号定义 630332.2.1模型假设 6151482.2.2符号定义 6158832.3模型的建立 8313212.1.1目标函数分析 8205762.1.2车辆配送总成本分析 8246832.4D公司路径优化模型的求解 1184742.2.1求解算法的选择 11222842.2.2节约里程算法简述 12117482.2.3带模糊时间窗的节约里程算法基本思想及步骤 141.1D公司简介D公司成立于2007年，现有面积超过13000平方米，主要涉及生鲜农产品采购、仓储、配送和销售等业务。D公司配置了管理信息系统、制冷技术和配送车辆等基础设备，主要为连锁超市和生鲜超市等客户提供服务。当前，D公司最大特色是水果、蔬菜、肉禽和蛋等生鲜农产品的经营，其与多家生鲜农产品基地维持长期合作关系，采购渠道稳定，生鲜农产品持续供给有保障。秉承着产地直接采购的理念，D公司的采购环节没有中间商和其它环节介入，生鲜农产品品质有保证且采购成本较低，生鲜农产品收入在公司总收入中占有很大比重。为使生鲜农产品一直处于低温环境中，D公司对配送中心进行升级改造，增加了冷藏库和冷冻库面积，升级后中央空调分布在配送中心的分拣、加工和仓储等各个区域。同时，配送中心采用自营配送的方式，为客户配送生鲜农产品。随着客户数量不断增加以及客户对生鲜农产品的配送要求越来越严格，居高不下的配送成本已经制约了D公司生鲜农产品冷链配送业务的发展。D公司亟需合理安排车辆配送路径，降低配送成本。1.2D公司生鲜农产品冷链配送现状1.2.1生鲜农产品冷链配送作业情况D公司生鲜农产品供应流程可以划分为生鲜农产品采购阶段和冷链配送阶段，其供应流程见图1.1。在生鲜农产品采购阶段，D公司与多家生鲜农产品基地保持长期良好的业务合作关系。生鲜农产品经过采摘、分拣以及筛选等作业后，由负责人安排车辆将其运输至配送中心。配送车辆抵达配送中心后，仓库工作人员仔细查验生鲜农产品的数量、种类、品质和相关凭证等信息，检查无误后签收。在生鲜农产品冷链配送阶段，客户通过订货系统将产品需求信息传递给配送中心。配送中心合理控制库存，其收到客户订单后，会查询现有库存量是否满足客户需求。如果现有库存量满足客户需求，将安排工作人员拣货；如果现有库存量不满足客户需求，配送中心将从生鲜农产品基地采购产品。配送中心负责人根据经验安排车辆配送路径以及通知相关人员准备配送车辆。生鲜农产品出库前，仓库工作人员对分拣货物的数量、品种和质量等信息仔细核对，并做好出库记录。产品装车前，装车人员再次核对生鲜农产品的数量、品种、质量和配送地点等信息。核对完毕后，根据规划的配送路径将生鲜农产品装车。最后，司机关闭配送车辆的车厢门，依据安排的配送路径为客户送货。图1.1供应流程Figure1.1Supplyprocess生鲜农产品冷链配送过程中，配送车辆出车前、出车后都要进行检查，然后等待使用。出车前，装车人员对生鲜农产品数量、种类和品质等信息进行检查，确认无误后做好相应记录，并将生鲜农产品装车。接着，装车员根据配送顺序装货，清点后通知司机开车。当司机完成配送任务、返回配送中心后，负责人通知维护人员对配送车辆进行清洁和日常维护，等待下次使用。配送车辆使用流程如图1.2所示：图1.2配送车辆使用流程图Figure1.2Flowchartoftheuseofdeliveryvehicles1.2.2生鲜农产品冷链配送网络分布为给零售端客户提供高质量的配送服务，D公司自建了专业化的配送中心和购买了若干辆冷藏车，其采取自营配送的方式为客户配送生鲜农产品，并组成了以某市为中心面向周边城市的配送网络。目前，公司零售端客户主要分布在某市及其周边城市，公司与多家生鲜农产品基地维持稳定的合作关系，可以为多家连锁超市和生鲜超市等客户提供生鲜农产品配送和销售等服务。某市市内6区是D公司配送业务较为频繁的地区，区域配送业务量稳定，并且客户对配送车辆抵达时间存在不同需求。D公司采用每日自营配送的方式为市区内的零售端客户配送生鲜农产品，主要客户的地理分布如图1.3所示。图1.3D公司主要客户的地理分布图Figure1.3GeographicalDistributionMapofDCompany’sMajorCustomers1.3D公司生鲜农产品冷链配送存在问题由于客户的经营时间存在差异，其对生鲜农产品的配送时间存在不同要求。实地调研后发现，D公司在生鲜农产品配送过程中存在配送路径安排不合理、配送成本高和不重视客户配送时间需求这三个问题。（1）车辆配送路径安排以负责人经验为主D公司目前主要为连锁超市和生鲜超市等客户提供服务。连锁超市和生鲜超市具有生鲜农产品订货量多、订货周期短、订货品种多和客流量稳定等特点。当前，D公司的配送中心负责人根据配送客户的地理位置，以顺路或近路为原则来安排车辆配送路径，司机根据配送路径依次将生鲜农产品配送至客户指定地点，这种方法使得配送车辆迂回运输或对流运输的现象频繁发生，车辆行驶里程增加且生鲜农产品配送时间长，生鲜农产品经常变质。此外，D公司从业人员的专业素质较低，信息系统和冷链设备的使用停留在业务阶段，工作人员缺乏系统规划生鲜农产品配送路径的意识，现有规划车辆配送路径的方法不能同时满足公司降低配送成本和客户准时配送的要求。（2）车辆配送成本过高不合理的车辆配送路径，一方面，会导致部分工作人员和配送车辆的闲置，增加了非必要的人力、物力和财力开支。另一方面，根据配送中心负责人经验安排的车辆行驶路径，使得配送车辆经常迂回运输或对流运输，车辆行驶里程增加，导致了配送车辆的货损成本、制冷成本和时间惩罚成本增加。此外，生鲜农产品冷链配送需要在低温控制下进行，配送过程中制冷设备全程工作，产生大量制冷成本。配送中心需要合理安排生鲜农产品冷链配送路径，降低配送成本，进而提高企业经济收益。（3）忽视客户配送时间要求不同客户对产品配送时间具有不同要求。个体销售客户对于配送时间较为宽泛，可接受配送车辆在客户要求时间外抵达客户点；加盟型连锁客户对于货物配送时间较为宽松，可以接受配送车辆在客户要求时间外抵达客户点，企业只需支付提前或延迟到达的成本；直营型连锁客户对于货物配送时间非常宽松，配送车辆在客户需求时间外抵达客户点，企业只需支付很少的费用；连锁超市对于货物配送时间较为严格，配送车辆不在客户要求时间内抵达客户点，连锁超市将拒绝接货。企业依据合同中惩罚条款，支付配送车辆提前或延迟到达成本。连锁超市和生鲜超市是D公司的主要客户，其对配送车辆抵达时间存在差异。配送中心负责人安排车辆配送路径时，仅考虑了车辆为客户配送货物时是否顺路或近路，忽略了客户对配送车辆抵达时间的要求。不合理的配送顺序，使得生鲜农产品变质、配送车辆在客户要求时间外抵达等情况时有发生。一定时间内，虽然配送中心只需支付一些费用，客户仍会接收货物，但会增加企业配送成本，并且约定时间外送货，可能导致客户流失，不利于D公司长远发展。提高员工综合素质、加强信息管理水平以及减少冷链设备的资金投入降低配送成本时间长、见效慢，而合理规划车辆配送路径不仅能迅速、高效的降低配送成本，还可以满足客户对货物配送时间的要求。本文对D公司生鲜农产品冷链物流路径优化问题进行探究，以期为D公司解决生鲜农产品冷链配送中存在的问题。2构建带模糊时间窗的D公司路径优化模型根据D公司生鲜农产品冷链配送现状，结合生鲜农产品和冷链物流特点，引入模糊时间窗，以生鲜农产品冷链配送中各项成本之和最小为优化目标。同时，对比各种车辆路径求解算法优缺点，为下一章D公司路径优化分析奠定理论基础。2.1基本问题描述与仅考虑车辆行驶距离和成本因素的基本车辆路径问题不同，本文旨在解决D公司生鲜农产品冷链配送中存在问题，着重探究生鲜农产品从D公司的配送中心到零售商这一环节，只考虑新鲜度对产品品质的影响。将本文带模糊时间窗的D公司生鲜农产品冷链物流路径优化问题描述为：D公司的配送中心安排冷藏车为客户点配送货物，配送任务完成后，冷藏车必须返回配送中心。并且需要满足以下4个条件：（1）配送中心的生鲜农产品库存充足，不会缺货；（2）冷藏车配送路径上客户点需求总量不高于配送车辆的最大承载量；（3）冷藏车可以为多个客户服务但只可服务一次；客户需求信息和冷藏车行驶速度已知且不会改变；（4）冷藏车型号相同。2.2模型假设与符号定义2.2.1模型假设针对D公司生鲜农产品路径优化模型提出如下假设：（1）每个客户点地理位置已知，为D公司的配送中心和每个客户依次设置编号（初始配送中心标记为0）；（2）配送车辆必须从配送中心出发，最后返回配送中心；（3）配送中心不存在缺货情况；（4）配送车辆可为多个客户提供配送服务，但是每个客户仅能服务一次，并且同一车辆配送路径上客户点需求总量不得高于车辆最大承载量；（5）已知客户需求量和模糊时间窗，并且客户不存在临时取消或改变订单情况；（6）配送中心冷藏车型号相同且配有相关制冷设备，车辆行驶速度相同。2.2.2符号定义本文探究了带模糊时间窗的D公司生鲜农产品冷链物流路径优化问题，模型中参数变量及其含义如下所示：：配送中心拥有配送车辆数；：客户数；：车辆从客户行驶到客户的里程数；：车辆单次运输固定成本；：车辆单位距离运费；：单位产品价格；：客户需求量；：运输时生鲜农产品新鲜度损耗系数；：服务时生鲜农产品新鲜度损耗系数；：车辆到达客户时间；：车辆从配送中心出发时间；：车辆在客户的服务时间；：车辆回到配送中心时间；：单位小时早到惩罚成本；：单位小时迟到惩罚成本；：车辆平均行驶速度；：车辆最大承载量；：终端客户惩罚成本；：客户期望时间窗；：客户最大可容忍时间窗；：热导率；：车厢恶化程度；：车厢内表面积；：车厢外表面积；：车厢内环境温度；：车厢外环境温度；：单位制冷成本；：车厢体积；2.3模型的建立2.1.1目标函数分析提高信息管理水平、减少基础设施和技术资金投入来降低D公司成本较为困难。相比之下，合理规划车辆配送路径可以缩短配送时间，减少生鲜农产品新鲜度损失，以及降低车辆配送成本。此外，D公司如果只考虑降低配送费用，忽略客户需求，客户将大量流失，不利于公司长久发展。在满足客户对产品种类、数量、品质和配送时间等需求的前提下，合理安排车辆配送顺序。基于D公司迫切降低配送成本的需求，本文引入模糊时间窗，重点分析了D公司生鲜农产品冷链配送中各项成本，探究了以各项成本之和最低为优化目标的生鲜农产品冷链物流配送路径优化问题。2.1.2车辆配送总成本分析从公司层面考虑，公司希望以最低的配送成本完成送货任务，结合生鲜农产品和冷链物流特点，D公司生鲜农产品冷链物流的配送成本可描述如下：（1）固定成本固定成本是车辆在送货过程中固定消耗的成本，这部分成本不随配送时间、客户数量、车辆行驶里程和配送货物数量的改变而改变，仅与司机工资和车辆折旧费等有关。固定成本可用式（2.1）表示：（2.1）（2）行驶成本行驶成本是车辆完成一次配送任务过程中产生的费用，这部分成本与车辆运输距离成正比，即运输距离越大，行驶成本越大。行驶成本可用式（2.2）表示：（2.2）（3）货损成本生鲜农产品冷链配送过程中，生鲜农产品品质随着新鲜度的减少逐渐下降，产生一定的货损，即货损成本。本文所考虑的货损成本包括：①车辆运输过程中由于时间积累导致生鲜农产品腐败变质的成本。配送中心安排冷藏车辆为客户配送生鲜农产品，本文假定生鲜农产品运输过程中外界环境温度以及车厢内部环境温度固定不变，即假设生鲜农产品的新鲜度仅与时间有关。②冷藏车车厢门打开时，车厢外热空气进入，致使车厢内部温度上升，生鲜农产品腐损加快。厢门打开时间越长，生鲜农产品新鲜度损失越大。本文根据生鲜产品新鲜度函数描述车辆服务客户点时生鲜农产品的新鲜度[72]。其中，为生鲜农产品在客户点时新鲜度，为车辆到达客户点时间，为车辆从配送中心出发时间，为新鲜度损耗系数，假定配送过程中冷藏车温度恒定，则可视为常数。生鲜农产品新鲜度随车辆配送时间的增加不断减小，从数量关系看，生鲜农产品的新鲜度和生鲜农产品货损度之和为1。因此，车辆运输过程中和装卸服务时生鲜农产品货损成本和可表示为：（2.3）（2.4）其中，为单位产品价格，为客户需求量，和分别为生鲜农产品运输中新鲜度损耗系数和服务时新鲜度损耗系数，为车辆到达客户时间。因此，货损成本可用式（2.5）表示：（2.5）（4）制冷成本生鲜农产品冷链配送过程中，司机打开制冷设备，以延缓生鲜农产品新鲜度的降低，这个过程中会产生制冷成本。车辆制冷成本包括：①冷藏车运输中，制冷设备维持车厢内低温产生的制冷成本。②车厢门打开时，制冷设备额外工作产生的制冷成本。通过计算冷藏车运输时产生的热负荷以及厢门打开时进入的热负荷的方法，可以解决配送车辆的制冷成本问题。1）车辆运输时制冷成本冷藏车运输时产生的热负荷为：（2.6）其中，为冷藏车厢体热导率，单位是；和分别为冷藏车车厢内、外表面积，单位；由车厢恶化程度决定，为常数；和为车厢内、外环境温度，单位。则车辆运输时制冷成本可用式（2.7）表示：（2.7）其中，为单位制冷成本；和分别为车辆返回配送中心时间以及从配送中心出发时间。2）服务时制冷成本冷藏车厢门打开时，车厢外热空气进入车厢内部，产生空气对流现象，使得冷热负荷发生交换。车厢门打开时，由于空气对流而进入车厢的热负荷为：（2.8）其中，为车厢体积；为厢门打开频度系数，具体数值见表2.1。表2.1厢门打开频度系数Table2.1Frequencycoefficientofdooropening开门次数1次以下1次-5次6-10次11次及以上值1/41/23/41所以，车厢门打开时的制冷成本可表述为：（2.9）则总制冷成本可用式（2.10）表示：（2.10）（5）惩罚成本客户对生鲜农产品配送时间存在较高要求。配送车辆提前或延迟抵达时间在客户期望时间外、最大容忍时间窗内，企业将支付一定费用；配送车辆提前或延迟到达时间在客户最大容忍时间窗外，企业将支付巨额费用，客户拒绝接受服务。基于客户对生鲜农产品配送时间的要求，本文将模糊时间窗转化为时间惩罚成本，即冷藏车辆抵达时间距离客户期望时间窗越远，惩罚越严重。模糊时间窗下客户的惩罚成本函数表达式为：（2.11）因此，生鲜农产品冷链配送过程中总时间惩罚成本可用式（2.12）表示：（2.12）根据上述车辆总配送成本的组成要素，最终的目标函数为：（2.13）综上所述，本文构建了带模糊时间窗的D公司生鲜农产品冷链物流路径优化模型：（2.14）（2.15）公式（2.14）为路径优化模型的目标函数，即以生鲜农产品冷链配送中各项成本之和最小为优化目标，公式（2.15）为模型约束条件。其中，（1）为冷藏车配送路径上各客户点的需求总量不高于车辆最大承载量；（2）为提供配送服务的冷藏车总数不超过配送中心实际拥有冷藏车数量；（3）为每个客户点只可被一辆冷藏车提供一次配送服务；（4）冷藏车配送路径必须以配送中心为出发点和返回点；（5）为冷藏车到达客户点的时间表达式；（6）为冷藏车必须在客户最大可容忍时间内抵达客户点。2.4D公司路径优化模型的求解2.2.1求解算法的选择表2.2车辆路径问题求解算法适用范围及优缺点Table2.2Thescopeofapplicationandadvantagesanddisadvantagesofvehicleroutingproblemsolvingalgorithms算法类别算法名称适用范围优点缺点精确算法分支定界法小规模VRP问题最优解结果精确计算花费时间长割平面法动态规划法网络流算法传统启发式算法节约里程算法中、小规模VRP问题迭代次数少，计算快求解大规模VRP问题时，结果不理想扫描算法小规模VRP问题可与插入法结合求解时间长，可行解不为最优解插入算法小规模VRP问题可对元素进行升序或降序排序，计算快求解大规模VRP问题时，结果不理想最邻近算法小规模VRP问题求解速度快最优解质量不高，易陷入局部最优智能现代算法遗传算法大规模和复杂VRP问题全局并行性，计算快局部搜索能力弱，过于依赖初始可行解禁忌搜索算法带时间窗和带回程VRP问题可跳出局部最优解搜索过于依赖初始可行解，求解复杂表2.2（续）算法类别算法名称适用范围优点缺点智能现代算法蚁群算法大规模及复杂VRP问题计算效率高，对初始可行解依赖小搜索慢，解空间受限模拟退火算法大规模和客户需求确定或不确定VRP问题可搜索到质量较好的全局最优解，搜索质量与初始可行解关系不大，可与其它算法组成高效算法计算量大，花费时间久，只可求出近似最优解粒子群算法大规模VRP问题操作简单，应用范围广，精确度高后期收敛较慢，易得到局部最优解车辆路径问题规模的增加，会使精确算法计算量呈指数级增长，所以很少有学者使用精确算法求解车辆路径问题。通过对比各种车辆路径问题求解算法的优缺点以及本文研究具体情况，选择节约里程算法作为求解方法，见表2.2。2.2.2节约里程算法简述节约里程算法适用于处理具有以下特征的车辆路径问题：（1）由一个配送供应点向多个客户点配送货物，且同一条配送路径上客户需求总量不高于车辆最大承载量；（2）配送货物性质不互斥，可由一辆车装载和配送；（3）配送客户点的货物需求量和地理位置确定，且不会发生改变；（4）配送供应点车辆数足以配送完成任务；（5）配送供应点不存在缺货情况。该算法基本思想可用2个客户点阐述，见图2.1，图2.2。其中，配送中心和两个客户点分别用0，1和2表示，配送中心0与客户点1、配送中心0与客户点2以及客户点1与客户点2间的最短可行距离分别用、和表示。图2.1两个客户点的初始配送方案Figure2.1Theinitialdistributionplanfortwocustomersites图2.2优化后两个客户点的配送方案Figure2.2Optimizedthedistributionplanofthetwocustomerpoins图2.1为配送中心0向客户点1和客户点2送货的初始配送方案，即配送中心0需要安排两辆车分别向客户点1和客户点2送货，完成配送任务后返回配送中心0。此时，为完成客户点1和客户点2的配送任务，配送车辆总行驶里程为：（2.16）图2.2为使用节约里程算法优化后配送中心0向客户点1和客户点2送货的方案，即将客户点1和客户点2的货物装至一辆车上，车辆从配送中心0出发行驶至客户点1，接着从客户点1行驶至客户点2，最终从客户点2返回配送中心0。此时，配送车辆总行驶里程为：（2.17）将初始配送方案和优化配送方案相比，配送车辆节约的里程为：（2.18）将图2.2视作一个三角形，根据其几何性质，可得出：（2.19）采用节约里程算法优化车辆配送路径，不仅可以安排车辆顺利完成配送任务，还可以节约的车辆行驶里程。配送车辆从配送中心出发，为N个客户点配货，任务完成后返回配送中心。根据上述原理，计算N个客户点间的节约里程值并排序，依次将节约里程值最大的客户点并入该车配送路径，直至该辆车配送路径上客户需求总量大于车辆最大承