（控制理论与控制工程专业论文）改进蚁群算法在物流配送中的应用研究.pdf

浙江大学硕士学位论文改进蚁群算法在物流配送中的应用研究 摘要 随着我国物流业和国际的接轨以及客观条件的不断变化，现代物 流业正在我国得到迅猛的发展。本文分析并探讨了物流业中的几个重 要问题，并且给出了部分解决方案，仿真结果表明有应用参考价值。 本文首先论述了物流业在国内外的发展历史和当前趋势，介绍了 现代物流业中的主要概念，分析了常规物流系统中实施手段和物流环 节的规划和设计中常遇到一些重要问题。第二章探讨了物流配送最优 路径问题的模型选择问题，提出了基于m t s p 模型的建模方案。第 三章首先讨论了m t s p 问题的解决方法，而后研究了典型物流配送 问题；建议将其转换成为一个抽象的、可量化的基于m t s p 问题的 模型。第四章进一步探讨了用蚁群算法寻优解决m t s p 问题过程中 的重要的组合优化难题；并且对基本蚁群算法作了优化，使得原来 n p 完全的问题能够在时间可以接受的前提下获得满意的可行解。并 对该算法进行了仿真研究，证明了该算法的有效性。第五章就物流问 题中其他存在的一些问题进行了探讨，也给出了一些解决的方法和思 路。 【关键词】物流，m t s p ，t s p ，蚁群算法，组合优化 新江大学坝士学位论文改进蚁群算法在物流配送中的应用研芄 a b s t r a c t w i t ht h ec o n n e c t i o no ft h el o g i s t i c si nc h i n aa n dt h ew o r l d ，a l s ow i t h t h eb r o k e no ft h ec o n s t r a i no fe x t e r n a lc o n d i t i o n s ，t h el o g i s t i c si nc h i n a h a sm a d ear a p i de v o l u t i o n i nt h i sp a p e rs o m ei m p o r t a n tp r o b l e m so f l o g i s t i c s i sp r o p o s e d ，a n ds o m eo ft h es o l u t i o n so ft h e s ep r o b l e m sa r e o f f e r e dw h i c ha r ec o n f i r m e db ys i m u l a t i o n s t h e c o n c e p t so fl o g i s t i c sa r es h o w n a n dt h es t a t i s t i c so f l o g i s t i c si n o u rc o u n t r ya n da b r o a di sa n a l y z e d t h e ns o m eo f t h ei m p o r t a n t p r o b l e m s a b o u td e s i g n i n ga n di m p l e m e n t i n go fl o g i s t i c sh a sb e e np r o p o s e d ，i n c h a p t e ri i ，t h em o d e l c h o i c eo ft h ep r o b l e mo ft h eb e s tr o u t eo fal o g i s t i c p r o b l e mi ss t u d i e d ，a n dam o d e lb a s e do nm _ t s p i sc h o s e n i nc h a p t e r i i i ，t h es o l u t i o no f am t s pi ss t u d i e df i r s t l y ，t h e nat y p i c a ll o g i s t i c r o u t i n ep r o b l e mi st r a n s f o r m e di n t o a na b s t r a c ta n dq u a n t i t a t i v em o d e l w h i c hi sb a s e d o nm t s p t h e ni n c h a p t e r i v , a ni m p o r t a n t c o m b i n a t o r i a l o p t i m i z a t i o np r o b l e m w h i c hi sc a l l e dt s p w i t h n p c o m p l e t ep r o p e r t yi s s o l v e db ya n ta l g o r i t h m i nt h el a t t e rp a r to f t h i sc h a p t e r , s i m u l a t i o n so fs o m et s p l i bp r o b l e m sa r es h o w n t oc o n f i r m t h ee f f e c t i v e n e s so ft h ea l g o r i t h m a tl a s t ，c h a p t e rvg i v e ss o m e m e t h o d s o ra d v i c eo nh o wt os o l v es o m eo f t h eo t h e r p r o b l e m so fl o g i s t i c s k e yw o r d s l o g i s t i c s ，m - t s p , t s p , a n ta l g o r i t h m ，c o m b i n a t o r i a l o p t i m i z a t i o n 2 堑兰奎兰竺主兰堡堡苎坠兰些壁簦堡壅塑堕墼堂! 塑垦旦堕塞 1 1 引言 第一章物流问题综述 由于经营状况恶化和部分供应商停止供货，美国第三大零售商凯玛特公司 ( k m a r tc o r p o r a t i o n ) 2 0 0 2 年1 月2 2 日向芝加哥联邦破产法院申请了破产保护， 从而成为美国历史上寻求破产保护的最大零售商。 凯玛特是一家拥有4 0 0 亿美元资产、2 1 1 4 家全球分店、雇员2 5 - 2 万人的超 级连锁零售商，也是全美最大的日用品销售商之一。2 0 世纪的整个7 0 年代，凯 玛特成为美国零售业高质低价的代名词，在日后的规模扩张与竞争中，凯玛特世 先后成为报纸广告、电视促销等营销方式的先驱。 但是从盛极到衰败，凯玛特只用了短短1 0 年。在销售量方面，凯玛特的业 绩一向是无懈可击，但是在1 9 9 1 年，纯利润却首次出现了达8 2 0 0 万美元的亏损； 1 9 9 4 年l 一9 月间，凯玛特的零售商品总额虽然高达2 5 4 亿美元，但纯利润只有 1 5 1 亿美元。而且情况在不断恶化，到2 0 0 0 年，凯玛特的净利润亏损达高达2 3 4 亿美元，到2 0 0 1 年亏损进一步加剧，第2 财季亏损9 5 0 0 万美元，销售额较上年 同期也下降1 ：第3 财季亏损更是接近2 0 0 0 年全年的水平，达2 2 4 亿美元， 每股亏损4 5 美分。到2 0 0 1 年10 月3 1 日，在美国国内资产总额为1 7 0 亿美元的 凯玛特，负债已高达】1 3 亿美元：四面楚歌的凯玛特终于不得不申请自愿性破产 保护。 凯玛特遇到如此困境的原因十分复杂，其中牵涉到一些企业高层决断的失 误，但是的凯玛特衰败，并不是1 日之内达成的，其中有一些根深蒂固，决定性 的内部因素，是导致事态恶化的根本原因。其中有两个重要原因就是： ( 1 ) 一味的靠降价作为竞争手段，却不重视管理成本的控制 多年来，在与沃尔玛等竞争对手的激烈竞争中，凯玛特一味将降价作为自己 的促销手段，而忽略了为顾客提供有更多附加值等方面的服务。商品价格降下去 了，但公司的管理费用却没降。凯玛特的日常行政开支在1 9 9 4 年接近总收入的 2 3 4 ，而沃尔玛却只有1 6 1 。申请破产保护前，凯玛特的管理费用上升到占 销售成本的2 9 ，而其竞争对手沃尔玛下降为1 6 ，直接导致销售利润率出现 浙江大学硕士学位论文改进蚁群算法在物流配送中的应用研究 逐年下降的趋势。1 9 7 6 年凯玛特的销售利润率为3 1 ，1 9 8 0 年下降到了1 3 ， 而到2 0 0 0 年，这一比率更是下降为1 。可见，降价不是灵丹妙药，降低费用是 多么重要。 ( 2 ) 未能牢牢的掌握对物流的制控权 在供货商队伍培养和配送中心建设上，凯玛特也远远输给了其竞争对手沃尔 玛。与沃尔玛自建强大的配送中心相比，凯玛特选择了把大部分物流作业外包出 去的做法。从短期看，凯玛特这样做似乎降低了公司营运成本：但从长期看，却 丧失了对物流的控制，使总成本大幅提高。连锁商业经营的时间越长，这种丧失 物流控制的做法所带来的成本提高就越明显。统计显示，每1 美元商品销售额中， 凯玛特在配贷方面要花费5 美分，而沃尔玛只需i 美分多点。 从凯玛特的衰败，我们可以看出，一个现代的企业要在激烈的竞争中获胜， 最关键的并不是“能否把货物卖出去”，而是如何“卖得更省”。在社会分工不断 细化的今天，一件货物的售出并不是简单的钱货交易，而是一个复杂的资本流通 过程，其中牵涉一些经济学规律，不是本章要讨论的问题；但是有一点十分的明 确，就是如何有效的控制企业的生产和销售成本。凯玛特倒下了，并不是完全因 为“有货卖不出去”，而是因为它不能有效的控制成本，紧紧依靠降价这样“杀 鸡取卯”的做法和对手竞争，结果落得凄惨的下场。 根据对凯玛特不能控制成本的原因的分析，我们发现了一个重要启示，就是 如何降低货物的运输和储藏、管理成本，是至少是降低大规模零售业成本消耗的 关键：事实上，只要是商品，就一定会遇到运输、储藏和管理的棘手问题。在中 国古代，就有“一骑红尘妃子笑”的诗句，讲述的是唐明皇为了杨贵妃的“一笑”， 竟然派人从遥远的南国，以驿站接力的方式，迅速将新鲜的荔枝送到长安，而且 运达的时候荔枝依然红润如初。这件事要是放到今天，就是一个客观存在，并且 日益壮大的产业一物流业。只不过唐明皇手下的物流配送站比起凯玛特更昕话 而已。 4 萱坚登塑主兰丝笙墨垦堂些堂兰生垄塑鎏! ! 鲞主堕里旦堕查 1 2 物流的相关概念 1 2 1 物流的概念 物流( l o g i s t i c s ) 就是由货物的运输、贮藏、装卸、搬运、流通加工、配送、 情报处理等一系列功能所组成的一个行业或者部门。 可见物流是一个行业，同时也是一个跨部门的交叉行业，涉及面非常的广， 其他行业的发展也会对物流业产生正面或者负面的影响。物流业的具体策略设计 工作包括： ( 1 ) 企业物流的诊断和分析，包括物流成本、物流流程、物流资源配置、人力 资源配置以及物流职能机构设置等的诊断和分析。 ( 2 ) 企业物流策略的分析和设计，包括物流供应链和物流运作模式的分析和重 新设计。 ( 3 ) 企业全面物流设计，包括资源整合、物流流程优化、物流管理、资源配置、 物流技术、电子化物流等的规划和设计。 ( 4 ) 企业物流实施策略的规划和设计，包括企业物流网络管理、总仓和异地仓 储管理、运输管理、库存控制、成本和风险控制、物流实施指标、评估等物流实 施过程中实旌手段和物流各环节的规划和设计。 1 。2 2 供应链与物流供应链 一般认为，供应链是物流、信息流、资金流三个流的统一，物流贯穿供应链 的全过程，从供应商到核心企业的供应物流，核心企业的内部物流，再到分销商 与最终客户的分销物流，以及伴随而生的废弃物物流、回收物流等，形成了以核 心企业为集散中心的物流体系。物流连接供应链的各个企业，是企业间相互合作 的纽带。供应链物流的特点可以用如下几个术语简要概括：信息共享；过程同步： 合作互利；交货淮时；响应敏捷；服务满意。而物流是供应链管理体系的重要组 成部分，供应链的其他两个部分对物流起着指导和启发作用。 浙江大学硕士学位论文改进蚁群算法在物流配送中的应用研究 1 2 3 第三方物流和自营物流的概念 第三方物流( t h i r dp a r t yl o g i s t i c s ；3 p l ) 是指由发货人和收货人之外的专 业企业，即第三方来承担企业物流活动的物流模式。也就是“通过合同的方式确 定回报，承担货主企业全部或者一部分物流活动的企业”。日本政府在1 9 9 7 年颁布的综合物流实施大纲中，将第三方物流定义为“对客户提供物流改革 的方案，接受委托一揽子物流的业务”。 任何一种行业都要有利可图才能进一步发展，那么第三方物流的理论来源是 什么呢? 从本质上来讲来源于现代物流管理科学的推广所产生的新价值，也就是 我们经常提到的第三利润的源泉。 相对于第三方物流的是自营物流，就是由发货方自行承担各种物流活动的物 流模式，等于是企业自行承担了“第三方物流”。 1 2 4 第四方物流 第四方物流 4 0 ( f o u r t hp a r t yl o g i s t i c s ；4 p l ) 定义：一个供应链集成商， 调和管理组织自己的以及具有互补性的服务提供商的资源、能力和技术，以提供 一个综合的供应链解决方案。 第四方物流亦称“牵头物流服务商”( l l p ) ，也就是相对独立于客户和物流 施行方，并且对以上两者进行管理的一方。第四方物流服务商本身并不向用户直 接提供第三方物流服务，而是受托成为“监护人”为用户管理好其与多家第三 方物流服务商之间多方面的关系。它的诞生其实是社会分工不断扩大的结果，把 传统意义上物流业中的 组织规划协调工作独立 划分出来，使得物流业 的管理水平得到提升， 提高整个物流行业的效 率。如图1 1 所示就是 r ：主弃 。已詹；嚣： 壹i i 作i 融扈置 计翱i 拄 l 考f ；：f ；2 、 善：i 丹鼍i ；i ：； 主t 一t l t 曩讽蔓i 生i i - e 矗t 蟪l 畦$ n 量i 采i 开t f 曩l 事疆翻f 一培f 曩、 开杆 。百j _ t j 五f t 1 矗i i 1 i ；j j 。i i l ；i 。； 第四方物流相对第三方物流所起的 图1 1 第四方物流供应链解决方案 作用。 浙江大学硕士学位论文改进蚁群算法在物滤配送中的应用研究 1 2 5 绿色物流和逆向物流 绿色物流【3 2 j 是指以降低对环境的污染、减少资源消耗为目标，利用先进物 流技术，规划和实施的运输、储存、包装、装卸、流通加工等物流活动。 在绿色物流供应中，有必要增加供应商选择和评价的环境指标，即要对供应 商的环境绩效进行考察。绿色物流的行为主体主要是专业物流企业，同时也涉及 有关生产企业和消费者。国外对此问题十分重视，早在7 0 年代提出的一些理论 就把物流业的社会效益提升到和经济效益平等的地位上来。在绿色物流方面，我 国和发达国家的差距较大，应该受到更多的重视。 逆向物流 3 3 】 3 4 1 的定义为：计划、实施和控制原料、半成品库存、制成品和 相关信息，高效和成本经济地从原客户点返回出货点的过程。简单地说，逆向物 流就是为了回收价值或适当处置的目的而从它们典型的最后目的地移动货物的 过程。 产品、组件、原料、设备甚至完整技术上的系统都有可能在供应链中向相反 的方向流动。废弃物进入环境会造成污染，当这些废弃物有回收再利用价值的时 候，企业可能会愿意回收，但是当完全没有再利用价值的时候，就会忽视这种做 法的意义。其实从根本上讲，这部分企业成本转化为了社会成本，转嫁到社会公 共利益上了。其他的逆向物流主要就是各种情况下的退货，如果由企业自行负责 管理运输，那么对企业自身的要求比较高，一般的企业尚无力承担。相反该逆向 物流如由第三方物流业来执行，可以免去很多困难，而且综合效率较高，成本投 入也可能更小。 1 3 国内外物流和物流学发展状况 1 3 1 我国物流的发展概况 人尽其才，物尽其流。物流学在我国的兴起是上世纪7 0 年代末。政府和企 业都为我国物流业的发展倾注了很多的心血和精力，但是几十年过去了，不但第 三方物流没有出现，作为试点的配送站最后也名存实亡。直到9 0 年代中期，随 着经济的发展，第三方物流业却悄悄从我国沿海地区自发的发展起来，直到今日， 浙江大学硕士学位论文改进蚁群算法在物流配送中的应用研究 形成了一股“第三方物流热”。今天作为与能源、信息流并列的物流，已经被看 成是继资源、劳动力之后的第三利润源泉，在国民经济中正发挥着重要作用。 中国物流学会的前身是1 9 8 0 年成立的中国物资经济学会和1 9 8 4 年成立的中 国物流研究会。1 9 8 4 年8 月，中国物流研究会第一次学术会议在北京召开，大 会收到各地提交的论文1 5 0 多篇。1 9 9 5 年，中国物资流通协会成立。协会是行 业组织，学会是学术组织，协会和学会利用各自优势，在物流领域做了大量工作， 对中国物流的理论研究与实际推动做出了新的贡献。 从1 9 9 9 年下半年开始第三方物流配送系统在中国得到了较快发展。我国已 经初步具备了发展物流管理和配送技术的经济环境和市场条件。初步形成了供求 平衡或供过于求的买方市场格局。同时现代物流管理和配送体系中的先进理念和 技术，由西方开始进入并得到越来越广泛的应用。全球经济一体以及产品融合趋 势的加强，使企业从传统对单纯仓储、运输的需求开始发展到综合物流服务。人 们消费观念的变化，使传统商业由原来的店式经营逐渐向无柜台、无铺面经营方 式转变，出现多种新型商业形态，客观上促进了物流的发展，例如2 0 0 3 年中国 电子商务的市场规模达到近4 0 亿美元，就为物流创造了巨大的市场。 我国的第三方物流尚处于初级阶段，国际流行的物流网络设计、预测、存订 货管理等服务只有少数企业才能提供。第三方物流在日本占总物流量的8 0 ，美 国5 7 ，我国只占1 8 。所以第三方物流是我国现阶段物流行业的发展重点。 1 3 2 国外物流的发展概况 国外对于物流学的研究历史要比国内起步早很多，至少已有7 0 余年的历史。 但是物流的发展和经济的发展也是密切相关，当一个行业基本没有什么大的利润 可以实现的时候，关于该行业的研究仅仅是浮于纸上。直到本世纪7 0 年代以后， 物流业突然随着各种相关行业的发展而受到越来越多的关注。很多新的名词出 现：m r p ( 物流需求计划) 、m r p i i ( 制造资源计划) 、e r p ( 企业资源计划) 等； 但是成功的依然不多，最主要是受到通信能力的限制。但是时间到今天，我国物 流业刚刚正式起步的同时，信息产业的巨大发展使得人们可以在任何地方得到需 要的信息，物流业的最后一个客观障碍被扫除了。有些大型的物流企业，例如沃 浙江大学硕士掌位论文改进蚁群算往在物流配送中的应用研宄 尔玛公司甚至拥有自己的商业通讯卫星。虽然国外的物流业发展比国内早，但是 由于客观因素的制约，正好使我国搭上了国际物流业迅猛发展的末班车。 国际上第三方物流业有2 0 年历史，虽然它是处在成长成熟期的年轻行业， 但在国民经济中已起着相当重要的作用。据统计，1 9 9 7 2 0 0 0 年，世界5 0 0 强 企业对第三方物流的需求由4 0 增加到了5 6 。在欧洲的物流服务市场，2 0 0 2 年约有2 8 由第三方物流完成。其中，德国9 9 的运输业务和5 0 咀上的仓储 业务交给了第三方物流。通过第三方，德国物流成本可以下降到商品总成本的 1 0 。英国的第三方物流，在商业领域已从货物配送发展到店内物流。美国从 1 9 9 0 年出现第三方物流后，2 0 0 0 年的市场规模约6 0 0 美元，前2 0 名第三方物流 服务企业净收入达到9 3 4 亿美元，被称作玫瑰色的新产业。日本在近2 0 年内， 物流业每增长2 , 6 ，经济总量就增加l 。自1 9 9 6 年开始，日本开始出现第三 方物流公司，而且有众多公司已成为或表示要成为第三方服务提供者。纵观国际 上第三方物流发展的特点，基本上的做法是首先由政府制定各种物流相关的法律 法规，例如日本政府制定的仓库法、综合物流实施大纲等等：在游戏规则 确定之后，第三方物流部门一方面加强自身的管理建设，降低成本，另一方面不 断拓展服务内容，提高服务质量。例如德国物流正在提出“五星级货物旅馆”的 口号，实际上是对物流中心的管理和运作提出更高的要求。物流中- 1 1 , 的货物配送 应该做到加工更方便、物审更快捷、服务更周到、运作成本更低，这样才能吸引 更多的客户。 1 ，3 3 国内物流业经历的误区和教训 我国物流业的特点是自营物流业比较“发达”，企业大多追求“大而全”、“小 而全”的经营模式。据国务院发展研究中心最近发表的一份调查报告称，3 6 和 4 6 的原材料物流由企业自身和供应商承担，而由专业物流企业承担的仅有1 8 ；产品销售中物流部分有2 4 由企业自理，6 0 是企业与第三方共同承担， 第三方物流供应商单独承担仅有1 6 。5 3 的生产企业及3 9 的商业企业拥有 车队：5 9 生产企业和4 4 商业企业拥有仓库，而它们之中还有3 拥有铁路专 用线。而这些企业自身对于提高物流配送的效率，降低成本的意识还不太强烈， 物流配送的管理方式，信息化程度还很低。所以，加大第三方物流的比例也是我 坠坚查兰堡三兰些丝三垫些壑壁兰鲨垄望堕! i 垄! 堕皇旦竺茎 国物流发展的一个重要方向，不能仅仅依靠企业自身的一些物流配送的小型改革 来推动整个中国物流业的发展，这和我国的国情是相悖的。 我国物流业无论是基础物流设施和网络的建设，还是在人才、技术、管理上， 都和国外有着比较大的差距。但是综观全局，我国物流建设的最主要瓶颈还是传 统的、非信息化的物流模式，降低了运行效率，造成了不必要的浪费。并不是有 了第三方物流公司，货物就一定可以高效、及时的运送到客户手中。如果没有实 际运作能力的提升，物流观念和管理手段的变革，那么所谓的物流业革新就是简 单的把一些仓储运输公司改名为“物流公司”，运作成本不会有任何意义上的减 少。如果不能从现代物流的标准出发，如对供应链做优化，预测和计划配送中心 建设和管理，通过信息系统做到货物的协调高效配送，那么我国的“物流热”仅 仅是一些泡沫。所以应该从我国实际出发，建设一批有中国企业运行特色的高效 率物流信息管理系统，宜“精”不宜“滥”，使得我国物流业能够健康、快速的 发展，赶上国际水平。 1 4 物流业的基本经济规律和实践经验 1 4 1 物流业基本经济规律 ( 1 ) 物流的建设管理和生产活动一样，是有成本消耗的；但是这种成本消 耗的核算应该和企业整体的成本核算挂钩，从整体的角度看这种成本投入是否值 得。如果抛弃了整体，单独从物流业本身看，那么是看不出这样的投入是有任何 的回报的。同样，在对比不同企业的物流所带来的效益或者亏损时，也不能仅仅 看到物流行业某些环节的成本消耗，而是应该从两家企业的总体成本的投入入 手。 ( 2 ) 物流业的主要目的是为了将体整体的成本消耗，提升企业的整体效益。 所以物流部门应该和企业做到信息共享，随时互通有无。要把物流业，不管是企 业自己建设的物流部门，还是第三方物流业，都看作是企业的一个不可分割的有 机组成部分。 ( 3 ) 物流业的平衡点及其影响 1 0 浙江大学硕士学位论文改进蚁群算法在物流配送中的应用研究 如果企业自己没有建设自己的物流部门，那么必须求助于第三方物流部门； 企业对第三方的要求当然是以最少的钱，办最多的事；而第三方的目标却是拿最 多的钱，把事刚刚办好。换句话说，企业和第三方物流业在企业所花出的物流成 本和物流业所提供的服务水平上必须达到一个平衡( 如图1 2 所示) 。显然，如 果企业自主建设现代化的物流部门就比较容易控制这种平衡关系。而国内真正有 企业能意识到这一点的还非常少，常见的仅仅是一些仓库改造之类的“小打小 闹”。 错售牧入 物流成本 锖售姒 【成本 及 图1 2 物流收入( 成本) 和服务水平的关系曲线 ( 4 ) 提高服务的集成化 如果能够将物流服务能商通过集成自身和其他物流企业的资源，精简物流服 务业务环节，加强组织之间的协调运作，为客户提供集成化的物流服务。那么将 进一步降低物流配送的成本( 如图1 3 所示) 。 俄舂； 鼋耀之鳟嘭蝴翻 图13 集成物流收入( 成本) 和服务水平关系f t t t _ 线 集成物流运作是对物流生产的组织方法的一种创新，这种创新是基于现代通 讯技术和网络技术基础上的集成管理思想在物流领域的应用。回过头看第三方物 浙江大学硕士学位论文改进蚁群算法在物流配送中的应用研究 流的经济学实质是分工和专业化，而正确的分工和专业化就能为物流服务的集成 化提供有利条件( 如图1 , 4 所示) 。所以，从整个物流行业来看，建设信息化、 集成化的第三方物流业是整个物流业的发展方向。当然从企业自身的发展考虑， 能够自己控制物流的脉搏是最好不过的，但是随之而来的是对企业管理能力和经 济实力的巨大要求，我国的企业一般还不具备这些条件。 萎燧萎避 分工 ( ) 圈1 4 分工和收益成本的关系曲线 1 4 2 物流业的一些实践经验 分工 ( b ) 经过长期的发展和摸索，物流业的经营者们虽然没有进行学习，却通过实践 摸索出了一些有效控制成本的方法。 ( 1 ) 整合运输：把大量的小宗货物一次性运出，以一次性的“旅行商回路”把 货物运到不同的客户手中，从而降低单位运输成本：这样做的前提是企业和物 流配送部门的供应链畅通，信息反馈迅速。 ( 2 ) 最低库存并提高仓库效率：库存是有害的，占用企业的资金，造成成本的 低效投入。最低库存的目标是把存货的数量控制在客户的服务目标的最低水 平。一个传统仓库的拣货、装卸操作占总的仓库作业时间的4 0 ，其它时间被 消耗在人员的空手行走中，劳动力成本的付出浪费极大。因此对仓库进行管理、 操作上的改进也有利于成本的节约。 ( 3 ) 快速反应( q r ) 和有效客户反映( e c r ) ：要求厂商及时地满足客户的服务 需求能力。换句话说，企业所依靠的物流部门要根据对市场和企业生产的预测， 有计划的把货物配送、装卸、贮藏等诸方面的准备工作提前做好a 从而可以由 一堑垩丕兰竺主兰生堡苎垦垄墼壁兰堕垄塑亟里堂! 竺壁星翌壅 较为宽裕的时间完成配送任务，也为实现前面所说的整合运输和最低库存提供 有力条件，从而达到降低成本的作用。例如前面提到的零售商业沃尔玛，其在 全球的4 0 0 0 多家分店通过它的网络可在i 小时之内对每种商品的库存、上架、 销售量全部盘点一遍，这样就可以随时对数目巨大、种类繁多的货物流动作出 一个优化方案。 ( 4 ) 最小变异：物流业经常会遇到一些意想不到的情况，例如地震、道路阻塞、 恶劣天气状况等等，经常导致一些任务不能按要求完成，例如不能及时将货物 送到客户手中。为了避免这些问题，有两类做法，一个就是增加各类成本，提 高配送、贮藏的安全性；另一种就是设立专门的物流信息评估部门，随时观察 分析各种和本部门物流有关的信息，对各种可能发生的状况作出评估，确定应 该采取的调整和补救措施，把风险降低到最小。 1 5 物流所面对的实践难题 从前面的分析看出，当前物流业所涉及的领域是广泛的，遍及管理学、经济 学、运筹学、数学、信息学、计算机科学等多个学科的内容。但是如果从最实际 的角度出发，就是要完成两个大的目标1 降低成本；2 满足客户需求。换句话 说，就是在满足某些“约束条件”的基础上实现“最节约成本”的配送方案。物 流业的最主要成本投入就是两大块，一块是前期投入，就是建立仓库、配送中心， 安排配送工具，如卡车；另一大块就是实际运行中的管理和配送消耗。下面针对 其中存在的一些问题分别作讨论，并给出本文后面几章所要研究的主要课题。 1 5 1 物流配送路径寻优问题 思考前面叙述的物流业长期发展所形成的些通用经验，发现物流配送的一 个重要目标就是要在满足客户要求( 般是时间) 的前提下，能够投入最少的配 送成本( 主要是各种运输线路上的损耗) 。在网络化的今天，由于信息流通便捷， 各部门协同工作的能力越来越强，实现诸如“整合运输”、“最低库存”、“快 速反应的客观条件越来越充实i 因此，如何充分利用现有条件t 达到物流配送 的最小成本消耗已经成为一个越来越受到重视的问题。特别是“整合运输”等一 浙_ i 工大学硕士学位论文改进蚁群算法在物流配送中的应用研究 系列新的货物运输概念的提出，更使得原来的单线的，仓库一 单个客户一 仓库的 配送模式被完全推翻，取而代之的是每个运输单位运输不同的货物到不同的客户 手中；而不是像往常那样，每个配送单位分配单名客户，把货物运到客户手中就 立即返回，造成路程上的大量浪费。这一问题可以描述为：如何选择最优配送路 径，使得投入的运输成本最低，又能满足客户的要求。实际上，由于客户数目的 巨大，这一问题的可行解数目非常巨大，甚至不可能用类似于枚举法的方法在能 够接受的时间范围内得到最优解或者较优解，因此该问题已经成为一个公认的物 流难题。 本文将针对这一最为常见的物流问题作个深入的探讨，在第二章中，将讨 论用何种模型表示物流配送最优路线寻找问题；第三章中，将讨论如何将该问题 转化为对应的组合数学模型；在第四章中，将使用一种仿生学算法一“蚁群算法” 作为数学工具进行该问题的数学求解。 1 5 2 物流配送其他问题 前期的资金投入，最大的成本投资就是配送中心的建设；一组好的配送中心， 应该能够对各种因素对将来物流配送造成的影响作好综合的考虑和权衡。事实 上，这样的因素非常多，例如：城市和城区的政策、文化经济氛围、各类市场的 位置、劳动力供给和成本、能源通讯状况、企业的目标、税收、公共设施的成本 和供应、环境管理政策、优惠鼓励性政策、离中心仓库和潜在客户的距离、土地 及其建设成本、铁路，公路水上运输条件和能力、供应设施的位置、环境气候条 件等等。这些因素不但数量众多，而且很多还是互相矛盾，关系复杂。因此，物 流配送中心的选址和建设问题是一个需要综合考虑的难题。本文将在第五章中就 这一问题作相关探讨。 物流配送所面对的实际情况是复杂的，货物的流动方向也很可能是随机的， 或者互逆的，如何处理这方面的关系也是物流将面对的一个实际问题。同样，随 着配送中心的不断涌现、物流配送的基础设施的不断完备，更为灵活的全局性的 多级或者网形配送方式不断被采用。与此同时，物流配送问题的复杂度也大大增 4 浙江大学碗士罕位诧j 改进蚁群算法在物沉配送中的应用研究 加。第五章中针对“逆向物流问题”和“多级配送中心”的物流配送模式进行探 讨，并给出解决方法或思路。 1 6 小结 物流业的产生和发展完全是一个符合经济规律的案例。当人们自觉的建设和 使用物流设施设备进行专业的，有计划的货物配送、管理的时候，就是物流业有 利可图的时候。当物流学从西方到东方，被越来越多的人重视和参与研究的时候， 就是物流从一个行业发展出一门学科，并且发生正反馈的时候。从事物流业基础 问题的研究将对社会发生良好的推动作用，加速现代化的步伐。 从国民经济的总体发展和长远战略出发，全面、系统地认识、研究、规划和 管理的物流，就是宏观物流。对应是全社会性的、全局性的或者说是国际性的、 区域性的物流。要从全球的范围考虑，把中国物流置于世界物流的大范围去认识。 微观物流与宏观物流相对而言，是指局部性、单一性或一个地域空间、一种活动 环节的物流。比如，企业物流或者企业的生产物流、供应物流、销售物流、回收 物流、废弃物物流等均可列入微观物流范畴。本论文的主要工作，就是试图初步 解决微观物流中的一些重要问题，如物流配送路径寻优问题，并且在一些与物流 相关的问题，如配送中心选址问题和逆向物流配送问题中寻求优化的思路。 浙江大学硕士学位论文改进蚁群算法在物流配送中的应用研究 第二章物流配送路径寻优模型的选择 物流配送路径寻优问题是一个复杂的有约束条件的最优路径查找问题，为了 能够对这个问题的本质有深入的了解，必须知道它的量化抽象模型，这样才能使 用现有的算法工具对其进行优化。所以本章首先将对图论中的些常见的路径寻 优问题加以分析，然后将物流配送路径寻优问题用这些模型中的某种来进行表 达，使得问题能够得到量化、简化、抽象化。 2 1 图论基本定义 图论最早起源于一些数学游戏的难题研究，如欧拉所解决的哥尼斯堡七桥问 题，以及在民间广泛流传的一些游戏难题，如迷宫问题、博奕问题、棋盘上马的 行走路线问题等。这些古老的难题，当时吸引了很多学者的注意。在这些问题 研究的基础上又继续提出了著名的四色猜想和汉米尔顿( 环游世界) 数学难题。 下面介绍一些图论基本定义。 ( 1 ) 图： 点集合v 和点与点之间的连线的集合e 所组成的集合对( 矿，e ) 称为图，用 c ( v ，e ) 来表示。v 中的元素称为节点，e 中的元素称为边。 符号p ( g ) = p ( g 】和q ( g ) = i e ( g 1 分别指图g 的点数和边数。 图g 中，如果任意两点之间都恰有一条边，则称图g 为完全图。 ( 2 ) 予图： 若e ，e ，矿= v v i 矿是f 中某边的端点) ，则称g7 = 缈，e ) 是g 中由e 生成的子图。 ( 3 ) 节点的度： 设v 矿( g ) 是。e ( g ) 的端点，则称v 与e 相关联，与节点v 关联的边的条 6 塑垩查兰堡圭堂垡丝兰坚苎些壁塞生垄塑垂里鲞主竺壁里竺茎 数叫做该节点的度数，记做d ( v ) ，容易证明 d ( v ) = 2 1 e ( g ) 。 p e r 旧) 由上式可知奇次节点的总数是偶数。 ( 4 ) 边的权值： 如果图中任一边0 ，v ) 都赋一个数0 ，v ) ，则称这种数为该边的权值。一条 边的权值也称之为它的长a 如果存在一条边0 ，v ) ( v ，“) ，则图g 是有向图， 反之则为无向图。 赋以权值的图在实际问题中十分有用，根据不同的实际情况，权值的含意可 以各不相同。例如，可用权值代表两地之间道路的长度或行车时间，也可用权值 代表菜工序所需的加工时间等。 ( 5 ) 路( 或链) ： 在无向图中前后相继连接的一串边的集合称为路( 或链) 。一条路 t l 尸= y 。v ：a 的长度是p 上所有边的长之和，即口( v ，t + ，) 。在有向图中，顺 向的首尾相接的一串有向边的集合称为有向路，通常用顺次的节点或边来表示路 或有向路。 ( 6 ) 回路( 或圈) 和连通图： 起点与终点为同一节点的路称为回路( 或圈) ，如果圈上个点都不同，则称 为一个初等圈，不特殊说明，圈特指简单圈；图g 中所有圈如果一个图中，任 意两个节点之间都存在一条路与之相连，称这种图为连通图。 ( 7 ) 树： 若一个连通图中不存在任何回路，则称为树。 ( 8 ) 最小生成树： 如上所述，一个连通的赋权图g ，可能有很多生成树，每棵均遍历g 的所 有节点。设t 为图g 的一个生成树，若把t 中各边的权数相加所得的和数称之 为生成树t 的权值。g 的所有生成树中，权数最小者称为g 的最小生成树。 浙江大学硕士学位论文改进蚊群算法在物流配送中的应用研究 2 2 图论中的路径寻优问题 针对连通图g ，有一些常见的路径寻优问题： ( 1 ) 最短路径问题 最短路径问题也称为最短链问题，包括以下两种： 狭义的最短路径问题：在一个赋权图g 中给定一个节点v ，作始点，另一个节 点v ，为终点，所谓最短路问题就是在g 中找一条从v ，到v ，长度最短的路。 广义的最短路径问题：从图g 中某一点出发到其他某个点的前n 条最短路径。 ( 也就是找到最短、次短、再次短的n 条路经) 对于问题，最经典的方法是1 9 5 9 年就提出的d d k s 订a 算法，它是一种复 杂度为多项式阶的最短路径寻找算法；此外还有f l o y d 算法等等。 对于问题，d u k s 缸a 算法并不能直接胜任，但是和本文以后涉及的算法没 有关系，所以不再赘述。 对于d 日k s 拄a 算法，它在实际运用中遇到的塌大问题就是要对图o 上所有道 路的权值事先确定，所以是一种静态的算法。也是一种预备算法，也就是当所有 路径的权值都确定之后，d i j k s t r a 算法的结果也就确定了，而且能在可以接受的 很短时间内获得结果。 ( 2 ) 求最小生成树问题 求最小生成树问题有很广泛的实际应用，例如把n 个城市用高压电缆连接起 来建立一个电网。如何设计一个把n 个城市联系起来的电网，使所用的电缆长度 之和最短，即费用最小( 假设费用与长度正比) ，就是一个求最小生成树的问题。 针对该问题，已经有了一些成熟的算法，例如克罗斯克尔算法( 1 9 5 6 ) ，俗 称“避圈法”，以及普莱姆算法等等。 ( 3 ) e u l e r 问题 e u l e r 问题源起著名的七桥游戏。p e r g e l 河横贯k o u i g b e r g 城，在陆地和河心 之间架设有7 座桥梁，问题是旅游者能否经过每座桥梁一次且仅此一次。( 如图 2 1 所示) 渐扛大孛硕士字位佗义改进蚁群算法在物流配送中的应用研究 圈2 1 k o u i g b e i “g 七轿j 司趣 图2 2 七桥问题的图论表示 该问题可以被抽象为图2 2 所示的图g 。原问题就转化为：对于图g ，若存 在一条简单链，通过g 的每条边，则称他为e u l e r 链；类似的，若存在一个简单 圈，通过g 的每条边，则称他为e u l e r 圈。若图中有e u l e r 圈，那么称为e u l e r 图。同时可以看出，e l u e r 问题其实是一个“遍历边”的问题。 可以证明，n n q ( g ) 0 的连通图g 有e 链当且仅当g 至多含有两个奇次 点。而e u l e r 定理( 1 7 3 6 ) 指出：q ( g ) 0 的连通图g 是e 图当且仅当g 不含奇 次点。 从中看出，判断是否有e u l e r 链并不困难；并且在1 9 2 1 年，由弗罗莱( f l e u r y ) 提出了一种有效的方法，可以快速的求出e u l e r 链。 算法步骤如下： 任取起始点v 。，v 。一月。 设路r = p 。( v 。，v ) ， 8 ：( v 。，v 。) ，r ( v 。，v 。，) 已选出，则从e 扣- ，e z ，e r ) 中选出边p 。，使p 。与p 。相连，除非没有其它选择，g ，、 p 。 仍应为连 通的。 重复步骤，直至不能进行下去为止。 至此，关于该“e u l e r 路径寻优问题”已经有了圆满的解决。 ( 4 ) 中国邮递员问题( c b s n a p o s t m a n p r o b l e m ) 一个邮递员，每次送信，走遍他所属的每个街道，完成送信任务之后回到邮 局，求一条路线，使得该邮递员走过的总路程最短。用图论的描述就是：在一个 连通的赋权图o ( v ，e ) 中，要寻找一条回路，使该回路包含g 中的每条边至少一 次，且该回路的权数最小，也就是说要从包含g 的每条边的回路中找一条权数 最小的回路。 该问题是由我国的管梅谷教授与1 9 6 0 年提出的，后来又发展出多个邮递员 浙江大学硕士学位论文改进蚁群算法在物流配送中的应用研究 问题( k - c p p ) 。在该问题的求解过程中，遇到了先前从遇到过的困难，虽然有 一些解法尝试给出一些但简单的小规模中国邮递员问题的最优解，例如“奇偶点 图上作业法”，但是此方法要验证每个回路，所以在计算量上仍然十分巨大，在 面对大规模问题的时候时间消耗不可接受。由于没有一个有效的解决它的多项式 计算方法，故该问题属于n p - 完全的组合优化问题。 ( 5 ) 最优担货郎回路问题 最优担货郎回路问题也称t s p 问题( 旅行商问题) ：对于完全图g ，求一个 旅行商从某一个城市( 节点) 出发，遍历所有的城市一次回到出发点，根据要求 分为每个城市经过仅经过一次和不限次数两种情况。 从图论的角度来定义t s p 问题就是： 狭义t s p 问题 可以表述成一个完全加权的有向图g = ( 矿，e ，d ) ，其中巧“= l l ：，。1 是n 个节点 ( 城市) 集合，e = ( i ，歹j 0 ，j ) y 矿 是支路集合，d ：e l - + n 是e 的权函数，它 将每条支路( f ，j ) 与一个正整数权d ( i ，) 相关联( d ( f ，) 可以是节点i 和，之间的距 离，但是并非一定为欧氏几何中所指的距离) 。目标是找到恰好访问每个节点一 次的最小长度的闭合回路。若任意的d ( i ，) = d u ，班则称为对称的t s p ；若至少 有一对d ( j ，) d 0 ，f ) ，则称为不对称的t s p 。 狭义t s p 问题又称为求最优汉米尔顿圈问题。 广义t s p 问题 图2 , 3 德国1 5 1 1 2 城市t s p 问题 图24 德国1 2 0 城市t s p 问题 浙江大学硕士学位论文改进蚁群算法在物流配送中的应用研究 其他定义和狭义t s p 一样，但是允许存在重复的路径，即要求经过每个城 市至少一次，从实际出发，本文考虑的t s p 问题均指广义t s p 问题。同时看出， 广义t s p 问题也就是上面提到的中国邮递员问题。图2 3 是德国1 5 1 1 2 个城市的 t s p 仿真结果图( 2 0 0 1 ) ；图2 4 是1 2 0 城市的仿真结果图( 1 9 7 7 ) 。 t s p 问题有着广泛的意义，它不仅仅是解决推销员的最优巡游路线，而且运 用场合可以拓展到到诸如公交车辆的最优行驶路线，公安巡警的巡回路线，车间 流水作业的顺序问题，装配进度问题，以及数控机床的运行问题等等，因而引起 了人们的极大关注。和c p p 一样，t s p 也是一个n p 一完全的组合优化问题。 ( 6 ) 多条最优回路问题 也就是多路旅行商问题( m t s p ) 定义：在加权图g 中，求顶点集的一个划分k ，将g 分成i t l