《4第四章城市物流配送规划与决策(精品PPT).ppt》由会员分享，可在线阅读，更多相关《4第四章城市物流配送规划与决策(精品PPT).ppt（71页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第四章第四章 城市物流配送城市物流配送规划规划(guhu)与决策与决策第一页，共七十一页。二、配送二、配送(pi sn)(pi sn)类型类型 第二页，共七十一页。三、配送三、配送(pi sn)(pi sn)模式模式第三页，共七十一页。四、配送运输的根本流程四、配送运输的根本流程1 1划分配送区域，根据客户地理分布情况和效劳时划分配送区域，根据客户地理分布情况和效劳时间窗口决定间窗口决定(judng)(judng)配送区域。配送区域。2 2车辆配载，根据货物分类特性、轻重急缓，车辆配载，根据货物分类特性、轻重急缓，选择运输工具。选择运输工具。3 3暂定配送先后顺序，根据客户的交货时间和位置。暂
2、定配送先后顺序，根据客户的交货时间和位置。4 4车辆安排，考虑货物特征与数量、车辆吨位利车辆安排，考虑货物特征与数量、车辆吨位利用率和本钱费用等。用率和本钱费用等。5 5选择配送线路，根据交通状况、客户的具选择配送线路，根据交通状况、客户的具体位置、送货时间限制等作出安排。体位置、送货时间限制等作出安排。6 6确定最终的配送顺序，路线经过的客户数确定最终的配送顺序，路线经过的客户数量、行程、到达与出发时间等。量、行程、到达与出发时间等。7 7完成车辆积载，货物装车、卸货等问题的解决，完成车辆积载，货物装车、卸货等问题的解决，遵守遵守“后送先装等原那么。后送先装等原那么。 第四页，共七十一页。划
3、分基本配送区域车辆配载车辆安排选择配送线路确定配送顺序完成车辆积载货物体 积 质量 数 量其他车辆体积额定载货量费用货物性 质 形状 体 积质量交通状况客户的具体位置送货时间限制客户分布地点货物特征客户的交货时间确定配送先后顺序（暂定）图3-3-1 配送的基本作业流程第五页，共七十一页。第二节第二节 配送中心配送中心(zhngxn)(zhngxn)管理管理 一、配送中心的定义一、配送中心的定义 配送中心是从事配送业务的物流场配送中心是从事配送业务的物流场所或组织，应根本符合以下要求：主要为所或组织，应根本符合以下要求：主要为特定的客户效劳；配送功能健全；有完善特定的客户效劳；配送功能健全；有完
4、善的信息网络；辐射范围小；多品种、小批的信息网络；辐射范围小；多品种、小批量配送；以配送为主，储存为辅。量配送；以配送为主，储存为辅。 配送中心是配送网络设计的核心，配送配送中心是配送网络设计的核心，配送中心的层次、个数和地理位置是决定企业中心的层次、个数和地理位置是决定企业整体供给链绩效的关键。整体供给链绩效的关键。第六页，共七十一页。二、按配送中心的经营主体分类1制造商型配送中心 Distribution Center built by Maker，MDC 是由大型制造商建设的，专门效劳于制造企业的生产、销售活动。通过设立配送中心可以减少中间环节，降低企业产品销售的流通费用(li tn f
5、i yn)；提高企业的客户效劳水平。配送的产品种类有限且变化小，订货和进货作业比较单一，易于标准化和标准化。通常，家用电器、汽车、化装品和食品等厂商采用这种形式。2批发商型配送中心Distribution Center built by Wholesaler，WDC是由产品的批发商或代理商出资建设的，此类配送中心的运作方式是先向上游的厂商订货，然后将各种产品进行组合，再转卖给它的下游零售商。第七页，共七十一页。p3零售商型配送中心Distribution Center built by Retailer，ReDCp 是由大型零售商建设的。零售企业在经营规模到达一定水平后，可以把来自不同进货者的
6、货物在配送中心集中分拣、加工，然后按其所属的店铺进行方案配送。企业集中采购和集中运输可以获得规模效益，包括运输本钱的节省和采购价格的下降等。p4第三方成立的配送中心Distribution Center Built by Trucker，TDCp属于社会化的配送中心，是由专业的物流公司出资建设的，向货主企业提供配送效劳。通常具有较强的物流配送能力，在与货主企业签订物流效劳合同的根底上，代理企业开展物流配送业务，可以迅速地按照客户的要求(yoqi)将产品送到指定地点，可以充分发挥专业物流企业的整体优势，综合利用物流设施，提高物流配送效率。第八页，共七十一页。三、根据配送中心的效劳范围分类三、根据
7、配送中心的效劳范围分类1城市配送中心城市配送中心 城市配送中心是以一个城市为配送效劳城市配送中心是以一个城市为配送效劳的范围，将商品直接送到零售商或消费者手中。的范围，将商品直接送到零售商或消费者手中。城市配送中心主要采用公路运输方式，选择城市配送中心主要采用公路运输方式，选择“多品种、小批量、多客户的配送方式。多品种、小批量、多客户的配送方式。2区域配送中心区域配送中心区域配送中心是以较强的辐射区域配送中心是以较强的辐射(fsh)能力和能力和库存准备，向全省、全国、或国际范围的客户库存准备，向全省、全国、或国际范围的客户进行产品配送。这种配送中心的规模比较大，进行产品配送。这种配送中心的规模
8、比较大，客户比较多，配送的批量也比较大。在通常情客户比较多，配送的批量也比较大。在通常情况下，区域配送中心的产品先运到城市配送中况下，区域配送中心的产品先运到城市配送中心，然后再从城市配送中心运到最终需求点上。心，然后再从城市配送中心运到最终需求点上。第九页，共七十一页。四、根据配送中心的效劳功能分类四、根据配送中心的效劳功能分类1储存型配送中心储存型配送中心重点强调的是配送中心的储存功能，在功能上重点强调的是配送中心的储存功能，在功能上与传统的仓库非常接近，通常具有较大规模的仓库与传统的仓库非常接近，通常具有较大规模的仓库和场地，具有较强的库存调节功能。和场地，具有较强的库存调节功能。2流通
9、型配送中心流通型配送中心重点强调的是配送中心的集运功能，作为产品集中重点强调的是配送中心的集运功能，作为产品集中和组合的场所，将同方向的、小批量的产品或原料集中和组合的场所，将同方向的、小批量的产品或原料集中起来，及时地分发到各客户指定的地点。特点是不设储起来，及时地分发到各客户指定的地点。特点是不设储存仓库，只设周转区，占地面积比较小。主要效劳对象存仓库，只设周转区，占地面积比较小。主要效劳对象是城市区域内的各连锁店铺，在地理位置上定位于是城市区域内的各连锁店铺，在地理位置上定位于(wiy)接近主要客户的地点。接近主要客户的地点。3加工型配送中心加工型配送中心主要以流通加工为核心业务，根据客
10、户提出的主要以流通加工为核心业务，根据客户提出的加工深度、尺寸、标准、数量等要求，将不同客户加工深度、尺寸、标准、数量等要求，将不同客户的商品集合后，经过加工再配送给各个客户；或者的商品集合后，经过加工再配送给各个客户；或者按照各个客户需要将大批量的商品进行细分，进行按照各个客户需要将大批量的商品进行细分，进行小件包装以及贴附标签、条形码等操作。加工型配小件包装以及贴附标签、条形码等操作。加工型配送中心需要配置特定商品的加工处理设施、场地技送中心需要配置特定商品的加工处理设施、场地技术和人员。术和人员。第十页，共七十一页。五、配送中心的根本功能五、配送中心的根本功能配送中心是一个多功能、集约化
11、的物流节配送中心是一个多功能、集约化的物流节点，它把收货验货、存储保管、装卸搬运、拣点，它把收货验货、存储保管、装卸搬运、拣选、流通加工、配送、结算和信息处理，甚至选、流通加工、配送、结算和信息处理，甚至订货等作业有机地结合在一起。订货等作业有机地结合在一起。1集散功能集散功能 是指配送中心能够将分散在各个生产企业是指配送中心能够将分散在各个生产企业的产品集中到一起，经过分拣、配组等向多家的产品集中到一起，经过分拣、配组等向多家客户进行配送。客户进行配送。2储存功能储存功能是指配送中心配备相应的仓储设施设备和储是指配送中心配备相应的仓储设施设备和储存一定数量的货物存一定数量的货物(huw)，以
12、满足市场的需要和流，以满足市场的需要和流通加工、配送等环节的正常运转。配送中心的库通加工、配送等环节的正常运转。配送中心的库存作为商品供需的缓冲区，能够满足不同消费者存作为商品供需的缓冲区，能够满足不同消费者在不同时间段的个性化需求，这种集中储存可以在不同时间段的个性化需求，这种集中储存可以大大降低库存总量，增加调控能力。大大降低库存总量，增加调控能力。第十一页，共七十一页。p3配组功能p 配组是指单个客户所需要的配售数量不能到达车辆的有效载运负荷时，就存在如何集中不同客户的配送货物，进行搭配装载以充分利用运能、运力的问题。通过配组可以提高送货水平及降低送货本钱。配组已成为配送中心与传统(ch
13、untng)仓储企业的明显区别之一，也是配送中心最重要的特征之一。p4流通加工功能p 是指物品在从生产地到使用地的流通过程中，根据客户提出的要求和根据合理配送商品的原那么对物品施加包装、分割、计量、分拣、刷标志、拴标签、组装等简单作业的总称。pp5分拣功能p每个客户的订单都至少包含一项以上的商品，这些不同种类的商品需要由配送中心选出并集中在一起。分拣就是将一批相同或不同的货物，按照客户不同的要求拣选后集中在一起进行配送。第十二页，共七十一页。p6配送功能p 配送就是按客户的订货要求，在配送中心进行分货、配货作业，并将配好的商品送交收货人。与运输相比，配送要求完全按照客户对商品种类、规格、数量、
14、时间和地点(ddin)的要求，进行分拣、配货、集装、车辆调度、路线安排的优化等一系列的工作，再运送给客户的一种特殊的送货形式。p7信息整合功能p 配送中心的信息系统将各种作业环节的信息进行实时采集、分析、传递，为配送中心的经营管理、政策制定等提供有用的信息，有效地为整个流通过程的控制、决策和运转提供依据。p8资源回收功能p是指回收及处理作业过程中产生的许多可回收资源，如拆箱更换包装后的纸箱等。第十三页，共七十一页。六、配送中心作业管理六、配送中心作业管理配送中心的根本作业包括如下内容：订单配送中心的根本作业包括如下内容：订单处理、进货作业、搬运作业、存储处理、进货作业、搬运作业、存储(cn c
15、h)作业、作业、拣货作业、流通加工作业、补货作业和配送作拣货作业、流通加工作业、补货作业和配送作业。业。1订单处理订单处理订单处理通常指由接到客户订单开始到准备订单处理通常指由接到客户订单开始到准备拣货之间的作业，主要工作包括：客户订单的数拣货之间的作业，主要工作包括：客户订单的数据确认、存货查询、订单整理与编号及订单出货据确认、存货查询、订单整理与编号及订单出货数据处理等。具体内容包括：数据处理等。具体内容包括：1接受订单接受订单2订单数据处理订单数据处理3订单状况管理订单状况管理第十四页，共七十一页。 2进货作业进货作业是指从确认客户订单是指从确认客户订单(dn dn)，发出订货，从运输工
16、具上把货物卸下，核，发出订货，从运输工具上把货物卸下，核对单据与实物数量、检查包装及产品质量，并办理入库手续等作业，主要包对单据与实物数量、检查包装及产品质量，并办理入库手续等作业，主要包括括3个环节。个环节。1订货订货配送中心在收到和汇总客户的订单后，首先要确定需要配送的商品的种类和数量，配送中心在收到和汇总客户的订单后，首先要确定需要配送的商品的种类和数量，然后查询现有存货数量是否满足配送需要，当商品的库存量低于平安库存量时就需要然后查询现有存货数量是否满足配送需要，当商品的库存量低于平安库存量时就需要发出订货。配送中心也可以根据市场需求情况提前订货，以备发货。发出订货。配送中心也可以根据
17、市场需求情况提前订货，以备发货。2接货接货配送中心组织人力物力接收从客户发出的货物。配送中心组织人力物力接收从客户发出的货物。3验收入库验收入库货物到达配送中心，配送中心负责对货物进行验收，验收的标准通常是货物到达配送中心，配送中心负责对货物进行验收，验收的标准通常是按照订货合同或者订单的规定。验收的内容包括商品质量、数量、品名、规按照订货合同或者订单的规定。验收的内容包括商品质量、数量、品名、规格、外观和生产日期等几个方面。验收合格的货物办理录入信息和入库手续，格、外观和生产日期等几个方面。验收合格的货物办理录入信息和入库手续，对于与订单规定不符的货物或者有破损的货物，就需要做出适当的处理。
18、对于与订单规定不符的货物或者有破损的货物，就需要做出适当的处理。第十五页，共七十一页。3装卸搬运装卸搬运(bnyn)作业作业装卸装卸loading and unloading是指物品在指定地点进行的垂是指物品在指定地点进行的垂直移动为主的物流作业；直移动为主的物流作业； 搬运搬运handling/carrying是指在同一场所内将物品进行水平移动是指在同一场所内将物品进行水平移动为主的物流作业。为主的物流作业。第十六页，共七十一页。4存储作业存储作业存储作业应该充分有效地利用空间，尽可能提高人力资源及设备的存储作业应该充分有效地利用空间，尽可能提高人力资源及设备的利用率，有效地保护好商品的质量
19、和数量，维持良好的储存环境。利用率，有效地保护好商品的质量和数量，维持良好的储存环境。良好的存储策略可以提高存储效率，存储策略可以分为以下几种：良好的存储策略可以提高存储效率，存储策略可以分为以下几种：1定位存储定位存储定位存储是指每一类货物都有自己固定的储位，这种存储方法比较便于定位存储是指每一类货物都有自己固定的储位，这种存储方法比较便于管理，但缺点是需要较多的存储空间。管理，但缺点是需要较多的存储空间。2随机存储随机存储随机存储是指每一类货物的储位不是固定的，而是随机的。这种存储方法最随机存储是指每一类货物的储位不是固定的，而是随机的。这种存储方法最大限度地提高了仓库的空间利用率，但是给
20、货物的进出和盘点等工作带来了一定大限度地提高了仓库的空间利用率，但是给货物的进出和盘点等工作带来了一定(ydng)的困难。的困难。3分类存储分类存储分类存储是指按货物的相关性、流动性、尺寸和重量及货物的特性分类存储是指按货物的相关性、流动性、尺寸和重量及货物的特性对货物进行分类，对货物按类进行存储。对货物进行分类，对货物按类进行存储。第十七页，共七十一页。存储的方式主要有托盘堆垛方式和货架存储方式。1托盘堆垛方式托盘堆垛方式就是用叉车将满载货物的托盘直接放置(fngzh)到存储的位置，用叉车依次提升堆放。这种堆垛的方式完全采用叉车作业，减轻了人的体力劳动，但托盘上的货物必须堆码平整，让上面的托
21、盘能够平稳放置(fngzh)。2货架存储方式货架存储系统分为固定货架系统和旋转货架系统二种。高层固定货架一般分为几排，排与排之间设有一条巷道，供巷道堆垛机和叉车行驶作业。第十八页，共七十一页。 5拣货作业拣货作业是按照不同的顾客或不同的配送路线要求，使用各种是按照不同的顾客或不同的配送路线要求，使用各种( zhn)拣选设备拣选设备和传输装置，及时、准确、快速地按顾客要求从储存区域将物品拣出，并按和传输装置，及时、准确、快速地按顾客要求从储存区域将物品拣出，并按一定的方式进行分类和集中，送入指定的发货区。拣货可以分为人工分拣和一定的方式进行分类和集中，送入指定的发货区。拣货可以分为人工分拣和利用
22、自动分类机分拣二种。利用自动分类机分拣二种。6流通加工作业流通加工作业是指物品在从生产地到使用地的过程中，根据需要施加包装、分割、计是指物品在从生产地到使用地的过程中，根据需要施加包装、分割、计量、分拣、刷标志、拴标签、组装等简单作业的总称。量、分拣、刷标志、拴标签、组装等简单作业的总称。流通加工主要的目的是为了促进销售、维护产品质量和提高物流效流通加工主要的目的是为了促进销售、维护产品质量和提高物流效率，实现物流增值效劳。率，实现物流增值效劳。第十九页，共七十一页。 7补货作业补货作业是当拣货区的货物数量低于平安存量时，从存储区把货物运到是当拣货区的货物数量低于平安存量时，从存储区把货物运到
23、拣货区的作业。补货的形式有以下二种：拣货区的作业。补货的形式有以下二种：1批次补货批次补货每天或每批次拣货之前，先检查货物的库存量是否到达所需要每天或每批次拣货之前，先检查货物的库存量是否到达所需要的拣取量，假设数量缺乏，那么的拣取量，假设数量缺乏，那么(n me)在拣货之前一次性补足。在拣货之前一次性补足。2定时补货定时补货把每天分成几个时点，当拣货区的存货量小于设定标准时，立即进行把每天分成几个时点，当拣货区的存货量小于设定标准时，立即进行补货。补货。8配送作业配送作业是利用配送车辆把客户订购的物品从配送中心运送到客户的作业。配送作是利用配送车辆把客户订购的物品从配送中心运送到客户的作业。
24、配送作业要到达运送距离最短、时间最少、本钱最低业要到达运送距离最短、时间最少、本钱最低3个目标。个目标。第二十页，共七十一页。第三节第三节 配送路线优化设计配送路线优化设计(shj)(shj)一、配送网络结构一、配送网络结构 常用的配送网络结构有三大类，即集中型配送网络、单层次配送网络和多层次配送网络结构。第二十一页，共七十一页。1 1、集中型配送网络、集中型配送网络 集中型配送网络是指配送系统(xtng)中只设一个配送中心，所有货物首先要在配送中心集结，然后再根据客户需求进行配送供应商客户DC集中型配送网络第二十二页，共七十一页。2 2、单层次配送网络、单层次配送网络 单层次配送网络，也称分
25、散型配送网络，是配送单层次配送网络，也称分散型配送网络，是配送系统中在一个层次上设多个配送中心，供给商将货物系统中在一个层次上设多个配送中心，供给商将货物运送到不同的配送中心，然后再配送给用户。配送中运送到不同的配送中心，然后再配送给用户。配送中心是按照用户地理位置分布划分配送区域心是按照用户地理位置分布划分配送区域(qy)(qy)，即按，即按照客户就近原那么设立。照客户就近原那么设立。 供应商客户DC图3-3-3 单层次配送网络DC第二十三页，共七十一页。3 3、多层次配送网络、多层次配送网络 多层次配送网络是配送系统中在两个(lin )或两个(lin )以上层次上设多个配送中心，是集中型配
26、送网络与分散型配送网络于一体的一种网络结构。 供应商客户DC图3-3-4 多层次配送网络DCDC第二十四页，共七十一页。合理的运输合理的运输(ynsh)(ynsh)路线路线1 1 一辆运货车顺次途经各一辆运货车顺次途经各停车点的路线要呈凸状，或水点的路线要呈凸状，或水滴形，各条线路之间是不交叉的。滴形，各条线路之间是不交叉的。仓库库仓库二、典型二、典型(dinxng)(dinxng)不合理运输路线不合理运输路线第二十五页，共七十一页。DD合理的运输路线合理的运输路线2 2将相互(xingh)接近的停车点的货物装在一辆车上运送。 第二十六页，共七十一页。仓库仓库仓库仓库第二十七页，共七十一页。三
27、、城市配送运输决策三、城市配送运输决策1 1、城市配送运输常用、城市配送运输常用(chn yn)(chn yn)的决策方法的决策方法1 1TSPTSP行程安排决策行程安排决策2 2VRPVRP运输路线选择及行程安排决策运输路线选择及行程安排决策 第二十八页，共七十一页。1运输工具的类型运输工具的类型如普通卡车大、中、小型、厢式货车、冷藏车、集装箱货车等。如普通卡车大、中、小型、厢式货车、冷藏车、集装箱货车等。2运输工具的来源运输工具的来源一是自有，二是外协。一是自有，二是外协。外协的运输工具又可以分为两种，一是以前有长期协议的外协车辆外协的运输工具又可以分为两种，一是以前有长期协议的外协车辆(
28、chling)，二是临时租赁，二是临时租赁的车辆的车辆(chling)。前者，比方目前很多物流企业的运输车辆都是由司机自带的，物流企业也可以前者，比方目前很多物流企业的运输车辆都是由司机自带的，物流企业也可以和其他企业签订长期协议租赁车辆。这类外协车辆的使用性质与企业自有车辆和其他企业签订长期协议租赁车辆。这类外协车辆的使用性质与企业自有车辆相近，只是不拥有所有权。相近，只是不拥有所有权。3运输工具的数量运输工具的数量物流企业拥有一定规模的运输工具自有或合同外协，再根据业务规模到市场上物流企业拥有一定规模的运输工具自有或合同外协，再根据业务规模到市场上临时租赁车辆。有的物流效劳企业不拥有任何车
29、辆，承揽了运输业务后再去寻找运临时租赁车辆。有的物流效劳企业不拥有任何车辆，承揽了运输业务后再去寻找运输车辆。输车辆。2、运输工具选择、运输工具选择(xunz)第二十九页，共七十一页。案例案例YRCYRC国际国际(guj)(guj)物流企业在物流企业在中国的开展战略中国的开展战略第三十页，共七十一页。3、运输工具配载、运输工具配载(pi zi)与调度问题与调度问题 运输工具配载的根本原那么运输工具配载的根本原那么1 1将相互接近的停留点的货物装在一辆车上运送将相互接近的停留点的货物装在一辆车上运送(yn sn)(yn sn)。2 2优先使用大载重量的送货车辆，并将提货与送货过程结合进行。优先使
30、用大载重量的送货车辆，并将提货与送货过程结合进行。 3 3上轻下重上轻下重 即密度大的货物应装载在运输车辆的下面，轻泡的货物装即密度大的货物应装载在运输车辆的下面，轻泡的货物装载在上面。载在上面。4 4先远后近先远后近 远途的货物和后送的货物应先装载，近途的或先送的货物应远途的货物和后送的货物应先装载，近途的或先送的货物应后装载。后装载。第三十一页，共七十一页。课堂交流 针对(zhndu)运输物流管理课堂教学内容，写一篇论文PPT，字数不限，但应该符合论文要求应具有提出问题、分析问题、解决问题。第三十二页，共七十一页。四、四、 TSP TSP问题问题( (起点和终点起点和终点(zhngdin)
31、(zhngdin)相同的路径规划相同的路径规划) ) TSP TSP问题，即旅行商问题问题，即旅行商问题Traveling Traveling Salesman ProblemSalesman Problem又译为旅行推销员问题、货又译为旅行推销员问题、货郎担问题，是数学领域中著名问题之一。假设有郎担问题，是数学领域中著名问题之一。假设有一个旅行商人要拜访一个旅行商人要拜访n n个城市，他必须选择所要个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目而且最后要回到原来出发的城市。路径的选择目标
32、是要求得的路径路程为所有路径之中的最小值。标是要求得的路径路程为所有路径之中的最小值。 TSPTSP问题是一个组合优化问题。该问题可以被问题是一个组合优化问题。该问题可以被证明具有证明具有NPNP计算复杂性。计算复杂性。 中国邮递员问题中国邮递员问题 著名图论问题之一。邮递员从邮局出发送信，著名图论问题之一。邮递员从邮局出发送信，要求对辖区内每条街，都至少通过一次，再回邮局。要求对辖区内每条街，都至少通过一次，再回邮局。在此条件下，怎样选择一条最短路线在此条件下，怎样选择一条最短路线? ?此问题由中此问题由中国数学家管梅谷于国数学家管梅谷于19601960年首先研究并给出算法，故年首先研究并给
33、出算法，故名。名。 第三十三页，共七十一页。1、TSP问题的描述问题的描述p 基本的TSP模型描述如下：给出一个起点配送中心和一组n个客户的集合，寻找一条在起点配送中心开始和结束的路线，这条路线经过每一个消费者，并且是最短路，即p每一个车辆在配送中心起程和终止；p一条路线一次要包含所有需要服务的客户点的配送 ；p每一个客户点必须在预先设置的时间窗口内得到服务；p以行程最短为确定车辆路线行程的评价指标。 第三十四页，共七十一页。 TSP旅行商是在单回路运输问题。 单回路运输问题是指在路线优化中，存在节点集合D，选择一条适宜的路径(ljng)遍历所有的节点，并且要求闭合。单回路运输模型在运输决策中
34、，主要用于单一车辆的路径(ljng)安排。目的在于在该车辆遍历所有的用户的同时，到达所行驶距离最短。这类问题的两个显著特点是： 1单一性只有一个回路。 2遍历性不可遗漏。 第三十五页，共七十一页。 目标函数：以行程最短为确定车辆路线行程的评价指标。 物流配送路径优化常见的约束条件包括(boku)：车辆装载能力限制，停车点的工作时间约束，运行时间、不同区段的车速限制，运行途中的障碍物湖泊、山脉等、交通管制、司机的短时间休息等。 如果问题中包含送货点的个数很多，附加了许多约束条件，问题求解就变得十分复杂。 对这类问题的求解，往往采用的是启发式算法，以求得一个满意解近似解。2 2、TSPTSP问题问
35、题(wnt)(wnt)的数学模型的数学模型第三十六页，共七十一页。 TSP模型可以如下描述：在给出的一个n顶点网络（有向或无向），要求找出一个包含所有n个顶点的具有最小耗费的环路。TSP模型的数学描述为：设有连通图G，其定点集V，定点间的距离C = cij 1 i, j n 目标函数：约束条件：11mnijijijc xmin11,nijjx11mijixi=1,2,m j=1,2,n决策变量：0ijx 1ijx 从i到j无通路 从i到j有通路 第三十七页，共七十一页。五、五、VRPVRP问题问题 1 1、VRPVRP描述描述 在实际运输中，经常会遇到车辆在实际运输中，经常会遇到车辆受承载能力
36、、容积的限制，一辆车不能满足所受承载能力、容积的限制，一辆车不能满足所配送区域用户的需求。配送区域用户的需求。 多回路运输问题多回路运输问题Vehicle Vehicle Routing Problem, VRPRouting Problem, VRP，是对一系列客户的，是对一系列客户的需求点设计适当的路线，使车辆有序地通过它需求点设计适当的路线，使车辆有序地通过它们，在满足一定的约束条件下，如货物需求量、们，在满足一定的约束条件下，如货物需求量、发送量、交发货时间、车辆载重量限制、行驶发送量、交发货时间、车辆载重量限制、行驶里程限制、时间限制等等，到达一定的优化目里程限制、时间限制等等，到达
37、一定的优化目标，如里程最短、费用最少、时间最短，车队标，如里程最短、费用最少、时间最短，车队规模最少、车辆利用率高。规模最少、车辆利用率高。 VRP VRP问题和问题和TSPTSP问题的区别在于：客户问题的区别在于：客户群体的数量大，只有一辆车或一条路径满足不了群体的数量大，只有一辆车或一条路径满足不了(blio)(blio)客户的需求。相对于客户的需求。相对于TSPTSP问题，问题，VRPVRP问题更复杂，问题更复杂，求解更困难，但也更接近实际情况。求解更困难，但也更接近实际情况。第三十八页，共七十一页。典型的典型的VRPVRP可描述为：可描述为：1) 1) 多个客户同时需要运输效劳，且一辆
38、车不能同多个客户同时需要运输效劳，且一辆车不能同时满足这些客户的要求。时满足这些客户的要求。2 2每个客户只能被一辆车访问一次。每个客户只能被一辆车访问一次。3) 3) 所有所有(suyu)(suyu)车辆从仓库出发，并最终回到仓库。车辆从仓库出发，并最终回到仓库。4) 4) 所有的车辆必须满足能力约束。所有的车辆必须满足能力约束。5 5车辆在路线上可以取车辆在路线上可以取/ /送货。送货。第三十九页，共七十一页。2 2、VRPVRP图解根本原理图解根本原理VRPVRP是考虑车辆是考虑车辆(chling)(chling)的装载能力吨位或容积时，的装载能力吨位或容积时，对配送线路进行优化。对这一
39、类问题的求解可根本对配送线路进行优化。对这一类问题的求解可根本上分为两大步骤：上分为两大步骤：第一步根据客户地理位置和时间窗口将配送区域第一步根据客户地理位置和时间窗口将配送区域中的客户聚类，然后根据客户需求的数量和一中的客户聚类，然后根据客户需求的数量和一辆车的装载能力确定配送路线数量和配送车次；辆车的装载能力确定配送路线数量和配送车次；第二步在每一条路线上采用第二步在每一条路线上采用TSPTSP解决方法。解决方法。第四十页，共七十一页。案例：丁秋雷-系统工程理论(lln)与实践2007-10第四十一页，共七十一页。第四十二页，共七十一页。第四十三页，共七十一页。 TSP问题是物流配送业务中
40、的常见问题，在物流中的描述是对应一个物流配送公司，欲将n个客户的订货沿最短路线全部送到。如何确定最短路线。解决此类问题的目标是找出途中经过的点的顺序，使其经过所有送货点并满足各点对送货时间的要求，且总距离最短或总行驶时间。“旅行推销员TSP问题。TSP问题最简单的求解方法是枚举法。它的解是多维的、多局部极值的、趋于无穷大的复杂解的空间，搜索空间是n个点的所有排列的集合，大小(dxio)为n-1。可以形象地把解空间看成是一个无穷大的丘陵地带，各山峰或山谷的高度即是问题的极值。求解TSP，那么是在此不能穷尽的丘陵地带中攀登以到达山顶或谷底的过程。 旅行商问题Traveling Saleman Pr
41、oblem，TSP是VRP的特例，由于Gaery已证明TSP问题是NP难题，因此，VRP也属于NP难题。 随着问题中包含点个数和约束条件的增加，求解问题的复杂程度增加，要找到最优路径非常困难。即使用最快的计算机进行计算，求最优解的时间也非常长。启发式求解法是求解这类问题的好方法。 六、六、TSPTSP问题问题(wnt)(wnt)和和VRPVRP问题的求解算法问题的求解算法第四十四页，共七十一页。求解TSP模型时，如果要得到精确的最优解，最简单的方法也是枚举法。对于小规模问题，枚举法是一种有效的方法。但是对于大规模问题，由于枚举法的例举次数为n一1！次，这在实际操作中是很难实现的。整数规划的方法
42、用于解决局部TSP模型，其原理也是分枝定界法，该算法只能(zh nn)对一局部中小规模的问题进行求解，对于大多数问题的求解都存在一定的难度。第四十五页，共七十一页。组合(zh)爆炸例如，一台汽车每天要给20-30个不同的自动售货机补货。如果要访问20台机器的时候，其巡回路线就有20！2432902021176640000条巡回路线可供选择；如果要访问30台，就有30！265252859812191058636308480000000条巡回路线可供选择，利用现有计算机，假设一秒钟可以计算100亿条路线的距离的话，对于(duy)20台自动售货机的计算需要花费7年的时间，对于(duy)30台自动售货
43、机那么需要花费8411兆年的时间，这种现象称为“组合爆炸第四十六页，共七十一页。组合组合(zh)(zh)爆炸爆炸第四十七页，共七十一页。1 1、解决、解决VRPVRP问题的几种问题的几种(j zhn)(j zhn)传统启发式算法传统启发式算法第四十八页，共七十一页。 图解法的根本原理假设在每一次的配送中，客户的地理位置、配送数量、客户接受货物的时间窗口都是确定的。图解法就是将这些已有的信息在地图或GIS上标注，根据决策问题类型，采用一定的优化方法，将配送中心与客户连接(linji)在一起，进行配送路线优化设计的一种方法。由于是以地图或GIS为根本工具，故称此种方法为图解法。 第四十九页，共七十
44、一页。1 1解决解决VRPVRP问题的扫描法问题的扫描法问题：对于假设干个停车点客户安排最优问题：对于假设干个停车点客户安排最优行车路线。行车路线。第一步，将仓库出发点和所有的停车点位第一步，将仓库出发点和所有的停车点位置画在地图上或坐标图上；置画在地图上或坐标图上；第二步，通过仓库位置放置第二步，通过仓库位置放置(fngzh)(fngzh)一直尺，然一直尺，然后顺时针或逆时针方向转动直尺，直到直尺后顺时针或逆时针方向转动直尺，直到直尺交到一个停车点。询问：累计的装货量是否交到一个停车点。询问：累计的装货量是否超过送货的载重量或容积首先要使用最大超过送货的载重量或容积首先要使用最大的送货车辆。
45、如是，最后的停车点排除，的送货车辆。如是，最后的停车点排除，将路线确定下来。然后再从这个停车点开始将路线确定下来。然后再从这个停车点开始继续扫描，开始一条新的路线。这样扫描下继续扫描，开始一条新的路线。这样扫描下去，直至全部的停留点都被分配到路线上。去，直至全部的停留点都被分配到路线上。 第三步，对每条路线安排运行顺序，以求第三步，对每条路线安排运行顺序，以求运行距离最小化。运行距离最小化。方案的误差率在方案的误差率在10%10%左右。左右。第五十页，共七十一页。100030002000400030003000200020002000200020001000仓库图图5-13停留点提货量数据停留
46、点提货量数据例5-7 从各客户点提货，然后将货物运回仓库。全天的提货量见图5-13。送货车每次可运载10000件。要求确定：需多少条路线即多少辆送货车；每条路线上有哪几个客户点；送货车辆效劳有关(yugun)客户点的顺序。第五十一页，共七十一页。扫描法扫描法:手工计算。车的载货量是手工计算。车的载货量是10000件。需要多少条线件。需要多少条线路？每条线路上的站点如何排列？路？每条线路上的站点如何排列？D300030001000300020002000200020002000100020004000D30003000100030002000200020002000200010002000400
47、0第五十二页，共七十一页。 图3-3-14是客户为12个的配送网络，单车装载能力(nngl)为3个客户单位，用扫描法确定的配送线路数为4条。 第五十三页，共七十一页。2 2解决解决 VRP VRP 问题的最近插入法图解问题的最近插入法图解 最近的插入法是从企业仓库出发，选择与仓最近的插入法是从企业仓库出发，选择与仓库距离最近的客户要考虑时间窗口形成库距离最近的客户要考虑时间窗口形成一条配送线路，然后寻找与这条线路最近的一条配送线路，然后寻找与这条线路最近的客户点，并将其参加到原先的路线中，重新客户点，并将其参加到原先的路线中，重新(chngxn)(chngxn)形成一条配送线路；依次类推，直到
48、将形成一条配送线路；依次类推，直到将所有客户都加到配送路线上为止，形成一条所有客户都加到配送路线上为止，形成一条可行的配送路线。按照线路的合理判断准那可行的配送路线。按照线路的合理判断准那么，对可行配送路线进行合理化改进，就得么，对可行配送路线进行合理化改进，就得到一条优化的配送路线。到一条优化的配送路线。 第五十四页，共七十一页。 设企业车辆一次配送5个客户，客户接受货物时间无特别要求(yoqi)。企业配送中心用表示，客户用表示，配送中心与客户之间的相对距离如图3-3-7所示。第五十五页，共七十一页。第五十六页，共七十一页。第五十七页，共七十一页。3解决解决 VRP 问题问题(wnt)的节约
49、法的节约法 The Savings Method 利用里程节约法确定配送线路的主要出发点是，根据配送方的运输能力及其到客户之间的距离和各客户之间的相对距离，来制定使配送车辆(chling)总的运输本钱到达或接近最小的配送方案。第五十八页，共七十一页。节约算法用来解决(jiju)VRP问题节约算法Savings Algorithm是 Clarke和Wright在 1964年提出的，它是目前用来解决VRP模型最有名的启发式算法。节约算法可以解决运输车辆数目(shm)不确定运输车辆数目(shm)在VRP问题中是一个决策变量的VRP问题，这个算法对有向和无向问题同样有效。第五十九页，共七十一页。节约法
50、的原理节约法的原理初始路线初始路线线路里程线路里程BOOBAOOAdddd将两个站点合并到同一路线上的里将两个站点合并到同一路线上的里程程BOABOAddd节约的距离为 S=dAO+dOB-dABABOABO第六十页，共七十一页。节约节约(jiyu)法法1. 1. 选择企业配送中心作为起点，并记为选择企业配送中心作为起点，并记为 “0 “0. . 2. 2. 计算节约值计算节约值Sij = Ci0 + C0j - CijSij = Ci0 + C0j - Cij3. 3. 从最大到最小排序节约值从最大到最小排序节约值. .4. 4. 根据节约连接消费者形成路线根据节约连接消费者形成路线(lxi