5运输及配送系统规划

5-运输及配送系统规划5-运输及配送系统规划5-运输及配送系统规划重点、难点1）运输方式的定量选择方法；2）单车辆路线优化方法；3）多车辆路线优化方法（扫描法和节约法25-运输及配送系统规划5-运输及配送系统规划5-运输及配送系重点、难点1）运输方式的定量选择方法；2）单车辆路线优化方法；3）多车辆路线优化方法（扫描法和节约法2重点、难点1）运输方式的定量选择方法；2第一节运输方式的选择一、运输方式选择的原则成本、速度、可靠性、安全性

（一）安全性原则（二）及时性原则（三）准确性原则（四）经济性原则3第一节运输方式的选择一、运输方式选择的原则3二、运输服务方式选择的定性方法即根据各种运输方式的经济和服务特征进行判断：运输成本：成本如何确定？速度（运输时间）：可靠性（运输时间的波动）：4二、运输服务方式选择的定性方法即根据各种运输方式的经济和服务三、运输方式的定量分析法1、成本比较法的基本思想（运输成本与库存成本的总成本）使该运输服务的成本与该运输服务水平以及相关库存成本之间达到平衡的运输服务就是最佳服务。即：既能满足客户需求，又使总成本最低的服务。——成本比较法5三、运输方式的定量分析法1、成本比较法的基本思想——成本比较2、计算过程示例说明某公司欲将产品从位置A的工厂运往位置B的公司自有仓库，年运量D=700000件，产品单价C=30元，年存货成本I=产品价格的30％。公司希望选择使总成本最小的运输方式。据估计，运输时间每减少一天，平均库存成本可以减少1％。62、计算过程示例说明某公司欲将产品从位置A的工厂运往位置各种运输服务的有关参数：方式费率R(元/件)时间T(天)年运送批次平均存货量Q/2铁路0.12110100000驮背0路0.252042000航空1.424020250选择哪种运输方式最满意？7各种运输服务的有关参数：方式费率R(元/件)时间T(选择依据总成本=运输成本+库存成本运输成本=运输量

费率库存成本=在途库存成本+工厂存货成本+

仓库存货成本库存量

库存费率

物资价格8选择依据总成本=运输成本+库存成本库存量库存费率物资价库存成本=在途库存成本+工厂存货成本+

仓库存货成本在途库存费用=I

C

D

T/365工厂存货成本=I

C

Q/2仓库存货成本=I

（C+R）

Q/2年运量D=700000件，产品单价C=30元，存货费率I=30%9库存成本=在途库存成本+工厂存货成本+

仓各种运输方式成本计算：成本类型计算公式铁路运输驮背运输公路运输航空运输运输成本R

D？在途库存ICDT/365工厂存货ICQ/2仓库存货I(C+R)Q/2总成本

年运量D=700000件，产品单价C=30元，存货费率I=30%10各种运输方式成本计算：成本类型计算公式铁路运输驮背运输各种运输方式成本计算结果：总成本最低的是公路运输方式，其次是驮背运输，成本最高的是铁路运输。成本类型计算公式铁路运输驮背运输公路运输航空运输运输成本R

D70000105000140000980000在途库存ICDT/3653452052416448630134521工厂存货ICQ/2900000416500378000182250仓库存货I(C+R)Q/2903000420593380520190755总成本

22182051185737984821138752611各种运输方式成本计算结果：总成本最低的是公路运输方式结果讨论1）存储费率改变，对选择有什么影响？降低存储费率，结果会怎样？2）运输费率和运输时间，对于选择结果有何影响？12结果讨论1）存储费率改变，对选择有什么影响？12第二节物资运输调配决策指在多个供应地和多个需求地之间如何合理调配货物，在满足需求前提下，使总运输成本最低。

13第二节物资运输调配决策指在多个供应地和多个需求地之间如何合第二节物资运输调配决策问题特征：两点间的运输线路固定，运输距离的影响反映在单位运费中，运输总成本由运输量决定。不涉及运输路线如何优化。

14第二节物资运输调配决策问题特征：两点间的运输线路固定，运输问题分类一、多起迄点间的直达运输（一）产销平衡的运输问题

（二）产销不平衡的运输问题

二、存在中间转运的物资调配

15问题分类一、多起迄点间的直达运输15一、多起迄点间的直达运输供应商A供给400供应商B供给700供应商C供给500客户2需求量=500客户3需求量=300客户1需求量=60047965555816一、多起迄点间的直达运输供应商A供应商B供应商C客户2客户3运输问题多个货源可服务于多个市场地，怎么指定各目的市场的供货地？在有多个供应商、工厂、仓库服务于多个客户的情况下，这是运输组织中常见的问题。若供求不平衡呢？更复杂。请看下面几种情况：(1)某企业要将济南、郑州、兰州三个工厂生产的钢材运输到北京、上海、西安、杭州，应该如何组织运输使运费最小?(2)某大零售商有3个大型配送中心在北京、上海、广州，给它在天津、杭州、武汉、南宁四个城市的超市连锁店配货，应该如何组织运输使运费最小?17运输问题多个货源可服务于多个市场地，怎么指定各目的市场的供货（一）产销平衡的运输问题

从每一供应地运送多少物资到各需求地，总运费最低？完成练习题4

18（一）产销平衡的运输问题从每一供应地运送多少物资到各需求（一）产销平衡的运输问题

从每一供应地运送多少物资到各需求地，总运费最低？供应商A供给=400供应商B供给=700供应商C供给=300客户2需求量=500客户3需求量=300客户1需求量=60047965555819（一）产销平衡的运输问题从每一供应地运送多少物资到各需求求解方法

运输问题的表上作业法、单纯形法销地

产地

B1

B2

B3

供应量

A1

4

7

6

400

A2

5

5

5

700A3

9

5

8

300需求量

600500

300

最佳方案：A客户1：400；B客户1：200；B客户2：200；B客户3：300；C客户2：300完成练习题4

20求解方法运输问题的表上作业法、单纯形法销地产地B1（二）产销不平衡的运输问题1．总产量大于总销量2．总销量大于总产量（略）21（二）产销不平衡的运输问题1．总产量大于总销量21二、存在中间转运的物资调配（一）问题描述22二、存在中间转运的物资调配（一）问题描述22（一）问题描述某物流系统中有f个供应地，m个中转站，n个需求地。工厂Ak的生产能力为ak（k=1，…，f），流通中心Ti的配送能力为ti（i=1，…，m），零售店Bj的需求量为bj（j=1，2，…，n）。由Ak经Ti运到Bj的单位运价为Ckij。求：在设施点能力限制的条件下，满足零售店需求量的最优运输方案。23（一）问题描述某物流系统中有f个供应地，m个中转站，n个需求（二）数学模型决策变量Xkij——由产地Ak经Ti运到零售店Bj的物资量目标函数：约束条件：（1）配送量

生产能力的限制：（2）流通中心发送能力的限制：（3）满足零售店需求量（4）变量非负：24（二）数学模型决策变量Xkij——由产地Ak经Ti运到零售店（三）求解方法（1）一般的线性规划方法求解（2）运输问题表上作业法

方法（2）的思路：补充一些虚拟的产地或需求地，将有中转的运输问题转化为无中转的直达运输问题；进一步转化为供需平衡的运输问题；运用表上作业法求解。25（三）求解方法25存在中间转运的物资调配：算例题目条件：ABDCFE150200130130中转能力不限26存在中间转运的物资调配：算例ABDCFE1502001301存在中间转运的物资调配：算例运输问题表：

ABEFCD空列供应A0134612140

B1307613120

E4703880

F6630780

C1213870170

D1412881700

需求

90

27存在中间转运的物资调配：算例

ABEFCD空列供应A0134运输问题表中需求和供应量确定准则：转运问题中点在运输表中的供应值在运输表中的需求值供应点起始供应+总供应总供应转运点总供应总供应需求点总供应起始需求+总供应空

点0起始供应－起始需求28运输问题表中需求和供应量确定准则：转运问题中点在运输表中的存在中间转运的物资调配：算例最终运输表：

ABEFCD空列供应A0134612140500B1307613120550E4703880350F6630780350C1213870170350D1412881700350需求35035035035048048090

29存在中间转运的物资调配：算例

ABEFCD空列供应A0134第三节单一车辆配送路线的优化两类问题：从O点送货到T点；从A点出发最后回到A点。OABCDET225417443175起点终点CABD3818312227344530第三节单一车辆配送路线的优化两类问题：OABCDET225问题及方法分类一、起迄点不同的单一路线优化（一）动态规划法

（二）Dijkstra方法二、起迄点重合的单一路线优化（一）旅行商问题TSP模型

（二）中国邮递员问题

31问题及方法分类一、起迄点不同的单一路线优化31一、起迄点不同的单一路线问题1、应用问题

从一个发货点运输到一个不同的收货点，例如有一批货需要从A城市运送到E城市，根据从A城市到E城市的公路路网，用点表示经过的县市，线(链)表示两市之间的运输代价：时间、或距离、或时间和距离的加权平均。要确定：从A市到终点的最佳运输路线。//最短路径问题32一、起迄点不同的单一路线问题1、应用问题322问题的不同条件OABCDET225417443175起点终点沿着眼前(局部)的最短路走下去，可能找不到最佳路线！332问题的不同条件OABCDET225417443175起点终（一）最短路径的动态规划法

要点：适用于什么场合？如何求解？逆序、标号法52871220141919在节点旁标出该点到终点的最短距离34（一）最短路径的动态规划法要点：适用于什么场合？528（一）最短路径的动态规划法

要点：最佳路径是：52871220141919AB2C2D1E35（一）最短路径的动态规划法要点：最佳路径是：52871思路：若点序列{Vs,V1,V2,…,Vn-1,Vn}是从Vs到Vn的最短路，则{Vs,V1,V2,…,Vn-1}必定是从Vs到Vn-1的最短路。定义：P(Vi)=Vi到Vs的最短距离；lij两点间距离（二）最短路径的网络图法——Dijkstra方法OABCDET225417443175起点终点36思路：若点序列{Vs,V1,V2,…,Vn-1,Vn}是次序n旧节点新节点总距离第n个最近的节点，最短距离，连接1OA2A2OA2OC4C4OCAB2+2=4B4AB3AD2+7=9BE4+3=7E7BECE4+4=84AD2+7=9BD4+4=8D8BDED7+1=8D8ED5DT8+5=13T13DTET7+7=14求解过程OABCDET225417443175起点终点37次序n旧节点新节点总距离二、起迄点重合的运输路线规划应用问题

货车运输时碰到的普遍问题:●从某仓库（或配送中心）送货到零售点然后返回；●从零售店到客户地配送的路线设计；●垃圾收运车（或送餐车）的路线设计。CWBD38二、起迄点重合的运输路线规划应用问题货车运输时碰到的二、起迄点重合的运输路线规划应用问题原则：——既经过所有点或街道，又要求时间最短或总距离最短。问题复杂性：

可行方案很多，优化上的“组合爆炸”，CABD3818312227344539二、起迄点重合的运输路线规划应用问题原则：CABD3818(一)旅行商问题TSP模型（TravelingSalesmanProblem）

经过网络中的各顶点问题及方法的分类CABD38183122273445（二）中国邮递员问题40(一)旅行商问题TSP模型问题及方法的分类CABD38183（二）中国邮递员问题邮递员从邮局出发，走遍他所负责的街道，完成投递后返回邮局，怎样走才使总路程最短？城市配送中心为分布在各街道的便民连锁店配送完货物后再返回配送中心；流动推销员从销售中心出发，沿着街道推销商品，最后再返回销售中心，也属于这类问题。问题及方法的分类41（二）中国邮递员问题问题及方法的分类41（一）单回路运输TSP模型单一车辆的路径安排要求：不可遗漏：访问所有节点(或客户)只有一个回路，各点只能被访问一次例如：从A出发送货到B、C、D个小配送站。任意两点间距离已知(或可求)求：最佳行程？CABD3818312227344542（一）单回路运输TSP模型单一车辆的路径安排不可遗漏：访问所TSP的数学模型：0-1模型Xij=0从i到j无通路Xij=1从i到j有通路43TSP的数学模型：0-1模型Xij=0从i到j无通路43组合爆炸可行方案共(n-1)!个站点C1C2C3C4行车次序12340100000110000010送货顺序：C3

C1

C2

C4总路长d=d31+d12+d24+d43dij—CiCj之间的距离44组合爆炸可行方案共(n-1)!个站点行车次序0TSP问题的求解算法整数规划（小规模问题）启发式算法：

贪婪算法（参见例题解法）最近插入法(nearestinsertion)现代优化方法：

Hopfield神经网络优化GA遗传算法45TSP问题的求解算法整数规划（小规模问题）45（二）中国邮递员问题及其解法图论要点复习：偶点与奇点“一笔画”问题“一笔画”的条件图论之“奇偶点图上作业”奇点之间的边重复46（二）中国邮递员问题及其解法图论要点复习：46求解过程：确定初始可行方案判断方案的最优性行走方案B方案A判断标准：每一边上最多有一条重复边；图中每个圈上重复边的总权不大于该圈总权的一半。47求解过程：确定初始可行方案行走方案B方案A判断标准：47邮递员问题及其解法最优行走方案：方法局限：图形复杂后，可行方案太多。圈过多。48邮递员问题及其解法最优行走方案：方法局限：48第四节多车辆配送路线的优化

车辆路径问题VRP（VehicleRoutingProblem）

49第四节多车辆配送路线的优化

车辆路径问题VRP（Vehic第四节多车辆配送路线的优化50第四节多车辆配送路线的优化50一、问题描述某物流中心要为q个客户提供服务。己知每个客户点的地理位置及其货运需求量，物流中心需要调用多辆货车来满足这些客户的服务需求，每辆车载重量一定。如何指派车辆？行车路径？

51一、问题描述某物流中心要为q个客户提供服务。己知每个客（一）模型假设（1）单一物流中心，多部车辆配送。（2）每个需求点由一辆车服务，每个客户点货物需求量不超过车辆的载重容量。（3）车辆为单一车种，相同载重量，且容量有限。（4）无时窗限制的配送问题。（5）客户的位置和需求量均为已知。（6）配送的货物视为同一种商品，便于装载。52（一）模型假设（1）单一物流中心，多部车辆配送。52（二）多车辆配送路线优化数学模型（了解）1、变量2、目标：xijk——车辆k是否直接从节点i到节点j；yik——车辆k是否访问节点i。53（二）多车辆配送路线优化数学模型（了解）1、变量xijk——（二）多车辆配送路线优化数学模型3、约束条件：（1）每个客户点只能被一辆车访问：（2）车辆的载重能力约束：（3）进入和离开某个客户的是同一辆车：

（4）消除子回环：（5）参数的取值范围：（6）

所需最少车辆数：54（二）多车辆配送路线优化数学模型3、约束条件：（1）每个客户（三）多车辆路径问题求解方法概述

1．精确优化方法

2．人工智能方法

3．模拟方法

4．启发式方法

扫描法节约法

55（三）多车辆路径问题求解方法概述1．精确优化方法扫描法5二、扫描法（sweepmethod)***算法原理按照角度大小以逆时钟或顺时钟方向扫描所有客户点，若满足车辆装载量即划分为一群；扫描完毕，在每个群内部用最短路径算法求出车辆行驶路径。

二阶段法56二、扫描法（sweepmethod)***算法原理按照角度二、扫描法例8-5载重量为10吨的车若干辆57二、扫描法例8-5载重量为10吨的车若干辆57例题各点位置的图形显示58例题各点位置的图形显示58二、扫描法算法步骤以物流中心为原点，计算客户点的极坐标按一定方向扫描所有客户点客户点需求量进行累加划归同一群形成新的群NY超过车载量吗？所有客户吗？车辆行驶路径59二、扫描法算法步骤以物流中心为原点，计算客户点的极坐标按一定在极坐标系显示各点位置，标出相应货运量60在极坐标系显示各点位置，标出相应货运量60例61例61例62例62课堂练习：

客户的取货量（单位：件），车辆载重10000件货物。W30002000300040001000300020001000200020002000200063课堂练习：

客户的取货量（单位：件），车辆载重10000三、节约法（savingsmethod）1、基本思想：

如果将运输问题中的两个回路合并成一个回路，就可缩短线路总里程（即节约了距离），并减少了一辆卡车。

节约的里程=?64三、节约法（savingsmethod）1、基本思想：节约2、节约法步骤例8-6站点X坐标Y坐标需求量(件)配送中心顾客1顾客2顾客3顾客4顾客5顾客6顾客7顾客8顾客9顾客10顾客11顾客12顾客1300679152017711520720125151230-2-4-6-6-7-9-15

4836439257165630574