（管理科学与工程专业论文）物流配送车辆路径优化方法研究.pdf

中文摘要 目前，国际物流业正朝着高度专业化和社会化的方向发展。近年来，虽然 我国物流业取得了很大的发展，但与国外发达国家相比，仍有较大的差距。在 物流各环节中，物流配送对物流企业增加利润起着关键作用，车辆路径问题 ( v l 心) 作为解决物流配送问题技术的一部分，得到越来越多研究学者和物流 企业的重视。 v r p 是一个典型的n p h a r d 问题，即使在客户规模比较小的情况下，求解 也比较困难。因此，研究求解各种条件下v r p 的有效算法显得尤为重要。从目 前的研究状况来看，虽然对v r p 的研究得到了重视，但是仍没有对实际v r p 面临的各种情况进行深入的探讨，而且成果比较分散，无论是研究的深度和广 度，都不能满足当今物流业迅速发展的需要。 本论文的主要研究内容及创新点如下： 一、设计了求解c v r p 的分支切割算法。采用多种切割面，提出新的分支 规则、节点选择与删除规则、切割面库更新规则等。通过与国内外算例进行比 较，体现了本文提出的算法性能优越性。 二、对多种智能算法在容量约束v r p 条件下的性能进行了分析和比较，分 析多种算法在处理具体v r p 问题时的优、劣势，找出了最适合优化v r p 的智 能算法。 三、提出了核心路径的概念，并设计了求解c v r p 的核心路径禁忌算法。 通过对标准数据库进行测试，该算法的优化能力、运算速度和稳定性与同类算 法相比具有较大的优势。 四、对各种静态非满载v r p 进行比较系统的研究，主要包括：单车场单送 货单集货车辆路径问题；单车场集送一体化车辆路径问题；单车场开放式车辆 路径问题；多车场单送货单集货车辆路径问题；多车场集送一体化车辆路径问 题。 五、本文对实时车辆路径问题进行了研究，能应用到当车辆从配送中心出 发后，顾客要求突然发生改变后的紧急调度情况，是对更复杂、更接近实际的 v r p 问题应用的初步探讨。 六、本文提出了物流配送均衡原理，建立了考虑物流配送中心选址的v r p 问题的双层规划模型，并设计了优化算法，是对集成物流环境下车辆路径问题 的扩展。 七、将能力约束车辆路径问题与自动化仓库拣货问题进行了比较，将研究 成果应用到了企业实际当中，具有较大的应用价值。 关键词：物流配送；车辆路径问题；核心路径；遗传算法：模拟退火算法；禁 忌算法 a b s t r a c t i nr e c e n ty e a r s ，c h i n a sl o g i s t i c si n d u s t r yh a sa c h i e v e dg r e a td e v e l o p m e n t ，b u ta s c o m p a r e dw i t hf o r e i g nd e v e l o p e dc o u n t r i e s ，t h e r ea r es t i l ll a r g eg a p s i na l lt h el i n k s o fl o g i s t i c s ，l o g i s t i c sd i s t r i b u t i o np l a y sak e yr o l ei n i n c r e a s i n gp r o f i t so fl o g i s t i c s e n t e r p r i s e s a sp a r to fs o l u t i o n st ot h et e c h n i c a lp r o b l e mo fl o g i s t i c sd i s t r i b u t i o n ， v e h i c l er o u t i n gp r o b l e m ( v r p ) i sg e t t i n gm o r ea n dm o r ea t t e n t i o ni na c a d e m i c sa n d e n t e r p r i s e s v r pi sat y p i c a ln p h a r dp r o b l e m e v e ni nt h er e l a t i v e l ys m a l ls i z eo ft h e c u s t o m e r s ，g e t t i n gt h e s o l u t i o n a l s oi s d i f f i c u l t t h e r e f o r e ，s t u d y i n gu n d e ra l l c o n d i t i o n sf o rt h ee f f e c t i v ev r pa l g o r i t h ma p p e a r st ob ep a r t i c u l a r l y i m p o r t a n t j u d g i n gf r o mt h ec u r r e n ts i t u a t i o no ft h es t u d y , a l t h o u g ht h es t u d yo nv r ph a sg o t m u c ha t t e n t i o n ，b u ts t i l ln o to nt h ea c t u a ls i t u a t i o nf a c i n gt h ev r p - d e p t hs t u d y t h e v r pr e s e a r c hr e s u l t sa r er a t h e rs c a t t e r e d ，t h ed e p t ha n db r e a d t ho fw h i c ha r eu n a b l e t om e e tt o d a y sr a p i dd e v e l o p m e n to ft h el o g i s t i c si n d u s t r y t h et e x t u a lm a i nw o r ka n di n n o v a t i o np o i n t si n c lu d e ： f i r s t l y ，ab r a n c ha n dc u t t i n ga l g o r i t h mi sd e s i g n e dt os o l v ec v r p t h e a l g o r i t h mu s e sm u l t i p l ec u t t i n gs u r f a c e s ，t h ei m p r o v e db r a n c hr u l e s ，t h en o d e s s e l e c t i o na n dd e l e t i o nr u l e s ，t h ec u r i n gs u r f a c eu p d a t i n gr u l e s ，a n ds oo n t h r o u g ht h e c o m p a r i s o no fd o m e s t i ca n di n t e r n a t i o n a le x a m p l e s ，t h ea l g o r i t h mp r o p o s e di nt h e d i s s e r t a t i o ne m b o d i e st h ep e r f o r m a n c es u p e r i o r i t y s e c o n d l y ，t h ep e r f o r m a n c e so fm a n yi n t e l l i g e n ta l g o r i t h m st oc v r pa r e a n a l y z e da n dc o m p a r e d t h e s ea l g o r i t h m si n c l u d eg e n e t i ca l g o r i t h m ，a n n e a l i n g a l g o r i t h m ，t a b u s e a r c h a l g o r i t h m i n t h e d i s s e r t a t i o n ，t h ea d v a n t a g e s a n d d i s a d v a n t a g e so ft h ev a r i o u sa l g o r i t h m si nd e a l i n gw i t ht h es p e c i f i ci s s u eo ft h ev r p a r ea n a l y z e d ，a n dt h em o s ts u i t a b l ef r a m eo fi n t e l l i g e n ta l g o r i t h mi si d e n t i f i e df o rt h e o p t i m i z m i o no fv r p t h i r d l y ，t h ec o n c e p to fc o r ep a t hi sp r o p o s e di nt h ed i s s e r t a t i o n b a s e do nc o r e p a t h ，at a b us e a r c ha l g o r i t h mi sd e s i g n e dt os o l v ec v r p t h es t a n d a r dd a t a b a s ei s u s e dt ot e s tt h e a b i l i t yo ft h ea l g o r i t h mo p t i m i z a t i o n ，c o m p u t a t i o n a ls p e e da n d s t a b i l i t y c o m p a r e dw i t ht h es i m i l a ra l g o r i t h m s ，t h ea l g o r i t h mp r e s e n t e di nt h e d i s s e r t a t i o nh a sm o r ea d v a n t a g e s f o u r t h l y , v a r i o u sn o n - f u l ll o a dv r p sa r es y s t e m a t i c l ys t u d i e di nt h ed i s s e r t a t i o n t h e s ev r pc o n d i t i o n si n c l u d e ：s i n g l e d e p o tv r pw i t hp i c k u p s o rd e l i v e r i e s ； s i n g l e d e p o t v r pw i t h w i t h p i c k u p sa n dd e l i v e r i e s ；s i n g l e - d e p o to p e n 冲； m u l t i d e p o tv r p w i t hp i c k u p so rd e l i v e r i e s ；m u l t i - d e p o tv r pw i t hp i c k - u p sa n d d e l i v e r i e s f i f t h l y , t h er e a l - t i m ev r p i ss t u d i e d ，w h i c hc a nb ea p p l i e dt ot h es i t u a t i o nw h e n v e h i c l e sh a v es t a r t e df r o mt h ed i s t r i b u t i o nc e n t e ra n dt h ec u s t o m e r sr e q u i r e m e n t s s u d d e n l yc h a n g e d t h ee m e r g e n c ys c h e d u l i n gp r o b l e mi st h ep r e l i m i n a r yd i s c u s s i o n t ot h em o r ec o m p l e xv r p ，a n di ti sc l o s e rt ot h ea c t u a la p p l i c a t i o n s i x t h l y , t h el o g i s t i c sd i s t r i b u t i o ne q u i l i b r i u mp r i n c i p l ei sp r o p o s e d t h eb i l e v e l p r o g r a m m i n gm o d e lo fv r pp r o b l e mw i t hl o g i s t i c sd i s t r i b u t i o nc e n t e r l o c a t i o ni s p r e s e n t e di nt h ed i s s e r t a t i o n s u c hw o r ki s t h ee x p a n s i o no f 理i ni n t e g r a t e d l o g i s t i c se n v i r o n m e n t s e v e n t h l y , c v r pa n dt h ea u t o m a t e dw a r e h o u s ep i c k i n gp r o b l e m a r ec o m p a r e d t h er e s e a r c hr e s u l t sa r ea p p l i e dt ot h ea c t u a le n t e r p r i s ea n dt h ea p p l i c a t i o na c h i e v e s g o o dr e s u l t s k e yw o r d s ：l o g i s t i c sd i s t r i b u t i o n ；v e h i c l er o u t i n gp r o b l e m ；c o r e p a t h ；g e n e t i c a l g o r i t h m ；s i m u l a t e da n n e a l i n ga l g o r i t h m ；t a b us e a r c ha l g o r i t h m 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研究 成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或撰写 过的研究成果，也不包含为获得墨鲞盘堂或其他教育机构的学位或证书而使用过 的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说 明并表示了谢意。 一躲钗石每撕期：硎年，月弘日 学位论文版权使用授权书 本学位论文作者完全了解墨鲞盘鲎有关保留、使用学位论文的规定。特 授权墨鲞盘鲎可以将学位论文的全部或部分内容编入有关数据库进行检索，并采 用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国家有关 部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：嘭。装? 氛 掺- j - - t 一1 期；砂矿喀年r 月7 , , z 7 日 导师繇弈岁细 签字日期：砂多年 月2 1 天津大学博士学位论文：物流配送车辆路径优化方法研究 1 1 研究背景及意义 1 1 1 研究背景 第一章绪论弟一早瑁下匕 自从1 8 世纪工业革命在西方发轫以来，人类便以为自己寻到了自我发展的 终极密码，随着滚滚的车轮与隆隆的机器轰鸣，一番无边无际、无限无量的乐 观发展前景被反复展示。但这种乐观最终被现实击碎，“无限发展观一步步沦 陷。在西方发达国家的经济发展过程中，最初企业是把降低材料的成本当作是 扩大利润的一个最重要的来源，所以这时候把降低材料费用作为第一利润源泉。 当材料成本降低到一定幅度以后，可能的空间就不大了，这时候发现通过降低 人工成本可以获取更多的利润，于是实现了工厂作业的自动化，所以把这种途 径称为第二利润源泉。同样，随着市场竞争日益激烈，企业人工费用的降低也 是有一定限度的，达到一定限度的时候，企业的发展受到很大的限制。后来人 们发现如果能有效地降低在成本中占据相当高比例的物流费用，就等于提高了 利润，这时候人们开始把物流称为第三利润源泉。 尽管物流活动自古有之，但直到1 9 1 5 年，“物流 这一名词才第一次出现 在阿齐肖的市场流通中的若干问题一书中，经过数十年的理论研究和实际 运作，人们越来越认识到物流的重要性。虽然人们对物流的认识有了长足的进 步，但是这个领域未知的东西还很多，理论和实践皆不成熟。著名的管理学权 威p h e 德鲁克曾经讲过，“流通是经济领域里的黑暗大陆 。日本早稻田大学西 泽修教授在研究物流成本时发现，现行的财务会计制度和会计核算方法都不可 能掌握物流费用的实际情况，因而人们对物流费用的了解是一片空白，甚至有 很大的虚假性，他把这种情况比作“物流冰山”。冰山的特点，是最大部分沉 在水面之下，而露出水面的仅是冰山的一角。物流就是一座冰山，其中沉在水 面以下的是我们看不到的黑色领域，而我们看到的不过是物流的一部分。西泽 修先生对物流成本的具体分析论证了德鲁克的“黑暗大陆”说。事实证明，物 第一章绪论 流领域的方方面面对我们而言还是不清楚的，在黑大陆中和冰山的水下部分正 是物流尚待开发的领域，也正是物流的潜力所在。 随着信息技术的发展尤其是因特网的出现和普及，使电子商务得到了迅速 的发展，商务活动所必需的信息流、资金流都可以在网上瞬间实现，这是电子 商务成为可能条件之一，大大缩短了商品交易活动的时间和空间，这使传统的 商务模式受到极大的挑战。另一方面，人们发现，有形商品最终的交易却无法 在网上直接实现，“物流”成了电子商务发展中绕不过去的关键环节，及时履行 订单是决定电子商务公司成功的非常重要的因素，而履行订单关键的环节是配 送，其系统优化主要是配送车辆优化调度。因此，对配送车辆进行优化调度， 可以提高物流经济效益、实现物流科学化，其中车辆路径问题( v e h i c l er o u t i n g p r o b l e m s ，简称v r p ) 具有很大的代表性。 1 1 2 研究意义 一我国发展现代物流的意义 1 现代物流产业的发展，是降低企业成本，促进我国经济发展的需要 1 ) 现代物流产业的发展，可以大大降低高昂的物流费用 有资料显示，目前我国工业企业生产中，直接劳动成本占总成本的比重不 到1 0 ，物流费用占商品总成本的比重高达4 0 。全社会物流费用占g d p 的比 重约为2 0 ，而美国不足1 0 。如果我国能达到同一水平，按照2 0 0 6 年的g d p 水平，全社会可节约2 万亿元的物流成本，或者说可以多产生近2 万亿元的利 润。 2 ) 现代物流产业的发展，能极大的减少库存占压资金， 由于物流速度缓慢，加之企业业务流程以传统模式为主，目前全国长年积 累的库存商品高达4 万亿元左右。落后的物流和巨大的库存占压资金，使我国 众多企业资本周转极其缓慢。目前，我国国有独立核算工业企业流动资本年平 均周转速度为1 2 次，国有商业流动资本年平均周转2 3 次，而现代物流体系发 达的日本企业流动资金年平均周转1 5 至1 8 次，沃尔玛、麦德龙、家乐福等跨 国连锁流通企业资金的年周转速度则高达2 0 至3 0 次。 3 ) 现代物流产业的发展，将减少低水平、条块分割的物流方式造成的巨大 2 天津大学博士学位论文：物流配送车辆路径优化方法研究 物耗 我国传统物流采取的是“大而全”、“小而全”的经营方式，各种物流方式 互不关联，物流过程中的物耗惊人。据估算，全国一年蔬菜损失价值达13 5 4 亿 元，粮食损失价值3 5 7 亿元，钢材锈蚀损失价值1 0 0 0 亿元。在传统的物流模式 下，一件商品从生产环节到最终的消费环节，至少要搬运十几次，如果实行社 会化的多式联运、一单到底，物流过程中的物耗可以大大减少。 2 现代物流产业的发展，是经济全球化的需要 经济全球化的加强是当前世界经济的一个重要特征，其含义是指商品、资 本、技术、劳动力等资源配置已超出一个国家的范围，是在地区甚至在全球范 围内实现最优配置的过程，其实质是一场以发达国家为主导，跨国公司为推动 力，通过交叉投资、兼并收购为主要方式进行的世界范围内产业结构的调整。 它的产生意味着“无国界经济”及“地球村等现象的显现，表明世界经济中 各国经济开放度不断提高及相互依存关系的加深。 经济全球化的加强迫使国内外工商企业为参与市场竞争，越来越注重集中 精力发展主业，培育在技术、管理、采购、营销等上的核心竞争力，一般把非 核心的如在运输、仓储、配送等物流业务作为整体供应链的一部分外包给专业 的物流公司，这是现代物流产生的重要动因。而目前我国第三方物流市场的特 征之一是“两头在外”( 物流的需求方和供应商多为跨国公司) ，现代物流服务 作为传统货运服务的替代品，前者同后者的区别主要表现在其功能的集成和基 于合同为基础的客户合作伙伴关系，由此导致现代物流服务的发展潜力巨大。 二物流配送的意义 配送本质上是运输，因此创造空间效用自然是它的主要功能。但配送又不 同于运输，它是运输在功能上的延伸。物流配送的发展对物流的重要意义可归 纳为以下几个方面l _ 卜纠： 1 能促进物流设施和装备的技术进步 现代大载重量的运输工具，固然可以提高效率，降低运输成本，但是只适 用于干线运输。支线运输一般是小批量，使用载重量大的运输工具则是一种浪 费。支线小批量运输频次高、服务性强，要求比干线运输具有更高的灵活性和 适应性，而配送通过其他的物流环节的配合，可实现定制化服务，能满足这种 要求。发展物流配送有利于促进物流设施和装备的技术进步，具体表现在三个 第一章绪论 方面：一是促进信息处理技术的进步。随着配送业务的开展，处理的信息量将 越来越多，原始手工的信息处理速度慢且容易出错，已经适应不了配送工作的 要求，必然大量应用电子计算机这一现代化的信息处理技术；第二是促进物流 处理技术的进步，从而提高物流速度，缩短物流时间，降低物流成本，减少物 流损耗，提高物流服务质量。配送业务的发展，必然伴随着自动化立体仓库、 自动化分拣装置、无人搬运车、托盘化、集装箱化等现代物流技术的应用；第 三是推动物流规划技术的开发与应用。配送业务的开展，配送货主越来越多， 随之而来的就是产生一个配送路线的合理选择、配送中心选址、配送车辆的配 置和配送效益的技术经济核算等问题，对于这些问题的研究解决，能促进我国 物流技术的发展，并使之达到一个新阶段。 2 能消除交叉运输 。 在没有配送中心的情况下，由生产企业直接运送货物到用户，即使采取直 接配送方式，交叉运输也是普遍存在的。由于交叉运输的存在，使输送路线长， 规模效益差，运输成本高。如果在生产企业与客户之间设置配送中心，采取配 送方式，则可消除交叉运输。因为设置配送中心以后，将原来直接由各生产企 业送至各客户的零散货物通过配送中心进行整合再实施配送，缓解了交叉输送， 使输送距离缩短，成本降低。用大型卡车成批量的送到消费者的配送中心，再 用小型车从配送中心运给用户的方法，可以从总体上节省费用。集中配送有利 于集中库存，维持合理的库存水平，消除了分散库存造成的各种浪费；同时还 能减少不必要的中转环节，缩短物流周转时间，减少物品的损耗，对提高物流 综合经济效益有利。 3 能改变仓储职能 配送通过集中库存，在同样的需求满足水平上，可使系统总库存水平降低， 既降低了存储成本，也节约了运力和其它物流费用。尤其是采用准时制配送方 式后，生产可以根据配送中心准时送货而无须保持自己的库存，或者只需保持 少量的保险库存，这就可以实现生产企业的“零库存”或低库存，减少资金占 用，改善企业的财务状况。开展配送业务后，现代仓储的作用已由储存、保管 物品的使用价值向着集散、分送货物，加速物品流通速度的方向发展。仓储业 将从储存、保管的静态储存转向以保管储存、流通加工、分类、拣选、物品输 送等联为一体的动态储存。建立配送中心后，仓储业的经营活动将由原来的储 4 天津大学博士学位论文：物流配送车辆路径优化方法研究 备型转为流通型，不仅要保证物品的使用价值完好无损，而且要做到货源充足， 品种齐全，供应及时，送货上门，其经营方式将从等客上门向主动了解用户的 需求状况，以满足用户的各种要求的方向转变。 4 提高保证供应速度、方便用户 采用配送方式，配送中心比任何单独供货企业有更强的物流能力，可使用户 减少缺货风险。由于配送可提供全方位的物流服务，采用配送方式后，用户只 需向配送供应商进行一次委托，就可以得到全过程、多功能的物流服务，从而 简化了委托手续和工作量，节省了开支。 三v r p 的研究意义 v r p 问题作为解决物流配送核心技术的一部分，越来越得到研究学者和物 流企业的重视。v r p 问题主要解决的问题为：如何有效地使用载运工具来运送 各站点间的旅客和货物，要求确定哪些旅客和货物该由何车辆、按何顺序、在 何时运送，才能在满足诸如车辆装载能力和运送时间等限制条件下，使总费用 为最小。v r p 的研究意义主要表现在以下几个方面。 1 能提高物流经济效益 针对具体的v r p 问题，通过对实际情况分析，可以将v r p 相关的前提条件 和各项成本进行量化，明确v r p 的目标和约束，对资源进行优化整合与配置， 通过优化配送路径、开展“计划配送”、“共同配送 等形式，消除迂回运输、 重复运输、交叉运输、空载运输等不合理现象，减少物流配送成本，提高企业 的物流经济效益。据统计【l 】，我国的汽车空驶率高达3 7 ，如按照现代物流要 求合理设计流程，可使空驶率降低到5 ，能极大减少运载成本。 2 能提高物流管理的科学化水平 v r p 不仅能解决车辆调度的优化问题，同时也是提高物流管理水平的一种 手段。一方面，通过对具体v r p 问题进行分析，能够得出在现有条件下极大的 减小物流成本、提高服务水平的物流配送方案。例如确定配送车辆对客户的服 务时间窗范围、优先顺序和服务水平等。同时，对于一些突发事件，能够采取 有效的候选方案，减小不确定事件对企业和客户的影响；另一方面，由妞优 化方案实施后反馈的数据，也能对企业员工的工作效率和工作质量进行监督与 控制，提高企业管理水平。例如，能够根据预先制定的优化方案与客户反馈的 信息与进行对比，对员工的表现进行评价，制定相应的激励机制，提高物流管 第一章绪论 理的科学化水平。 3 能够促进v r p 相关领域的发展 虽然v r p 最初是以物流配送为背景提出来的，但其应用范围早已超出了物 流配送领域。在国外，v r p 已经广泛的运用于生产、生活的各个方面，如报纸 投递及线路的优化、牛奶配送及送达线路的优化、电话预定货物的车辆载货和 线路的设计、垃圾车的线路优化及垃圾站选址的优化、连锁商店的送货及线路 优化等。随着v r p 研究的加深和应用的扩展，该问题的应用不仅仅局限在物流 配送领域，还被拓展到仓库货位、拣货优化、电路设计、电网布局等领域。 1 2v r p 相关理论研究综述 1 2 1 国外v r p 研究现状 v r p 最早由著名学者d a n t z i g 和r a m s e r - 于1 9 5 9 年提出l 。经过近5 0 年的发 展，人们设计了多种算法对其进行求解。算法主要分为精确算法和近似算法两 大类。 一求解v r p 的精确算法综述 求解v r p 的精确算法主要包括分支定界算法，列生成算法，动态规划算法， 分支切割算法。 1 9 8 1 年，c h r i s t o f i d e s 等采用分支定界法1 7j 求解v r p 问题，开创了用精确算法 求解v r p 问题的一个新阶段。文中提出了最小容量路径的概念。容量 路径指从车场出发，最多经过总容量为c 的客户之后返回车场。该方法从最小容 量路径子问题中运用l a g r a n g e a n 松弛条件得到边界，能解决多达2 5 个客户 点的能力约束v r p 。c h r i s t o f i d e s ，f i s h e r 8 1 ， m a r t i n h o n 9 1 ，m i l l e r t l 0 1 等人将v r p 转化为k 度中心树，再运用分支定界算法求解v r p 问题。l a p o a e ，m e r c u r e ， n o b e r t l l l - 1 4 等人也对v r p 的分支定界算法的发展做了重要贡献。 b a l i n s k i 1 5 】等人从能力约束v r p 模型出发，将容量不超过c 的客户集合设为 一列，求得车场和该集合并集的最小费用，转化为能力约束t s p 问题。由于能力 约束t s p 问题的计算规模也是呈指数规律增长，故该方法并不实用，但是为另外 一种精确算法提供了思路，这就是列生成算法。19 8 7 年，a g a r w a l l l 6 等人提出了 6 天津大学博士学位论文：物流配送车辆路径优化方法研究 一种列生成算法，该方法列集合的费用由线性规划求得，所有列集合的总费用 可转化为背包问题。h a 蛳c o n s t a n t i n o u 【1 7 】等人运用自适应方法并结合容量路 径和最d , k 路径松弛条件得到列集合的对偶解，从而求出v r p 问题的最优解。 求解v r p 的动态规划算法最早由e i l o n l l 8 j 等人提出，该方法将客户划分为多 个子集，应用动态规划递推公式v r p 的最优解。由于该方法要求的状态数非常 大，所以只能求得规模很小的v r r 问题。c h r i s t o f i d e s 1 8 】 1 9 1 等通过运用状态空间 松弛技术大大减少了状态数，使动态规划算法的性能得到了很大程度上的改善。 他们的实验表明，该方法可有效求解顶点数不超过5 0 的能力约束v r p 。 最近精确算法的热点已转移到分支切割法上来。分支切割算法是将一个凸 多面体的各条棱映射为v r p 问题的多条可行路径，通过在运算过程中切割集合 的不可行部分，逐步降低v r p 的下界，从而得到问题的解。分支切割算法发展 非常快，其中，a c h u t h a n ，c a c c e t t a ，h i l l ，a r a q u e ，k u d v a ，c o m u e j o l s ，l e t c h f o r d ， e g l e s e ，n a d d e f , r i n a l d i 2 0 - 2 8 1 都为它的发展做了重要贡献。 二求解v r p 的近似算法综述 虽然人们在v r p 精确算法的研究上作了很大的努力，也取得了很多的成果， 但由于v r p 问题的复杂性，精确算法的计算成本随问题规模的扩大呈指数规律 增长，因此很难有效的解决大规模的v r p 问题，即使对于较小规模的v r p ，精 确算法也不能保证在可接受的时间内运算出来。随着v r p 应用的扩展，要求能 求解的问题规模越来越大，对求解v r p 的算法的速度和稳定性要求越来越高， 因此越来越多学者求助于近似算法来解决v r p 问题。 求解v r p 问题的近似算法可分为传统启发式算法和现代启发式算法1 2 9 1 。 1 ) 求解v r p 的传统启发式算法 目前已经提出的求解v r p 的传统启发式算法有很多，如先安排路线后分组 的方法、先分组后安排路线的方法、改进交换法、节约插入法、基于数学规划 的算法和交互式优化算法掣2 9 】。 先安排路线后分组的方法( r o u t ef i r s t c l u s t e rs e c o n d ) 这种方法首先构造一条或几天很长的线路( 通常不可行) ，它包括了所有需 求对象，然后再把这些很长的线路划分成一些短而可行的线路。具体进行时， 一般是先解一个经过所有点的旅行商问题，形成一条线路，然后根据一定的约 束对他进行分划。如最短路法( t h es h o r t e s tp a t ha p p r o a c h ) l a o 、匹配算法( m a t c h i n g 7 第一章绪论 a p p r o a c h ) 【31 1 、集划分算法( s e tp a r t i t i o n i n ga p p r o a c h ) 3 2 - 3 5 1 、集覆盖算法( s e t c o v e r i n ga p p r o a c h ) 3 6 - 3 8 等都属于此类。 先分组后安排线路的方法( c l u s t e rf i r s t r o u t es e c o n d ) 这种方法先把节点的需求进行分组或划群，然后对每一组设计一条经济的 线路。如g i l l e t t 和m i l l e r 的s w e e p 【3 9 - 4 2 等算法，其目的在于形成需求点的径向区 域，从车场发出的射线“扫过 这个区域，使不超过车辆容量和需求点组成一 个区域，一个区域就是一个组，当形成一系列这样的组后，再对每一组中的各 点安排线路。 节约插入算法( s a v i n g i n s e r t i n ga l g o r i t h m ) 1 4 3 - 4 7 根据一定的准则把不在线路上的点插入线路，直到所有点都被安排进线路， 如c l a r k w r i g h t 节约算法。 改进交换法( i m p r o v i n g e x c h a n g ea l g o r i t h m ) 4 8 - 5 0 在始终保持解可行的情况下，力图向最优解目标靠近，每一步都产生另一 个可行解，使目标函数得以改进，一直继续到不能再改进为止。 基于数学规划的算法( m a t h e m a t i c a lp r o g r a m m i n gb a s e da l g o r t i t h m ) 把问题直接描述成一个数学规划问题，根据其模型的特殊构形，应用一定的 技术( 如分解) 进行分化，进而求解已被广泛研究过的子问题，如f i s h e r 和j a i k u m a r 的分派算法1 5 1 | 。 交互式优化算法( i n t e r a c t i v em e t h o d ) 在问题的求解过程中加入决策者的判断选择，是一个交互的过程，如c u l l e n ， j a r v i s 和r a t l i f l 韵算法【5 2 j 等。 上述传统启发式算法分类并不是绝对的，有的方法同属于好几类。这些启发 式算法是人类智能的结晶，能够较好的解决顶点数较少的v r p 问题。但是，随 着顶点数的增加，精确度变差，有些计算量增加较快，而且很多传统启发式算 法不好用计算机来实现，因此，应用受到了一定的限制。 2 ) 求解v r p 的现代启发式算法 进入2 0 世纪8 0 年代，一些新颖的优化算法，如人工神经网络、遗传算法、 模拟退火算法、禁忌算法等陟6 引，通过模拟或揭示自然现象或过程得到发展， 其思想涉及数学、物理、生物进化、人工智能等各方面，一为解决复杂问题提供 了新的思路和手段。在优化领域，由于这些算法构造的直观性与自然机理，因 天津大学博士学位论文：物流配送车辆路径优化方法研究 而被称为智能优化算法( i n t e l l i g e n to p t i m i z a t i o na l g o r i t h m s ) 或现代启发式算法 ( m e t a h e u r i s t i ca l g o r i t h m s ) 。 人工神经网络 19 8 2 年，h o p f i e l d 开创性的在物理学、神经生物学和计算机科学等领域架起 了桥梁，提出了h o p f i e l d 反馈神经网络模型( h n n ) ，证明在高强度连接下的神 经网络依靠集体协同作用能自发产生计算行为。h o p f i e l d 网络是典型的全连接网 络，通过在网络中引入能量函数以构造动力学系统，并使网络的平衡态与能量 函数的极小解想对应，从而讲求节能量函数极小解的过程转化为网络向平衡态 的演化过程。 将v r p 的各客户点用神经网络中的神经元加以刻画，构造能量函数，在能 量函数下降的过程中寻求v r p 的最优解。 蚁群算法 蚁群算法( a n tc o l o n yo p t i m i z a t i o n ，a c o ) ，又称蚂蚁算法，是一种用来在图 中寻找优化路径的机率型技术。它由m a r c od o r i g o 于1 9 9 2 年在他的博士论文中 引入，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。蚂蚁算法通过设 置可视范围、环境、觅食规则、移动规则等、避障规则、播撒信息素规则等来 模拟蚂蚁觅食过程。虽然蚂蚁之间并没有直接的关系，但是每只蚂蚁都和环境 发生交互，而通过信息素这个纽带，实际上把各个蚂蚁之间关联起来了。蚂蚁 算法是继遗传算法、模拟退火算法禁忌算法之后发展起来的一种新型智能算法， 在现代v r p 研究中应用较多，不过其优化效果有待进一步改进。 3 ) 其它智能算法 其它智能算法包括遗传算法、禁忌算法、模拟退火算法等。由于将在下一章 进行基本理论介绍，这里不进行赘述。这些算法都是通过模拟人或其它生物的 行为得到的寻求策略，在v r p 中得到了很好的体现。 就目前的情况来看，在研究v r p 算法的学者中，大多数的学者致力于上述 智能算法的研究，发展势头很强劲，是进行v r p 研究的一个热点方向。 1 2 2 国内v r p 研究现状 国内对v l 冲的研究还处在起步阶段。在解决具体问题方面：郭耀煌、李军 是国内第一批研究v l 冲的学者，他们用传统启发式算法解决了一些相对简单的 9 第一章绪论 v r p 问题，如送货点比较少得容量约束、时间窗约束v r p ；蔡延光用遗传算法、 模拟退火算法等 6 9 - 7 1 1 研究重载v r p 问题，取得了一些成绩。张涛等通过遗传算 法来保证搜索的全局性，用3 - o p t 算法来加强局部搜索能力，得到针对v r p 的 混合算澍7 2 】；谢秉磊、郎茂祥等用遗传算法在容量约束和时间窗约束的v r p 上 做了些工作1 7 3 - 7 5 1 ；在理论综述方面：汪寿阳、林岩【7 6 1 【7 7 1 等对选址路径问题的 研究进行了分析；祝崇隽1 7 8 j 较全面的回顾了v r p 领域的最新进展；谢秉磊、郭 耀煌等 7 9 1 对动态v r p 的最新发展作了评述。尽管国内学者在v r p 的研究方面已 经有了一定的成果，但是总的说来还是处在起步阶段。主要表现在如下几个方 面： 1 ) 对该领域的专有名词没有统一规范的提法( 如对v r p ，v s p 的区别等) ； 2 ) 研究的问题大多是确定型问题，很少见到研究不确定条件下，特别是实 时调度情况下v r p 的文献。 3 ) 研究问题的手段比较单一。目前国内主要用智能算法对v r p 进行研究， 在可参考的文献中，还没有见到用精确算法做算例的研究成果。 4 ) 算法能解决的v r p 问题规模都较小。国内的研究成果一般仅能解决5 0 个客户点以下的能力约束v r p ，且很少用国际上通用的v r p 测试数据库进行比 较试验。 5 ) v r p 问题的扩展研究成果较少。在目前集成物流的大环境下，要求v r p 问题与物流配送中的其它问题( 如选址问题) 相结合，才能更有效的节约成本， 增加企业利润。 6 ) 该领域的研究者群体小。就v r p 研究的深度和广度来说，远不能适应 当前我国配送业以及物流业迅速发展的需要。 1 3 本文研究框架及创新点 1 3 1 本文的研究框架 本文的研究框架如下： 第二章中对v r p 问题组成要素、分类、复杂度以及求解v r p 的各种算法理 论进行较为详细的总结归纳，为后面各章的研究奠定基础。 1 0 天津大学博士学位论文：物流配送车辆路径优化方法研究 第三章对静态v r p 的精确算法进行了研究，设计了求解能力约束v r p 的分 支切割算法。通过与国内外算例进行比较，体现了本章提出算法性能的优越性。 第四章对静态v r p 的智能算法进行了研究。本章涉及的智能算法包括：遗 传算法、禁忌算法、模拟退火算法以及禁忌模拟退火混合算法。本章涉及到的 v r p 问题类型包括：封闭式开放式，单送货单集货集送一体化，单车场多车 场，各问题类型中还分别包括能力约束、时间窗约束等各种约束。本章首先在 单车场能力约束条件下对各智能算法进行多次试验，对各算法在同条件下的性 能进行比较，找到最适用于求解v r p 问题的算法。然后运用较好的智能算法对 不同条件下的v r p 问题进行研究。本章对静态v r p 进行了较为系统的研究， 包含了v r p 中常见的各种类型和约束，稍加改动，可以运用到实际物流配送中。 第五章对动态条件下v r p 问题进行了初步的探讨。给出了实时调度系统的 框架，并且设计了禁忌算法优化基于顾客时间窗和配送量变化的实时车辆调度 问题，最后对算例进行了求解，并对实时调度前后效果进行了比较。 第六章是v r p 问题的扩展研究，对考虑物流配送中心选址的v r p 问题进 行了研究。本章提出了物流配送均衡原理，建立了考虑物流配送中心选址的v r p 问题的双层规划模型，并且设计了优化该问题的禁忌模拟退火混合算法，仿真 试验证明了混合算法求解该问题的有效性。 第七章是应用实例章节。本章将能力约束v r p 问题应用到自动化仓库固定 货架拣选优化中。通过对企业应用效果的观测，引进自动拣货优化系统后，提 高了仓库的吞