《基于双层规划模型的生鲜物流配送中心选址和配送路线优化实证探究》17000字（论文）

基于双层规划模型的生鲜物流配送中心选址和配送路线优化实证研究摘要近年来，生鲜产品在电子商务平台上的订单规模不断增大，体现出生鲜电商市场发展的巨大潜力。生鲜产品物流的及时配送成为制约生鲜电商企业发展的重要因素，而影响配送的关键点在于配送中心的选址和配送路线的优化等方面。本文主要研究生鲜物流配送中心选址和配送路线优化问题，基于系统的思想，建立了选址-路线双层规划模型，并通过设计上下层模型的启发式算法，对生鲜电商物流配送系统进行优化。首先，文章介绍了本文的研究背景、研究意义和国内外研究现状。随后，本文介绍了选址问题和路径优化问题的常见模型，并分别介绍了模型对应的求解算法。接着，本文针对选址-路径问题建立了双层规划模型，上层选址模型是改进后的P-中值模型，在目标函数中加入了配送中心的固定成本和腐败成本，使得模型更加准确合理；下层路径优化模型中考虑了生鲜产品配送时的固定成本、运输成本、货损成本和时间窗惩罚成本，并对TSP问题模型进行了改进。本文又针对双层规划模型设计了求解算法，在上层模型中利用贪婪取走启发式算法进行求解，在下层模型中利用最近插入法对配送路径进行优化。最后，本文将所建模型和求解算法应用于实际案例中，对案例中的生鲜电商企业进行配送中心的选址和配送路线的优化。关键词：双层规划模型；选址-路径；贪婪取走启发式算法；最近插入法目录TOC\o"1-3"\h\u7941第1章绪论 1105741.1研究背景 1139871.2研究意义 2229801.3国内外研究现状 3245631.3.1国外研究现状 3194251.3.2国内研究现状 325878第2章生鲜物流中心选址与配送路径优化问题研究 5146362.1生鲜物流中心选址问题研究 5311612.1.1选址问题概述 5281212.1.2常见求解模型介绍 7275362.2生鲜物流配送路径优化研究 10127572.2.1路径优化问题概述 10306492.2.2常见求解模型介绍 1259182.3生鲜物流配送中心选址及路径优化问题研究 13297412.3.1选址-路径问题概述 13163772.3.2选址-路径基本模型 1313725第3章生鲜物流配送中心选址及路径优化模型分析 159663.1双层规划模型介绍 1575463.2模型的构建思路 15203533.3上层模型的构建 16227743.3.1模型假设 16182203.3.2符号介绍 17248883.3.3成本分析 1760773.3.4生鲜物流配送中心选址模型 1836193.4下层模型的构建 1995383.4.1模型假设 19226213.4.2符号介绍 19244073.4.3成本分析 2031893.4.4配送路线优化模型 225672第4章模型求解算法研究 23924.1双层规划模型的求解流程 23154984.2上层模型的求解算法 2496174.3下层模型的求解算法 2410237第5章案例分析 26260225.1案例背景 2696155.2上层规划——配送中心选址 26256215.3下层规划——配送路径优化 3013045结论 3225944参考文献 34第1章绪论1.1研究背景随着信息技术的不断发展，新兴电子商务已向各个行业渗透，生鲜电商成为当前社会关注的热点之一。自从2016年10月，阿里巴巴集团创始人马云在杭州演讲时第一次提出了新零售商业模式，即企业借助互联网，通过运用大数据、AI、云计算和人工智能等现代化先进科学信息技术，对商品从生产到流通、从运营到销售的整个过程进行升级改造，进一步重塑业态结构和生态圈，并对线上服务、线下体验和现代物流进行深度融合的零售新模式[1]。马云也进一步表示今后的十年、二十年将是新零售的天下，不再仅仅是纯电商。2016-2020年中国生鲜电商行业市场规模发展趋势如下图1-1：图1-12016-2020年中国生鲜电商行业市场规模示意图自马云提出新零售之后，2017年中国生鲜电商行业的市场规模比2016年增长45.1%，直到2020年，中国生鲜电商行业市场规模高达2034.8亿元。据前瞻产业研究院发布的《中国生鲜行业研究报告》显示，2020年，我国人均蔬菜占有量将达400公斤，速冻食品的产量也以20%的速度不断增加，由此可见，中国未来的生鲜行业市场规模巨大，生鲜电商市场也将继续扩大。多多买菜是拼多多在2020年8月上线的一种线上买菜交易平台，它采取的是“线上下单+线下自提”的半预购模式，消费者每天23点前下单，次日便可到最近的自提点取回商品。多多买菜的线下自提模式是通过与农村个体超市或者城市社区超市合作，每天将前一日客户在线上订购的产品送至这些合作的提货点，然后通知用户在下单的次日去最近的自提点取货。这种客户自提的方式，将物流配送的“最后一公里”环节省略，消费者可以根据自己的时间自由地去提货点取货，用户的满意度也会随之提高。在各提货点的上级，多多买菜在每个地区都会设置一定数量的物流配送中心，用来对商品进行流通加工、包装和分拣，并且每天都会由配送员将线上订单的商品派送到多个不同的提货点。拼多多的物流中心是由第三方物流企业所提供的，所以从物流角度来说，降低其生鲜产品流通成本主要在于两个方面，一方面是通过优化物流配送中心的选址问题，加快配送中心生鲜产品的周转，减少资金的占用；另一方面是对配送路径进行优化，提高生鲜产品的配送效率，降低生鲜产品的货损率，降低配送成本。目前，我国针对单一的配送中心选址问题和路径优化的研究已经相对成熟，但对生鲜产品的配送中心选址及配送路径联合优化问题的研究较少，尤其是这种省略“最后一公里”配送的城乡提货点的终端配送路径的研究仍需进一步探索。所以文章基于以上背景，以多多买菜生鲜物流中心选址和配送路径优化为研究内容，设计物流中心选址和配送路径双层规划目标，通过设计求解算法，实现生鲜物流系统成本的降低。1.2研究意义物流设施选址和路径规划问题是物流网络优化的两个关键节点。选址问题是对设施位置和数量进行科学的决策，路径问题是对配送路线进行优化，以提高物流配送的效率。所以，通过对物流网络优化所涉及的选址和路径优化问题进行集成优化，可以有效地避免单独优化所导致的局部最优。（1）理论意义目前关于生鲜产品物流的研究主要集中在供应链、产品溯源和配送模式研究等问题上，关于生鲜物流配送中心选址及路径协同优化问题的研究并不多。本文通过研究选址-路径模型，以物流系统成本最低为目标，建立选址-路径双层目标规划模型，对生鲜物流网络结构进行优化，以实现提高物流运作效率，降低物流配送成本的目的。（2）现实意义本文深入分析了配送中心选址及路径优化问题，构建了生鲜产品配送中心选址与路径优化问题的双层规划模型。企业可以依据自身情况合理制定配送路径的方案和适应本企业的配送中心最佳选址方案，为生鲜电商企业优化物流系统提供了新思路和新方法，降低了企业的物流配送成本，从而提高了企业的经营收益。1.3国内外研究现状1.3.1国外研究现状物流配送中心选址问题较早是在国外开展研究的，1909年由Weber提出韦伯问题，主要研究单一仓库与各需求点之间的路径最短问题[2]。后来，随着社会的发展，众多学者开始加入自身的考虑因素，不再局限于单一目标，Owensh等在配送中心选址模型中加入了配送途中动态性以及变动性需求信息[3]。Syam等建立了物流链网络问题的0-1混合整数线性规划模型，问题的目标函数是以最低成本选择开放的设施（工厂和配送中心）来满足配送需求，通过运用模拟退火算法对冷链物流多设施选址模型进行求解[4]。车辆路径规划问题是在1959年由著名学者Dantzig和Rasmer首次提出的。国外学者对车辆路径问题较多研究的是现代启发式算法，包括遗传算法、禁忌搜索算法、蚁群算法和人工神经网络算法等。Lahyani研究了多约束车辆路径问题的若干变型，形成了一类富有车辆路径问题[5]。Rahimi-Vahed等对多车辆段车辆路径问题、周期车辆路径问题进行了研究，使用模块化启发式算法对问题进行规划[6]。1.3.2国内研究现状物流配送中心的选址及配送路径优化问题是整个生鲜物流网络规划设计中的两个重要因素，整个物流系统的效率和效益与这两个因素之间存在着紧密联系。在配送中心的选址、车辆的配送路径优化以及选址-配送模型问题方面国内专业学者做了大量的研究。马帅对仓储、未满装载惩罚两个相互博弈的因素以及时间窗等因素进行分析，建立了配送中心选址及路径优化双层规划模型；然后设计了枚举法与遗传算法相结合的双层规划模型求解[7]。王萌构建了考虑新鲜度和时间窗约束的生鲜物流配送优化模型，结合配送时间对食品腐败的影响及时间窗约束，并根据新鲜度变化函数，构造最小化配送成本和最大化新鲜度的生鲜产品配送双目标模型，然后设计了双目标遗传算法进行求解[8]。李慧针对O2O生鲜电商配送网络配送成本过高，配送效率低下等问题，设计双层布局规划法，上层规划考虑社区之间的物流联系，将其作为综合评价指标对末端节点的配送范围进行划分；下层规划以配送成本最低为目标，对整个配送网络进行以成本为导向的配送路径优化[9]。丁欢根据生鲜产品消费者所注重的配送时长问题，构建客户时间满意度函数，并从不同客户对企业来说存在差异性的实际情况出发，引入客户价值的概念，建立客户价值指标评价体系，又基于冷链物流的特点，分析冷链配送的成本构成，通过推导生鲜食品的新鲜度函数，描述了因新鲜度下降对客户需求量的影响；构建了包括固定成本、货损成本、运输成本、能耗成本的选址成本模型，进而得到考虑客户时间满意度和价值权重的配送中心多目标选址模型[10]。第2章生鲜物流中心选址与配送路径优化问题研究2.1生鲜物流中心选址问题研究2.1.1选址问题概述在物流系统规划设计中，物流节点的选址是一个重要的决策问题，它决定了整个物流网络的结构、模式和形状。物流节点的选址决策就是确定整个物流系统中所需的节点数量、节点的地理位置，以及它们的服务对象分配方案[11]。生鲜物流配送中心是生鲜电商与终端消费者之间的桥梁，是生鲜电商加工处理和配送的关键物流节点。有效合理地对生鲜配送中心进行选址，可以显著提高生鲜物流的配送效率，还可以降低车辆配送的成本以及货物的损耗率，从而实现生鲜电商的效益最大化。物流配送中心选址问题（Location-AllocationProblem,LAP）是配送中心的定位-分配问题，标准的选址问题一般假设商品在设施与配送点的关系属于点对点的关系，配送中心的配送模式属于中心放射状，在选址时不考虑车辆的路径规划问题。但在确定生鲜配送中心的具体位置后，相应的车辆配送方案也会根据配送中心的位置做出相应的调整。所以，配送中心的选址问题影响着车辆配送路线的规划问题。（1）生鲜配送中心选址规划的目标配送中心的选址是物流系统规划的基础性工作，对企业未来的生产和经营起到非常重要的作用。1）成本最小化成本最小化是物流节点选址中最常见的目标，与物流节点选址规划有关的成本主要包括设施成本和运输成本。与设施相关的成本有固定成本、存储成本和搬运成本。固定成本是指那些不随设施的经营活动水平而改变的成本，比如租金、税金和折旧费都属于固定成本。存储成本与所存储的货物相关，典型的存储成本有仓储损耗、库存占用的资金费用、货物的保险费等。搬运成本是指随着设施吞吐量变化的成本。运输成本取决于运输货物的数量、运输距离和运输单价。所以配送中心的选址直接影响到运输距离，与运输成本控制有着密切的联系。2）物流量最大化物流量反映了物流节点的作业能力。反映物流量的主要指标包括吞吐量和周转量，这两个指标可以用来测量物流节点的利用率，通常物流量越大，效益越高。但由于生鲜电商配送具有多品种、小批量、高频度的特点，所以吞吐量和周转量这两个指标便无法适应这种发展趋势，如物流节点与顾客距离越远，则周转量越大，但运输和管理费用也越高。因此，在配送中心选址时，首先要考虑成本最小，再考虑物流量最大。3）服务最优化与物流节点选址决策直接相关的服务指标主要包括送货时间、距离、速度和准时率。对于生鲜产品，产品的新鲜度是影响客户满意度的主要因素，所以运输速度越快，产品越新鲜，这就要求物流节点与客户的距离越近越好。4）发展潜力最大化物流配送中心不仅投资大，而且投资回报率相对较低，所以在选址时还要考虑将来的发展潜力，包括物流节点生产扩展的可行性和消费者需求增长的潜力。（2）常见设施选址问题1）中值问题该问题是在区域中选择若干个设施位置，使得该位置离需求点到最近设施的距离（或成本）的加权和最小。这种加权和最小的目标通常用于解决企业问题，所以也称为“经济效益性”。这类问题是minimum问题，它的目标函数通常写成以下形式：式中，：新的待定设施的位置坐标；：已存在且位置固定的需求点编号；：新设施在位置时到需求点的距离（或成本）。2）中心问题中心问题是根据使得被选择设施位置离最远需求点的距离（或成本）集合中取最小的原则，在区域内选择设施的位置。中心问题的目标是由可选集合中设施的单个成本最大的部分组成，它的目标是优化最坏的情况，这种目标通常是在军队、紧急情况或者公共部门使用。中心问题的目标函数是：式中，：新的待定设施的数量：需求地编号：新设施在位置时到需求点的距离（或成本）。3）反中心问题反中心问题和中心问题相反，它是根据在一定区域内使得被选择设施位置离最近需求点的距离（或成本）集合中取最大的原则进行选址。它的目标也是优化最坏的情况，这种目标通常在有害设施的选址中使用，其目标函数如下：式中，：新的待定设施的数量：需求地编号：新设施在位置时到需求点的距离（或成本）。4）覆盖问题覆盖问题包括最大覆盖问题和集合覆盖问题，它是一类离散点选址问题。最大覆盖问题是对有限个服务设施进行选址，并为尽可能多的需求点提高服务，但可能无法满足所有需求点的需求。集合覆盖问题是选择尽可能少的设施来满足所有需求点的需求。以上问题的具体解法见2.1.2。2.1.2常见求解模型介绍在进行生鲜物流配送中心选址时，除了要考虑配送中心的建设成本和车辆的运输成本外，还需要使用合适的数学模型来进行求解，以获得最优的决策方案。上文的中值问题、中心和反中心问题的求解模型一般是用于单个设施节点的选址，覆盖模型通常用于多个设施节点的选址。下面本文介绍几种常见的选址模型，分别为重心法、最大覆盖模型、集合覆盖模型。（1）重心法重心法适用于单个生鲜物流配送中心的选址研究。假设每个终端提货点所覆盖的范围需求为，坐标为；配送中心的坐标为，生鲜物流配送中心到第个终端提货点的距离是，配送单位质量的生鲜产品的单位运输费用为，则利用重心法进行选址的数学模型为：（2-1）（2-2）模型中，目标函数（2-1）表示车辆配送的总费用最小，约束条件（2-2）表示终端提货点需求量为非负。在对模型求解时，能够使得达到最小的点即为最佳决策点。重心法由于自身具有缺陷，其没有对选址的位置进行约束，所以可能导致选址位置的不合理，重心法往往只能作为参考。（2）最大覆盖模型最大覆盖模型的目标是选择有限数量的物流配送中心，并为尽可能多的需求点服务，但可能不能满足所有需求点的需求。最大覆盖模型的数学模型如下：（2-3） S.t. （2-4）（2-5） （2-6）（2-7）（2-8）模型中，：个需求点集合；：第个需求点的需求量；：设施节点的容量；：设施节点所覆盖的需求点集合；：可以覆盖需求点的设施集合；：允许投建的设施数；：节点需求中被分配给设施节点服务的部分，小于等于1；：节点是否被选中成为设施，如选中则为1，否则为0。式（2-3）为目标函数，其目标是为尽可能多的需求点提供服务，满足他们的需求；式（2-4）表示需求点的需求有可能得不到满足；式（2-5）是对每个设施的服务能力的限制；式（2-6）是对允许建设的设施的数量的限制；式（2-7）是指允许一个设施为某个需求点提供部分需求。以上模型是一个混合的0-1整数规划模型，通常可采用精确求解方法和启发式方法求解。Richard和CharlesR.Velle设计贪婪启发式算法，用以对最大覆盖模型进行求解。贪婪启发式算法首先求出可以作为候选点的集合，并以一个空集作为原始解的集合，然后在候选点集合中选择一个具有最大满足能力的候选点进入原始解集合，作为二次解，依次重复进行以上步骤，直到设施的数目满足要求为止。（3）集合覆盖模型集合覆盖模型的目标是用尽可能少的设施去满足所有需求点的需求，其数学模型如下：（2-9）S.t.（2-10）（2-11）（2-12）（2-13）式中，：个需求点集合；：第个需求点的需求量；：设施节点的容量；：设施节点所覆盖的需求点集合；：可以覆盖需求点的设施集合；：节点需求中被分配给设施节点服务的部分，小于等于1；：节点是否被选中成为设施，如选中则为1，否则为0。模型中，式（2-9）是目标函数，使被选为设施的节点数最小；式（2-10）保证了每个需求点的需求都能得到满足；式（2-11）是对每个设施的服务能力的限制；（2-12）表示允许一个设施为某个需求点提供部分需求。对此类带有约束的极值问题，一种求解方法是用分支定界，能够找到小规模问题的最优解。第二种求解方法是启发式算法，可以用于对大规模问题的分析与求解，但所得到的结果不能保证是最优解。2.2生鲜物流配送路径优化研究2.2.1路径优化问题概述运输路线优化主要是选择起点到终点的最短路，最短路的度量单位可能是时间最短、距离最短或费用最小等[11]。运输问题可以分为点点之间运输问题、多点之间运输问题及回路运输问题。路径优化问题目的是为了通过科学、合理地对配送路线进行规划，在满足车辆载重和配送时间约束等条件下实现成本最低和收益最大。生鲜物流配送路径优化问题可以描述为：在生鲜物流配送中心和终端提货点（或客户）的具体位置和需求量确定时，安排冷藏车为每个终端提供生鲜产品的配送业务。每个终端需求点只由一辆车辆配送，在优化时要考虑车辆的载重能力限制、行驶距离和配送时间段等约束，最终达到例如配送费用最少、冷藏车辆数目最小、配送时间最短等优化目标。生鲜电商产品配送具有小批量、多品类、多频率的特点，所以通常属于是多点之间的运输问题，最常见的两种运输模型为单回路运输——TSP模型和多回路运输——VRP模型。（1）TSP模型旅行商问题（TravelingSalesmanProblem,TSP）是单回路运输问题中最典型的一个模型。其含义为：一个旅行商从某个城市出发，到n个城市中去售货，要求访问每个城市各一次且一次，然后回到原城市，问这个旅行商应该走什么样的路线才能使走过的总里程最短或旅行费用最低[11]。应用图论，可以将以上问题转化为如下描述：在给出一个有n个顶点的连通图中（有向或无向），寻求一条包含所有n个顶点的具有最小总权（可以是距离、费用、时间等）的回路。TSP问题的数学模型为：（2-14）S.t.（2-15）（2-16）（2-17）（2-18）式中，决策变量表示不连接到的边；表示连接到的边。是到边上的权数。（2-15）表示每个顶点只有一条边出去；（2-16）是指每个顶点只有一条边进入；式（2-17）用来限制除了起点边和终点边以外，其它选中的边不构成回路用来避免出现子回路的现象。上述模型是一个0-1整数规划问题，对于一些小规模问题的求解，可以用分支定界方法进行求解；而大规模问题需要使用启发式算法，如模拟退火算法、禁忌算法、遗传算法、蚁群算法等。（2）VRP模型车辆调度问题（VehicleRoutingProblem,VRP）一般是指对一系列发货点和收货点，组织调用一定的车辆，安排适当的行车路线，使车辆能够有序地通过，在满足制定的约束条件下（货物的需求量与发货量、交货发货时间、车辆可载量限制、行驶里程限制、行驶时间限制等），力争实现一定的目标（如车辆空驶总里程最短、运输总费用最低、车辆按一定时间到达、使用的车辆数量最小等）[11]。VRP的数学模型如下：配送中心O拥有的车辆数目是Q，配送点的总数目为,终端节点需求量为，配送车辆的最大载重量为，表示终端节点到节点的距离。（2-19）S.t.（2-20）（2-21）（2-22）（2-23）（2-24）（2-25）（2-26）上述模型中，式（2-19）为目标函数，表示配送车辆的配送距离的总和最小；式（2-20）和式（2-21）表示每个终端节点有且仅有一辆配送车辆服务；式（2-22）表示所有需求点的需求总和不超过配送车辆的最大承载量；式（2-23）是对可以提供服务的车辆的数量限制；式（2-24）表示配送车辆配送路线为回路，即车辆运输的起点和终点都是配送中心；（2-25）和（2-26）是模型的决策变量。2.2.2常见求解模型介绍单回路运输问题主要用于对单一车辆的路径安排，目标是在该车辆遍历所有目标终端节点的同时，实现所行驶的距离最短。多回路运输问题又可以成为车辆调度问题，是针对有大量服务对象的实体。当进行车辆运输服务时，由于条件的限制，无法用一条回路来完成任务，解决此类问题的核心是对车辆的调度。下面本文将针对两种回路运输提出常见的解决方法。（1）最近邻点法计算步骤：①从零点（即配送中心）开始，作为整个回路的起点。②找到离刚刚加入到回路中的上一个顶点最近的一个顶点，并将其加入到回路中。③重复②，直到将所有的顶点都加入到回路中。④将最后一个加入的顶点与起点连起来。（2）节约算法节约算法的核心思想是将运输问题中存在的两个回路与合并成一个回路。然后计算合并后的回路的运输距离，与原来两个回路的距离和进行比较，如果合并之后的回路运输距离下降，则说明节约了运输距离。节约距离的节约值用表示，计算公式为：2.3生鲜物流配送中心选址及路径优化问题研究2.3.1选址-路径问题概述由于目前生鲜物流网络不断扩展，城市交通网络日益复杂，所以生鲜物流配送中心选址对车辆路径规划的影响越来越大。例如，若仅考虑配送中心的选址问题则无法对车辆的高油耗和运输距离进行分析；如果仅从配送路径分析，则无法将可覆盖的终端节点考虑在内。因此，在对生鲜产品配送中心选址和车辆配送路线规划时，要从集成优化的角度出发，将两者进行有机结合统筹规划，从而可以避免单独优化带来的局限和瓶颈。选址-路径问题（LocationRoutingProblem，LRP）所要解决的问题是从一组备选的设施中选择一个或者多个设施作为配送中心为终端客户进行服务，同时合理地规划在满足所有终端客户需求的同时，实现配送成本的降低。LRP问题可以从供应链的两端对生鲜物流网络进行集成优化，基于系统论，实现整体生鲜物流系统成本的最小化。2.3.2选址-路径基本模型选址-路径问题与上文介绍的选址问题和路径问题有密切的联系，但将二者基于系统集成的方法结合起来所组成的模型也会随之更为复杂和困难。选址-路径数学模型如下：（2-27）S.t.（2-28）（2-29）（2-30）（2-31）（2-32）（2-33）模型中，表示客户与设施的集合；表示设施集合；为客户集合；表示设施的固定成本；是客户的需求量；为由运输到的成本；表示车辆集合；为车辆的载重量；为0,1变量。式（2-27）为目标函数，即系统整体成本最低；式（2-28）是对车辆载重的限制；式（2-29）表示客户仅由一辆车服务；式（2-30）和（2-31）是流量守恒公式；最后两个式子表示车辆完成配送任务后返回配送中心。本文基于选址-路径模型，将生鲜物流配送中心的选址与配送运输路线优化结合起来进行研究。通过建立选址和配送路径优化的双层目标规划，设计基于最短路径的算法，最终求解出实现降低物流系统成本的选址和路线规划结果。第3章生鲜物流配送中心选址及路径优化模型分析3.1双层规划模型介绍双层规划模型具有二层传递性，其上下层的模型都有各自的目标函数、约束条件和决策变量。双层规划数学模型如下：（3-1）（3-2）其中反应函数由下层规划所得：（3-3）（3-4）上述模型中，式（3-1）是上层规划模型的目标函数；式（3-2）是上层规划模型的约束条件；（3-3）和（3-4）分别表示下层规划模型的目标函数和约束条件。被称为反应函数，它是上层和下层模型的共同约束条件，对上层和下层的决策都有影响，可以使可行解在双重约束条件下达到平衡。可以将双层规划模型看作一个分层级的系统，由处于两个层级的决策者进行决策。上层的决策者是领导者，控制变量，下层的决策者称为跟随者，控制决策变量。在双层规划模型中，上层规划决策时要考虑可能给下层带来的不利影响，下层规划时也要考虑如何在上层决策达到最优的前提下可以实现自己的最优化。所以，双层规划模型的上下层之间相互制约、相互联系，通过双方结果的不断改进，实现整个系统的绩效最优。3.2模型的构建思路上层规划模型的目标是确定生鲜物流配送中心的选址位置和数量，是在给定数量和位置的需求集合和可选设施位置集合的前提下，考虑配送中心的固定成本、配送成本和腐败成本（生鲜产品在运输途中的损耗成本），用来共同对生鲜物流配送中心选址问题进行优化决策。下层规划模型是在上层模型确定了配送中心的位置之后，对配送中心的车辆配送路线进行规划。考虑到生鲜产品对时间的高要求，所以以总配送距离最小为目标，并加入车辆配送的固定成本、运输成本、货损成本、时间窗惩罚成本。通过双层模型之间的协调优化，在保证生鲜产品新鲜度的前提下，将整个成品配送物流系统的总成本降至最低。双层规划模型的构造思路如下图3-1：图3-1双层规划模型的构建思路3.3上层模型的构建上层模型要解决生鲜物流配送中心选址问题，其可描述为：在某区域中，在给定数量和位置的终端提货点集合的前提下，从一个候选配送中心位置集合中选择合适的给定数量的配送中心位置，并指派每一个提货点仅被一个配送中心服务，使得配送中心的总成本最小。3.3.1模型假设本文在建立区域生鲜物流配送中心选址模型时，做出如下假设：（1）配送中心的可选位置局限在一定的范围之内；（2）一个终端提货点只由一个配送中心提供服务；（3）所在区域内客户的需求量可以预测；（4）区域内配送中心的个数是有限的；（5）建模时不考虑对客户的价格折扣和订购的规模效应；（6）不考虑生鲜商品的存储成本；（7）不考虑配送中心的吞吐频率限制。3.3.2符号介绍表3-1上层模型符号说明符号含义表示第个生鲜物流配送中心到第个提货点的实际行驶里程表示配送中心与终端提货点之间冷链车辆的平均配送速度表示配送中心的集合表示终端提货点的集合表示提货点的需求量表示配送中心的固定成本表示第个配送中心到第个提货点的单位运输费用表示运输产品的单价表示生鲜产品的变质速率系数表示区域生鲜物流配送中心的数量表示区域内生鲜物流配送中心的吞吐量3.3.3成本分析基于对生鲜物流配送中心运营和配送中存在的成本分析，在建立生鲜物流配送中心选址模型时，将考虑以下几种成本构成，在满足一定条件的基础上，实现配送中心成本的最小化。（1）配送中心的固定成本在本文研究背景下，拼多多的物流配送中心是租赁的第三方物流企业的仓库，所以此处的配送中心成本主要是由租赁成本、运营成本和购买冷链运输车辆、设施设备的成本构成。由于成本构成较为复杂，所以此处以表示配送中心的固定成本，所以配送中心的固定成本可以表示为。（2）配送成本配送成本在生鲜电商企业的日常运营中占据很大的比重，它能够衡量一个企业在配送路径规划方面的能力。配送成本属于可变成本，它与终端客户需求量、客户距离和单位配送成本有关。此处以表示需求点的需求量，表示从第个配送中心到第个需求点的运输距离，表示第个配送中心到第个需求点的单位运输费用。所以，生鲜物流配送中心的配送成本为。（3）腐败成本腐败成本也可以看做是货损成本，由于生鲜产品对温度和运输时间的严格要求，所以在仓储和运输过程中都会存在货损。本文用腐败系数来衡量生鲜产品的货损成本，根据国内外学者的研究，得出生鲜产品的腐败系数为[12]，其中表示从配送中心到终端客户运输的平均速度。用表示运送物品的单价，则腐败成本可以表示为。3.3.4生鲜物流配送中心选址模型本文研究区域生鲜物流配送中心的选址问题，由于受到区域的经济因素和市场需求因素的影响，所以对区域的生鲜需求可以进行有效的预测，因此本文研究的问题符合P-中值问题的基本要求。所以本文在P-中值模型的基础上，在目标函数中加入了配送中心的固定成本和生鲜产品的腐败成本，追求在满足区域内所有终端需求点需求的情况下，实现区域生鲜物流配送中心的总成本最小。区域生鲜物流配送中心选址模型如下：（3-5）S.t.（3-6）（3-7）（3-8）（3-9）（3-10）模型中，式（3-5）是目标函数，目标实现配送中心的固定成本、配送成本和生鲜产品腐败成本的最小化；式（3-6）是对配送中心数量的限制；（3-7）是对配送中心吞吐量的约束，要满足终端客户的需求；式（3-8）保证每个需求点只能由一个配送中心提供服务；（3-9）可以有效地保证没有选中的配送中心候选点不能为需求点提供服务。模型中的和是0-1决策变量，表示配送中心是否被选中。3.4下层模型的构建生鲜产品的物流配送问题可以描述为：配送由一个配送中心和多个终端客户构成，配送中心负责个终端提货点的生鲜产品的配送，提货点的需求量为。配送中心拥有辆车，每辆车被分配一定的配送任务，可以将每辆车的配送路径问题看为TSP问题，每辆车从配送中心出发，遍历其配送任务中的所有终端提货点各一次且一次，然后回到配送中心。配送车辆的最大载重量为，且每个提货点的需求量不大于每辆车的最大载重量。3.4.1模型假设（1）配送过程中，订单都可以一次配送成功；（2）订单不可拆分，单个订单的商品量不超过配送车辆的最大载重量；（3）客户的订单信息已知，每辆车的任务已知；（4）每个配送路线由一个配送员工负责，且只负责这一条路线；（5）假设车辆内的温度为恒温，只考虑配送时间对生鲜产品新鲜度的影响；（6）每辆车辆的配送任务不超过车辆的最大容量；（7）配送中心的运力充足，可以完成所有的订单配送。3.4.2符号介绍表3-2下层模型符号说明符号含义表示客户集合，其中表示客户点配送中心提货点的集合，表示配送中心，表示配送车辆集合，表示配送车辆的最大载重量表示车辆的行驶速度表示提货点的需求量表示车辆的单位运输成本表示使用车辆的固定成本表示提货点到提货点的距离表示车辆从提货点到提货点的时间，且提货点由车辆服务时取1，否则为0表示车辆到达提货点的时间表示产品配送到客户手中的新鲜度车辆从提货点到取1，否则为03.4.3成本分析生鲜电商产品配送中最注重的是客户满意度，考虑到生鲜产品的易腐性，且生鲜产品对配送时间和冷链设备有较高的要求，所以在进行成本分析时要将冷链车辆和相关设备的成本以及时间窗约束考虑在内。（1）固定成本固定成本包括购买和维护车辆的成本、人员的薪酬等。设为单位配送车辆的固定成本，为0-1变量，表示车辆从车场出发，则配送中心总的固定成本为。（2）运输成本生鲜产品配送车辆的运输成本包括车辆的燃油费用，与行驶里程有关；冷藏车辆及相关设备的制冷费用，与配送时间有关。设为单位距离的配送车辆运输成本；为提货点到提货点的行驶距离；为0-1变量，若配送车辆从提货点行驶到提货点，则，否则为0。所以，配送车辆的运输成本为。（3）货损成本货损成本是生鲜产品在配送过程中因损或腐败而造成的，在前文中提到产品的腐败速率随时间变化并呈指数型变化。有学者曾总结出货损函数为[8],其中表示商品离开车辆送达客户的时间，是生鲜产品的时间敏感程度，通常与产品的生命周期有关。因此，生鲜产品的货损成本可表示为。其中，是生鲜产品的单位价值；是车辆提供给提货点的商品量；表示提货点的货物是否由车辆配送；是车辆为提货点服务的时间；为车辆从配送中心出发的时间；到达提货点产品新鲜度为。（4）时间惩罚成本多多买菜平台的产品配送虽然省略了“最后一公里”环节，但从配送中心送至各个提货点的时间仍然受到客户满意度时间窗的限制。如果配送车辆提前到达提货点，则车辆可能会产生一定的机会损失成本，且货物在没有温度控制的情况下会产生更多的损耗；而如果车辆延迟到达，车辆会付出更多的冷藏费用，同时可能造成消费者提货等待的情况，降低了客户的满意度。混合时间窗惩罚函数[8]可以表示为如下式：（3-11）上式（3-11）中，是车辆到达提货点时相应的时间窗惩罚成本；是客户满意度最优的时间窗，若车辆在此时间段内到达提货点，客户的满意度最大；是提货点的可服务时间窗，只有在此范围内才接受服务；、分别是配送车辆提前到达和延迟到达的惩罚系数。3.4.4配送路线优化模型参考上文中介绍的TSP模型，在考虑成本时加入了固定成本、货损成本和配送时间窗惩罚成本，以配送总成本最小化为目标，建立了配送路线规划模型。生鲜产品配送路线优化模型如下：目标函数：S.t.（3-12）（3-13）（3-14）（3-15）（3-16）（3-17）（3-18）（3-19）在上述模型中，目标函数为固定成本、运输成本、货损成本和时间窗惩罚成本之和的最小值。式（3-12）表示配送中的车辆数不超过配送中心的车辆总数；式（3-13）表示配送车辆从配送中心出发，完成后再返回配送中心；（3-14）是指每辆车的配送任务不可超过其最大载重量；（3-15）和（3-16）是指每个提货点只被一辆配送车服务，且只服务一次；（3-17）是生鲜产品的新鲜度函数，用于求其货损成本；式（3-18）是车辆从提货点到提货点的时间；（3-19）是决策变量。第4章模型求解算法研究4.1双层规划模型的求解流程在双层规划模型中，上层的配送中心选址问题是企业发展中的长期规划，属于战略性决策；下层规划中的车辆路径规划问题属于短期可调整的规划[13]。前文曾说过，上层规划相当于领导者，下层规划是双层规划中的跟随者。上层规划模型的目标追求的是整体的最优化，下层规划模型则是跟随上层给出的方案，追求自身目标的最优，并将结果返回给上层领导者，上层继续对方案进行优化，依次类推，经过多次迭代，最终实现双层规划模型的整体最优。（1）双层规划模型的求解思路双层规划模型的一般求解思路为：求出上层模型的最优解，将上层规划模型的最优方案代入下层模型的目标函数，求出下层模型的最优解，从而得出了整个双层规划模型的最优解。生鲜物流配送中心选址和配送路线优化双层规划模型的详细求解思路为：1）求解上层模型确定选址方案；2）下层模型根据上层模型得出的选址方案求解配送路线规划方案；3）将下层的配送路线规划结果返回给上层，对上层规划模型中的可变成本（配送费用）进行重新求解；4）把上层目标作为整体双层规划的目标进行迭代，直到满足迭代终止条件。（2）求解算法框架本文建立的选址-路径双层规划模型是一个典型的NP-hard问题，运用一般的运筹学方法无法求得其精确结果，因此本文构建了双层启发式算法求解基于双层规划的选址-路径问题，如图4-1。上层模型是根据P-中值模型改进得到的，所以此处采取一种常用于解决P-中值问题的贪婪取走启发式算法。通过求解上层规划模型得到最优选址方案，在此基础之上求解下层模型。此处的生鲜电商车辆配送问题可以看作是TSP问题，由一辆车从配送中心出发，向其任务计划中的提货点配送生鲜产品，要求车辆必须经过计划中的所有提货点各一次且一次，且以行驶距离最短为目标，最终返回到配送中心。在求解TSP问题时，本文采用最近插入法求解车辆的配送路线。图4-1双层启发式算法框架4.2上层模型的求解算法贪婪取走启发式算法（greedydroppingheuristicalgorithm）是一种常用于解决P-中值模型的算法。它是一种不追求最优解，目标获得相对较为满意的结果的启发式算法。在使用贪婪取走启发式算法求解时，首先要明确求解目标，并且制定一个可行的贪婪准则，以当前状态为最优选择，不考虑其他各种可能的整体情况，从初始状态开始一步步地搜索，直到找到满足问题要求的目标值。贪婪取走启发式算法的基本步骤如下[14]：（1）初始化，令，将所有的候选位置都选中，然后将每个客户指派给距离最近的一个候选设施。（2）选择并取走一个位置点，要求其满足以下条件：假设将该点取走，并将它的客户重新指派给距离最近的一个候选位置，总费用的增量最小。若满足，则。（3）重复（2），直到。4.3下层模型的求解算法车辆配送路线规划是短期策略，每次的配送路线也要根据车辆的任务来重新规划，所以本文在研究配送路线优化时，仅考虑一辆车的单回路运输问题。解决TSP问题的常用简单的启发式算法有最近邻点法和最近插入法，最近插入法虽比邻点法复杂，但能够得到相对比较满意的结果。最近插入法的基本原理是：首先找到一个离配送中心最近的点构成一个子回路，然后在剩下的提货点集合中寻找离子回路中的某一点最近的节点，将其插入到子回路中，依次不断推进，直到将所有的提货点都插入到闭合回路中，所形成的回路就是该TPS问题的解。最近插入法的具体步骤[11]如下：（1）找出距离最小的节点，形成一个子回路；（2）在剩下的节点中，找出一个距离子回路中的某个节点最近的节点；（3）在形成的子回路中找到一条弧，使得最小，然后将节点加入到子回路中，插入到节点和之间，用两条新弧和来代替原来的；（4）重复（2）和（3）步骤，直到所有的节点都加入到闭回路中。第5章案例分析基于上文对生鲜电商物流配送中心选址和配送路线规划的分析，本文建立了双层规划模型，并研究了对应的求解算法。本章以多多买菜在HD区的生鲜配送中心选址和配送路线优化为例，收集整理相关数据，使用本文所建模型和研究算法进行求解，给出多多买菜在HD区的配送中心选址和配送路线优化方案，并对求解结果进行分析。5.1案例背景案例的分析对象是HD区的多多买菜，它是拼多多平台提供的一个线上买菜服务。拼多多是我国移动互联网的主流电子商务应用产品，多多买菜是其在2020年8月上线的一个“线上下单+线下自提”的生鲜产品交易平台，目前上线的生鲜商品包括蔬菜、水果、肉蛋和乳品，等等。近年来，我国生鲜电商市场规模不断扩大，随之而来的是各个企业之间的竞争。物流作为企业的第三利润源泉，越来越受到生鲜企业的重视，企业力图通过科学的方法降低生鲜物流的成本，提高生鲜物流运行效率，提高企业的利润。本文基于多多买菜“线上下单+线下提货”的运行模式，研究讨论多多买菜在HD区的生鲜物流配送中心选址和向各个提货点配送时的路线优化问题。本文选取了10个终端提货点作为主要研究对象，拟建2个配送中心，进行选址-配送的协同优化，给出多多买菜在HD区较优的生鲜物流配送中心选址方案和车辆配送路线优化方案，力求实现降低生鲜产品损耗、提高配送效率和降低生鲜物流总成本的目标。5.2上层规划——配送中心选址已知多多买菜在HD区现有10个提货点，公司拟租赁2个配送仓库作为多多买菜平台集散分配的生鲜物流配送中心。公司希望以最低的运输成本来满足10个提货点所覆盖地区的需求。经过考察筛选后，公司确定了5个候选地，从候选地到各提货点的单位运输成本如下表5-1所示，各候选点和提货点的位置分布如下图5-1。表5-1各提货点需求量与单位运输成本矩阵表需求量3045481035102560703550628152532101145302024122558122560301565301557331365351645282022303520168282518354012302018281518图5-1候选点和提货点位置分布图由3.4.3可知配送中心的固定成本主要是由租赁成本、运营成本和购买运输车辆和冷藏设施设备的成本构成。由于5个候选位置的地理位置、交通状况和经济发展水平不同，所以其租赁成本、基础设施条件也不同。通过综合分析计算，得到了5个候选位置的固定成本如下表5-2：表5-25个候选位置的固定成本表候选点固定成本（每日）腐败成本200当日配送生鲜商品总价值的2%250400300500利用层次分析法（AHP）确定配送中心选址三项成本的权重系数，，。首先由专家利用数字1-9对配送成本、固定成本和腐败成本的重要性进行打分。构造出比较判断矩阵，利用标度值的倒数作为标度，求出各项成本在决策中所占权重，求解的判断矩阵及求解结果如下表5-3：表5-3三项成本判断矩阵及权重表配送成本固定成本腐败成本配送成本1790.67固定成本1/711/20.165腐败成本1/9210.165由上表5-3可知，配送成本是在进行生鲜物流配送中心选址时最重要的因素。在4.2中本文研究了贪婪取走启发式算法，用来求解改进后的P-中值模型。由层次分析的结果可知，配送成本在目标函数中占比高达67%，且各个候选点的固定成本和腐败成本相差较少，所以本文在进行生鲜物流配送中心选址时主要考虑配送中心的配送成本。利用贪婪取走启发式算法求解P-中值问题的具体过程如下：（1）对表5-1中的单位运输成本进行比较，按照距离最近进行分派，得到的初始化结果如图5-2，总费用为：150+100+128+300+270+110+216+320+195+180=1969，k=5图5-2初始化指派结果（2）分别移走候选地、、、、，然后对其原本服务的提货点进行重新指派，并计算各自的增量。当移走后，受影响的是，将指派给，产生的增量=210-150=60；当移走后，受影响的是，将指派给，产生的增量=375-180=195；当移走后，受影响的是、、，将指派给，指派给，指派给，所产生的增量=390+560+300-195-320-216=519；当移走后，受影响的是，将指派给，产生的增量=300-100=200；当移走后，受影响的是、、、，将指派给，指派给，指派给，指派给，产生的增量=165+500+160+324-110-300-128-270=341；所以，选择移走后产生的影响最小的点，将其移走后并把重新指派给，K=4。同理，依次取走、，最终将指派给,指派给，给，k=2,循环结束。最终的结果为选择候选点和，总的运输成本为2564，的运输成本为1106，的运输成本为1458，指派结果如图5-3所示。图5-3指派后的结果5.3下层规划——配送路径优化假设配送中心，每天用一辆车给其服务的提货点配送，要求车辆对每个提货点只能去一次，送完货后返回配送中心。配送中心和提货点、、、之间的距离矩阵如表5-4所示。此类单回路运输问题一般采用启发式算法进行求解，此处采用最近插入法求解，力求获得相对比较满意的解。表5-4配送中心与提货点之间的距离矩阵点元素-9768-10189-912-12-求解过程：车辆从配送中心出发，最终再回到。观察上表5-4，比较从出发的所有的路径大小，得出，则令配送中心和构成一个子回路，即。继续考虑剩下的提货点、、到子回路中某一节点的最小距离，求得点，，将插入和之间，构成新的回路。同理，继续找到下一点，，计算分析应将插入到回路的哪个位置：①插入之间，②插入之间，③插入之间，将插入到距离增量最小的之间，所