（管理科学与工程专业论文）基于最短路径算法的物流配送方案优化研究.pdf

原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进 行研究所取得的成果。除文中已经注明引用的内容外，本论文不包含任何 其他个人或集体已经发表或撰写过的科研成果。对本文的研究作出重要贡 l 献的个人和集体，均已在文中以明确方式标明。本声明的法律责任由本人 承担。 论文作者签名：啦一 日期：二盟立虹 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学校保 留或向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅 和借阅；本人授权山东大学可以将本学位论文的全部或部分内容编入有关 数据库进行检索，可以采用影印、缩印或其他复制手段保存论文和汇编本 学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：驻导师签名： 山东大学硕士学位论文 摘要 物流业的发展成为国民经济的一个新的增长点，作为企业的“第三方利润源”， 科学合理的物流业是经济可持续发展的重要部分，而其中物流的存储和配送实现 信息化不仅仅是压缩物流成本的有效途径，更是社会经济协调发展的一个重要体 现。本文在对国内外物流现状进行评述的基础上对目前实际操作人员较难解决的 线路优化问题及其算法进行了较深入的研究，引入并介绍了( 有时间窗) 车辆配 送路径优化问题( t h e t a b u s e a r c h a l g o r i t h m f o r t h e p r o b l e m w i t h t l m e w i n d o w s ) 的算法设计出一种普遍适用的线路配送问题优化方案，尽管方案在具体的实施过 程中仍然要做相应的调整，但相对于当前该方向研究的深度而言，该系统不失为 较为全面而科学的全新研究。通过对一定的数据检测得出较其他方案更为优化的 检测结果，并作了相应的对比分析。 基于一定的数学理论与管理实践相结合的能力上，作者做了尽可能的数学语 言的可应用性描述，把一些算法本身进行了简单的程序语言描述，结合作者自身 的知识背景明确了一些数学研究与管理实践结合较为困难的问题。通过借鉴国内 外相关研究的成果加以创新从而确立了属于本文独有的算法，并对该算法的几个 重要环节作了进一步的探讨。 关键词：配送线路 优化可达迭代算法时间复杂度 、#， 山东大学硕士学位论文 a b s t r a c t t h ed e v e l o p m e n to fl o g i s t i c sh 鹪g r o w nt h en 删p o 硫o fg r o w t h a st h e e n t e r p r i s e ”t h e3 r dp a r t yp r o f i t $ o b r c c ”，s c i e n c ea n dr e a s o n a b l el o g i s t i c si n d u s t r yi s i m p o r t a n tp a r to ft h ee c o n o m i c a l s u s t a i n a b l ed e v e l o p m e n t t h ei n v e n t o r ya n d d i s l f i b m i o na r ei m p o 姗tp 矾船 t h i sa r t i c l ei n t e g r a t e st h ed i f f i c u l tq u e s t i o n ：t h er o a da n da l g o r i t h m , w h i c hi s d i f f i c u l t yf o rs o m ep e o p l e t h e nw ec a r li n v e n taw i d e s p r e a da p p l i c a t i o nn e wp l a n , b u t i ts h o u l db ea d j u s t e di na p p l i c a t i o n i ti ss t i l lan e ws c i e n c er e s e a r c hc o n t r a s tt ot h e o t h e rr e s e a r c h t h i sa r t i c l ep a y sm o r ea t t e n t i o nt ot h et a b us e a r c ha l g o r i t h mf o rt h e p r o b l e mw i t ht i m ew i n d o w sa n dn o w a d a y ss i t u a t i o n b a s e do ns o m ed a t ao ft h ep r a c t i c ew cc a nc o n c l u d es u p e r i o rp l a nt h a nt h eo t h e r , a n dt h i sa r t i c l ea n a l y z et h e s ed a t a t h ea u t h o rd o e sh i sb e s td e s c r i b et h ea l g o r i t h mi t s e l fb a s e do nt h eb a c k g r o u n do f m a t h e m a t i c sa n dm a n a g e m e n t i ta l s or e f e r e n c et ot h ec u r r e n tr e s e a r c ha l lo v e rt h e w o r l d a n db r i n gf o r t hn e wi d e a si nt h i sf i e l d h o wt oo p t i m i z et h ed i s t r i b u t i o nr o a d s 棚ln e e do u gc o n t i n u er e s e a r c h k e y w o r d s ：d i s t r i b u t i o nr o a do p t i m i z a t i o n r e a c h a b l em a t r i xt i m ec o m p l e x i t y 4 ! ? 0 山东大学硕士学位论文 第一章导言 1 i 选题背景 中国经济在经过了十几年的高速发展后，我们对经济发展的认识也由以前追 求数字的增加成长为更为理性的追求内涵的增长。如何切实提高我国经济发展的 质量，从而做到在可持续发展基础上的高速增长成为举国关注和探讨的热点。无 论是从宏观角度还是从微观角度看，物流都是贯穿国民经济发展始终的重要方面， 文章着眼点就是物流环节的成本如何有效降低的问题。 物流业作为新的经济增长点，在国民经济中占据了重要的地位。我国物流成 本近几年一直徘徊在占g d p 的2 0 0 以上，这其中运输、存储成本分别占到物流 总成本的5 7 1 、3 1 8 嘣d ，而国外发达国家物流成本占g d p 的比重基本上稳定在 1 0 左右。因此，在存储、配送的环节上进行深入地研究是降低物流成本并且合 理规划我国物流园区未来发展方向的基础工作。表1 1 从统计数字上说明了我国 从经济高速发展的9 0 年代以来物流成本的构成和占到g d p 的比重： 表1 - 1 ：1 9 9 1 年以来物流总费用占g d p 比重( ) o 年份运输费用保管费用管理费用杜会物流总费用 1 9 9 l1 3 37 53 22 4 0 1 9 9 21 2 77 23 12 3 0 1 9 9 31 3 o 6 73 1 2 2 8 1 9 9 41 1 97 ，o3 22 2 1 1 9 9 51 1 o7 63 42 2 ，o 1 9 9 6 1 1 2 7 ，53 3 2 2 0 1 9 9 71 1 07 73 52 2 3 1 9 9 81 1 o6 8 3 5 2 i 4 1 9 9 91 1 66 23 62 1 4 2 0 0 01 1 26 53 ，62 i 2 2 0 0 i1 1 26 4 3 5 2 1 1 2 0 0 21 1 66 43 42 1 5 2 0 0 31 2 r o6 33 12 1 4 2 0 0 41 2 16 23 o2 i 3 2 0 0 5 年l 9 月l l ，46 53 o2 0 9 从表l - 1 可以看出，我国整体物流成本在g d p 中所占据的比重有逐年下降的 中国物溉信息中心，2 0 0 4 年 中国物流与采购联合会，2 0 0 5 年 山东大学硕士学位论文 趋势，这种趋势是符合经济发展要求的，但总体上仍然超过2 0 ，相对于上面提 到的国外1 0 左右的比重是很高的。 我国物流整体规划的现状令人堪忧，其中“中外物流的差异不是在硬件上。 而是需求的差异，要改变这种状况，需要一段时期的市场培育”国。首先政府要起 到引导作用，中国企业有跟国情相关的中国企业的需求，政府可借鉴的是国外在 政策、规划制定i ； 的“调查分析”。目前缺少的是“定量分析”，即中国企业在物 流方面的需求到底是什么? 中国企业的物流成本到底有多少? 没有量化的数据可 供参考，也就难于制订出详细的、可操作性的政策规划。随着信息化在日常生活 中的不断渗透，物流也不仅仅是直观意义上的物资的存储和运输，而是更为合理 的供应链环节上源与下游沟通和合作的。信息枢纽”。 1 2 论文研究的意义 1 2 1 论文研究的理论意义 随着经济全球化的不断深入，许多跨国公司都已经或计划将制造、采购中心 转移到中国，越来越多的国内企业也开始面向全球进行生产和经营，中国作为世 界制造中心的地位日益凸显。这种大的国际环境更加刺激了我国物流业的高速发 展。与此同时，国家经济建设的深入和商业活动的繁荣刺激了市场对物流服务需 求的激增：一方面表现在社会物资流通总量高速增长，呼唤更优化的快递物流解决 方案和专业的物流咨询服务；另一方面则是越来越国际化的商业运作要求物流服 务水平跟上国际化标准，在速度、可靠性、安全性、个性化、战略远见等方面提 出了更高要求。因此，通过降低物流成本，使得物流业的开展更加科学合理并进 而通过开展服务创新，提升服务质量已经成了广大物流服务供应商的共识。 本文着重从配送环节中的线路选择入手，分析如何优化调整配送线路问题， 进而达到降低物流成本的目的。 总体而言，国内外配送路线相关领域的理论研究在近些年发展较为缓慢，在 算法上缺少创新，“理论研究的枯燥和当前急功近利思想的驱动使得从事该领 域研究的动力相比较( 以前) 而言已经令我们理论工作者汗颜”o 。因此，总结 前人研究成果，结合当前经济领域发展的实际情况，有必要进行理论与实践的双 重探索。文章就是从实践中所共同体现出来的问题出发，着力进行线路优化算法 邬跃，北京物资学院教授 6 山东大学硕士学位论文 的研究，力求在理论和方法上得到突破性的尝试。 无论是最短路径法还是有特定约束的线性规划问题都是运输问题发展的经典 方法，在交通和物流配送发展过程中发挥了其重要作用，而理论的发展要基于物 流和交通实践的应用，要引导和适合实际的应用，就要有相应的理论创新和提出 新的构想应对当前出现的新要求。当然，正如部分专家所言“经典算法之所以经 典，就在于其本身对问题解决铺就了最直接的道路” 。所以，文章基于传统的经 典理论，结合实际应用中的新情况设计出一类新的算法方案，以供有相关需求的 开发商或理论研究者从方法上加以借鉴。 1 2 2 论文研究的现实意义 很多物流公司所作的物流发展可行性报告、物流配送路线规划等等都是接一 个做一个，还没有成熟的属于自己的理论基础和一整套方法，因而在给企业物流 部门或者物流企业所作的软件产品往往是比较零碎的产品。 存储和运输线路分析是物流研究工作的重点，在供应链的各个环节中，物流 是连接整个供应链从而形成价值链的一条。红线”。它不仅涉及运输，更有财务、 资源调配、人员管理等各项工作。所有的工作目标是实现企业及社会效益的最大 化这不仅是物流企业的目标也是一种社会责任，更是实现物流作为“第三利 润源”的具体操作的表现。在我国物流成本居高不下、经济需要快速而健康发展 的前提下，如何更合理压缩企业成本、提高企业利润，从而提高我国企业在国际 市场中的竞争力是摆在我们面前的一个难题，更是物流研究者的责任。 实际生活中的布点以及所谓的线路问题是包含很多个配送节点( 如烟草配送 和小件物品的运输在一个城市或地区都很可能是几千上万个点) ，这就牵涉到用什 么样的模型来解决这上万个点之间的关系在某烟草集团配送中，所在市区有一 万多个配送节点，所采用的节约里程算法在对这上万个点进行线路的仿真运算中 花去了计算机l o 天的时间! 而把整个城市进行简单的划分两片之后也用去了l 天的时间。如果说划片可以使问题简单化，那么这个方法本身就使得问题出现漏 洞：这种划片已经破坏了线路是在整个城市随机行走的前提了，实际上追求的是 局部最优而不是配送系统的整体最优。在自上而下的信息化要求中这种软件的开 发是不科学的，也就是说这是一种失败的解决问题方法，总结一下国内外相关研 菲尔兹奖得主、美国科学院院士。中周科学院外籍院士丘成桐教授( p r o s 工y h u ) 7 山东大学硕士学位论文 究成果，进而根据我国物流发展的具体情况高效的算法进而开发出适用的应用软 件是当前这方面研究的一个突破口和难点，很有研究的价值。而这一切工作的目 的只有一个：降低成本，增加社会经济运营的效益。g d p 的2 0 0 , 6 以上是耗费在物 流上，而这里面的一半以上又是在运输成本上，因此。设计科学合理的运输方案 从而达到降低运输成本的目标，是一项既有理论价值又有现实意义的工作。 山东大学硕士学位论文 第二章物流系统发展研究现状及理论综述 2 1 国内发展及研究现状 2 1 1 我国物流发展现状 2 0 0 4 年温家宝总理所作的政府工作报告明确指出：要重视经济结构的合理发 展，以提高经济发展的质量，。投资总规模保持合理水平，投资效益得到提高，要 按照走新型工业化道路的要求”函因此从国民经济发展大局出发，提高经济效益 是作为个体单位的行业企业要长期谋求的发展观，这其中科学合理发展社会生产 中的物流业是重要一环从1 9 9 8 年起，我国各地( 尤其是工业城市) 相继开始了 物流园区规划，一些大的工业企业也开始建立属于自己的物流公司( 完全控股公 司) ，这既是政策扶持的一个明显信号，也是我国工业企业对物流成本降低在企业 整个发展过程中的重视。无论是物流企业还是企业物流，当前物流基地的规划向 专业化方向发展是一种必然，更是社会分工的根本体现，专业化物流规划及运输 不仅仅是一种规模经济的客观要求更是合理化建设的必然趋势。 2 1 1 1 物流发展的优势及成果 l 物流需求快速上升，增幅明显高于经济增长 国内外物流发展的经验表明，物流发展与一个国家的经济总量成正比，与一 个国家的经济发展水平成正比。二十世纪九十年代以来，我国经济持续快速发展， g d p 年均增长约1 0 ，2 0 0 2 - - 2 0 0 5 年我国g d p 增长速度分别为8 、9 4 、9 5 和9 9 0 , 4 ，经济总量居世界第四位去年g d p 增幅将达到8 5 ，从而构成了强大 的物流需求。 2 物流需求弹性逐年增高，经济增长越来越依赖于物流的发展 从经济发展与物流需求的关系上看，1 9 9 1 年2 0 0 2 年每亿元g d p 带动的物 流需求平均为1 7 3 亿元。“八五”期间平均为1 5 7 亿元：。九五”期间上升到1 7 l 亿元；“十五”期间进一步上升到2 8 亿元，物流需求弹性系数1 2 年问的平均值 为1 4 ，“八五”时期平均为1 2 6 ，“九五”时期平均为1 3 5 ，。十五”时期约在2 左右，这说明我国国民经济每增长1 个百分点，将拉动物流总值增长2 个百分点。 温家宝，政府工作报告，2 0 0 4 年 ， 山东大学硕士学位论文 这些数据均呈上升趋势，反映出我国的物流需求伴随经济增长是同步发展的。也 说明经济发展对物流的依赖程度越来越高。 3 工业品物流总值比重最大，增幅最高 2 0 0 3 年，工业品物流总值达到2 5 万亿元，占社会物流总值的8 4 6 1 9 9 1 年至2 0 0 2 年，工业品物流总值平均增长2 2 ，2 0 0 3 年增长2 7 2 ，是物流需求 增长最快的行业。这与我国处在工业化发展中期、工业化加速发展是相适应的。 这也说明工业加工制造业物流仍将是今后我国物流发展的主体。 ， 4 物流成本增长逐年趋缓 1 9 9 1 年至2 0 0 4 年，我国全社会物流总成本从5 1 8 2 亿元扩张到2 9 万亿元， 增长了5 8 倍，年均递增1 4 ，高于经济年均增速4 个百分点左右。预计2 0 0 5 年将达3 2 万亿元，但这种增长势头趋于减缓，尤其是1 9 9 4 年以后增势明显放慢。 5 物流成本占g d p 比重逐渐下降，但总体水平依然偏高 从与g d p 的相关性来看，全社会物流成本与g d p 呈高度正相关性，相关系 数几乎等于l ，二者之间可以建立线性回归模型，用y 代表g d p ，用x 代表全社 会物流成本，则有y = 4 9 4 5 x - 8 5 6 矿该方程的经济意义表明，经济发展水平越 高，物流支出也越多，对物流的需求越大。方程中的负截距具有特定的经济含义， 表明如果物流支出达不到一定的水平( x 1 7 3 1 9 ) ，则不可能有g d p 产出，由此 也可见物流在国民经济中的地位和作用。 从1 9 9 1 年至2 0 0 2 年，物流成本占g d p 的比例缓慢下降，从2 4 下降到2 1 5 ， 今年预计在2 1 4 左右。特别是占社会物流总值的比例下降趋势明显，目前已经 由1 9 9 1 年的1 7 1 下降到2 0 0 2 年的9 5 ，平均每年下降约o 7 个百分点。其中， 运输成本占全社会物流总值的比例下降尤为明显，从9 5 下降到4 6 ；其次是 保管成本，所占比例从5 3 下降到3 1 。这反映出我国物流业效率正在逐步提 高，但物流成本总体水平仍然偏高，与美国、日本、欧盟国家相比要高出8 1 0 个百分点 6 物流增加值的增幅高于国民经济增长水平 1 9 9 1 年至2 0 0 2 年，我国物流产业增加值从2 2 5 7 亿元上升到7 1 3 3 亿元，增 长了2 倍多，年均递增1 1 ，高于同期g d p 年均增速1 个百分点左右。十五期 中国物流信息中心，2 0 0 3 年 1 0 山东大学硕士学位论文 间发展最快的是配送、加工、包装物流，1 2 年间平均增长速度为1 7 6 ，其次是 仓储物流平均增速为1 6 ，批发物流为1 3 4 ，邮政业物流为1 2 7 ，交通运输 物流为8 6 。 物流增加值的增幅高于国民经济增长水平，说明我国物流社会化程度在不断 提高，专业化物流( 第三方物流) 正在加快发展。物流业在我国国民经济中的地 位和作用不断提高，被经济学界和政府管理部门视为国民经济发展的动脉和基础 产业，是一种新的生产力，是新的经济增长点。它直接创造了时间价值和空间价 值，创造了国民收入，扩大了经济总量。 7 物流业发展对我国第三产业的发展具有举足轻重的地位 物流业的发展提升了第三产业的比重，促进了经济结构的调整。1 9 9 1 年至 2 0 0 2 年，物流增加值占第三产业增加值的比重平均为2 4 8 。从近几年的情况来 看，这一比例较为稳定，目前基本维持在2 0 以上水平，说明物流是拉动第三产 业发展的稳定因素。 8 物流领域固定资产投资快速增长 改革开放以来，国家对物流基础设施作了大量投入。统计数据表明，自1 9 9 1 年至2 0 0 2 年，国有物流行业固定资产投资额从3 2 5 8 亿元上升到3 5 6 8 3 亿元，增 长了1 0 倍，年均递增速度达到2 4 3 ，快于全社会固定资产投资增速4 个百分点。 从新增投资情况来看，自1 9 9 1 年至2 0 0 2 年，国有物流行业新增固定资产投 资从1 9 7 7 亿元上升到2 7 3 1 4 亿元，增长了1 2 8 倍，年均递增2 7 。 9 物流基础设施建设和装备发展初具规模 经过多年发展，目前我国已经在交通运输、仓储设施、信息通讯、货物包装 与搬运等基础设施建设方面取得了长足的发展，为物流产业的发展奠定了必要的 物质基础。 据统计，从1 9 9 1 年至2 0 0 5 年，铁路营业里程从5 7 8 万公里上升到7 5 万公 里，年均增长2 以上；公路里程从1 0 4 1 万公里上升到1 7 6 5 万公里，增长了 6 9 5 ，年均增长约5 ；内河航道从l o 9 7 万公里上升到1 2 1 6 万公里，增长了 1 0 8 ，年均增长约1 ；民用航空线从5 5 9 l 万公里上升到1 6 3 7 7 万公里，增长 了近2 倍，年均增长1 0 3 ；输油( 气) 管道里程从1 6 2 万公里上升到2 9 8 万公 里，增长了8 4 - ，年均增长5 7 ；民用货用汽车拥有量从3 9 8 6 2 万辆上升到8 1 2 2 2 ， 山东大学硕士学位论文 率4 4 个百分点；进入“十五”时期，这一比率已经达到5 0 ，大大高于国民经 济投资率。从1 9 9 1 年到2 0 0 2 年，物流投资率从1 4 2 上升到5 0 1 ，平均每年 上升3 3 个百分点，高过这期间国民经济投资率升幅2 个多百分点。这些数据反 映出当前我国物流发展仍然是粗放式量的扩张，有关部门对此要引起重视，并采 取因势利导，使物流行业走向集约化发展轨道。 从我国整体物流业发展的情况来看，这里面既有我们发展的机遇和成绩，还 有发展环境的制约和潜在的威胁，中国物流业真正的“狼来了”。 2 1 2 国内物流研究现状 1 我国物流理论研究由于起步较晚，并且受到国外物流发展理论的影响颇 深，也一度拥有不同的理解。2 0 世纪7 0 年代末期，“物流”概念从日本引入我国， 但由于当时计划经济环境的限制，在理解和应用上来说，物流概念基本局限在物 资的储存、调拨和相应的运输组织上，没有形成具有自己经济运行特点的物流概 念由于缺乏物流活动组织化和经济运行的环境，在物流概念引进的近2 0 年时间 里，我国物流的发展相当缓慢。随着经济发展和改革开放的深入，各种理解逐渐 趋于一致，认为。物流”是“生产、流通和消费领域物质资料从供应者到用户问 的物理性流动” 或者“物质资料从供给者到需求者的物理性运动，主要是创造时 间价值和场所价值有时也创造一定加工价值的活动”国。从这些不同的表述上可以 得出一个共同的概念“物流是指物品从供应地向接收地的实体流动过程，根据实 际需要，将运输、储存、装卸、搬运、包装、流通加工、配送、信息处理等基本 功能实现有机结合”西。 2 在物流配送上，北方交通大学的郎茂祥教授所做的有时间窗配送车辆调 度问题的禁忌搜索算法在算法的优化上入手尝试解决车辆调度的难题；山东大 学的崔玉泉教授及其博士生王新红所做的城市道路定向问题及其算法也是着 手解决最为困难的配送中心到配送点配送线路问题；大连理工大学系统工程研究 所承担的国家自然科学基金重点项目。电子商务环境下的供应链管理”中，涉及 到的运输车辆路线安排问题( v e h i c l er o u t i n gp r o b l e m sv r p ) ，这类问题作为 中国物流产业发展现状 ，中国电子商务协会 九部委关于促进我国现代物流业发展的意见 董千单著i 岛级物漉学 王之豢著现代物流学 中华人民共和国国家标准物流术语 ，2 0 0 1 年 山东大学硕士学位论文 n p - h a r d 问题( n o n d e t e r m i n i s t i cp o l y n o m i a lh a r d 无确定解的多项式难题) ，“t s p 问题的求解算法”在目前来说是一个非常典型的n p h a r d 问题。迄今为止，这 类问题中没有一个找到有效算法目前倾向于接受n p 完全问题( n p - c o m p l e t 或 n p c ) 和n p 难题不存在有效算法这一猜想，认为这类问题的大型实例不能用精 确算法求解，必须寻求这类问题的有效的近似算法。在这种观点下，上述的这些 都是国内在配送线路研究中的较为前沿的尝试性的研究，并取得一定的突破。 总体而言，我国物流业发展和研究的现状既有压力和不足又有让人乐观的广 阔前景。因此，针对我国经济发展及物流业的现状，借鉴发达国家走过的道路和 经验，建立符合我国国情的物流发展战略是一项重要的工作。 2 2 国外物流发展及研究现状 2 2 1 发达国家物流发展现状 由于国外尤其是发达国家物流研究起步较早，因此国外发达国家物流成本的 构成相对稳定，更是我国物流发展的一个榜样性的方向。当然，具体情况还要视 我国经济以及国情的具体情况作具体分析。表2 1 和表2 2 是发达国家和地区物 流成本及物流构成上的对比： 国家和地区 g d p 1 0 亿美元物流总费用1 0 亿美元物流占g d p 百分比( ) 中国台湾 3 0 84 01 3 i 中国香港1 7 52 4 1 3 7 新加坡 8 51 21 3 9 日本3 0 8 03 5 l 1 1 4 美国 8 0 站9 4 9io 5 英国1 2 4 2 1 2 5lo i 另外，我们还可以从北美发达国家物流成本开支对比中看出物流发展较为合 理地区的成本构成情况： 物流成本管理) ，来伟生，机械t 业出版社 1 4 山东大学硕士学位论文 表2 - 22 0 0 0 年美国，加拿大物流成本开支 美国加拿大 占销售额比例( ) 加拿大元厢磅 占销售额比例( ) 加拿大元，百磅 运输3 5 44 2 9 l3 3 82 4 1 7 仓储2 3 92 7 2 3 92 0 订单清关客户服务 0 7 68 4 40 6 91 3 9 4 管理o 8 54 2 9o r 7 37 1 0 库存搬运2 0 33 0 6 32 0 92 0 9 l 物流总成本 9 4 41 1 4 0 79 0 21 2 3 i o 注；资科源自e s t a b l i s i l i n c h e r b e r t w d a v i s a n d c o m p a n y 下面，重点分析几个物流业起步较早发展也更为科学的发达国家和地区物流 现状。 i 日本：从5 0 年代物流概念引入日本开始，物流的规模、产业结构、发展 模式就随着日本经济的发展日渐成熟。根据日本物流协会的资料，目前日本的物 流成本占g d p 的比重约在1 0 左右。在6 0 年代，日本政府就注重流通政策的研 究和调整。比如通产省与经济企划厅、运输省、建设省，农林水产省等六个政府 部门联合制定了流通市街地整备法。该法统一规划流通设施，在资金，土地方 面设定优惠政策，鼓励集中大城市中心的流通设施向外围地区搬迁，提高城市的 流通机能。 日本政府对物流的引导和支持在持续进行，并随着环境的改变，在政策上做 出迅速反应。1 9 9 6 年，公布产业再造计划。背景是在此期间日本很多企业移师海 外，国内有产业空心化趋势，这将对经济发展产生负面影响。为了强化经济，政 府提出以“解决企业后顾之忧”为主旨的政策。提倡基础设施的建设要国际化和 现代化，并制定了物流结构改革、市内物流效率化、物流信息化等发展方向。 2 欧美：引导物流创新服务，节约物流各个环节的成本，增加物流环节中的 产成品附加值。欧洲推动第三方物流发展的根本措施是减少成本，改善服务欧 洲劳动力成本较高，工会会费和税赋较重，还有法规和经营限制。欧洲的物流经 营成本达到美国的两倍。在欧洲开设分支机构的公司选择第三方物流管理和经营 物流设施，不仅能降低分销成本，而且能提供专业化的服务。物流需求的膨胀导 山东大学硕士学位论文 致了欧洲物流服务供应商剧增，第三方物流给欧洲带来了范围广泛的创新服务。 在英国，目前推动店内物流。零售店把从开门到关门，从清扫店堂、清理商 品到补货上架等原先由商店营业员负责的销售i i 和销售后的一系列服务都交由 第三方物流承担，使得第三方的服务范围延伸到店堂内。零售店把物流环节交由 专业物流公司，商店可以更加专注于商品销售。大型物流企业为制造商提供范围 广泛的服务，包括制作不同语言的标签和包装，帮助这样的制造商在欧洲不同市 场进行销售。而且欧洲的不同市场差异较大，不同市场对服务的需求不同。在法 国、荷兰和德国提供精确的外包物流服务，重点在于技术性和供应链：在地中海 国家，公共交通设施不如上述国家发达，服务的重点在于运输和仓储；在东欧国 家，公共交通和通讯设施不发达，企业需要的第三方服务只是基本的运输和物流。 2 2 2 国外物流研究现状 关于“物流”概念的理解目前存在管理学派、技术学派、工程学派、流通学 派等许多派系，因此，对于物流配送的侧重也就有所区别： 1 、管理、流通学派更倾向于政策主导的配送中心规划从全局角度考虑，追求 运作的合理化，或者干脆不考虑配送中心的概念，用现在的物流发展观点来看很 明显管理和流通学派有些落后； 2 、技术、工程学派更倾向于将配送中心和运输结合起来，从技术的角度去考 察建设以及运输过程的合理化，这包括：运输基地( 配送中心) 存取货物的技术 以及装备要具备现代化的冗余并且能够进行科学合理的动态规划； 3 、绿色物流，物流虽然促进了经济的发展，但是物流的发展同时也会给环境 带来不利的影响。如运输工具的噪声、污染排放、对交通的阻塞等。为此，2 l 世 纪将对世界物流发展提出新的要求。即绿色物流，这包括两方面：一是对物流的 环境污染进行控制，即在物流系统和物流活动的规划与决策中尽量采用对环境污 染小的方案；二是建立工业和生活废弃物处理的物流系统回。但在作者看来，还有 一层意思应该加上去那就是物流发展必须体现“和谐社会”下的“可持续发展”。 表2 - - 3 是当前较为系统的几种物流划分观点： 南京大学课程设置说明 1 6 山东大学硕士学位论文 表2 3 ：物流的四种划分 物流 第一种划分第一= 种划分第三种划分第1 j 1 1 种划分 宏观物流微观物流社会物漉企业物流国际物流 国内物流一般物流特殊物流 国家物流供戍物流 第三方物供应物流外贸物漉经济圈、经带有普追危险品、易燃、 发展规划，生产物流 流，运输，生产物流国际联运济带物流， 性、通用性易爆，易腐蚀， 法律、法规销售物流仓储等专 销售物流远洋运输城市及城和共同性剧毒、易变质物 及政镱制回收物流 业物流，企刨收物流国际航空市外围物的物流活品物流，对速 定，物流布废弃物物业物流以 废弃物物周际邮件流以及邻动。或者说度、条件有特殊 局，物流理流 及铁路、公流口岸物流近地区具没有特殊要求的物流，如 论研究。知 路、港口，大陆桥物有互朴条性要求的文件、贵重物 识普及，人 码头、物漉 流 件的自然物流活动品，动植物运输 材培养，物 园区，仓区物流。本等 流基础设 库、配送中地区物流 旌和信息 心等物流 平台构筑， 活动 经济手段 支持、引导 4 、在物流发展理论上也存在这样一种理论，就是将物流运作上分第三方物流 企业，第四方物流企业，第五方物流企业。其中第三方物流发展较为成熟，也广 为相关研究人员所认可，下面着重介绍如下几个概念： ( 1 ) 第四方物流 安德森咨询公司首先提出了第四方物流( 4 p l ) 的概念，他们将第四方物流定义 为“一个调配和管理组织自身的及具有互补性的服务提供商的资源、能力与技术， 来提供全面的供应链解决方案的供应链集成商”o 。 第四方物流是有领导力量的物流提供商，它可以通过整个供应链的影响力， 提供综合的供应链解决方案，也为其顾客带来更大的价值；它不仅控制和管理特 定的物流服务，而且对整个物流过程提出解决方案，并通过电子商务将这个过程 集成起来。第四方物流正日益成为一种帮助企业实现持续运作成本降低和区别于 传统的外包业务的真正的资产转移。宣挟际上是一种虚拟物流，是依靠业内最优 秀的第三方物流供应商、技术供应商、管理咨询顾问和其他增值服务商，整合社 会资源，为用户提供独特的和广泛的供应链解决方案，这是任何一家公司所不能 单独提供的。 第四方物流4 p l 通过提供一个全方位的供应链解决方案来满足今天的企业所 安德森咨询公司 1 7 山东大学硕士学位论文 面临的广泛而又复杂的需求。这个方案关注供应链管理的各个方面，既提供持续更 新和优化的技术方案，同时又能满足客户的独特需求。 第四方物流具有以下两个特点： 第一，第四方物流提供一整套完善的供应链解决方案，以有效地适应需方多样 化和复杂的需求，集中所有的资源为客户完善地解决问题。 第二，第四方物流通过其对整个供应链产生影响的能力来增加价值即其能够 为整条供应链的客户带来利益。 ( 2 ) 第五方物流 第五方物流是指在实际运作中提供电子商贸技术去支持整个供应链，并且能 够组合各接口的执行成员为企业的供应链协同服务。它有三个特点，一是一个系 统的提供者，二是一个优化者，三是一个组合者。所谓一个系统的提供者，即第 五方物流是以1 1 r 技术为客户组合供应链上各个环节，将平台系统放进客户的实际 运作中，收集实时资讯，以达到评估、监控、快速回顾运作信息的作用；所谓一 个优化者就是，第五方物流可以促进物流标准化的实现；所谓一个组合者，就是 第五方物流是一个用户之间可以寻求多种组合，构成多接口、多用户、跨区域、 无时限的物流平台。 第五方物流同样以r r 技术为基础，同样着眼于整个供应链。第五方与第四方 的最大区别就在于。第四方只是一个供应链的集成商，它提供的物流信息系统是 在客户已有的物流信息系统商的优化、完善，所以更多的是针对一个企业或者是 一些企业，即是一种架构对一种架构的物流信息系统。同时，第四方物流公司还 要参与，实际物流运作的完成，不能算是一个完全意义上的软件服务商。但是， 第五方是一种标准化物流信息系统的提供者，只要是这个供应链上的任何一个环 节，都可以安装这个物流信息系统与自己的上下游进行无缝对接，在这个系统平 台上的任何信息都是公开的、透明化的，它是一个层面对一个层面的物流信息系 统。 5 配送环节理论发展情况 自2 0 世纪8 0 年代以来，国际上流通业的发展出现了一种大的变化趋势 整合( i n t e g r a t e ) 即综合、集成、系统化和一体化的意思。整合优化业务流程和 价值增值链是配送的规模经济和专业化的有效方式和必然要求。总体来讲国外配 送发展的现状可以总结如下： 1 8 山东大学硕士学位论文 ( 1 ) 政府在物流业发展中发挥重要作用； 一 ( 2 ) 物流设施现代化程度高； ( 3 ) 物流业配送的社会化、组织化程度高。 物流配送作为现代化物流系统的一个重要环节是指按照用户的订货需求在配 送中心进行分货、配货，并按照既定路线、时间送交收货人( 客户) ，这里面就相 应地存在配货管理机制( 配货层级) 、配送线路优化、车辆调度的决策问题。国外 由于企业发展模式相对成熟，企业的服务意识浓厚，因此物流配送上的准时、准 确性较高，在配送研究上的理论发展更快。下面是国外配送基本理论上的一些发 展情况。 根据客户对送货时间的要求，配送车辆调度及路线的选择可以为无时限( 对 送达的货物无时限要求) 和有时限( 客户要求将需求的货物在规定时间内送达) 也称为有时间窗问题( d i s t r i b u t i o nv e h i c l es c h e d u l i n gp r o b l e mw i t ht i m e w i n d o w s ) 。本文没有考虑“时间窗”问题，当然不是说“时间窗”现象并不常 见，相反，随着企业j i t 战略的实施，“零库存”( z e r oi n v e n t o r y ) 成了许多企业 追求的目标，客户对货物送达的时间提出了更高的需求；准时、及时到货也是提 高物流企业服务、增强企业竞争力的一种体现。 运输模式的选择与库存、选址密切相关，运输决策要受到库存、选址的影响， 就不同运输模式而言，其对库存的影响有以下几点： ( 1 ) 较慢的运输模式会引起较大的周转或运输库存： ( 2 ) 较大运输量单位的运输方式会出现订单批量超过当前需求量的情况，出 现不需要的库存。这时要综合考虑定购成本与定购批量之间的关系，即采用e o q 模型进行分析，选取优化方案； ( 3 ) 较慢的运输模式会引起安全库存的提高，从而增加物流成本。 在运输路径的算法优化选择中，当前还主要是基于既有的几种经典算法或者 对其进一步的改进，当然即便这样由于行业和专业知识背景的限制，应用领域( 管 理人员、程序员) 与理论研究领域( 主要是各研究机构和高校) 的沟通存在着很 大的“信息不对称”现象很多理论研究超越了应用所需要的深度而存在着一 种“空中楼阁”的现状；而同时应用领域对理论研究的不信任和理解上的难度导 致对能够或者最接近解决自身问题的研究无法真正应用。这是作者在物流公司和 研究机构调研时所切身体会和认识到的，只有双方本着真正合作、相互学习提高 的态度加强沟通，才能为我国流通经济的发展做出应有的贡献。 山东大学硕士学位论文 第三章配送路径算法 配送线路和布点问题是数学领域和管理应用学科领域的一个结合点，这方面 的问题到目前为止最大的困难是理论研究成果向应用的转换，很多相关领域的研 究人员限于学术活动领域往往顾此失彼，甚至于出现了即便是双方都有相关需求， 但限于彼此的研究范围无交界点，而难以将所需内容相互转换的困难。 3 1 配送运输模型概述 当前主要存在的配送路线模型有如下几种： 3 1 1 点点间运输 也称作单源节点运输，这是比较简单的模型。但点点运输却体现了后面所要 着重介绍的一种算法一最短路经算法，也就是说后面几种模型的处理都或多或 少用到了在该模型中所体现出的最为基本、最为重要的最短路径思想。下面介绍 最短路径算法的基本思想： 假设有一个( 具有) n 个节点和m 条弧的有向连通图g ( v ，a ) ( v = v i v 2 ， v n ) ，a = a l ，a 2 ，a l n ) ) ，并且图中的每条弧( v i ，v j ) 都有一个权重c o ( 可代表 费用、距离等) ，则最短路径问题为：在连通图g ( v ，a ) ( v = v t , v 2 ，v n ， a = a l ，a 2 ，a i l i ) 中找到一条从节点v l 到v n 的距离最短的路径，g i 。为所有连 接从节点v l 到v n 的连通图，显然g l n 为g 的一个子图。该类问题用数学方法表达 就是： j 连通图g ( v ，a ) ( v = v b v 2 ，v n ) ，a i a l ，a 2 ，a i l i ) ) ，且其权重矩 阵c = c o l l i s n ，l 蜀m i ，g l 。c g ，且g l 。为所有连接点v i 和v n 的弧和相应 的点构成的连通图。 目标函数为：m i n l = c ， + ( - e g 。 3 1 2 多点问运输 也称作多源节点运输，也是较为简单的运输模型，主要用于解决几个节点之 间送货、配货的产销平衡问题，指的是起始点和目的点不唯一的运输调配问题： 在这类问题中一般有m 个已知的供应点a 芦( a l ，a 2 ，乒。) ，其供应向量为 a i - a t l ，a 1 2 ，a t 。 。同时还有n 个已知的需求点b = ( b l ，b 2 , - - , b 。) ，他们的需 山东大学硕士学位论文 求向量为b j = b l ，b 2 ，b 。 它们之间由一系列代表权重的值( 可能是距离、成 本或者时间等) c 目( i - l ，2 ，m ；j = 1 , 2 ，n ) 连接起来，其数学模型如下： 圈3 _ 一l 。 多点运输模型 条件变量： a i = a u ，a i 2 ，a i 。 为供应点的供应能力矩阵； b _ i = d i i ，b 协 。) 为需求点的需求量矩阵； c = c uil i s n ，ls j m l 为运输距离或成本矩阵。 决策变量： x 尸从a i l 到k 的发送量； 目标函数： 满足 w i n q b i 。i - i 确 j 爿 勤砘t i z l 0 ，i = 1 , 2 ，m ；j 2 1 , 2 ，n 3 1 3 单回路运输t s p 模型 单回路运输问题是指在线路优化中存在节点集合d ，选择一条合适的路径要 2 i o o o 山东大学硕士学位论文 经过所有的节点，并且要求闭合。说该模型比较简单主要是考虑的该模型对很多 实际存在的问题没有做过多的限制约束，从而使得问题简单化。t s p ( t r a v e l i n g s a l e s m a np r o b l e m ) 是一个典型的单回路运输问题模型，同时也是一个典型的n p h a r d 问题，对于大规模的线路优化问题无法获得最优解，只能通过择优来获取 近优解。属于运筹学中的整数规划问题，因此可以采用整数规划的解的方法。 t s p 模型可以做如下的描述：在给出一个n 个顶点的交通运输网络( 有向或 者无向均可) ，要求找出一个包含所有顶点的具有最小权重( 可能是时间、距离、 费用等) 。任何一个包含网络中所有这n 个顶点的环路走法被称作一个回路( t o u r ) 或者解( s o l u t i o n ) 。这里可以很明显的看出，这种方法适合解决的是实际问题中 节点不多、且相对来说限制约束条件较少的运输或者走向问题，但是由于t s p 所 体现的思想很重要，是本文今后要介绍