4第四章城市物流配送规划与决策课件

第四章第四章 城市物流配送城市物流配送规划与决策规划与决策2024/4/241kevin按配送组织主体分类商店配送配送中心配送仓库配送按配送商品数量和种类分类 少品种（或单品种）、大批量配送多品种、小批量、多批次配送配套型配送按企业经营环节分类 分销配送供应配送按配送时间和配送商品数量分类定时配送定量配送定时定量配送定时定路线配送即时配送按加工程度分类 加工配送集疏配送按配送专业化程度分类 综合配送专业配送二二、配配送送类类型型 2024/4/242kevin按照配送组织者分类自营配送第三方配送共同配送按照配送的产品分类生产资料配送生活资料配送新兴的配送模式超市配送跨国配送邮政配送电子商务配送冷链配送三、配送模式三、配送模式2024/4/243kevin四、配送运输的基本流程四、配送运输的基本流程1）划分配送区域，根据客户地理分布情况和服务时间窗口决定配送区域。2）车辆配载，根据货物分类（特性、轻重急缓），选择运输工具。3）暂定配送先后顺序，根据客户的交货时间和位置。4）车辆安排，考虑货物特征与数量、车辆吨位利用率和成本费用等。5）选择配送线路，根据交通状况、客户的具体位置、送货时间限制等作出安排。6）确定最终的配送顺序，路线经过的客户数量、行程、到达与出发时间等。7）完成车辆积载，货物装车、卸货等问题的解决，遵守“后送先装”等原则。2024/4/244kevin划分基本配送区域车辆配载车辆安排选择配送线路确定配送顺序完成车辆积载货物体 积 质量 数 量其他车辆体积额定载货量费用货物性质形状体积质量交通状况客户的具体位置送货时间限制客户分布地点货物特征客户的交货时间确定配送先后顺序（暂定）图3-3-1 配送的基本作业流程2024/4/245kevin第二节第二节 配送中心管理配送中心管理 一、配送中心的定义一、配送中心的定义 配送中心是从事配送业务的物流场所或组织，应基本符合下列要求：主要为特定的客户服务；配送功能健全；有完善的信息网络；辐射范围小；多品种、小批量配送；以配送为主，储存为辅。配送中心是配送网络设计的核心，配送中心的层次、个数和地理位置是决定企业整体供应链绩效的关键。2024/4/246kevin二、按配送中心的经营主体分类二、按配送中心的经营主体分类p（1）制造商型配送中心（Distribution Center built by Maker，MDC）是由大型制造商建设的，专门服务于制造企业的生产、销售活动。通过设立配送中心可以减少中间环节，降低企业产品销售的流通费用；提高企业的客户服务水平。配送的产品种类有限且变化小，订货和进货作业比较单一，易于标准化和规范化。通常，家用电器、汽车、化妆品和食品等厂商采用这种形式。p（2）批发商型配送中心（Distribution Center built by Wholesaler，WDC）是由产品的批发商或代理商出资建设的，此类配送中心的运作方式是先向上游的厂商订货，然后将各种产品进行组合，再转卖给它的下游零售商。2024/4/247kevinp（3）零售商型配送中心（Distribution Center built by Retailer，ReDC）是由大型零售商建设的。零售企业在经营规模达到一定水平后，可以把来自不同进货者的货物在配送中心集中分拣、加工，然后按其所属的店铺进行计划配送。企业集中采购和集中运输可以获得规模效益，包括运输成本的节省和采购价格的下降等。p（4）第三方成立的配送中心（Distribution Center Built by Trucker，TDC）属于社会化的配送中心，是由专业的物流公司出资建设的，向货主企业提供配送服务。通常具有较强的物流配送能力，在与货主企业签订物流服务合同的基础上，代理企业开展物流配送业务，可以迅速地按照客户的要求将产品送到指定地点，可以充分发挥专业物流企业的整体优势，综合利用物流设施，提高物流配送效率。2024/4/248kevin三、根据配送中心的服务范围分类三、根据配送中心的服务范围分类p（1）城市配送中心 城市配送中心是以一个城市为配送服务的范围，将商品直接送到零售商或消费者手中。城市配送中心主要采用公路运输方式，选择“多品种、小批量、多客户”的配送方式。p（2）区域配送中心区域配送中心是以较强的辐射能力和库存准备，向全省、全国、或国际范围的客户进行产品配送。这种配送中心的规模比较大，客户比较多，配送的批量也比较大。在通常情况下，区域配送中心的产品先运到城市配送中心，然后再从城市配送中心运到最终需求点上。2024/4/249kevin四、根据配送中心的服务功能分类四、根据配送中心的服务功能分类p（1）储存型配送中心重点强调的是配送中心的储存功能，在功能上与传统的仓库非常接近，通常具有较大规模的仓库和场地，具有较强的库存调节功能。p（2）流通型配送中心重点强调的是配送中心的集运功能，作为产品集中和组合的场所，将同方向的、小批量的产品或原料集中起来，及时地分发到各客户指定的地点。特点是不设储存仓库，只设周转区，占地面积比较小。主要服务对象是城市区域内的各连锁店铺，在地理位置上定位于接近主要客户的地点。p（3）加工型配送中心主要以流通加工为核心业务，根据客户提出的加工深度、尺寸、标准、数量等要求，将不同客户的商品集合后，经过加工再配送给各个客户；或者按照各个客户需要将大批量的商品进行细分，进行小件包装以及贴附标签、条形码等操作。加工型配送中心需要配置特定商品的加工处理设施、场地技术和人员。2024/4/2410kevin五、配送中心的基本功能五、配送中心的基本功能配送中心是一个多功能、集约化的物流节点，它把收货验货、存储保管、装卸搬运、拣选、流通加工、配送、结算和信息处理，甚至订货等作业有机地结合在一起。p（1）集散功能 是指配送中心能够将分散在各个生产企业的产品集中到一起，经过分拣、配组等向多家客户进行配送。p（2）储存功能是指配送中心配备相应的仓储设施设备和储存一定数量的货物，以满足市场的需要和流通加工、配送等环节的正常运转。配送中心的库存作为商品供需的缓冲区，能够满足不同消费者在不同时间段的个性化需求，这种集中储存可以大大降低库存总量，增加调控能力。2024/4/2411kevinp（3）配组功能 配组是指单个客户所需要的配售数量不能达到车辆的有效载运负荷时，就存在如何集中不同客户的配送货物，进行搭配装载以充分利用运能、运力的问题。通过配组可以提高送货水平及降低送货成本。配组已成为配送中心与传统仓储企业的明显区别之一，也是配送中心最重要的特征之一。p（4）流通加工功能 是指物品在从生产地到使用地的流通过程中，根据客户提出的要求和根据合理配送商品的原则对物品施加包装、分割、计量、分拣、刷标志、拴标签、组装等简单作业的总称。p（5）分拣功能每个客户的订单都至少包含一项以上的商品，这些不同种类的商品需要由配送中心选出并集中在一起。分拣就是将一批相同或不同的货物，按照客户不同的要求拣选后集中在一起进行配送。2024/4/2412kevinp（6）配送功能 配送就是按客户的订货要求，在配送中心进行分货、配货作业，并将配好的商品送交收货人。与运输相比，配送要求完全按照客户对商品种类、规格、数量、时间和地点的要求，进行分拣、配货、集装、车辆调度、路线安排的优化等一系列的工作，再运送给客户的一种特殊的送货形式。p（7）信息整合功能 配送中心的信息系统将各种作业环节的信息进行实时采集、分析、传递，为配送中心的经营管理、政策制定等提供有用的信息，有效地为整个流通过程的控制、决策和运转提供依据。p（8）资源回收功能是指回收及处理作业过程中产生的许多可回收资源，如拆箱更换包装后的纸箱等。2024/4/2413kevin六、配送中心作业管理六、配送中心作业管理配送中心的基本作业包括如下内容：订单处理、进货作业、搬运作业、存储作业、拣货作业、流通加工作业、补货作业和配送作业。1订单处理订单处理订单处理通常指由接到客户订单开始到准备拣货之间的作业，主要工作包括：客户订单的数据确认、存货查询、订单整理与编号及订单出货数据处理等。具体内容包括：（1）接受订单（2）订单数据处理（3）订单状况管理2024/4/2414kevin 2进货作业进货作业是指从确认客户订单，发出订货，从运输工具上把货物卸下，核对单据与实物数量、检查包装及产品质量，并办理入库手续等作业，主要包括3个环节。（1）订货配送中心在收到和汇总客户的订单后，首先要确定需要配送的商品的种类和数量，然后查询现有存货数量是否满足配送需要，当商品的库存量低于安全库存量时就需要发出订货。配送中心也可以根据市场需求情况提前订货，以备发货。（2）接货配送中心组织人力物力接收从客户发出的货物。（3）验收入库货物到达配送中心，配送中心负责对货物进行验收，验收的标准通常是按照订货合同或者订单的规定。验收的内容包括商品质量、数量、品名、规格、外观和生产日期等几个方面。验收合格的货物办理录入信息和入库手续，对于与订单规定不符的货物或者有破损的货物，就需要做出适当的处理。2024/4/2415kevin3装卸搬运作业装卸搬运作业装卸（loading and unloading）是指物品在指定地点进行的垂直移动为主的物流作业；搬运（handling/carrying）是指在同一场所内将物品进行水平移动为主的物流作业。2024/4/2416kevin4存储作业存储作业存储作业应该充分有效地利用空间，尽可能提高人力资源及设备的利用率，有效地保护好商品的质量和数量，维持良好的储存环境。良好的存储策略可以提高存储效率，存储策略可以分为以下几种：（1）定位存储定位存储是指每一类货物都有自己固定的储位，这种存储方法比较便于管理，但缺点是需要较多的存储空间。（2）随机存储随机存储是指每一类货物的储位不是固定的，而是随机的。这种存储方法最大限度地提高了仓库的空间利用率，但是给货物的进出和盘点等工作带来了一定的困难。（3）分类存储分类存储是指按货物的相关性、流动性、尺寸和重量及货物的特性对货物进行分类，对货物按类进行存储。2024/4/2417kevin存储的方式主要有托盘堆垛方式和货架存储方式。（1）托盘堆垛方式托盘堆垛方式就是用叉车将满载货物的托盘直接放置到存储的位置，用叉车依次提升堆放。这种堆垛的方式完全采用叉车作业，减轻了人的体力劳动，但托盘上的货物必须堆码平整，让上面的托盘能够平稳放置。（2）货架存储方式货架存储系统分为固定货架系统和旋转货架系统二种。高层固定货架一般分为几排，排与排之间设有一条巷道，供巷道堆垛机和叉车行驶作业。2024/4/2418kevin 5拣货作业拣货作业是按照不同的顾客或不同的配送路线要求，使用各种拣选设备和传输装置，及时、准确、快速地按顾客要求从储存区域将物品拣出，并按一定的方式进行分类和集中，送入指定的发货区。拣货可以分为人工分拣和利用自动分类机分拣二种。6流通加工作业流通加工作业是指物品在从生产地到使用地的过程中，根据需要施加包装、分割、计量、分拣、刷标志、拴标签、组装等简单作业的总称。流通加工主要的目的是为了促进销售、维护产品质量和提高物流效率，实现物流增值服务。2024/4/2419kevin 7补货作业补货作业是当拣货区的货物数量低于安全存量时，从存储区把货物运到拣货区的作业。补货的形式有以下二种：（1）批次补货每天或每批次拣货之前，先检查货物的库存量是否达到所需要的拣取量，若数量不足，则在拣货之前一次性补足。（2）定时补货把每天分成几个时点，当拣货区的存货量小于设定标准时，立即进行补货。8配送作业配送作业是利用配送车辆把客户订购的物品从配送中心运送到客户的作业。配送作业要达到运送距离最短、时间最少、成本最低3个目标。2024/4/2420kevin第三节第三节 配送路线优化设计配送路线优化设计一、配送网络结构一、配送网络结构 常用的配送网络结构有三大类，即集中型配送网络、单层次配送网络和多层次配送网络结构。2024/4/2421kevin1 1、集中型配送网络、集中型配送网络 集中型配送网络是指配送系统中只设一个配送中心，所有货物首先要在配送中心集结，然后再根据客户需求进行配送供应商客户DC集中型配送网络2024/4/2422kevin2 2、单层次配送网络、单层次配送网络 单层次配送网络，也称分散型配送网络，是配送系统中在一个层次上设多个配送中心，供应商将货物运送到不同的配送中心，然后再配送给用户。配送中心是按照用户地理位置分布划分配送区域，即按照客户就近原则设立。供应商客户DC图3-3-3 单层次配送网络DC2024/4/2423kevin3 3、多层次配送网络、多层次配送网络 多层次配送网络是配送系统中在两个或两个以上层次上设多个配送中心，是集中型配送网络与分散型配送网络于一体的一种网络结构。供应商客户DC图3-3-4 多层次配送网络DCDC2024/4/2424kevin合理的运输路线合理的运输路线1 1 一辆运货车顺次途经各一辆运货车顺次途经各停车点的路线要呈凸状，点的路线要呈凸状，或水滴形，各条线路之间是不交叉的。或水滴形，各条线路之间是不交叉的。仓库库仓库二、典型不合理运输路线二、典型不合理运输路线2024/4/2425kevinDD合理的运输路线合理的运输路线2 2将相互接近的停车点的货物装在一辆车上运送。2024/4/2426kevin仓库仓库仓库仓库2024/4/2427kevin三、城市配送运输决策三、城市配送运输决策1 1、城市配送运输常用的决策方法、城市配送运输常用的决策方法（1）TSP行程安排决策（2）VRP运输路线选择及行程安排决策 2024/4/2428kevin（1）运输工具的类型）运输工具的类型如普通卡车（大、中、小型）、厢式货车、冷藏车、集装箱货车等。（2）运输工具的来源）运输工具的来源一是自有，二是外协一是自有，二是外协。外协的运输工具又可以分为两种，一是以前有长期协议的外协车辆，二是临时租赁的车辆。前者，比如目前很多物流企业的运输车辆都是由司机自带的，物流企业也可以和其他企业签订长期协议租赁车辆。这类外协车辆的使用性质与企业自有车辆相近，只是不拥有所有权。（3）运输工具的数量）运输工具的数量物流企业拥有一定规模的运输工具（自有或合同外协），再根据业务规模到市场上临时租赁车辆。有的物流服务企业不拥有任何车辆，承揽了运输业务后再去寻找运输车辆。2、运输工具选择、运输工具选择2024/4/2429kevin案例案例YRCYRC国际物流企业在中国的发展战略国际物流企业在中国的发展战略2024/4/2430kevin3、运输工具配载与调度问题、运输工具配载与调度问题 运输工具配载的基本原则运输工具配载的基本原则（1）将相互接近的停留点的货物装在一辆车上运送。（2）优先使用大载重量的送货车辆，并将提货与送货过程结合进行。（3）上轻下重 即密度大的货物应装载在运输车辆的下面，轻泡的货物装载在上面。（4）先远后近 远途的货物和后送的货物应先装载，近途的或先送的货物应后装载。2024/4/2431kevin课堂交流 针对运输物流管理课堂教学内容，写一篇论文PPT，字数不限，但应该符合论文要求（应具有提出问题、分析问题、解决问题）。2024/4/2432kevin四、四、TSP问题问题(起点和终点相同的路径规划起点和终点相同的路径规划)TSP问题，即旅行商问题（Traveling Salesman Problem）又译为旅行推销员问题、货郎担问题，是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。TSP问题是一个组合优化问题。该问题可以被证明具有NP计算复杂性。中国邮递员问题 著名图论问题之一。邮递员从邮局出发送信，要求对辖区内每条街，都至少通过一次，再回邮局。在此条件下，怎样选择一条最短路线?此问题由中国数学家管梅谷于1960年首先研究并给出算法，故名。2024/4/2433kevin1、TSP问题的描述问题的描述p基本的TSP模型描述如下：给出一个起点配送中心和一组n个客户的集合，寻找一条在起点配送中心开始和结束的路线，这条路线经过每一个消费者，并且是最短路，即p每一个车辆在配送中心起程和终止；p一条路线一次要包含所有需要服务的客户点的配送；p每一个客户点必须在预先设置的时间窗口内得到服务；p以行程最短为确定车辆路线行程的评价指标。2024/4/2434kevin TSP旅行商是在单回路运输）问题。单回路运输问题是指在路线优化中，存在节点集合D，选择一条合适的路径遍历所有的节点，并且要求闭合。单回路运输模型在运输决策中，主要用于单一车辆的路径安排。目的在于在该车辆遍历所有的用户的同时，达到所行驶距离最短。这类问题的两个显著特点是：（1）单一性（只有一个回路）。（2）遍历性（不可遗漏）。2024/4/2435kevin 目标函数：以行程最短为确定车辆路线行程的评价指标。物流配送路径优化常见的约束条件包括：车辆装载能力限制，停车点的工作时间约束，运行时间、不同区段的车速限制，运行途中的障碍物（湖泊、山脉等、交通管制）、司机的短时间休息等。如果问题中包含送货点的个数很多，附加了许多约束条件，问题求解就变得十分复杂。对这类问题的求解，往往采用的是启发式算法，以求得一个满意解（近似解）。2 2、TSPTSP问题的数学模型问题的数学模型2024/4/2436kevin TSP模型可以如下描述：在给出的一个n顶点网络（有向或无向），要求找出一个包含所有n个顶点的具有最小耗费的环路。TSP模型的数学描述为：设有连通图G，其定点集V，定点间的距离C=cij 1 i,j n 目标函数：约束条件：mini=1,2,mj=1,2,n决策变量：从i到j无通路 从i到j有通路2024/4/2437kevin五、五、VRPVRP问题问题 1、VRP描述 在实际运输中，经常会遇到车辆受承载能力、容积的限制，一辆车不能满足所配送区域用户的需求。多回路运输问题（Vehicle Routing Problem,VRP），是对一系列客户的需求点设计适当的路线，使车辆有序地通过它们，在满足一定的约束条件下，如货物需求量、发送量、交发货时间、车辆载重量限制、行驶里程限制、时间限制等等，达到一定的优化目标，如里程最短、费用最少、时间最短，车队规模最少、车辆利用率高。VRP问题和TSP问题的区别在于：客户群体的数量大，只有一辆车或一条路径满足不了客户的需求。相对于TSP问题，VRP问题更复杂，求解更困难，但也更接近实际情况。2024/4/2438kevin典型的典型的VRPVRP可描述为：可描述为：1)多个客户同时需要运输服务，且一辆车不能同时满足这些客户的要求。2）每个客户只能被一辆车访问一次。3)所有车辆从仓库出发，并最终回到仓库。4)所有的车辆必须满足能力约束。5）车辆在路线上可以取/送货。2024/4/2439kevin2 2、VRPVRP图解基本原理图解基本原理qVRP是考虑车辆的装载能力（吨位或容积）时，对配送线路进行优化。对这一类问题的求解可基本上分为两大步骤：q第一步根据客户地理位置和时间窗口将配送区域中的客户聚类，然后根据客户需求的数量和一辆车的装载能力确定配送路线数量和配送车次；q第二步在每一条路线上采用TSP解决方法。2024/4/2440kevin案例：丁秋雷-系统工程理论与实践2007-102024/4/2441kevin2024/4/2442kevin2024/4/2443kevin TSP问题是物流配送业务中的常见问题，在物流中的描述是对应一个物流配送公司，欲将n个客户的订货沿最短路线全部送到。如何确定最短路线。解决此类问题的目标是找出途中经过的点的顺序，使其经过所有送货点并满足各点对送货时间的要求，且总距离最短或总行驶时间。“旅行推销员（TSP）”问题。TSP问题最简单的求解方法是枚举法。它的解是多维的、多局部极值的、趋于无穷大的复杂解的空间，搜索空间是n个点的所有排列的集合，大小为（n-1）。可以形象地把解空间看成是一个无穷大的丘陵地带，各山峰或山谷的高度即是问题的极值。求解TSP，则是在此不能穷尽的丘陵地带中攀登以达到山顶或谷底的过程。旅行商问题（Traveling Saleman Problem，TSP）是VRP的特例，由于Gaery已证明TSP问题是NP难题，因此，VRP也属于NP难题。随着问题中包含点个数和约束条件的增加，求解问题的复杂程度增加，要找到最优路径非常困难。即使用最快的计算机进行计算，求最优解的时间也非常长。启发式求解法是求解这类问题的好方法。六、六、TSPTSP问题和问题和VRPVRP问题的求解算法问题的求解算法2024/4/2444kevin求解TSP模型时，如果要得到精确的最优解，最简单的方法也是枚举法。对于小规模问题，枚举法是一种有效的方法。但是对于大规模问题，由于枚举法的例举次数为（n一1）！次，这在实际操作中是很难实现的。整数规划的方法用于解决部分TSP模型，其原理也是分枝定界法，该算法只能对一部分中小规模的问题进行求解，对于大多数问题的求解都存在一定的难度。2024/4/2445kevin组合爆炸例如，一台汽车每天要给20-30个不同的自动售货机补货。如果要访问20台机器的时候，其巡回路线就有20！2432902008176640000条巡回路线可供选择；如果要访问30台，就有30！265252859812191058636308480000000条巡回路线可供选择，利用现有计算机，若一秒钟可以计算100亿条路线的距离的话，对于20台自动售货机的计算需要花费7年的时间，对于30台自动售货机则需要花费8411兆年的时间，这种现象称为“组合爆炸”2024/4/2446kevin问题规模 nn!的计算时间（1宇宙龄150亿年）100.036秒20771年305.61106 宇宙龄401.721022 宇宙龄506.421038 宇宙龄1001.7710132 宇宙龄组合爆炸组合爆炸2024/4/2447kevin1 1、解决、解决VRPVRP问题的几种（传统）启发式算法问题的几种（传统）启发式算法2024/4/2448kevin 图解法的基本原理图解法的基本原理p假设在每一次的配送中，客户的地理位置、配送数量、客户接受货物的时间窗口都是确定的。p图解法就是将这些已有的信息在地图或GIS上标注，根据决策问题类型，采用一定的优化方法，将配送中心与客户连接在一起，进行配送路线优化设计的一种方法。由于是以地图或GIS为基本工具，故称此种方法为图解法。2024/4/2449kevin（1 1）解决）解决VRPVRP问题的扫描法问题的扫描法问题：对于若干个停车点（客户）安排最优行车路线。第一步，将仓库（出发点）和所有的停车点位置画在地图上或坐标图上；第二步，通过仓库位置放置一直尺，然后顺时针或逆时针方向转动直尺，直到直尺交到一个停车点。询问：累计的装货量是否超过送货的载重量或容积（首先要使用最大的送货车辆）。如是，最后的停车点排除，将路线确定下来。然后再从这个停车点开始继续扫描，开始一条新的路线。这样扫描下去，直至全部的停留点都被分配到路线上。第三步，对每条路线安排运行顺序，以求运行距离最小化。方案的误差率在10%左右。2024/4/2450kevin100030002000400030003000200020002000200020001000仓库图图5-13停留点提货量数据停留点提货量数据例5-7 从各客户点提货，然后将货物运回仓库。全天的提货量见图5-13。送货车每次可运载10000件。要求确定：需多少条路线（即多少辆送货车）；每条路线上有哪几个客户点；送货车辆服务有关客户点的顺序。2024/4/2451kevin扫描法扫描法:手工计算。车的载货量是手工计算。车的载货量是10000件。需要多少条线件。需要多少条线路？每条线路上的站点如何排列？路？每条线路上的站点如何排列？D300030001000300020002000200020002000100020004000D3000300010003000200020002000200020001000200040002024/4/2452kevin 图3-3-14是客户为12个的配送网络，单车装载能力为3个客户单位，用扫描法确定的配送线路数为4条。2024/4/2453kevin（2 2）解决）解决 VRP VRP 问题的最近插入法图解问题的最近插入法图解 最近的插入法是从企业仓库出发，选择与仓库距离最近的客户（要考虑时间窗口）形成一条配送线路，然后寻找与这条线路最近的客户点，并将其加入到原先的路线中，重新形成一条配送线路；依次类推，直到将所有客户都加到配送路线上为止，形成一条可行的配送路线。按照线路的合理判断准则，对可行配送路线进行合理化改进，就得到一条优化的配送路线。2024/4/2454kevin 设企业车辆一次配送5个客户，客户接受货物时间无特别要求。企业配送中心用表示，客户用表示，配送中心与客户之间的相对距离如图3-3-7所示。2024/4/2455kevin2024/4/2456kevin2024/4/2457kevin（3）解决）解决 VRP 问题的节约法问题的节约法 （The Savings Method）利用里程节约法确定配送线路的主要出发点是，根据配送方的运输能力及其到客户之间的距离和各客户之间的相对距离，来制定使配送车辆总的运输成本达到或接近最小的配送方案。2024/4/2458kevin节约算法用来解决VRP问题节约算法（Savings Algorithm）是 Clarke和Wright在 1964年提出的，它是目前用来解决VRP模型最有名的启发式算法。节约算法可以解决运输车辆数目不确定（运输车辆数目在VRP问题中是一个决策变量）的VRP问题，这个算法对有向和无向问题同样有效。2024/4/2459kevin节约法的原理节约法的原理初始路线初始路线线路里程线路里程将两个站点合并到同一路线上的将两个站点合并到同一路线上的里程里程节约的距离为 S=dAO+dOB-dABABOABO2024/4/2460kevin节约法节约法1.1.选择企业配送中心作为起点，并记为选择企业配送中心作为起点，并记为 “0 0”.2.2.计算节约值计算节约值S Sijij=C=Ci0i0+C+C0j0j-C Cijij3.3.从最大到最小排序节约值从最大到最小排序节约值.4.4.根据节约连接消费者形成路线根据节约连接消费者形成路线.-不要破坏先前连接的任何连线不要破坏先前连接的任何连线.-当所有消费者连接在一条路线上时，停止当所有消费者连接在一条路线上时，停止.2024/4/2461kevin节约算法用来解决节约算法用来解决VRP问题的步骤问题的步骤一、计算相互之间的最短距离二、计算各个用户之间的节约里程三、对节约里程进行排序四、连线、形成配送线路2024/4/2462kevin把节约量从大到小的顺序依次把客户连成一条回路，直到整个回路各个用户的需求量之和不超过这辆载重车的载重量，就组成了一条节约量最大的配送回路，派出一辆车。然后再在剩下的用户中同样按节约量从大到小的顺序继续组织配送回路，派出车辆，这样下去一直到所有的用户都组织完毕为止，就做完了一个完整的配送计划。2024/4/2463kevin节约算法案例节约算法案例例如，某月某日，长江物流公司接受的武汉某商场给武汉市十个用户送货的任务单，多个品种运量共80吨，各个用户的需求量如表，各点之间的路程如图75所示。公司现有十吨车二辆、5吨车若干辆。需要制定配送计划。用户PM需求量（吨）P160.0P212.0P31.0P41.5P50.5P60.5P71.5P80.8P91.2P101.02024/4/2464kevinA10P11210P211911P31312109P41511141226P5131412152515P616142018241716P71712182023191721P8181114222221192215P920151624212318201718P10表75各个用户之间的路程（路程单位：公里）制定配送计划的第一步，首先按排直送，把大运量用户先用专车直送，剩下的小运量用户再统一安排配送。由图75可以看出，物流中心A到用户P1的路程仅10公里，可以由一辆10吨车来回运送4次，一天可以完成。剩下的20吨加上的10吨可以由另一辆10吨车运送3次。派一辆10吨车专为P1用户来回运送四趟，每趟运10吨，来回算20公里。工作量为：10吨20公里4800吨公里。第二辆10吨车专为P1送20吨，为P2送10吨，来回运三次。其工作量为：10吨20公里2+10吨12公里2640吨公里。把这些大运量用户直送安排完后，P2还剩下2吨，其余小运量用户再安排配送，制定配送计划。2024/4/2465kevin2 2、解决、解决VRPVRP问题的几种智能（启发式）算法问题的几种智能（启发式）算法2024/4/2466kevin邮递员每次要走遍他所负责街区的每一条道路，投递完毕后仍须回到邮局，他应走什么路线才能使总路程最短。这个问题是由我国山东师范学院管梅谷教授在1962年首次提出的，所以国际上通称为中国邮递员问题。中国邮递员问题可以抽象为一个连通图，每个边都有一个非负权数，试求一个圈，过每边至少一次，并使圈的总权数最小。六、中国邮递员问题六、中国邮递员问题 2024/4/2467kevin定义：定义：给一个连通多重图G，若存在一条链（圈）过每边一次且仅一次，则称这条链（圈）为欧拉链（圈）欧拉链（圈）。定义：定义：一个图如果存在欧拉圈，则称之为欧拉图欧拉图。显然，一个图若能一笔不重复地画出，则这个图就是欧拉图或含有欧拉链。定理：定理：连通多重图G是欧拉图，当且仅当图中无奇点。这个定理的结论是显然的，因为欧拉图从某一点出发又回到原来的出发点，这就要求与每个顶点相关联的边数应是偶数，从而才能保证从一条边进入该点，从与该点相关联的另一条边出去。2024/4/2468kevin欧拉图问题起源与著名的哥尼斯堡七桥问题，它的实质是如何判断一个连通图能否一笔不重复地画出。这个问题是由大数学家欧拉解决的，所以称为欧拉图问题。推论：推论：连通多重图G有欧拉链，当且仅当G恰有两个奇点。上面的定理和推论提供了识别一个图能否一笔不重复画出的简单方法。如下图，有两个奇点，所以能一笔不重复地画出，从奇点V2开始一笔画到奇点V5。2024/4/2469kevin解此问题的基本思路是：若街区路无奇点，显然按欧拉图定理可以不重复地走遍所有街道回到出发位置。如果图中有奇点，每边只走一次又回到出发点是不可能的。如果要回到原地就得走些重复路，也就是在原来的街区图上添加一些边，使有奇点的图转换成无奇点的图。由于我们要求总权数最小，所以必须寻找使新增加的边的总权数最小的方案。我们称增加重复边使图中无奇点的方案为可行方案，称总权数最小的方案为最优方案。详细解法请参阅运筹学，清华大学出版社2024/4/2470kevin