第四章运输决策与配送路线规划
本章主要内容
?运输模式选择
?运输线路优化模型
?配送线路设计
第一节运输模式的选择
一.运输模式的特点
?常用的运输方式有
?铁路
?公路(整车发运、零担货运)
?包裹运输
?空运
?水运
运输模式的特点
?1.铁路运输：
?高额的固定成本及低廉的运营成本。
?运输价格主要取决于运量与运输距离。
?缺点是时间较长，所以一般适合于大规模、低价值、对时间要求不敏感的产品。
?铁路运输的主要目标是充分提高机车、车组人员的利用率。
?2.公路运输：
?包括整车发运(TL)与零担货运(LTL)两种。
?整车发运按照整车收费，不考虑货运量，费率随运输距离的不同而改变。
?零担货运则按照运输量与运输距离来收费。
运输模式的特点
?3.包裹运输
?利用空运、铁路或公路运输方式为顾客提供时间敏感的小件货物的运输。
?主要运输对象是小件、对时间非常敏感的货品，其收费标准较昂贵。
?4.空运
?基础设施及装备方面的固定成本很高，劳动力与燃料耗费主要取决于航线，与一次飞行运载的乘客量与货物重量无关。
运输模式的特点
?就货物量的大小而言，铁路、水路的批量最大、空运的批量最小；
?就运输速度而言，空运速度最快、水路运输速度最慢；
?就运输成本而言，一般来说，水路运输的成本最低、空运最高；
?就服务响应时间而言，水路最慢、空运最快；
?就运输引起的库存成本而言，铁路、水路最高，空运最低。
?进行运输决策时，要综合考虑上述因素，进行成本分析，确定最佳方案。
二. 库存与运输决策
?就不同的运输模式而言，其对库存的影响有以下几点：
(1) 较慢的运输模式会引起较大的中转或运输库存。
(2) 较大运量单位的运输方式会出现订单批量超过当前需求量的情况，出现不需要的库存。
(3) 较慢的运输模式会引起安全库存的提高。
?例：某销售公司的商品需求互相独立，每周的平均需求为1000件，每件成本为200美元，存储成本率为25%，每件重量为3公斤。运输方式初步选择采用铁路或整车、零担，其中零担有2个批量1000或2000，如表所示。请根据上述信息确定优化的运输方式。
解：根据上述信息，可首先计算运输费用如表所示。从中可以看出铁路运输的成本最低，1000件零担货运的运输成本最高。
?计算周期库存成本以及由于运输时间引起的中转库存成本，并累加计算其总库存成本。从中可以看出，铁路运输引起的总库存成本最高，1000件起运的零担方式总库存成本最低。
库存成本的计算（单位：美元）
累积运输成本以及总库存成本（单位：美元）
第二节线路优化模型
?点点间运输——最短路线问题
?多点间运输——运输问题（直达与中转）
?多回路运输——配送问题
最短路线问题
例如图所示为一交通线路网络，现在一批货物要从A点运至E点，中间要经过3个地区B、C、D。图中各点之间的连线表示两点间通行路线，连线上的数字表示两点间的距离。要求选择一条A点至E点的最短路线。
一.最短路线问题求解
?最短路线问题重要性质
?若已经给定从始点S到终点T的最短路线，如图2-3中的实线所示，则从其上任一中间点P 到终点T的部分路线也必然是P点到终点T的所有可选择的路线中的最短路线。
最短路线问题求解
?逆序递推法
根据最短路线问题的性质，我们可以从最后一个阶段开始，由终点向始点方向逐阶段递推，寻找各点到终点的最短路线，当递推到始点时，就找到了始点到终点的最短路线。
最短路线问题求解
?逆序递推法求解例题中的最短路线问题
首先把从A到E的全过程分成4个阶段，用k表示阶段变量，第1阶段，有一个初始状态A，3条可供选择的支路AB1、AB2、AB3；第2阶段，有3个初始状态B l、B2、B3，它们各有3条可供选择的支路……。我们用d k（s k，s k＋1）表示在第k阶段由初始状态s k到下阶段的初始状态s k＋l 的支路的距离。例如，d3(C2，D1)表示在第3阶段，由 C2到 D1的距离，即d3(C2，D1)=2。用 f k(s k)表示从第k阶段的s k到终点E的最短距离。例如，f3(C1)表示从第3阶段的C1到终点E的最短距离。f3(C1)＝7。
最短路线问题求解
?阶段k=4
?f4(D1)=3
?f4 (D2)=4
?阶段k=3
?f3(C1)=d3 (C1，D1 )+ f4 (D1)=4+3=7
?f3(C2)=min{[d3 (C2，D1 )+ f4 (D1)]， [d3 (C2，D2 )+ f4 (D2)] }= min (5,7)=5
?f3(C3)=min{[d3 (C3，D1 )+ f4 (D1)]， [d3 (C3，D1 )+ f4 (D2)] }= min (9,9)=9
?阶段k=2
?f2(B1)=min{[d2 (B1，C1 )+ f3(C1)]， [d2(B1，C2 )+ f3(C2)] } = min (14,12)=12
?f2(B2)=min{[d2 (B2，C1 )+ f3(C1)]， [d2 (B2，C2 )+ f3(C2)] ， [d2 (B2，C3 )+ f3(C3)] }= min (11,10,15)=10
?f2(B3)=min{[d2(B3，C2 )+ f3(C2)]， [d2 (B3，C3)+ f3 (C3)] }= min (10,12)=10
?阶段k=1
?f1(A)=min{[d1(A，B1 )+ f2(B1)]， [d1 (A，B2 )+ f2(B2)] ， [d2 (A，B3 )+ f2(B3)] }= min (15, 16 , 14)=14
最短路线问题求解
使用逆序递推法求解例2-5，得到A到E的全过程最短路线为A→B3→C2→D1→E，如图2-4中双线所示，最短距离是14。
二.直达运输线路优化问题
在物流系统的设计中，如何根据已有的运输网络，制订调运方案，将货物运到各需求地，而使总运费最小，是非常典型的运输决策优化问题。
已知有m个生产地点Ai，i=1，2，……，m，可供应某种物资，其供应量分别为ai，i=1，2，……，m，有n个销地（需求地）Bj，j=1，2，……，n，其需求量分别为bj，j=1，2，……，n，从Ai到Bj运输单位物资的运价为Cij。整理成如表6-2所示产销平衡表和单位运价表。
运价系数表
直达运输优化模型
直达运输线路优化是一个产销平衡的运输模型，即m个供应点的总供应量等于n个需求点的总需求量，运输问题满足供需平衡。这时，由各供应点Ai调出的物质总量应等于它的供应量ai（i=1，2，……，m），而每一个需求点Bj调入的物资总量应等于它的需求量bj，j=1，2，……，n。
我们若用xij表示从Ai到Bj的运量，其数学模型如下：
直达运输数学模型
直达运输问题模型求解方法
手工求解方法：表上作业法
利用表上作业法，寻求运费最少的运输方案，有三个基本步骤：
1）依据问题列出运输物资的供需平衡表及运价表。
2）确定一个初始的调运方案。
3）根据一个判定法则，判定初始方案是否为最优方案。
当判定初始方案不是最优方案时，再对这个方案进行调整。一般说来，每调整一次得到一个新的方案，而这个新方案的运费比前一个方案要少一些，如此经过几次调整，就会得到最优方案。
例1 已知三个产地A1，A2，A3，四个销地Bl，B2，B3，B4的产销量及单位运价如表6．1所示，求使总运费最少的调运方案。
运价系数表
最优调运方案
最低的总运费Z＝4350。
产地A：实际上只调运出200，多余的300只能贮存在原地或者不生产。
中转运输优化模型
1）问题的提出
①产地与销地之间没有直达路线，货物由产地到销地必须通过某中间站转运；
②某些产地既输出货物，也吸收一部分货物；某销地既吸收货物，又输出部分货物，即产地或销地也可以起中转站的作用，或者既是产地又是销地；
③产地与销地之间虽然有直达路线，但直达运输的费用或运输距离分别比经过某些中转站还要高或远。
存在以上情况的运输问题，统称为转运问题。
中转运输优化模型
2）约束分析与数学模型
解决中转运输问题的思路是先把它化为无转运的平衡运输问题。为此，作如下假设：
①首先根据具体问题求出最大可能中转量Q（Q是大于总产量的一个数）；
②纯中转站可视为输出量和输入量均为Q的一个产地和销地。
③兼中转站的产地Ai可视为一个输入量为Q的销地及一个产量为Q+ai的产地。
④兼中转站的销地可视为一个输出量为Q的产地及一个销量为Q+bi的销地。
在此假设的基础上，列出各产地的输出量，各销地的输入量及各产销地之间的运价表，最后用表上作业法求解。
中转运输优化模型
例2 转运问题，已知A1、A2和A3三个工厂生产同一规格的产品，用相同价格供应B1，B2和B3三个销售网点销售。有两个转运站T1、T2，并且产品的运输允许在各产地、各销地及各转运站之间相互转运。已知各产地、销地、中转站相互之间每吨货物的单位运价和产销量（见表6.4）,求合理的调运方案。
中转运输优化模型
中转运输优化模型
?解：将其化成一个等价的扩大运输问题，应做如下处理：
(1)将所有的产地、转运站和销地都作为产地，也作为销地。因此，整个问题成为有8个产地和8个销地的扩大的运输问题
(2)对扩大的运输问题建立运价表。对于没有运输路线的取任意大的正数M；对于自己给自己运输的，运价记Cij＝0。
中转运输优化模型
(3)所有转运站的产量等于销量，即流入量等于流出量。但事先又无法知道该数量的确切值，因此可以将调运总量(即总产量或总销量)作为该数值的上界。本题中调运总量为60t，取T1,T2的产量和销量均为60t。
(4)在扩大的运输问题中，原来的产地与销地由于也具有转运作用，所以在原来的产量与销量的数值再加上调运总量；同时原各产地的销量、原各销地的产量均取为调运产量。已知调运总量为60t，三个工厂的产量改为90t，70t，80t，销量均为60t；三个销售点的销量改为75 t，95 t，70 t，产量均为60 t。
三.多回路问题——节约里程法
?基本原理
?三角形两边之和大于第三边
?ΔL=L1+L2-L3
节约里程法
例题：由配送中心P向A-I等9个用户配送货物，图中连线上的数字表示里程（km），括号内数字表示用户需求量（t）。配送中心有2 t和4 t载货汽车，且汽车一次巡回走行里程不能超过35km ，设送到时间均符合用户要求，求配送中心的最优送货方案。
节约里程法
1、计算配送中心到各用户之间以及用户相互之间的最短距离，并列表
节约里程法
2、利用节约法计算出各用户之间的节约里程
节约里程法
3、根据节约里程表中节约里程多少的顺序，由大到小排列，编制节约顺序表。
节约里程法
4、根据节约里程的排序表和配送车的载重量（本题忽略容积因素）决定配送路径
节约里程法
?结果
?路径A：4t车,走行32km ,载重量3.7 t
?路径B：4 t车,走行31km,载重量3.9 t
?路径C: 4 t车,走行30km,载重量1.8 t
?总共行走里程93km,节约里程63公里
第三节配送线路设计
?合理配送路线制定原则
?行车路线和时间表制定方法
合理路线的制定原则
（1）安排车辆负责相互距离最接近的站点的货物运输。
卡车的行车路线围绕相互靠近的站点群进行计划，以使站点之间的行车时间最短。
合理路线的制定原则
（2）安排车辆各日途经的站点时，应注意使站点群更加紧凑
（3）从距仓库最远的站点开始设计路线
（4）卡车的行车路线应呈水滴状
（5）尽可能使用最大的车辆进行运送，这样设计出的路线是最有效的
（6）取货、送货应该混合安排，不应该在完成全部送货任务之后再取货
（7）对过于遥远而无法归入群落的站点，可以采用其它配送方式
行车路线和时期表的制定方法
?扫描法(The Sweep Method)
?节约法(The Savings Method)
扫描法(The Sweep Method)
①在地图或方格图中确定所有站点(含仓库)的位置。
②自仓库始沿任一方向向外划一条直线。沿顺时针或逆时针方向旋转该直线直到与某站点相交。考虑，如果在某线路上增加该站点，是否会超过车辆的载货能力?如果没有，继续旋转直线，直到与下一个站点相交。再次计算累计货运量是否超过车辆的运载能力(先使用最大的车辆)。如果超过，就剔除最后的那个站点，并确定路线。随后，从不包含在上一条路线中的站点开始，继续旋转直线以寻找新路线。继续该过程直到所有的站点都被安排到路线中。
③排定各路线上每个站点的顺序使行车距离最短。排序时可以使用“水滴”法或其他数学算法。扫描法
行车时间的制定
?例表6-7为某运输公司的线路时刻表，假设该公司的卡车型号和载重量均相同，请为该公司制定行车路线计划，使得在满足所有线路服务的条件下，所用车辆最少，车辆空闲时间最短。
行车时间的制定
行车时间的制定
解：将所有路线在一天时间内按照时间进行排序，就可满足条件。图6.2为排序结果，即为行车路线计划。
（资料素材和资料部分来自网络，供参考。可复制、编制，期待你的好评与关注）
蔬菜配送方案 背景：上海蔬菜配送有限公司主要提供以配送蔬菜、水果、冻品、调料、鲜猪、牛、羊肉、家禽、海鲜等农产品为主的全方位配送菜服务公司。是一家集送菜服务、营养配餐、食品购销及物流配送为一体全新商业模式的企业。本公司位于上海最大的农副产品批发市场，公司有丰富的货物资源，有专车和专业的配送团队！送菜的服务对象：专业为各大饭店、酒店、西餐厅、酒吧、火锅店，学校、医院、会所,KTV娱乐场所,企业食堂，各大超市等提供各种蔬菜水果调料冻品等农产品配送服务。 配送产品介绍： 水产有：澳龙、东星斑、老虎斑、右口鱼、多宝鱼、桂鱼、鲟鱼、斑节虾、草虾等上百个品种。 冻品有：银鳕鱼、三文鱼、大墨鱼、澳洲带子、驼鸟肉、驴肉、牛排、兔腿等几百个品种。肉类有：猪颈肉、赤肉、肉眼、粉肠、生肠、牛柳、牛林、牛展、羊肉等其他各部位的产品。家禽有：乌骨鸡、清远鸡、老母鸡、野鸡、野鸭、黑宗鹅、火鸡、大王鸽、飞龙等几十个品种 蔬菜有：广东介兰、广东菜心、广东豆苗、广东丝瓜、西洋菜、西生菜、迷迭香、罗勒叶、紫苏叶、黄圆椒、青节瓜等上海本地及全国各地的百余个品种。 水果有：猕猴桃、牛油果、哈密瓜、火龙果、青柠檬、青苹果、进口橙子、草莓、进口柠檬等.调料有：番茄沙司、黄油、奶酪、空心粉、卡夫奇妙酱、沙姜粉、孜然、白糖、食盐、黑胡椒粉、冰糖、卡夫芝士粉、吉士粉、韩国多味辣椒酱、保卫尔牛肉汁等几百个品种 订单：于2009-10-10日，收到北京华联超市的配送订单，如下： 品种质量标准数量（公斤）单价（公斤/元）总价（元） 上海青有机200 1.5300 菜心有机300 1.4420 白菜有机100 1.2120 要求：于10月15日送到北京华联超市。地址：北京市解放路113号。 配送方案 1、本次配送计划的因素的分析 客户服务策略： 北京华联超市是本配送中心的大客户，通过优质服务将其成为长期客户。主要针对于顾客抱怨处理问题。“处理顾客抱怨行为”是物流企业对服务失误的补救，其策略有：①建立服务补救预警系统。化解顾客抱怨的最佳时机是在事前，以预防为主，补救为辅，即在问题出现前预见到问题即将发生而予以避免。②鼓励和引导不满的顾客投诉。物流服务提供者要设计方便顾客投诉的程序，以鼓励和引导顾客投拆。还应鼓励不满意顾客中“沉默的大多数”说出他们的不满，利用这些信息发现潜伏的危机和问题的根源，及时改进。③快速解决问题。当发生服务失误时，企业作出反应越快，服务补救效果会越好。服务人员必须在失误发生的同时迅速解决，避免服务失误扩大并升级。
物流配送最优路径规划
关于交通运输企业物流配送最优路径规划的 研究现状、存在问题及前景展望 摘要：本文综述了在交通运输企业的物流配送领域最优路径规划的主要研究成果、研究存在问题及研究方向。主要研究成果包括运用各种数学模型和算法在运输网中选取最短或最优路径；从而达到路径、时间最优和费用最优；以及物流配送网络优化、车辆系统化统一调度的发展。今后研究的主要方向包括绿色物流，运输系统及时性和准确性研究等。 关键词：物流配送；最优路径；路径规划 Overview of scheme on Shortest Logistics Distribution Route in Transportation Industry Student: Wan Lu Tutor: Chen Qingchun Abstract: This paper reviewed of the optimal path planning about the main research results, problems and direction in the field of transportation enterprise logistics distribution. Main research results include using various mathematical model and algorithm selection or optimal shortest path in the network. So we can achieve the optimal path, the shortest time and minimum cost. At the same time, logistics distribution network optimization, the vehicle systematic development of unified scheduling are the research issues.The main direction of future research include green logistics, transportation system accurately and timely research and so on. Key words: Logics Distribution; Optimal Path; Path Planning 引言 物流业在我国的新兴经济产业中占据了重要了地位，称为促进经济快速增长的“加速器”。而物流配送作为物流系统的重要环节，影响着物流的整个运作过程以及运输企业的发展趋势和前景。采用科学、合理的方法来进行物流配送路径的优化，是物流配送领域的重要研究内容。近年，国内外均有大量的企业机构、学者对物流配送中最优路径选择的问题，进行了大量深入的研究，从早期车辆路径问题研究，到根据约束模型及条件不断变化的车辆最优路径研究，以及随着计算机学科的发展而推出的针对物流配送路径最优化的模型和算法等方面，都取得丰硕的学术成果。但是对于绿色物流配送的研究仍然不足。鉴于物流配送最优路径研究的重大理论意义和实践价值，为对我国物流配送的效率水平有一个系统的理解和把握，有必要对现有成果进行统计和归纳。本文尝试对我国运输企业物流配送最优路径规划进行探讨，以期为今后做更深人和全面的研究提供一定的线索和分析思路。 1 国内外研究现状 1.1 国内研究现状 1.1.1 主要研究的问题
西南财经大学天府学院 2011 届 期末论文（设计） 论文题目：物流节点规划之优化配送路线 学生姓名：×××× 所在学院：西南财经大学天府学院 专业：物流管理 学号：×××× 指导教师：×××× 2010 年 6 月
摘要 最近几年，有很多的连锁超市在我国各地迅速发展起来，连锁超市之间的竞争也愈演愈烈。连锁超市要在激烈的竞争中取得优势，就必须改进物流现状，重视配送中心的作用，降低物流成本，从而降低整个运营成本。在物流配送中，为了达到高效率配送，做到时间做少，距离最短，成本最低，就必然要求选择最佳配送路线和车辆的综合调度，本文介绍了节约里程法在内江红旗连锁超市物流配送中心配送中的实际运用，以求选择最佳配送路线和车辆的综合调度。 关键字：配送路线；连锁超市；节约里程法；距离
Abstract In the recent years, there are a lot of supermarket chains developed quickly in our country, the competition between the supermarket chains is very strong.If supermarket chain want to get the advantage in the competition, they must improve their logistics present situation, pay more attention to the role of the distribution center, reduce logistics cost to reduce the operation cost.In the logistics distribution. in order to achieve efficient distribution, the shortest distance, the lowest cost, it have to ask to choose the best distribution line and comprehensive control of the vehicle, this paper introduces that the mileage method is used for the Neijiang Red flag supermarket chain logistics distribution center, in order to n choose the best route and the vehicle distribution of comprehensive control. Key word: Distribution Route；Supermarket Chain；Saving Algorithm；Distance
关于交通运输企业物流配送最优路径规划的 研究现状、存在问题及前景展望 摘要：本文综述了在交通运输企业的物流配送领域最优路径规划的主要研究成果、研究存在问题及研究方向。主要研究成果包括运用各种数学模型和算法在运输网中选取最短或最优路径；从而达到路径、时间最优和费用最优；以及物流配送网络优化、车辆系统化统一调度的发展。今后研究的主要方向包括绿色物流，运输系统及时性和准确性研究等。 关键词：物流配送；最优路径；路径规划 Overview of scheme on Shortest Logistics Distribution Route in Transportation Industry Student: Wan Lu Tutor: Chen Qingchun Abstract: This paper reviewed of the optimal path planning about the main research results, problems and direction in the field of transportation enterprise logistics distribution. Main research results include using various mathematical model and algorithm selection or optimal shortest path in the network. So we can achieve the optimal path, the shortest time and minimum cost. At the same time, logistics distribution network optimization, the vehicle systematic development of unified scheduling are the research issues.The main direction of future research include green logistics, transportation system accurately and timely research and so on. Key words: Logics Distribution; Optimal Path; Path Planning 引言 物流业在我国的新兴经济产业中占据了重要了地位，称为促进经济快速增长的“加速器”。而物流配送作为物流系统的重要环节，影响着物流的整个运作过程以及运输企业的发展趋势和前景。采用科学、合理的方法来进行物流配送路径的优化，是物流配送领域的重要研究内容。近年，国内外均有大量的企业机构、学者对物流配送中最优路径选择的问题，进行了大量深入的研究，从早期车辆路径问题研究，到根据约束模型及条件不断变化的车辆最优路径研究，以及随着计算机学科的发展而推出的针对物流配送路径最优化的模型和算法等方面，都取得丰硕的学术成果。但是对于绿色物流配送的研究仍然不足。鉴于物流配送最优路径研究的重大理论意义和实践价值，为对我国物流配送的效率水平有一个系统的理解和把握，有必要对现有成果进行统计和归纳。本文尝试对我国运输企业物流配送最优路径规划进行探讨，以期为今后做更深人和全面的研究提供一定的线索和分析思路。 1 国内外研究现状 1.1 国内研究现状 1.1.1 主要研究的问题 国内对于物流配送的研究内容，概括提炼为物流配送中心选址，系统内部作业与管理，
第八章运输及配送路线的优化 教学目的：使学生理解各种运输方式的特点及运输方式选择的原则，掌握运输方式选择的定量分析法，理解存在中间运转的物资调配方法，掌握旅行 商问题和中国邮递员问题的解法以及扫描法和节约法。 基本要求：1、理解各种运输方式的特点； 2、掌握运输方式选择的定量分析法； 3、理解存在中间运转的物资调配方法； 4、掌握旅行商问题和中国邮递员问题的解法。 教学重点：扫描法、节约法 教学时数：6学时 第一节运输方式的选择 ?运输方式选择的原则 当同时存在多种运输方式可供选择的情况下，就需要进行选优抉择。通常根据各种运输方式的经济特性和服务特征来选择合适的运输方式，即主要依据运输成本、运输速度、可靠性、安全性等指标进行判断和选择。 安全性原则——首要的原则 及时性原则 准确性原则 经济性原则——主要原则 货物运输的六大方式： 根据运输工具的不同，可分为：水路、公路、铁路、航空、管道和多式联运等运输形式。 在各种运输方式中，如何选择适当的运输方式是物流合理化的重要问题。可以选择一种运输方式也可以选择使用联运的方式。 运输方式的选择，需要根据运输环境、运输服务的目标要求，采取定性分析与定量分析的方法进行考虑。 ?运输方式选择的定性分析法 定性分析法主要是依据完成运输任务可用的各种运输方式的运营特点及主要功能、货物的特性以及货主的要求等因素对运输方式进行直观选择的方法。 1.单一运输方式的选择 单一运输方式的选择，就是选择一种运输方式提供运输服务。公路、铁路、水路、航空和管道五种基本运输方式各有自身的优点与不足，可以根据五种基本运输方式的优势、特点，结合运输需求进行恰当的选择。 一般要考虑的因素是：
车辆路径问题VRP（Vehicle Routing Problem），又称车辆调度问题，通常可以描述为：对一系列装货点和卸货点，组织适当的行车路线，使车辆有序地通过它们，在满足一定的约束条件（如货物需求量、发送量、交货时间、车辆运量限制、行驶里程限制、时间限制等）下，达到一定的目标（如路程最短、费用最少、时间尽量少、使用车辆台次数尽量少等）。对这个问题的研究比较多，现在还是许多物流专业大学生毕业设计的热门题材。 当前，解决VRP问题已经很少靠手工操作了，基本都是在TMS中有相应的模块，输入基础数据后直接得出推荐的最优路线。总结起来，解决VRP问题的常规方法，主要包括以下这些。 一、定性方法。主要有经验判断法，综合评价法。这些方法配以GPS导航，可用性还是比较强的，起码王二的仓库里主要就是这么用的。 二、定量方法 1、货物调拨规划 指的是当一个企业的产品有多个供应商和多个市场时，需要决定产品从不同供应地到不同市场的分拨方案，即如何在多个供应地和多个需求地之间合理调配货物，在满足需求的前提下实现总运输成本的最小化。可采用的方法包括：图上作业法、表上作业法（西北角法、闭回路法、位势法等）。 2、车辆路径优化 （1）单一车辆配送 一般以行车时间最短、距离最短或费用最小为优化目标，也称为最短路径问题，通常采用的方法有：多阶段动态决策法、Dijkstra方法、旅行商问题模型、中国邮递员问题等。 （2）多车辆路径问题 一般描述为：某仓库要为多个客户提供服务，已知每个客户的地理位置及货运需求量，仓库需要调用多辆货车来满足这些客户的需求，每辆汽车的载重量一定，要求确定为这些客户提供服务的货车数量，并为每辆车分配一定的服务客户；同时，确定每辆车的行驶路径（或服务顺序），使总成本（如距离、时间等）最低，可以采用的方法包括：扫描法、里程节约法等。 当然了，随着AI技术的兴起，一些更智能的方法已经应用于实际工作中，比如模拟退火算法、禁忌搜索算法、遗传算法、蚁群算法和神经网络方法等。
实训0501：配送线路优化设计实训 实训目标： 1、能根据给出的配送中心与单个客户之间的路线图及图中各节点之间的综合成本数值， 找到配送中心与单个客户之间的成本最小路线并计算出此路线成本的数值。 2、能够在配送中心现有送货车辆能力及实际送货成本限定的前提下，规划出配送中心 往各个客户送货综合成本最低的送货网络路径图。 实训内容： 1、某配送中心与某单个客户之间成本最小路线规划及最小成本数值计算 2、在配送中心现有车辆送货能力及车辆单趟送货成本有限定的前提下，为配送中 心向多个客户送货规划若干条送货线路，并使各条线路的总成本数最小。 环境要求：普通多媒体机房教室 情境描述： 实训第1部分情境：某连锁超市的配送中心位于城市边缘的郊区，但超市的一家门店位于繁华的城市中心区，因此负责送货路线规划的计划调度员要规划出配送中心到这个门店的送货成本最低的路线。最初按交通图所示里程最短的线路进行送货，见下图： 图中O代表配送中心，A代表门店，V1—V4代表要经过的关键节点（如主要道路的交叉路口、立体交叉互通枢纽等），连线边上的数值代表每一路段的里程，图中绿线连接的O-V1-V4-A为里程最短线路。 但很快发现里程最短并不意味着成本最低，因为里程最短这条路有一条新建的大桥（图中V4点与A点之间黑色加粗部分）来回都要收取通行费，这条路是城区主干道且建成时间较长通行条件较差，越往城中心走道路拥堵越严重，每趟送货产生的油耗、车辆送货时间占用、送货人员工作时间等综合成本超出了正常水平，并且多次发生没按门店的要求时间送达的情况。因此计划调度员对每一条能从O到A的线路都进行了实地勘察记录，并综合考虑每条送货线路的里程、时间、车辆耗损，得出了每条线路每一个路段的送货运行成本，汇总出了一张从配送中心到此门店的送货路径数据图。现在计划调度员要依据此图，找出配送中心与该门店之间送货成本最低路径。 实训第2部分情境：该配送中心除为该门店送货外，还为其他地区的9个门店送货，按照实训第1部分的方法，计划调度员找到了配送中心到每个门店的成本最低线路，但配送中心的送货资源有限，不能为每个门店单独送货，只能一辆车一趟为几个门店循环送货。这样从一个门店到另一个门店之间也要找到成本最低的线路，因此同样采用实训第1部分的方法，找到了两两门店之间的成本最低线路并计算出了数值。现在，计划调度员要规划从配送中心出发为各个门店循环送货后最终回到配送中心的送货路线总规划图并且总送货成本要
第四章运输决策与配送路线规划 本章主要内容 运输模式选择 运输线路优化模型 配送线路设计 第一节运输模式的选择 一.运输模式的特点 常用的运输方式有 铁路 公路(整车发运、零担货运) 包裹运输 空运 水运 运输模式的特点 1.铁路运输： 高额的固定成本及低廉的运营成本。 运输价格主要取决于运量与运输距离。 缺点是时间较长，所以一般适合于大规模、低价值、对时间要求不敏感的产品。 铁路运输的主要目标是充分提高机车、车组人员的利用率。 2.公路运输： 包括整车发运(TL)与零担货运(LTL)两种。 整车发运按照整车收费，不考虑货运量，费率随运输距离的不同而改变。 零担货运则按照运输量与运输距离来收费。 运输模式的特点 3.包裹运输 利用空运、铁路或公路运输方式为顾客提供时间敏感的小件货物的运输。 主要运输对象是小件、对时间非常敏感的货品，其收费标准较昂贵。 4.空运 基础设施及装备方面的固定成本很高，劳动力与燃料耗费主要取决于航线，与一次飞行运载的乘客量与货物重量无关。 运输模式的特点 就货物量的大小而言，铁路、水路的批量最大、空运的批量最小； 就运输速度而言，空运速度最快、水路运输速度最慢； 就运输成本而言，一般来说，水路运输的成本最低、空运最高； 就服务响应时间而言，水路最慢、空运最快； 就运输引起的库存成本而言，铁路、水路最高，空运最低。 进行运输决策时，要综合考虑上述因素，进行成本分析，确定最佳方案。 二. 库存与运输决策 就不同的运输模式而言，其对库存的影响有以下几点： (1) 较慢的运输模式会引起较大的中转或运输库存。 (2) 较大运量单位的运输方式会出现订单批量超过当前需求量的情况，出现不需要的库存。 (3) 较慢的运输模式会引起安全库存的提高。
9 摘要：物流配送网络最短路线的规划不仅能提高商品运输效率，还能节约时间成本和运输成本。本文根据物流配送最短路线规划的现状，利用最小生成树法对现有问题进行分析。通过资料整合、建立实例模型、使用Kruskal算法建立模型、比较权值大小并用canvas画布显示最终路径图形等过程，得出物流配送网络的最佳路径，最后用Java实现整个模型，得出最短路径和最低时耗方案。 关键词：最小生成树；Kruskal算法；物流配送中心；最短路径规划 引言 电子商务作为一类崭新的商业模式，与传统商业模式下配送中心不同的是，电子商务时代下的配送中心往往需要提供送货上门的服务，这也成为了一笔额外的支出，因此，规划出合理的路线图也是很重要的。目前关于物流配送网络问题，研究方法主要有运筹学的应用、仿真技术评价方法、遗传算法等。研究也主要集中于解决时间最优和配送中心最优选址的问题，研究成果主要有：2013年，赵慧娟、汤兵勇、张云在《基于动态规划法的物流配送路径的随机选择》提出在基本的动态规划算法基础上，结合物流配送的路径选择问题，引入配送途中道路的拥堵因子，随机修正配送路径的相应权值，动态调整选择配送路径。2015年，朱金凤在《基于成本约束的冷链物流配送网络规划》中提出了“服务半径”的概念，将物流节点的配送时耗转换为物流节点的服务半径，并最终通过一系列的约束条件来表示决策变量之间的关系。2015年，钮亮、张宝友在《基于云计算求解城市物流配送最短路径研究》中提出了基于Map Reduce的并行算法和GIS仿真结合的求解方法。虽然目前解决物流配送最短路径规划的方法有很多，但是也存在着一些不足之处。本文基于目前的研究成果，采用Kruskal算法构建物流配送网络最短路线规划模型，并用实例进行了验证。 1、物流配送最短路线规划相关算法简介 目前关于最短路线的主要研究方法有整数线性规划法、Dijkstra算法、Floyd- Warshall算法、遗传算法、Bellman-Ford 算法、蚁群算法等。 Dijkstra算法利用起点为中心，向外层层扩展，最终求解出最短路径。但是，Dijkstra算法只适用于权值非负的情况，当权值为非负的时候，就不再适用了。Floyd-Warshall算法解决了弧长必须非负的问题，但是面对只需从一个顶点到其他各个顶点最短距离的问题时，Floyd-Warshall算法的时耗非常长。遗传算法，原理来自于生物界优胜劣汰的进化规律，是一种随机化搜索的方法。首先通过对问题的参数集进行编码，随机产生一个种 物流配送网络最短路线规划 文／刘婷婷 于卫红 群，计算适应函数和选择率，进行选择、交叉、变异操作，直到满足迭代收敛条件为止。受启发于蚂蚁在寻找食物过程中的路径的行为的蚁群算法，具有分布计算、信息正反馈和启发式搜索的特征，本质上是进化算法中的一种启发式全局优化算法。 此外，近年来还提出了一些新的算法，比如，基于最短路径的局部随机游走方法、求解点到点的最短路径的高效下界算法以及在路网上检索k近邻的基于预处理的近似算法等。 Kruskal算法相对于以上算法简便、易于实现，对解决结点比较少的情况，执行效率高。因此，本文用Kruskal算法构建模型研究了大连海事大学邮件收发中心快递配送的最短路径规划问题。 2、基于Kruskal算法的最短路线规划模型 Kruskal算法的主要思想是从源结点开始，按路径长度递增的次序，依次找结点到源结点的最短通路，从而产生最短路径。 使用该算法对物流配送网络最短路线进行规划主要遵循如下步骤： （1）初始化顶点：给所有顶点编号，并将顶点序号存储在顶点数组之中。将图的信息按照起点、终点、权重的顺序存储在结构体数组edge中（如公式1所示）。 edge .start = start ；edge .end = end ；edge .weight = weight (公式1) （2）权重排序：将所有权重按照从小到大的顺序排序，并设置临时变量存储最小权重，式中edge [edge.si z e ()].weight 表示带权路径图的所有权值（如公式2所示）。 Minweight =min{edge [edge.si z e ()].weight } (公式2) 图1 Kruskal算法流程
物流配送中的最优路径规划模拟 软件说明书 学校：武汉轻工大学 院系：数学与计算机学院 专业：信息与计算科学 指导教师：王防修 小组名称：一苹微歌 小组成员：胡鹏程新强彭肖飞日期：_____年______月_____日
目录 1引言-----------------------------------------------------1 2算法思路-------------------------------------------------2 3总体设计------------------------------------------------15 4系统出错处理设计----------------------------------------17 5客户数据生成模块设计说明--------------------------------18 6行车路径最短模块设计说明--------------------------------18 7行车时间最短模块设计说明--------------------------------19 8解决堵车问题模块设计说明--------------------------------20 9未解决的问题--------------------------------------------21 10参考资料-----------------------------------------------21
1引言 1.1编写目的 在B2C农产品电子商务物流配送时，物流车装载当日需要配送的货品从仓库出发，按照事先规划好的最优配送路径为每一个客户进行配送，最后返回仓库。物流配送模拟系统就是在配送之前需要根据客户的配送地址间线路间距、经验路况做分析计算出一条最优配送路径。在配送过程中，如果某路段堵车，物流配送模拟系统需要动态调整配送路线。 1.2背景说明 设计一个物流配送中的最优路径规划模拟软件，解决物流配送过程中路程最短，时间最短以及堵车后重新规划等问题，并在软件的界面上模拟车辆的运行。随着市场经济的发展和物流技术专业化水平的提高，物流配送业得到了迅猛发展。配送路径的选择是否合理，对加快配送速度、提高服务质量、降低配送成本及增加经济效益都有较大影响。配送路径的优化问题是物流配送系统的一个主要问题，物流配送路径的优化就是以最低的运营成本，最快捷的响应速度、最短的配送运输时间，把货物运至用户手中，而后两个指标与第一个指标之间存在着一定的制约关系，无法达到全体的最优，因此严格地讲，这是一个多目标的优化问题。 1.3定义 T S P（Traveling Salesman Problem）:旅行商问题 Backtrack：回溯
龙源期刊网 https://www.doczj.com/doc/b59963084.html, 智慧物流中的最优配送路径规划问题 作者：杨春 来源：《环球市场》2019年第10期 摘要：随着国家对智慧城市的大力发展，智慧物流作为智慧城市发展中的一部分，有着很大的作用，通过发展智慧物流，可以极大的提高物流效率，降低物流成本，加速产业的发展。 关键词：智慧物流；最优路径规划 慧物流首次由IBM提出，并在2009年12月由中国物流技术协会信息中心、华夏物联 网、《物流技术与应用》编辑部联合提出概念。随着信息技术快速发展，中国的智慧物流也受到了极大的影响。“智慧物流”是指通过智能硬件、物联网、大数据等智慧化技术与手段，提高物流系统分析决策和智能执行的能力，提升整个物流系统的智能化、自动化水平。通过智慧物流，在以下几方面会带来极大的进步：（1）降低物流成本，提高企业利润；（2）加速物流产业的发展，成为物流业的信息技术支撑；（3）节约消费者的购物成本，让消费者放心；（4）可以提高社会各部门工作效率，尤其是提高政府部门工作效率。分析物流的最优路径是发展智慧物流中极为重要的一部分，可以极大的节省配送成本，提高配送效率。 一、智慧物流管理系统配送系统概述 智慧物流管理系统主要是借助互联网、物联网、计算机云计算等先进技术，更加科学、有效地进行管理，将物流系统各要素，如运输、存储、配送、信息反馈等信息进行收集更新，制定最优的配送方案，或遇紧急事件能够及时反馈信息并调整方案，实现整个物流管理的时效性及快捷性，进而对物流管理进行革新。智慧物流的快速发展，与计算机技术的进步密不可分。通过计算机信息技术的应用，可以将物流系统的管理进行优化创新，信息传输更加便捷，减少人力资源的投入，进而实现整个物流体系的优化利用，促进物流管理技术的全面提升。智慧物流配送系统通过大数据与人工智能技术的应用，可以快速实现订单分派，并对每一笔订单的情况进行监控，出现异常立即进行报警，实现配送过程中对车辆运输的全程跟踪，对订单的整体流程进行信息化的维护，保证客户对物流服务过程的知情权，便于物流企业更好地对业务处理情况进行考核，实现整个物流配送过程的优化管理，节省人力物力，达到资源的有效利用并提升作业效率。 二、智慧物流管理系统配送系统建立基础 智慧物流管理主要依托电子信息技术，其中地理信息技术的应用是配送的基础。物流配送区域主要集中在市区，道路结构复杂，众多道路容易出现拥堵，可供选择的路径较多，通过地理信息系统进行良好的路径优化，可以最大限度的提升物流配送的效率，减少配送时间和成本。传统配送方法通常依靠送货员经验进行选择，对于复杂的城市道路和实时的交通运输情况来讲适应性不足，造成配送效率差，成本也较高。特别是现在城市交通问题日益突出，在更短