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

第四章城市物流配送规划(guīhuà)与决策第一页，共七十一页。第四章城市物流配送规划(guīhuà)与决策第一页，共二、配送(pèisònɡ)类型第二页，共七十一页。二、配送(pèisònɡ)类型第二页，共七十一页。三、配送(pèisònɡ)模式第三页，共七十一页。三、配送(pèisònɡ)模式第三页，共七十一页。四、配送运输的根本流程1〕划分配送区域，根据客户地理分布情况和效劳时间窗口决定(juédìng)配送区域。2〕车辆配载，根据货物分类〔特性、轻重急缓〕，选择运输工具。3〕暂定配送先后顺序，根据客户的交货时间和位置。4〕车辆安排，考虑货物特征与数量、车辆吨位利用率和本钱费用等。5〕选择配送线路，根据交通状况、客户的具体位置、送货时间限制等作出安排。6〕确定最终的配送顺序，路线经过的客户数量、行程、到达与出发时间等。7〕完成车辆积载，货物装车、卸货等问题的解决，遵守“后送先装〞等原那么。第四页，共七十一页。四、配送运输的根本流程第四页，共七十一页。划分基本配送区域车辆配载车辆安排选择配送线路确定配送顺序完成车辆积载货物体积质量数量其他车辆体积额定载货量费用货物性质形状体积质量交通状况客户的具体位置送货时间限制客户分布地点货物特征客户的交货时间确定配送先后顺序（暂定）图3-3-1配送的基本作业流程第五页，共七十一页。划分基本配送区域车辆配载车辆安排选择配送线路确定配送顺序完成第二节配送中心(zhōngxīn)管理一、配送中心的定义

配送中心是从事配送业务的物流场所或组织，应根本符合以下要求：主要为特定的客户效劳；配送功能健全；有完善的信息网络；辐射范围小；多品种、小批量配送；以配送为主，储存为辅。配送中心是配送网络设计的核心，配送中心的层次、个数和地理位置是决定企业整体供给链绩效的关键。第六页，共七十一页。第二节配送中心(zhōngxīn)管理第六页，共七十一页二、按配送中心的经营主体分类〔1〕制造商型配送中心〔DistributionCenterbuiltbyMaker，MDC〕是由大型制造商建设的，专门效劳于制造企业的生产、销售活动。通过设立配送中心可以减少中间环节，降低企业产品销售的流通费用(liútōnɡfèiyònɡ)；提高企业的客户效劳水平。配送的产品种类有限且变化小，订货和进货作业比较单一，易于标准化和标准化。通常，家用电器、汽车、化装品和食品等厂商采用这种形式。〔2〕批发商型配送中心〔DistributionCenterbuiltbyWholesaler，WDC〕是由产品的批发商或代理商出资建设的，此类配送中心的运作方式是先向上游的厂商订货，然后将各种产品进行组合，再转卖给它的下游零售商。

第七页，共七十一页。第七页，共七十一页。〔3〕零售商型配送中心〔DistributionCenterbuiltbyRetailer，ReDC〕是由大型零售商建设的。零售企业在经营规模到达一定水平后，可以把来自不同进货者的货物在配送中心集中分拣、加工，然后按其所属的店铺进行方案配送。企业集中采购和集中运输可以获得规模效益，包括运输本钱的节省和采购价格的下降等。〔4〕第三方成立的配送中心〔DistributionCenterBuiltbyTrucker，TDC〕属于社会化的配送中心，是由专业的物流公司出资建设的，向货主企业提供配送效劳。通常具有较强的物流配送能力，在与货主企业签订物流效劳合同的根底上，代理企业开展物流配送业务，可以迅速地按照客户的要求(yāoqiú)将产品送到指定地点，可以充分发挥专业物流企业的整体优势，综合利用物流设施，提高物流配送效率。第八页，共七十一页。〔3〕零售商型配送中心〔DistributionCente三、根据配送中心的效劳范围分类〔1〕城市配送中心城市配送中心是以一个城市为配送效劳的范围，将商品直接送到零售商或消费者手中。城市配送中心主要采用公路运输方式，选择“多品种、小批量、多客户〞的配送方式。〔2〕区域配送中心区域配送中心是以较强的辐射(fúshè)能力和库存准备，向全省、全国、或国际范围的客户进行产品配送。这种配送中心的规模比较大，客户比较多，配送的批量也比较大。在通常情况下，区域配送中心的产品先运到城市配送中心，然后再从城市配送中心运到最终需求点上。第九页，共七十一页。三、根据配送中心的效劳范围分类第九页，共七十一页。四、根据配送中心的效劳功能分类〔1〕储存型配送中心重点强调的是配送中心的储存功能，在功能上与传统的仓库非常接近，通常具有较大规模的仓库和场地，具有较强的库存调节功能。〔2〕流通型配送中心重点强调的是配送中心的集运功能，作为产品集中和组合的场所，将同方向的、小批量的产品或原料集中起来，及时地分发到各客户指定的地点。特点是不设储存仓库，只设周转区，占地面积比较小。主要效劳对象是城市区域内的各连锁店铺，在地理位置上定位于(wèiyú)接近主要客户的地点。〔3〕加工型配送中心主要以流通加工为核心业务，根据客户提出的加工深度、尺寸、标准、数量等要求，将不同客户的商品集合后，经过加工再配送给各个客户；或者按照各个客户需要将大批量的商品进行细分，进行小件包装以及贴附标签、条形码等操作。加工型配送中心需要配置特定商品的加工处理设施、场地技术和人员。第十页，共七十一页。四、根据配送中心的效劳功能分类第十页，共七十一页。五、配送中心的根本功能配送中心是一个多功能、集约化的物流节点，它把收货验货、存储保管、装卸搬运、拣选、流通加工、配送、结算和信息处理，甚至订货等作业有机地结合在一起。〔1〕集散功能是指配送中心能够将分散在各个生产企业的产品集中到一起，经过分拣、配组等向多家客户进行配送。〔2〕储存功能是指配送中心配备相应的仓储设施设备和储存一定数量的货物(huòwù)，以满足市场的需要和流通加工、配送等环节的正常运转。配送中心的库存作为商品供需的缓冲区，能够满足不同消费者在不同时间段的个性化需求，这种集中储存可以大大降低库存总量，增加调控能力。

第十一页，共七十一页。五、配送中心的根本功能第十一页，共七十一页。〔3〕配组功能配组是指单个客户所需要的配售数量不能到达车辆的有效载运负荷时，就存在如何集中不同客户的配送货物，进行搭配装载以充分利用运能、运力的问题。通过配组可以提高送货水平及降低送货本钱。配组已成为配送中心与传统(chuántǒng)仓储企业的明显区别之一，也是配送中心最重要的特征之一。〔4〕流通加工功能是指物品在从生产地到使用地的流通过程中，根据客户提出的要求和根据合理配送商品的原那么对物品施加包装、分割、计量、分拣、刷标志、拴标签、组装等简单作业的总称。

〔5〕分拣功能每个客户的订单都至少包含一项以上的商品，这些不同种类的商品需要由配送中心选出并集中在一起。分拣就是将一批相同或不同的货物，按照客户不同的要求拣选后集中在一起进行配送。第十二页，共七十一页。〔3〕配组功能第十二页，共七十一页。〔6〕配送功能配送就是按客户的订货要求，在配送中心进行分货、配货作业，并将配好的商品送交收货人。与运输相比，配送要求完全按照客户对商品种类、规格、数量、时间和地点(dìdiǎn)的要求，进行分拣、配货、集装、车辆调度、路线安排的优化等一系列的工作，再运送给客户的一种特殊的送货形式。〔7〕信息整合功能配送中心的信息系统将各种作业环节的信息进行实时采集、分析、传递，为配送中心的经营管理、政策制定等提供有用的信息，有效地为整个流通过程的控制、决策和运转提供依据。〔8〕资源回收功能是指回收及处理作业过程中产生的许多可回收资源，如拆箱更换包装后的纸箱等。第十三页，共七十一页。〔6〕配送功能第十三页，共七十一页。六、配送中心作业管理配送中心的根本作业包括如下内容：订单处理、进货作业、搬运作业、存储(cúnchǔ)作业、拣货作业、流通加工作业、补货作业和配送作业。1．订单处理订单处理通常指由接到客户订单开始到准备拣货之间的作业，主要工作包括：客户订单的数据确认、存货查询、订单整理与编号及订单出货数据处理等。具体内容包括：〔1〕接受订单〔2〕订单数据处理〔3〕订单状况管理第十四页，共七十一页。六、配送中心作业管理第十四页，共七十一页。2．进货作业是指从确认客户订单(dìnɡdān)，发出订货，从运输工具上把货物卸下，核对单据与实物数量、检查包装及产品质量，并办理入库手续等作业，主要包括3个环节。〔1〕订货配送中心在收到和汇总客户的订单后，首先要确定需要配送的商品的种类和数量，然后查询现有存货数量是否满足配送需要，当商品的库存量低于平安库存量时就需要发出订货。配送中心也可以根据市场需求情况提前订货，以备发货。〔2〕接货配送中心组织人力物力接收从客户发出的货物。〔3〕验收入库货物到达配送中心，配送中心负责对货物进行验收，验收的标准通常是按照订货合同或者订单的规定。验收的内容包括商品质量、数量、品名、规格、外观和生产日期等几个方面。验收合格的货物办理录入信息和入库手续，对于与订单规定不符的货物或者有破损的货物，就需要做出适当的处理。第十五页，共七十一页。2．进货作业第十五页，共七十一页。3．装卸搬运(bānyùn)作业装卸〔loadingandunloading〕是指物品在指定地点进行的垂直移动为主的物流作业；搬运〔handling/carrying〕是指在同一场所内将物品进行水平移动为主的物流作业。第十六页，共七十一页。3．装卸搬运(bānyùn)作业第十六页，共七十一页。4．存储作业存储作业应该充分有效地利用空间，尽可能提高人力资源及设备的利用率，有效地保护好商品的质量和数量，维持良好的储存环境。良好的存储策略可以提高存储效率，存储策略可以分为以下几种：〔1〕定位存储定位存储是指每一类货物都有自己固定的储位，这种存储方法比较便于管理，但缺点是需要较多的存储空间。〔2〕随机存储随机存储是指每一类货物的储位不是固定的，而是随机的。这种存储方法最大限度地提高了仓库的空间利用率，但是给货物的进出和盘点等工作带来了一定(yīdìng)的困难。〔3〕分类存储分类存储是指按货物的相关性、流动性、尺寸和重量及货物的特性对货物进行分类，对货物按类进行存储。第十七页，共七十一页。4．存储作业第十七页，共七十一页。存储的方式主要有托盘堆垛方式和货架存储方式。〔1〕托盘堆垛方式托盘堆垛方式就是用叉车将满载货物的托盘直接放置(fàngzhì)到存储的位置，用叉车依次提升堆放。这种堆垛的方式完全采用叉车作业，减轻了人的体力劳动，但托盘上的货物必须堆码平整，让上面的托盘能够平稳放置(fàngzhì)。〔2〕货架存储方式货架存储系统分为固定货架系统和旋转货架系统二种。高层固定货架一般分为几排，排与排之间设有一条巷道，供巷道堆垛机和叉车行驶作业。第十八页，共七十一页。存储的方式主要有托盘堆垛方式和货架存储方式。第十八页，共七5．拣货作业是按照不同的顾客或不同的配送路线要求，使用各种(ɡèzhǒnɡ)拣选设备和传输装置，及时、准确、快速地按顾客要求从储存区域将物品拣出，并按一定的方式进行分类和集中，送入指定的发货区。拣货可以分为人工分拣和利用自动分类机分拣二种。6．流通加工作业是指物品在从生产地到使用地的过程中，根据需要施加包装、分割、计量、分拣、刷标志、拴标签、组装等简单作业的总称。流通加工主要的目的是为了促进销售、维护产品质量和提高物流效率，实现物流增值效劳。

第十九页，共七十一页。5．拣货作业第十九页，共七十一页。7．补货作业是当拣货区的货物数量低于平安存量时，从存储区把货物运到拣货区的作业。补货的形式有以下二种：〔1〕批次补货每天或每批次拣货之前，先检查货物的库存量是否到达所需要的拣取量，假设数量缺乏，那么(nàme)在拣货之前一次性补足。〔2〕定时补货把每天分成几个时点，当拣货区的存货量小于设定标准时，立即进行补货。8．配送作业是利用配送车辆把客户订购的物品从配送中心运送到客户的作业。配送作业要到达运送距离最短、时间最少、本钱最低3个目标。第二十页，共七十一页。7．补货作业第二十页，共七十一页。第三节配送路线优化设计(shèjì)一、配送网络结构常用的配送网络结构有三大类，即集中型配送网络、单层次配送网络和多层次配送网络结构。第二十一页，共七十一页。第三节配送路线优化设计(shèjì)第二十一页，共七十一1、集中型配送网络集中型配送网络是指配送系统(xìtǒng)中只设一个配送中心，所有货物首先要在配送中心集结，然后再根据客户需求进行配送供应商客户DC集中型配送网络第二十二页，共七十一页。1、集中型配送网络供应商客户DC集中型配送网络第二十二页，共2、单层次配送网络单层次配送网络，也称分散型配送网络，是配送系统中在一个层次上设多个配送中心，供给商将货物运送到不同的配送中心，然后再配送给用户。配送中心是按照用户地理位置分布划分配送区域(qūyù)，即按照客户就近原那么设立。供应商客户DC图3-3-3单层次配送网络DC第二十三页，共七十一页。2、单层次配送网络供应商客户DC图3-3-3单层次配送网络3、多层次配送网络

多层次配送网络是配送系统中在两个(liǎnɡɡè)或两个(liǎnɡɡè)以上层次上设多个配送中心，是集中型配送网络与分散型配送网络于一体的一种网络结构。

供应商客户DC图3-3-4多层次配送网络DCDC第二十四页，共七十一页。3、多层次配送网络供应商客户DC图3-3-4多层次配送网络合理的运输(yùnshū)路线1一辆运货车顺次途经各停车点的路线要呈凸状，或水滴形，各条线路之间是不交叉的。仓库库仓库二、典型(diǎnxíng)不合理运输路线第二十五页，共七十一页。合理的运输(yùnshū)路线1仓库库仓库二、典型(diǎnDD合理的运输路线2将相互(xiānghù)接近的停车点的货物装在一辆车上运送。

第二十六页，共七十一页。DD合理的运输路线2第二十六页，共七十一页。仓库仓库第二十七页，共七十一页。仓库仓库第二十七页，共七十一页。三、城市配送运输决策1、城市配送运输常用(chánɡyònɡ)的决策方法〔1〕TSP行程安排决策〔2〕VRP运输路线选择及行程安排决策

第二十八页，共七十一页。三、城市配送运输决策第二十八页，共七十一页。〔1〕运输工具的类型如普通卡车〔大、中、小型〕、厢式货车、冷藏车、集装箱货车等。〔2〕运输工具的来源一是自有，二是外协。外协的运输工具又可以分为两种，一是以前有长期协议的外协车辆(chēliàng)，二是临时租赁的车辆(chēliàng)。前者，比方目前很多物流企业的运输车辆都是由司机自带的，物流企业也可以和其他企业签订长期协议租赁车辆。这类外协车辆的使用性质与企业自有车辆相近，只是不拥有所有权。〔3〕运输工具的数量物流企业拥有一定规模的运输工具〔自有或合同外协〕，再根据业务规模到市场上临时租赁车辆。有的物流效劳企业不拥有任何车辆，承揽了运输业务后再去寻找运输车辆。2、运输工具选择(xuǎnzé)第二十九页，共七十一页。〔1〕运输工具的类型2、运输工具选择(xuǎnzé)第二十九案例YRC国际(guójì)物流企业在中国的开展战略第三十页，共七十一页。案例第三十页，共七十一页。3、运输工具配载(pèizǎi)与调度问题运输工具配载的根本原那么〔1〕将相互接近的停留点的货物装在一辆车上运送(yùnsònɡ)。〔2〕优先使用大载重量的送货车辆，并将提货与送货过程结合进行。〔3〕上轻下重即密度大的货物应装载在运输车辆的下面，轻泡的货物装载在上面。〔4〕先远后近远途的货物和后送的货物应先装载，近途的或先送的货物应后装载。第三十一页，共七十一页。3、运输工具配载(pèizǎi)与调度问题运输工具配载的课堂交流针对(zhēnduì)运输物流管理课堂教学内容，写一篇论文PPT，字数不限，但应该符合论文要求〔应具有提出问题、分析问题、解决问题〕。第三十二页，共七十一页。课堂交流第三十二页，共七十一页。四、TSP问题(起点和终点(zhōngdiǎn)相同的路径规划)TSP问题，即旅行商问题〔TravelingSalesmanProblem〕又译为旅行推销员问题、货郎担问题，是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。TSP问题是一个组合优化问题。该问题可以被证明具有NP计算复杂性。中国邮递员问题著名图论问题之一。邮递员从邮局出发送信，要求对辖区内每条街，都至少通过一次，再回邮局。在此条件下，怎样选择一条最短路线?此问题由中国数学家管梅谷于1960年首先研究并给出算法，故名。第三十三页，共七十一页。四、TSP问题(起点和终点(zhōngdiǎn)相同的路径1、TSP问题的描述基本的TSP模型描述如下：给出一个起点配送中心和一组n个客户的集合，寻找一条在起点配送中心开始和结束的路线，这条路线经过每一个消费者，并且是最短路，即每一个车辆在配送中心起程和终止；一条路线一次要包含所有需要服务的客户点的配送；每一个客户点必须在预先设置的时间窗口内得到服务；以行程最短为确定车辆路线行程的评价指标。

第三十四页，共七十一页。1、TSP问题的描述即第三十四页，共七十一页。TSP旅行商是在单回路运输〕问题。单回路运输问题是指在路线优化中，存在节点集合D，选择一条适宜的路径(lùjìng)遍历所有的节点，并且要求闭合。单回路运输模型在运输决策中，主要用于单一车辆的路径(lùjìng)安排。目的在于在该车辆遍历所有的用户的同时，到达所行驶距离最短。这类问题的两个显著特点是：〔1〕单一性〔只有一个回路〕。〔2〕遍历性〔不可遗漏〕。第三十五页，共七十一页。TSP旅行商是在单回路运输〕问题。第三十五页目标函数：以行程最短为确定车辆路线行程的评价指标。物流配送路径优化常见的约束条件包括(bāokuò)：车辆装载能力限制，停车点的工作时间约束，运行时间、不同区段的车速限制，运行途中的障碍物〔湖泊、山脉等、交通管制〕、司机的短时间休息等。如果问题中包含送货点的个数很多，附加了许多约束条件，问题求解就变得十分复杂。对这类问题的求解，往往采用的是启发式算法，以求得一个满意解〔近似解〕。2、TSP问题(wèntí)的数学模型第三十六页，共七十一页。目标函数：以行程最短为确定车辆路线行程的评价指标。2TSP模型可以如下描述：在给出的一个n顶点网络（有向或无向），要求找出一个包含所有n个顶点的具有最小耗费的环路。TSP模型的数学描述为：设有连通图G，其定点集V，定点间的距离C=cij1≤i,j≤n目标函数：约束条件：mini=1,2,…,m

j=1,2,…,n决策变量：从i到j无通路

从i到j有通路

第三十七页，共七十一页。TSP模型可以如下描述：在给出的一个n顶点网五、VRP问题1、VRP描述在实际运输中，经常会遇到车辆受承载能力、容积的限制，一辆车不能满足所配送区域用户的需求。多回路运输问题〔VehicleRoutingProblem,VRP〕，是对一系列客户的需求点设计适当的路线，使车辆有序地通过它们，在满足一定的约束条件下，如货物需求量、发送量、交发货时间、车辆载重量限制、行驶里程限制、时间限制等等，到达一定的优化目标，如里程最短、费用最少、时间最短，车队规模最少、车辆利用率高。VRP问题和TSP问题的区别在于：客户群体的数量大，只有一辆车或一条路径满足不了(bùliǎo)客户的需求。相对于TSP问题，VRP问题更复杂，求解更困难，但也更接近实际情况。第三十八页，共七十一页。五、VRP问题第三十八页，共七十一页。典型的VRP可描述为：1)多个客户同时需要运输效劳，且一辆车不能同时满足这些客户的要求。2〕每个客户只能被一辆车访问一次。3)所有(suǒyǒu)车辆从仓库出发，并最终回到仓库。4)所有的车辆必须满足能力约束。5〕车辆在路线上可以取/送货。第三十九页，共七十一页。典型的VRP可描述为：第三十九页，共七十一页。2、VRP图解根本原理VRP是考虑车辆(chēliàng)的装载能力〔吨位或容积〕时，对配送线路进行优化。对这一类问题的求解可根本上分为两大步骤：第一步根据客户地理位置和时间窗口将配送区域中的客户聚类，然后根据客户需求的数量和一辆车的装载能力确定配送路线数量和配送车次；第二步在每一条路线上采用TSP解决方法。第四十页，共七十一页。2、VRP图解根本原理第四十页，共七十一页。案例：丁秋雷-系统工程理论(lǐlùn)与实践2007-10第四十一页，共七十一页。案例：丁秋雷-系统工程理论(lǐlùn)与实践2007-10第四十二页，共七十一页。第四十二页，共七十一页。第四十三页，共七十一页。第四十三页，共七十一页。TSP问题是物流配送业务中的常见问题，在物流中的描述是对应一个物流配送公司，欲将n个客户的订货沿最短路线全部送到。如何确定最短路线。解决此类问题的目标是找出途中经过的点的顺序，使其经过所有送货点并满足各点对送货时间的要求，且总距离最短或总行驶时间。——“旅行推销员〔TSP〕〞问题。TSP问题最简单的求解方法是枚举法。它的解是多维的、多局部极值的、趋于无穷大的复杂解的空间，搜索空间是n个点的所有排列的集合，大小(dàxiǎo)为〔n-1〕。可以形象地把解空间看成是一个无穷大的丘陵地带，各山峰或山谷的高度即是问题的极值。求解TSP，那么是在此不能穷尽的丘陵地带中攀登以到达山顶或谷底的过程。旅行商问题〔TravelingSalemanProblem，TSP〕是VRP的特例，由于Gaery已证明TSP问题是NP难题，因此，VRP也属于NP难题。随着问题中包含点个数和约束条件的增加，求解问题的复杂程度增加，要找到最优路径非常困难。即使用最快的计算机进行计算，求最优解的时间也非常长。启发式求解法是求解这类问题的好方法。六、TSP问题(wèntí)和VRP问题的求解算法第四十四页，共七十一页。TSP问题是物流配送业务中的常见问题，在物流中的描述是对求解TSP模型时，如果要得到精确的最优解，最简单的方法也是枚举法。对于小规模问题，枚举法是一种有效的方法。但是对于大规模问题，由于枚举法的例举次数为〔n一1〕！次，这在实际操作中是很难实现的。整数规划的方法用于解决局部TSP模型，其原理也是分枝定界法，该算法只能(zhīnénɡ)对一局部中小规模的问题进行求解，对于大多数问题的求解都存在一定的难度。第四十五页，共七十一页。求解TSP模型时，如果要得到精确的最优解，最简单的方法也是枚组合(zǔhé)爆炸例如，一台汽车每天要给20-30个不同的自动售货机补货。如果要访问20台机器的时候，其巡回路线就有20！＝2432902021176640000条巡回路线可供选择；如果要访问30台，就有30！＝265252859812191058636308480000000条巡回路线可供选择，利用现有计算机，假设一秒钟可以计算100亿条路线的距离的话，对于(duìyú)20台自动售货机的计算需要花费7年的时间，对于(duìyú)30台自动售货机那么需要花费8411兆年的时间，这种现象称为“组合爆炸〞第四十六页，共七十一页。组合(zǔhé)爆炸例如，一台汽车每天要给20-30个不同的组合(zǔhé)爆炸第四十七页，共七十一页。组合(zǔhé)爆炸第四十七页，共七十一页。1、解决VRP问题的几种(jǐzhǒnɡ)〔传统〕启发式算法第四十八页，共七十一页。1、解决VRP问题的几种(jǐzhǒnɡ)〔传统〕启发式算

图解法的根本原理假设在每一次的配送中，客户的地理位置、配送数量、客户接受货物的时间窗口都是确定的。图解法就是将这些已有的信息在地图或GIS上标注，根据决策问题类型，采用一定的优化方法，将配送中心与客户连接(liánjiē)在一起，进行配送路线优化设计的一种方法。由于是以地图或GIS为根本工具，故称此种方法为图解法。第四十九页，共七十一页。第四十九页，共七十一页。〔1〕解决VRP问题的扫描法问题：对于假设干个停车点〔客户〕安排最优行车路线。第一步，将仓库〔出发点〕和所有的停车点位置画在地图上或坐标图上；第二步，通过仓库位置放置(fàngzhì)一直尺，然后顺时针或逆时针方向转动直尺，直到直尺交到一个停车点。询问：累计的装货量是否超过送货的载重量或容积〔首先要使用最大的送货车辆〕。如是，最后的停车点排除，将路线确定下来。然后再从这个停车点开始继续扫描，开始一条新的路线。这样扫描下去，直至全部的停留点都被分配到路线上。第三步，对每条路线安排运行顺序，以求运行距离最小化。方案的误差率在10%左右。第五十页，共七十一页。〔1〕解决VRP问题的扫描法第五十页，共七十一页。100030002000400030003000200020002000200020001000仓库图5-13停留点提货量数据例5-7从各客户点提货，然后将货物运回仓库。全天的提货量见图5-13。送货车每次可运载10000件。要求确定：需多少条路线〔即多少辆送货车〕；每条路线上有哪几个客户点；送货车辆效劳有关(yǒuguān)客户点的顺序。第五十一页，共七十一页。100030002000400030003000200020

扫描法:手工计算。车的载货量是10000件。需要多少条线路？每条线路上的站点如何排列？D300030001000300020002000200020002000100020004000D300030001000300020002000200020002000100020004000第五十二页，共七十一页。扫描法:手工计算。车的载货量是10000件。需要多少条线图3-3-14是客户为12个的配送网络，单车装载能力(nénglì)为3个客户单位，用扫描法确定的配送线路数为4条。

第五十三页，共七十一页。图3-3-14是客户为12个的配送网络，单车装载能力(〔2〕解决VRP问题的最近插入法图解

最近的插入法是从企业仓库出发，选择与仓库距离最近的客户〔要考虑时间窗口〕形成一条配送线路，然后寻找与这条线路最近的客户点，并将其参加到原先的路线中，重新(chóngxīn)形成一条配送线路；依次类推，直到将所有客户都加到配送路线上为止，形成一条可行的配送路线。按照线路的合理判断准那么，对可行配送路线进行合理化改进，就得到一条优化的配送路线。第五十四页，共七十一页。〔2〕解决VRP问题的最近插入法图解第五十四页，共七十一设企业车辆一次配送5个客户，客户接受货物时间无特别要求(yāoqiú)。企业配送中心用■表示，客户用●表示，配送中心与客户之间的相对距离如图3-3-7所示。第五十五页，共七十一页。第五十五页，共七十一页。第五十六页，共七十一页。第五十六页，共七十一页。第五十七页，共七十一页。第五十七页，共七十一页。〔3〕解决VRP问题(wèntí)的节约法〔TheSavingsMethod〕利用里程节约法确定配送线路的主要出发点是，根据配送方的运输能力及其到客户之间的距离和各客户之间的相对距离，来制定使配送车辆(chēliàng)总的运输本钱到达或接近最小的配送方案。第五十八页，共七十一页。〔3〕解决VRP问题(wèntí)的节约法利用里程节约算法用来解决(jiějué)VRP问题节约算法〔SavingsAlgorithm〕是Clarke和Wright在1964年提出的，它是目前用来解决VRP模型最有名的启发式算法。节约算法可以解决运输车辆数目(shùmù)不确定〔运输车辆数目(shùmù)在VRP问题中是一个决策变量〕的VRP问题，这个算法对有向和无向问题同样有效。第五十九页，共七十一页。节约算法用来解决(jiějué)VRP问题节约算法〔Savi节约法的原理初始路线——线路里程将两个站点合并到同一路线上的里程节约的距离为S=dAO+dOB-dABABOABO第六十页，共七十一页。节约法的原理初始路线——线路里程将两个站点合并到同一路线上的节约(jiéyuē)法1.选择企业配送中心作为起点，并记为“0〞.

2.计算节约值Sij=Ci0+C0j-Cij3.从最大到最小排序节约值.4.根据节约连接消费者形成路线(lùxiàn). -不要破坏先前连接的任何连线. -当所有消费者连接在一条路线上时，停止.第六十一页，共七十一页。节约(jiéyuē)法1.选择企业配送中心作为起点，并记为节约算法用来解决VRP问题(wèntí)的步骤

一、计算相互之间的最短距离二、计算各个用户之间的节约里程三、对节约里程进行(jìnxíng)排序四、连线、形成配送线路第六十二页，共七十一页。节约算法用来解决VRP问题(wèntí)的步骤

第六十二页，把节约量从大到小的顺序依次把客户连成一条回路，直到整个回路各个用户的需求量之和不超过(chāoguò)这辆载重车的载重量，就组成了一条节约量最大的配送回路，派出一辆车。然后再在剩下的用户中同样按节约量从大到小的顺序继续组织配送回路，派出车辆，这样下去一直到所有的用户都组织完毕为止，就做完了一个完整的配送方案。第六十三页，共七十一页。把节约量从大到小的顺序依次把客户连成一条回路，直到整个回路各节约算法案例例如，某月某日，长江(chánɡjiānɡ)物流公司接受的武汉某商场给武汉市十个用户送货的任务单，多个品种运量共80吨，各个用户的需求量如表，各点之间的路程如图7－5所示。公司现有十吨车二辆、5吨车假设干辆。需要制定配送方案。第六十四页，共七十一页。节约算法案例第六十四页，共七十一页。表7－5各个用户之间的路程(lùchéng)〔路程(lùchéng)单位：公里〕制定(zhìdìng)配送方案的第一步，首先按排直送，把大运量用户先用专车直送，剩下的小运量用户再统一安排配送。由图7－5可以看出，物流中心A到用户P1的路程仅10公里，可以由一辆10吨车来回运送4次，一天可以完成。剩下的20吨加上的10吨可以由另一辆10吨车运送3次。派一辆10吨车专为P1用户来回(láihuí)运送四趟，每趟运10吨，来回(láihuí)算20公里。工作量为：10吨＊20公里＊4＝800吨公里。第二辆10吨车专为P1送20吨，为P2送10吨，来回运三次。其工作量为：10吨＊20公里＊2+10吨＊12公里＊2＝640吨公里。把这些大运量用户直送安排完后，P2还剩下2吨，其余小运量用户再安排配送，制定配送方案。第六十五页，共七十一页。表7－5各个用户之间的路程(lùchéng)〔路程(lùch2、解决VRP问题(wèntí)的几种智能〔启发式〕算法第六十六页，共七十一页。2、解决VRP问题(wèntí)的几种智能〔启发式〕算法第六

邮递员每次要走遍他所负责街区的每一条道路，投递完毕后仍须回到邮局，他应走什么路线才能使总路程最短。这个问题是由我国山东师范学院管梅谷教授在1962年首次提出的，所以国际(guójì)上通称为中国邮递员问题。

中国邮递员问题可以抽象为一个连通图，每个边都有一个非负权数，试求一个圈，过每边至少一次，并使圈的总权数最小。

六、中国(zhōnɡɡuó)邮递员问题第六十七页，共七十一页。

邮递员每次要走遍他所负责街区的每一条道路，投递完毕后仍须回定义：给一个连通多重图G，假设存在一条链〔圈〕过每边一次且仅一次，那么称这条链〔圈〕为欧拉链〔圈〕。

定义：一个图如果存在欧拉圈，那么称之为欧拉图。

显然，一个图假设能一笔不重复地画出，那么这个图就是欧拉图或含有欧拉链。

定理：连通多重图G是欧拉图，当且仅当图中无奇点。这个定理的结论是显然的，因为欧拉图从某一点(yīdiǎn)出发又回到原来的出发点，这就要求与每个顶点相关联的边数应是偶数，从而才能保证从一条边进入该点，从与该点相关联的另一条边出去。第六十八页，共七十一页。定义：给一个连通多重图G，假设存在一条链〔圈〕过每边一次且仅

欧拉图问题起源与著名的哥尼斯堡七桥问题，它的实质是如何判断一个连通图能否一笔不重复地画出。这个问题是由大数学家欧拉解决(jiějué)的，所以称为欧拉图问题。推论：连通多重图G有欧拉链，当且仅当G恰有两个奇点。上面的定理和推论提供了识别一个图能否一笔不重复画出的简单方法。如以下图，有两个奇点，所以能一笔不重复地画出，从奇点V2开始一笔画到奇点V5。第六十九页，共七十一页。

欧拉图问题起源与著名的哥尼斯堡七桥问题，它的实质是如何判断解此问题的根本思路是：假设街区路无奇点，显然按欧拉图定理可以不重复地走遍所有街道回到出发位置。如果图中有奇点，每边只走一次又回到出发点是不可能的。如果要回到原地就得走些重复路，也就是在原来(yuánlái)的街区图上添加一些边，使有奇点的图转换成无奇点的图。由于我们要求总权数最小，所以必须寻找使新增加的边的总权数最小的方案。我们称增加重复边使图中无奇点的方案为可行方案，称总权数最小的方案为最优方案。

详细解法请参阅?运筹学?，清华大学出版社第七十页，共七十一页。解此问题的根本思路是：假设街区路无奇点，显然按欧拉图定理可以内容(nèiróng)总结第四章城市物流配送规划与决策。kevin。物流企业拥有一定规模(guīmó)的运输工具〔自有或合同外协〕，再根据业务规模(guīmó)到市场上临时租赁车辆。以行程最短为确定车辆路线行程的评价指标。目标函数：以行程最短为确定车辆路线行程的评价指标。要求确定：需多少条路线〔即多少辆送货车〕。初始路线——线路里程。3.从最大到最小排序节约值.。4.根据节约连接消费者形成路线.。推论：连通多重图G有欧拉链，当且仅当G恰有两个奇点第七十一页，共七十一页。内容(nèiróng)总结第四章城市物流配送规划与决策第四章城市物流配送规划(guīhuà)与决策第一页，共七十一页。第四章城市物流配送规划(guīhuà)与决策第一页，共二、配送(pèisònɡ)类型第二页，共七十一页。二、配送(pèisònɡ)类型第二页，共七十一页。三、配送(pèisònɡ)模式第三页，共七十一页。三、配送(pèisònɡ)模式第三页，共七十一页。四、配送运输的根本流程1〕划分配送区域，根据客户地理分布情况和效劳时间窗口决定(juédìng)配送区域。2〕车辆配载，根据货物分类〔特性、轻重急缓〕，选择运输工具。3〕暂定配送先后顺序，根据客户的交货时间和位置。4〕车辆安排，考虑货物特征与数量、车辆吨位利用率和本钱费用等。5〕选择配送线路，根据交通状况、客户的具体位置、送货时间限制等作出安排。6〕确定最终的配送顺序，路线经过的客户数量、行程、到达与出发时间等。7〕完成车辆积载，货物装车、卸货等问题的解决，遵守“后送先装〞等原那么。第四页，共七十一页。四、配送运输的根本流程第四页，共七十一页。划分基本配送区域车辆配载车辆安排选择配送线路确定配送顺序完成车辆积载货物体积质量数量其他车辆体积额定载货量费用货物性质形状体积质量交通状况客户的具体位置送货时间限制客户分布地点货物特征客户的交货时间确定配送先后顺序（暂定）图3-3-1配送的基本作业流程第五页，共七十一页。划分基本配送区域车辆配载车辆安排选择配送线路确定配送顺序完成第二节配送中心(zhōngxīn)管理一、配送中心的定义

配送中心是从事配送业务的物流场所或组织，应根本符合以下要求：主要为特定的客户效劳；配送功能健全；有完善的信息网络；辐射范围小；多品种、小批量配送；以配送为主，储存为辅。配送中心是配送网络设计的核心，配送中心的层次、个数和地理位置是决定企业整体供给链绩效的关键。第六页，共七十一页。第二节配送中心(zhōngxīn)管理第六页，共七十一页二、按配送中心的经营主体分类〔1〕制造商型配送中心〔DistributionCenterbuiltbyMaker，MDC〕是由大型制造商建设的，专门效劳于制造企业的生产、销售活动。通过设立配送中心可以减少中间环节，降低企业产品销售的流通费用(liútōnɡfèiyònɡ)；提高企业的客户效劳水平。配送的产品种类有限且变化小，订货和进货作业比较单一，易于标准化和标准化。通常，家用电器、汽车、化装品和食品等厂商采用这种形式。〔2〕批发商型配送中心〔DistributionCenterbuiltbyWholesaler，WDC〕是由产品的批发商或代理商出资建设的，此类配送中心的运作方式是先向上游的厂商订货，然后将各种产品进行组合，再转卖给它的下游零售商。

第七页，共七十一页。第七页，共七十一页。〔3〕零售商型配送中心〔DistributionCenterbuiltbyRetailer，ReDC〕是由大型零售商建设的。零售企业在经营规模到达一定水平后，可以把来自不同进货者的货物在配送中心集中分拣、加工，然后按其所属的店铺进行方案配送。企业集中采购和集中运输可以获得规模效益，包括运输本钱的节省和采购价格的下降等。〔4〕第三方成立的配送中心〔DistributionCenterBuiltbyTrucker，TDC〕属于社会化的配送中心，是由专业的物流公司出资建设的，向货主企业提供配送效劳。通常具有较强的物流配送能力，在与货主企业签订物流效劳合同的根底上，代理企业开展物流配送业务，可以迅速地按照客户的要求(yāoqiú)将产品送到指定地点，可以充分发挥专业物流企业的整体优势，综合利用物流设施，提高物流配送效率。第八页，共七十一页。〔3〕零售商型配送中心〔DistributionCente三、根据配送中心的效劳范围分类〔1〕城市配送中心城市配送中心是以一个城市为配送效劳的范围，将商品直接送到零售商或消费者手中。城市配送中心主要采用公路运输方式，选择“多品种、小批量、多客户〞的配送方式。〔2〕区域配送中心区域配送中心是以较强的辐射(fúshè)能力和库存准备，向全省、全国、或国际范围的客户进行产品配送。这种配送中心的规模比较大，客户比较多，配送的批量也比较大。在通常情况下，区域配送中心的产品先运到城市配送中心，然后再从城市配送中心运到最终需求点上。第九页，共七十一页。三、根据配送中心的效劳范围分类第九页，共七十一页。四、根据配送中心的效劳功能分类〔1〕储存型配送中心重点强调的是配送中心的储存功能，在功能上与传统的仓库非常接近，通常具有较大规模的仓库和场地，具有较强的库存调节功能。〔2〕流通型配送中心重点强调的是配送中心的集运功能，作为产品集中和组合的场所，将同方向的、小批量的产品或原料集中起来，及时地分发到各客户指定的地点。特点是不设储存仓库，只设周转区，占地面积比较小。主要效劳对象是城市区域内的各连锁店铺，在地理位置上定位于(wèiyú)接近主要客户的地点。〔3〕加工型配送中心主要以流通加工为核心业务，根据客户提出的加工深度、尺寸、标准、数量等要求，将不同客户的商品集合后，经过加工再配送给各个客户；或者按照各个客户需要将大批量的商品进行细分，进行小件包装以及贴附标签、条形码等操作。加工型配送中心需要配置特定商品的加工处理设施、场地技术和人员。第十页，共七十一页。四、根据配送中心的效劳功能分类第十页，共七十一页。五、配送中心的根本功能配送中心是一个多功能、集约化的物流节点，它把收货验货、存储保管、装卸搬运、拣选、流通加工、配送、结算和信息处理，甚至订货等作业有机地结合在一起。〔1〕集散功能是指配送中心能够将分散在各个生产企业的产品集中到一起，经过分拣、配组等向多家客户进行配送。〔2〕储存功能是指配送中心配备相应的仓储设施设备和储存一定数量的货物(huòwù)，以满足市场的需要和流通加工、配送等环节的正常运转。配送中心的库存作为商品供需的缓冲区，能够满足不同消费者在不同时间段的个性化需求，这种集中储存可以大大降低库存总量，增加调控能力。

第十一页，共七十一页。五、配送中心的根本功能第十一页，共七十一页。〔3〕配组功能配组是指单个客户所需要的配售数量不能到达车辆的有效载运负荷时，就存在如何集中不同客户的配送货物，进行搭配装载以充分利用运能、运力的问题。通过配组可以提高送货水平及降低送货本钱。配组已成为配送中心与传统(chuántǒng)仓储企业的明显区别之一，也是配送中心最重要的特征之一。〔4〕流通加工功能是指物品在从生产地到使用地的流通过程中，根据客户提出的要求和根据合理配送商品的原那么对物品施加包装、分割、计量、分拣、刷标志、拴标签、组装等简单作业的总称。

〔5〕分拣功能每个客户的订单都至少包含一项以上的商品，这些不同种类的商品需要由配送中心选出并集中在一起。分拣就是将一批相同或不同的货物，按照客户不同的要求拣选后集中在一起进行配送。第十二页，共七十一页。〔3〕配组功能第十二页，共七十一页。〔6〕配送功能配送就是按客户的订货要求，在配送中心进行分货、配货作业，并将配好的商品送交收货人。与运输相比，配送要求完全按照客户对商品种类、规格、数量、时间和地点(dìdiǎn)的要求，进行分拣、配货、集装、车辆调度、路线安排的优化等一系列的工作，再运送给客户的一种特殊的送货形式。〔7〕信息整合功能配送中心的信息系统将各种作业环节的信息进行实时采集、分析、传递，为配送中心的经营管理、政策制定等提供有用的信息，有效地为整个流通过程的控制、决策和运转提供依据。〔8〕资源回收功能是指回收及处理作业过程中产生的许多可回收资源，如拆箱更换包装后的纸箱等。第十三页，共七十一页。〔6〕配送功能第十三页，共七十一页。六、配送中心作业管理配送中心的根本作业包括如下内容：订单处理、进货作业、搬运作业、存储(cúnchǔ)作业、拣货作业、流通加工作业、补货作业和配送作业。1．订单处理订单处理通常指由接到客户订单开始到准备拣货之间的作业，主要工作包括：客户订单的数据确认、存货查询、订单整理与编号及订单出货数据处理等。具体内容包括：〔1〕接受订单〔2〕订单数据处理〔3〕订单状况管理第十四页，共七十一页。六、配送中心作业管理第十四页，共七十一页。2．进货作业是指从确认客户订单(dìnɡdān)，发出订货，从运输工具上把货物卸下，核对单据与实物数量、检查包装及产品质量，并办理入库手续等作业，主要包括3个环节。〔1〕订货配送中心在收到和汇总客户的订单后，首先要确定需要配送的商品的种类和数量，然后查询现有存货数量是否满足配送需要，当商品的库存量低于平安库存量时就需要发出订货。配送中心也可以根据市场需求情况提前订货，以备发货。〔2〕接货配送中心组织人力物力接收从客户发出的货物。〔3〕验收入库货物到达配送中心，配送中心负责对货物进行验收，验收的标准通常是按照订货合同或者订单的规定。验收的内容包括商品质量、数量、品名、规格、外观和生产日期等几个方面。验收合格的货物办理录入信息和入库手续，对于与订单规定不符的货物或者有破损的货物，就需要做出适当的处理。第十五页，共七十一页。2．进货作业第十五页，共七十一页。3．装卸搬运(bānyùn)作业装卸〔loadingandunloading〕是指物品在指定地点进行的垂直移动为主的物流作业；搬运〔handling/carrying〕是指在同一场所内将物品进行水平移动为主的物流作业。第十六页，共七十一页。3．装卸搬运(bānyùn)作业第十六页，共七十一页。4．存储作业存储作业应该充分有效地利用空间，尽可能提高人力资源及设备的利用率，有效地保护好商品的质量和数量，维持良好的储存环境。良好的存储策略可以提高存储效率，存储策略可以分为以下几种：〔1〕定位存储定位存储是指每一类货物都有自己固定的储位，这种存储方法比较便于管理，但缺点是需要较多的存储空间。〔2〕随机存储随机存储是指每一类货物的储位不是固定的，而是随机的。这种存储方法最大限度地提高了仓库的空间利用率，但是给货物的进出和盘点等工作带来了一定(yīdìng)的困难。〔3〕分类存储分类存储是指按货物的相关性、流动性、尺寸和重量及货物的特性对货物进行分类，对货物按类进行存储。第十七页，共七十一页。4．存储作业第十七页，共七十一页。存储的方式主要有托盘堆垛方式和货架存储方式。〔1〕托盘堆垛方式托盘堆垛方式就是用叉车将满载货物的托盘直接放置(fàngzhì)到存储的位置，用叉车依次提升堆放。这种堆垛的方式完全采用叉车作业，减轻了人的体力劳动，但托盘上的货物必须堆码平整，让上面的托盘能够平稳放置(fàngzhì)。〔2〕货架存储方式货架存储系统分为固定货架系统和旋转货架系统二种。高层固定货架一般分为几排，排与排之间设有一条巷道，供巷道堆垛机和叉车行驶作业。第十八页，共七十一页。存储的方式主要有托盘堆垛方式和货架存储方式。第十八页，共七5．拣货作业是按照不同的顾客或不同的配送路线要求，使用各种(ɡèzhǒnɡ)拣选设备和传输装置，及时、准确、快速地按顾客要求从储存区域将物品拣出，并按一定的方式进行分类和集中，送入指定的发货区。拣货可以分为人工分拣和利用自动分类机分拣二种。6．流通加工作业是指物品在从生产地到使用地的过程中，根据需要施加包装、分割、计量、分拣、刷标志、拴标签、组装等简单作业的总称。流通加工主要的目的是为了促进销售、维护产品质量和提高物流效率，实现物流增值效劳。

第十九页，共七十一页。5．拣货作业第十九页，共七十一页。7．补货作业是当拣货区的货物数量低于平安存量时，从存储区把货物运到拣货区的作业。补货的形式有以下二种：〔1〕批次补货每天或每批次拣货之前，先检查货物的库存量是否到达所需要的拣取量，假设数量缺乏，那么(nàme)在拣货之前一次性补足。〔2〕定时补货把每天分成几个时点，当拣货区的存货量小于设定标准时，立即进行补货。8．配送作业是利用配送车辆把客户订购的物品从配送中心运送到客户的作业。配送作业要到达运送距离最短、时间最少、本钱最低3个目标。第二十页，共七十一页。7．补货作业第二十页，共七十一页。第三节配送路线优化设计(shèjì)一、配送网络结构常用的配送网络结构有三大类，即集中型配送网络、单层次配送网络和多层次配送网络结构。第二十一页，共七十一页。第三节配送路线优化设计(shèjì)第二十一页，共七十一1、集中型配送网络集中型配送网络是指配送系统(xìtǒng)中只设一个配送中心，所有货物首先要在配送中心集结，然后再根据客户需求进行配送供应商客户DC集中型配送网络第二十二页，共七十一页。1、集中型配送网络供应商客户DC集中型配送网络第二十二页，共2、单层次配送网络单层次配送网络，也称分散型配送网络，是配送系统中在一个层次上设多个配送中心，供给商将货物运送到不同的配送中心，然后再配送给用户。配送中心是按照用户地理位置分布划分配送区域(qūyù)，即按照客户就近原那么设立。供应商客户DC图3-3-3单层次配送网络DC第二十三页，共七十一页。2、单层次配送网络供应商客户DC图3-3-3单层次配送网络3、多层次配送网络

多层次配送网络是配送系统中在两个(liǎnɡɡè)或两个(liǎnɡɡè)以上层次上设多个配送中心，是集中型配送网络与分散型配送网络于一体的一种网络结构。

供应商客户DC图3-3-4多层次配送网络DCDC第二十四页，共七十一页。3、多层次配送网络供应商客户DC图3-3-4多层次配送网络合理的运输(yùnshū)路线1一辆运货车顺次途经各停车点的路线要呈凸状，或水滴形，各条线路之间是不交叉的。仓库库仓库二、典型(diǎnxíng)不合理运输路线第二十五页，共七十一页。合理的运输(yùnshū)路线1仓库库仓库二、典型(diǎnDD合理的运输路线2将相互(xiānghù)接近的停车点的货物装在一辆车上运送。

第二十六页，共七十一页。DD合理的运输路线2第二十六页，共七十一页。仓库仓库第二十七页，共七十一页。仓库仓库第二十七页，共七十一页。三、城市配送运输决策1、城市配送运输常用(chánɡyònɡ)的决策方法〔1〕TSP行程安排决策〔2〕VRP运输路线选择及行程安排决策

第二十八页，共七十一页。三、城市配送运输决策第二十八页，共七十一页。〔1〕运输工具的类型如普通卡车〔大、中、小型〕、厢式货车、冷藏车、集装箱货车等。〔2〕运输工具的来源一是自有，二是外协。外协的运输工具又可以分为两种，一是以前有长期协议的外协车辆(chēliàng)，二是临时租赁的车辆(chēliàng)。前者，比方目前很多物流企业的运输车辆都是由司机自带的，物流企业也可以和其他企业签订长期协议租赁车辆。这类外协车辆的使用性质与企业自有车辆相近，只是不拥有所有权。〔3〕运输工具的数量物流企业拥有一定规模的运输工具〔自有或合同外协〕，再根据业务规模到市场上临时租赁车辆。有的物流效劳企业不拥有任何车辆，承揽了运输业务后再去寻找运输车辆。2、运输工具选择(xuǎnzé)第二十九页，共七十一页。〔1〕运输工具的类型2、运输工具选择(xuǎnzé)第二十九案例YRC国际(guójì)物流企业在中国的开展战略第三十页，共七十一页。案例第三十页，共七十一页。3、运输工具配载(pèizǎi)与调度问题运输工具配载的根本原那么〔1〕将相互接近的停留点的货物装在一辆车上运送(yùnsònɡ)。〔2〕优先使用大载重量的送货车辆，并将提货与送货过程结合进行。〔3〕上轻下重即密度大的货物应装载在运输车辆的下面，轻泡的货物装载在上面。〔4〕先远后近远途的货物和后送的货物应先装载，近途的或先送的货物应后装载。第三十一页，共七十一页。3、运输工具配载(pèizǎi)与调度问题运输工具配载的课堂交流针对(zhēnduì)运输物流管理课堂教学内容，写一篇论文PPT，字数不限，但应该符合论文要求〔应具有提出问题、分析问题、解决问题〕。第三十二页，共七十一页。课堂交流第三十二页，共七十一页。四、TSP问题(起点和终点(zhōngdiǎn)相同的路径规划)TSP问题，即旅行商问题〔TravelingSalesmanProblem〕又译为旅行推销员问题、货郎担问题，是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。TSP问题是一个组合优化问题。该问题可以被证明具有NP计算复杂性。中国邮递员问题著名图论问题之一。邮递员从邮局出发送信，要求对辖区内每条街，都至少通过一次，再回邮局。在此条件下，怎样选择一条最短路线?此问题由中国数学家管梅谷于1960年首先研究并给出算法，故名。第三十三页，共七十一页。四、TSP问题(起点和终点(zhōngdiǎn)相同的路径1、TSP问题的描述基本的TSP模型描述如下：给出一个起点配送中心和一组n个客户的集合，寻找一条在起点配送中心开始和结束的路线，这条路线经过每一个消费者，并且是最短路，即每一个车辆在配送中心起程和终止；一条路线一次要包含所有需要服务的客户点的配送；每一个客户点必须在预先设置的时间窗口内得到服务；以行程最短为确定车辆路线行程的评价指标。

第三十四页，共七十一页。1、TSP问题的描述即第三十四页，共七十一页。TSP旅行商是在单回路运输〕问题。单回路运输问题是指在路线优化中，存在节点集合D，选择一条适宜的路径(lùjìng)遍历所有的节点，并且要求闭合。单回路运输模型在运输决策中，主要用于单一车辆的路径(lùjìng)安排。目的在于在该车辆遍历所有的用户的同时，到达所行驶距离最短。这类问题的两个显著特点是：〔1〕单一性〔只有一个回路〕。〔2〕遍历性〔不可遗漏〕。第三十五页，共七十一页。TSP旅行商是在单回路运输〕问题。第三十五页目标函数：以行程最短为确定车辆路线行程的评价指标。物流配送路径优化常见的约束条件包括(bāokuò)：车辆装载能力限制，停车点的工作时间约束，运行时间、不同区段的车速限制，运行途中的障碍物〔湖泊、山脉等、交通管制〕、司机的短时间休息等。如果问题中包含送货点的个数很多，附加了许多约束条件，问题求解就变得十分复杂。对这类问题的求解，往往采用的是启发式算法，以求得一个满意解〔近似解〕。2、TSP问题(wèntí)的数学模型第三十六页，共七十一页。目标函数：以行程最短为确定车辆路线行程的评价指标。2TSP模型可以如下描述：在给出的一个n顶点网络（有向或无向），要求找出一个包含所有n个顶点的具有最小耗费的环路。TSP模型的数学描述为：设有连通图G，其定点集V，定点间的距离C=cij1≤i,j≤n目标函数：约束条件：mini=1,2,…,m

j=1,2,…,n决策变量：从i到j无通路

从i到j有通路

第三十七页，共七十一页。TSP模型可以如下描述：在给出的一个n顶点网五、VRP问题1、VRP描述在实际运输中，经常会遇到车辆受承载能力、容积的限制，一辆车不能满足所配送区域用户的需求。多回路运输问题〔VehicleRoutingProblem,VRP〕，是对一系列客户的需求点设计适当的路线，使车辆有序地通过它们，在满足一定的约束条件下，如货物需求量、发送量、交发货时间、车辆载重量限制、行驶里程限制、时间限制等等，到达一定的优化目标，如里程最短、费用最少、时间最短，车队规模最少、车辆利用率高。VRP问题和TSP问题的区别在于：客户群体的数量大，只有一辆车或一条路径满足不了(bùliǎo)客户的需求。相对于TSP问题，VRP问题更复杂，求解更困难，但也更接近实际情况。第三十八页，共七十一页。五、VRP问题第三十八页，共七十一页。典型的VRP可描述为：1)多个客户同时需要运输效劳，且一辆车不能同时满足这些客户的要求。2〕每个客户只能被一辆车访问一次。3)所有(suǒyǒu)车辆从仓库出发，并最终回到仓库。4)所有的车辆必须满足能力约束。5〕车辆在路线上可以取/送货。第三十九页，共七十一页。典型的VRP可描述为：第三十九页，共七十一页。2、VRP图解根本原理VRP是考虑车辆(chēliàng)的装载能力〔吨位或容积〕时，对配送线路进行优化。对这一类问题的求解可根本上分为两大步骤：第一步根据客户地理位置和时间窗口将配送区域中的客户聚类，然后根据客户需求的数量和一辆车的装载能力确定配送路线数量和配送车次；第二步在每一条路线上采用TSP解决方法。第四十页，共七十一页。2、VRP图解根本原理第四十页，共七十一页。案例：丁秋雷-系统工程理论(lǐlùn)与实践2007-10第四十一页，共七十一页。案例：丁秋雷-系统工程理论(lǐlùn)与实践2007-10第四十二页，共七十一页。第四十二页，共七十一页。第四十三页，共七十一页。第四十三页，共七十一页。TSP问题是物流配送业务中的常见问题，在物流中的描述是对应一个物流配送公司，欲将n个客户的订货沿最短路线全部送到。如何确定最短路线。解决此类问题的目标是找出途中经过的点的顺序，使其经过所有送货点并满足各点对送货时间的要求，且总距离最短或总行驶时间。——“旅行推销员〔TSP〕〞问题。TSP问题最简单的求解方法是枚举法。它的解是多维的、多局部极值的、趋于无穷大的复杂解的空间，搜索空间是n个点的所有排列的集合，大小(dàxiǎo)为〔n-1〕。可以形象地把解空间看成是一个无穷大的丘陵地带，各山峰或山谷的高度即是问题的极值。求解TSP，那么是在此不能穷尽的丘陵地带中攀登以到达山顶或谷底的过程。旅行商问题〔TravelingSalemanProblem，TSP〕是VRP的特例，由于Gaery已证明TSP问题是NP难题，因此，VRP也属于NP难题。随着问题中包含点个数和约束条件的增加，求解问题的复杂程度增加，要找到最优路径非常困难。即使用最快的计算机进行计算，求最优解的时间也非常长。启发式求解法是求解这类问题的好方法。六、TSP问题(wèntí)和VRP问题的求解算法第四十四页，共七十一页。TSP问题是物流配送业务中的常见问题，在物流中的描述是对求解TSP模型时，如果要得到精确的最优解，最简单的方法也是枚举法。对于小规模问题，枚举法是一种有效的方法。但是对于大规模问题，由于枚举法的例举次数为〔n一1〕！次，这在实际操作中是很难实现的。整数规划的方法用于解决局部TSP模型，其原理也是分枝定界法，该算法只能(zhīnénɡ)对一局部中小规模的问题进行求解，对于大多数问题的求解都存在一定的难度。第四十五页，共七十一页。求解TSP模型时，如果要得到精确的最优解，最简单的方法也是枚组合(zǔhé)爆炸例如，一台汽车每天要给20-30个不同的自动售货机补货。如果要访问20台机器的时候，其巡回路线就有20！＝2432902021176640000条巡回路线可供选择；如果要访问30台，就有30！＝265252859812191058636308480000000条巡回路线可供选择，利用现有计算机，假设一秒钟可以计算100亿条路线的距离的话，对于(duìyú)20台自动售货机的计算需要花费7年的时间，对于(duìyú)30台自动售货机那么需要花费8411兆年的时间，这种现象称为“组合爆炸〞第四十六页，共七十一页。组合(zǔhé)爆炸例如，一台汽车每天要给20-30个不同的组合(zǔhé)爆炸第四十七页，共七十一页。组合(zǔhé)爆炸第四十七页，共七十一页。1、解决VRP问题的几种(jǐzhǒnɡ)〔传统〕启发式算法第四十八页，共七十一页。1、解决VRP问题的几种(jǐzhǒnɡ)〔传统〕启发式算

图解法的根本原理假设在每一次的配送中，客户的地理位置、配送数量、客户接受货物的时间窗口都是确定的。图解法就是将这些已有的信息在地图或GIS上标注，根据决策问题类型，采用一定的优化方法，将配送中心与客户连接(liánjiē)在一起，进行配送路线优化设计的一种方法。由于是以地图或GIS为根本工具，故称此种方法为图解法。第四十九页，共七十一页。第四十九页，共七十一页。〔1〕解决VRP问题的扫描法问题：对于假设干个停车点〔客户〕安排最优行车路线。第一步，将仓库〔出发点〕和所有的停车点位置画在地图上或坐标图上；第二步，通过仓库位置放置(fàngzhì)一直尺，然后顺时针或逆时针方向转动直尺，直到直尺交到一个停车点。询问：累计的装货量是否超过送货的载重量或容积〔首先要使用最大的送货车辆〕。如是，最后的停车点排除，将路线确定下来。然后再从这个停车点开始继续扫描，开始一条新的路线。这样扫描下去，直至全部的停留点都被分配到路线上。第三步，对每条路线安排运行顺序，以求运行距离最小化。方案的误差率在10%左右。第五十页，共七十一页。〔1〕解决VRP问题的扫描法第五十页，共七十一页。100030002000400030003000200020002000200020001000仓库图5-13停留点提货量数据例5-7从各客户点提货，然后将货物运回仓库。全天的提货量见图5-13。送货车每次可运载10000件。要求确定：需多少条路线〔即多少辆送货车〕；每条路线上有哪几个客户点；送货车辆效劳有关(yǒuguān)客户点的顺序。第五十一页，共七十一页。100030002000400030003000200020

扫描法:手工计算。车的载货量是10000件。需要多少条线路？每条线路上的站点如何排列？D300030001000300020002000200020002000100020004000D300030001000300020002000200020002000100020004000第五十二页，共七十一页。扫描法:手工计算。车的载货量是10000件。需要多少条线图3-3-14是客户为12个的配送网络，单车装载能力(nénglì)为3个客户单位，用扫描法确定的配送线路数为4条。

第五