（载运工具运用工程专业论文）设施定位和车辆路线问题模型及其启发式算法研究.pdfVIP

摘要 随着物质需求的多样性和不规则性以及贸易呈全球化趋势的发展，作为“第 三利润源泉”的物流，其作用和地位显得比任何时候都更为重要，对经济活动的 影响也日益明显。目前，许多发达国家和地区已形成了比较成熟的物流管理理念、 先进的物流技术和高效的物流运营系统。我国在进入2 1 世纪之后，也逐渐加快 了现代物流的发展，以提高生产企业在国际上的竞争能力。为此企业管理者都希 望能协调物流系统中的各个环节，以最低的价格、最好的服务来满足顾客的需要， 所以物流决策显得极为重要。 在传统的物流决策模型中，定位一配给问题( 1 0 c a t i o na l l o c a t i o n p r o b l e m s ，l a p ) 和车辆运输路线问题( v e h i c l er o u t i n gp r o b l e m ，v r p ) 是最值 得关注的两个方面。但是在l a p 模型中仅考虑设施( 工厂、库存点、分销中心等) 的定位与货物配给之间的相互关系，却忽视了对车辆巡回行程路线的考虑，这就 有可能导致分销成本的增长；而在v r p 模型中，虽然考虑了车辆在各个客户点间 巡回访问的特性，使提高运输效率成为可能，但却没有分析设施的选址问题，这 将会使得整个物流系统成本仍有一定的下降空间。因此，本文运用系统分析的思 想和方法，研究了物流系统中的设施定位配给和车辆路线组合优化问题定位 车辆路线问题( 1 0 c a t i o nr o u t i n gp r o b l e m ，l r p ) 。 由于l r p 及其扩展模型属于n p h a r d 问题，在具有一定规模节点数情况下 目前仍难以求得最优解。因此对l r p 模型进行系统化优化求解研究具有重要的理 论价值，其理论意义则在于针对n p h a r d 模型大规模数值计算的解法突破和创 新，同时也是发展基于电子商务的城市物流配送理论的重要理论基础，这将为日 后面对巨大交易量的电子商务环境下开发自动物流配送调度系统软件具有非常 重要的现实意义。 本文在分析了物流系统中选址、运输以及库存的互相制约关系基础上，从提 高物流系统整体效率为出发点，站在理论研究层面，针对物流集成化数学模型及 其启发式解法进行了系统研究，即从系统化的角度分析和研究了复杂物流环境下 的l r p 优化问题，论文从问题的界定、模型的建立、模型的检验、启发式算法 求解途径、组合优化求解思路、算法实现及数据分析等多个方面对l r p 问题进 行了深入、具体的研究分析，得到了如下研究成果： ( 1 ) 论文系统性地研究了l r p 数学模型，对定位配给问题、车辆路线问题、 定位一车辆路线问题、带库存的定位车辆路线问题典型数学模型及其构成进行了 科学描述，通过小规模测试数据采用l i n g o 软件对l r p 数学模型给予了标定， 为今后人们在此方面的进一步研究奠定了模型基础： ( 2 ) 针对l r p 数学模型属性特点，分别采用禁忌搜索算法( t a b us e a r c h a l g o r i t h m ，t s ) 、模拟退火算法( 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 ，s a ) 对l r p 数 学模型进行了优化求解，编制了相应算法程序软件，并采用具有一定规模的仿真 测试数据测算了所提出算法求解l r p 模型的有效性，同时经过大量数值模拟计 算找出了其算法求解l r p 模型的优良参数搭配。通过与有关文献对比，证明本 文提出的求解思路对于l r p 模型求解更具有优良特性； ( 3 ) 提出了遗传一模拟退火组合算法和遗传一禁忌搜索组合算法求解l r p 模型的思路，并进行了相应的算法研究，通过编制计算软件和具有一定规模的数 据测试，实现了组合启发式算法求解l r p 模型的设想，这对于发展和完善组合 优化理论亦具有重要的科学理论价值。 ( 4 ) 分析了在库存管理策略下，库存控制策略对设施选址和路线优化问题 的影响，在此基础上建立了更为复杂的定位一路线一库存组合优化模型 ( c o m b i n e dl o c a t i o nr o u t i n ga n di n v e n t o r yp r o b l e m s ，c l r i p ) ，并设计了 求解该模型的一种两阶段启发式算法，通过小规模测试数据测算证明带库存的定 位路线组合优化模型比定位一路线问题和库存控制模型独立优化的情形更能有 效降低物流系统成本，并为进一步深入研究该问题的解法提供了基本思路。 ( 5 ) 提供了l r p 模型从8 个节点至2 0 0 个节点不同规模情形下的系列测 试数据源，为今后开展l r p 研究者提供了算法科学对比途径，同时为建立l r p 模型测试数据库做出了开创性基础工作。 关键词：定位车辆路线问题，物流系统优化，禁忌搜索算法，模拟退火算法， 遗传算法，启发式组合算法，库存定位路线问题 a b s t r a c t a l o n g w i t i lt h ed e v e l o p m e n to fs u b s t a n c en e e d i n gv a r i e t ya n d i r r e g u l a r l ya l lo v e r t h ew o r l d ，l o g i s t i c sa s “t h et h i r dp r o f i ts o u r c e h a sp l a y e dam o r ei m p o r t a n tr o l ei nt h e e c o n o m i ca c t i v i t yt h a na n yt i m e a tp r e s e n t ，m a n yd e v e l o p e dc o u n t r i e sh a v ef o r m e d c o m p a r a t i v e l ym a t u r el o g i s t i c sm a n a g e m e n tc o n c e p t s ，a d v a n c e dl o g i s t i c st e c h n i q u e s a n de f f e c t i v el o g i s t i c so p e r a t i n gs y s t e m s e n t e r i n gt h e21t hc e n t u r y , t h ec h i n e s e g o v e r n m e n th a sm a d ear a p i dd e v e l o p m e n t i nl o g i s t i c s ，i no r d e rt oe n h a n c ei t s i n t e r n a t i o n a lc o m p e t i t i o na b i l i t y n o wa l lt h eb u s i n e s sm a n a g e r sh o p et or u ne v e r y l i n ki nt h el o g i s t i c ss y s t e mw e l lt os a t i s f yt h ec l i e n t sn e e dw i t ht h el o w e s tp r i c ea n d b e s ts e r v i c e s ot h ed e c i s i o n - m a k i n go fl o g i s t i c si sv e r yi m p o r t a n t i nt h et r a d i t i o n a l d e c i s i o n - m a k i n go fl o g i s t i c sm o d e l ，l o c a t i o n a l l o c a t i o n p r o b l e m s ( l a p ) a n d v e h i c l er o u t i n gp r o b l e m ( v r p ) a r et h em o s tc o n c e r n e dp r o b l e m s b u tt h el a po n l yc o n s i d e r st h el o c a t i o n so ff a c i l i t i e s ( s u c ha sf a c t o r y , i n v e n t o r yp l a c e ， s a l ec e n t e r se t c ) a n dt h er e l a t i o n s h i pb e t w e e nf a c i l i t i e sa n dg o o d sd i s t r i b u t i o n s ， i g n o r i n gt h ev e h i c l e sr o u t e ，w h i c hm a yh a sas i g n i f i c a n te f f e c to nt h ec o s t a l t h o u g h t h ev r pc o n s i d e r st h ec h a r a c t e r i s t i co fv e h i c l e sc i r c u i tv i s i ti ne v e r yc l i e n t ，w h i c h m a yi m p r o v et h et r a n s p o r te f f i c i e n c y , b u ti td o e s n ta n a l y z et h el o c a t i o n so ff a c i l i t i e s ， w h i c hc a nm a k e st h ec o s tt od r o pi nl o g i s t i c ss y s t e m s t h e r e f o r e ，b yt h em e a n so f s y s t e m sa n a l y s i s ，t h i st h e s i ss t u d i e st h ef a c i l i t i e sl o c a t i o nd i s t r i b u t i o na n dt h ev e h i c l e r o u t i n gc o m b i n a t i o no p t i m i z ep r o b l e m - - l o c a t i o nr o u t i n gp r o b l e m ( l r p ) i nl o g i s t i c s s y s t e m s a st h el r pa n di t se x t e n d i n gm o d e lb e l o n gt on p h a r dp r o b l e m ，i ti sd i f f i c u l t t 0g e tt h em o d e l so p t i m a ls o l v i n gw h e nn o d e sa m o u n ti ss om u c h c o n s e q u e n t l y , i ti s m e a n i n g f u lt os y s t e m a t i c a l l yg e to p t i m a ls o l v i n go fl r pm o d e l s c o n t r i b u t i o no ft h e r e s e a r c hi st h ei n n o v a t i o ni nb i gs c a l em a t h e m a t i c a lc a l c u l a t i o no fn p h a r dp r o b l e m a n di ti sa l s ot h ea c a d e m i cf o u n d a t i o no fd e v e l o p e dc i t yl o g i s t i c sd i s t r i b u t i o ns y s t e m s o na c c o u n to fe l e c t r o n i cc o m m e r c e t h er e s e a r c hh a se x t r a o r d i n a r ys i g n i f i c a n c et o d e v e l o p e ds e l f - a c t i o nl o g i s t i c sd i s t r i b u t i o ns o f t w a r ei nl a r g ea m o u n to fe l e c t r o n i c c o m m e r c ed e a l i n g s t h i st h e s i sb a s e so nt h er e s t r i c t e dr e l a t i o n s h i pi nl o c a t i o nc h o o s i n g ，t r a n s p o r t i n g a n di n v e n t o r yi nl o g i s t i c ss y s t e m s ，i no r d e rt op r o m o t ew h o l ee f f i c i e n c yo fl o g i s t i c s s y s t e m s ，f r o mt h et h e o r yr e s e a r c hp o i n t so fv i e w , t os y s t e m i c a l l ya n a l y z et h el r p m o d e l so p t i m i z ep r o b l e mi nc o m p l e xl o g i s t i c se n v i r o n m e n t t h i st h e s i ss t u d i e si na d e e pg o i n gt h el r pb yb o u n d i n gt h ep r o b l e m ，e s t a b l i s h i n gt h em o d e l ，t e s t i n gt h e m o d e l ，g e t t i n gs o l v i n gb y h e u r i s t i ca l g o r i t h m ，c o m b i n a t i o n o p t i m i z ea l g o r i t h m a c h i e v i n ga n da n a l y z i n gd a t a , i nt h ee n d ，g e t st h ec o n c l u s i o n sa s ： ( 1 ) t h i st h e s i si n v e s t i g a t e st h el r pm a t hm o d e l ，a n dd e s c r i b e st h em a t hm o d e l o fl o c a t i o n d i s t r i b u t i o np r o b l e m ，v e h i c l er o u t i n gp r o b l e m ，l o c a t i o nr o u t i n gp r o b l e m ， i n v e n t o r yl o c a t i o nr o u t i n gp r o b l e m ，a n ds c a l e st h el r pm a t hp r o b l e mb yl i n g o s o f t w a r e 、们t hs m a l ls c a l ed a t a , w h i c hi st h eb a s i cm o d e lb a s ef o rt h ef u t u r es t u d yo f l 腿 ( 2 ) a c c o r d i n gt ot h ec h a r a c t e r i s t i c so fl r pm a t hm o d e l t h i st h e s i su s e st a b u s e a r c ha l g o r i t h m ( t s ) a n ds i m u l a t e da n n e a l i n ga l g o r i t h m ( s a ) t og e tt h eo p t i m i z e v a l u eo fl r pm a t hm o d e l ，a n dp r o g r a m sc o r r e s p o n d i n ga l g o r i t h ms o f t w a r e ，t h e nu s e s t h es i m u l a t e dd a t at os u b s t a n t i a t et h ev a l i d i t yo ft h ea l g o r i t h mt ol r pm o d e l m e a n w h i l e ，i t f i n d so u tt h ep r o p e rp a r a m e t e r s c o r r e s p o n d i n g t ol r pm o d e l c o m p a r e dw i t hr e l a t i v el i t e r a t u r e ，t h et h o u g h to ft h i st h e s i sh a sam o r ee x c e l l e n t m e a n st ol r pm o d e ls o l v i n g ( 3 ) t h i st h e s i sd e v e l o p st h eg e n e t i c s i m u l a t e da n n e a l i n ga l g o r i t h ma n d g e n e t i c - t a b us e a r c ha l g o r i t h mt og e tt h eo p t i m i z ev a l u eo nt h el r pm a t hm o d e l b y p r o g r a m m i n gt h ea c c o u n ts o f t w a r ea n dt e s t i n gw i t hs o m ed a t a ，t h eh e u r i s t i cc o m b i n e d a l g o r i t h mg e t st h eo p t i m i z ev a l u eo fl r p c o m et r u e i th a sa i li m p o r t a n ts c i e n c er o l e i ni m p r o v e da n dd e v e l o p e do fc o m bin e do p t i m i z et h e o r yr e s e a r c h ( 4 ) t h i st h e s i sa n a l y z e st h ee f f e c to fi n v e n t o r yc o n t r o ls t r a t e g yo nt h ef a c i l i t i e s l o c a t i o na n dr o u t eo p t i m i z ep r o b l e m s ，a n de s t a b l i s h e sm o r ec o m p l e xc o m b i n e d l o c a t i o nr o u t i n ga n di n v e n t o r yp r o b l e m s ( c l r i p ) m o d e l ，a n dd e s i g n sat w o - s t a g e h e u r i s t i ca l g o r i t h mt og e tt h eo p t i m i z ev a l u e b yt e s t i n g 、析ms m a l ls c a l ed a t a , i t p r o v e st h a tc o m b i n e dl o c a t i o nr o u t i n ga n di n v e n t o r yp r o b l e m sm o d e lc a nm o r e e f f e c t i v e l yr e d u c et h el o g i s t i c sc o s tt h a nt h el o c a t i o n - r o u t ep r o b l e mm o d e l ，o rt h e i n v e n t o r yc o n t r o lp r o b l e mm o d e l b e s i d e st h eh e u r i s t i ca l g o r i t h mp r o v i d e dab a s i c t h o u g h t sf o ra n a l y z es o l v i n gp r o c e s so ft h el r p m o d e li nd e p t h ( 5 ) t h i st h e s i sp r o v i d e s8t o2 0 0n o d e st e s t i n gd a t as o u r c ei nd i f f e r e n ts c a l e s b a s e do i lt h el r pm o d e l ，s u p p l i e sa na p p r o a c ho fe v e r ya l g o r i t h ms c i e n t i f i c c o n t r a s t e df o rt h ef u t u r el r pr e s e a r c h e r sa n dd o e ss o m ei n i t i a t i v ew o r kf o r e s t a b l i s h i n gl r p m o d e lt e s t i n gd a t as o u r c e k e yw o r d s l o c a t i o nr o u t i n gp r o b l e m s ；l o g i s t i c ss y s t e m so p t i m i z e ： t a b u s e a r c ha l g o r i t h m ；s i m u l a t e da n n e a li n ga l g o r i t h m ； g e n e t i ca l g o r i t h m ；h e u r i s t i cc o m b i n e da l g o r i t h m ：i n v e n t o r y l o c a t i o nr o u t i n gp r o b l e m s v 论文独创性声明 本人声明：本人所呈交的学位论文是在导师的指导下，独立进行 研究工作所取得的成果。除论文中已经注明引用的内容外，对论文的 研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本论 文中不包含任何未加明确注明的其他个人或集体已经公开发表的成 田 7 k0 本声明的法律责任由本人承担。 论文作者签名：钢尺咋耖 夕卯彦年莎月莎日 论文知识产权权属声明 本人在导师指导下所完成的论文及相关的职务作品，知识产权归 属学校。学校享有以任何方式发表、复制、公开阅览、借阅以及申请 专利等权利。本人离校后发表或使用学位论文或与该论文直接相关的 学术论文或成果时，署名单位仍然为长安大学。 ( 保密的论文在解密后应遵守此规定) 论文作者签名：荡哦呻 导师签名：却谬汐 0 2 加8 年痧月莎日 ；h 川易年夕月易日 长安大学博士学位论文 1 1 选题的背景和研究意义 第一章绪论 1 1 1 选题的背景 随着物质需求的多样性和不规则性以及贸易呈全球化发展的趋势，目前作为“第三 利润源泉”的物流，其作用和地位显得比任何时候都更为重要，对经济活动的影响也日 益明显，已成为流通行业“最重要的竞争领域”，在当前和未来的市场竞争中必然起着 举足轻重的作用 1 2 j 。许多发达国家和地区己形成了比较成熟的物流管理理念、先进的物 流技术和高效的物流运营系统。我国在加入w t o 以后，也逐渐加快了现代物流的发展， 以提高生产企业在国际上的竞争能力。为此企业管理者都希望能协调物流系统中的各个 环节，以最低的价格、最好的服务来满足顾客的需要，所以物流决策显得极为重要 在传统的物流决策模型中，定位一配给问题( 1 0 c a t i o na l l o c a t i o np r o b l e m s ，l a p ) 和车辆运输路线安排问题( v e h i c l e r o u t i n gp r o b l e m ，v r p ) 是最值得关注的两个方面b 1 。 l a p 问题考虑物流设施( 工厂、库存点、分销中心等) 的定位与货物配给之间的相互关 系，目的是对设施的数量、位置进行决策，使设施的运作成本及车辆的运输成本最低。 在l a p 中，一般认为设施到客户的运输路线是放射线状的，因此，在确定设施的位置时， 忽视了对车辆巡回行程路线的考虑，这就有可能导致分销成本的增长h 3 ；而v r p 问题则 是指在设施位置己知的前提下，确定车辆在各个客户间的行程路线，使得运输路线最短 或运输成本最低1 。在v r p 问题中，考虑了车辆在各个客户点间巡回访问的特性，提高 了运输效率，并与实际情形相吻合。但在此问题中，未分析设旌的选址问题，这将会使 得整个物流成本不能达到最低。 企业管理者希望能协调物流系统中的各个环节，以最低的价格、最好的服务来满足 顾客的需要。由此，在l a p 、v r p 和其他物流决策模型的基础之上，产生了集成物流管 理系统的概念1 ，其目标就是要提高物流系统的效率。这种概念认为：在设施( 制造厂、 库存点或分销中心) 相对于客户的位置、货物的配给、运输货物的车辆路线安排之间存 在相互依赖的关系，根据这种关系来相应地进行综合优化与管理。应用这种集成物流管 理系统的概念，国外一批学者对物流设施定位和运输路线安排问题( l o c a t i o n r o u t i n g p r o b l e m s ，l r p ) 进行了综合研究p 3 。通过建立l r p 模型，对于多客户与可选物流设施的 情形，需要同时确定设施最优数量、位置、容量与寻求最优运输计划、路线安排之间的 第一章绪论 总体问题，从而进一步降低物流系统成本，以实现提高产品分销效率。 从2 0 世纪7 0 年代起，国外许多学者对l r p 优化问题进行了大量的研究，构建了一 些解决实际问题的优化模型，并找到了相应求解算法阳1 。但由于l , r p 问题的复杂性，对 该类问题的研究进展比较缓慢呻1 。2 0 世纪9 0 年代以来，国外的学者对物流系统优化中 的l a p 和v r p 的研究取得了一定的进展n 0 ，由此促进了对l r p 研究的发展。随着集成 化物流管理概念被越来越多的企业所接受和全球贸易的快速增长，l r p 问题的研究也成 为学术界关注的热点问题之一口3 。 1 1 2 研究意义 目前，在许多物流系统中，管理者常常要对以下情况做出决策： 1 工厂、仓库和配送中心的位置，本文称之为设施定位： 2 将一定区域内的客户分配给相应的设施并由其提供服务； 3 连接客户、原材料供应商、工厂、仓库的运输计划。 在某种情况下，这些决策是非常重要的，它们很大程度上影响着客户的服务水平和 整个物流系统的总成本。对于确定设施位置，已经有很多的数学模型可以用于解决该问 题n 引。尽管如此，这些模型所假设的设施和客户之间的运输成本是不准确的，每一个客 户都由一辆车来服务，服务后车辆返回设施，事实上，多个客户是可以由一辆车在一个 路线内来服务的，只要不超过车辆的容量限制即可，这些模型忽略了定位和路线问题的 一体化，而l r p 恰恰综合考虑了定位和路线问题之间相互联系的关系。因此，l r p 更 贴近目前的物流系统的实际特征，所以对l r p 的研究具有十分现实的意义。 在物流系统分析和设计中，物流设施定位和运输线路优化是其中关键问题。物流设 施的建设投资大、周期长、回收缓慢，且一经选定后就将长期运营。因此，物流设施的 合理定位选址( 新建、改扩建或租用) 就显得十分重要，它不仅与运行费用直接相关，而 且对工作效率及物流控制水平会产生很大影响。运输合理化，是从物流系统的总体目标 出发，运用系统工程的原理和方法，使物品在运输过程中，力求运输距离短、运输能力 省、运输费用低、中间转运环节少，到达速度快、运输质量高和劳动消耗少，以实现物 流系统效益最大化的目标u 3 j 。 现代物流区别于传统物流，其主要表现在将传统物流中分别处理的运输、仓储、信 息处理等环节有机的结合在一起。它的核心思想就是强调“系统性”。本文将定位一配给 问题和车辆路线问题作为一个整体来研究，考虑到两方面不同因素彼此间的影响，在借 鉴已有的研究成果基础上，提出对该问题所对应数学模型的有效解法。 2 长安大学博士学位论文 由于l r p 模型及其变形属于n p h a r d 问题【1 4 1 ，在大规模节点数情况下目前仍无法 求得最优解。但实际中由于物流设施的投资建设将占去固定成本的较大比重，因此对物 流设施布局和选址进行优化非常重要；同时对车辆线路进行优化，可提高物流运营经营 效益。因此对由l a p 和v r p 二者构成的l r p 问题( 如图1 1 所示) 进行系统的优化研 究具有重要的理论价值【”1 ；同时也是发展基于电子商务的城市物流配送理论基础之一， 将为日后面对巨大交易量的电子商务环境下开发物流自动配送调度系统软件也具有非 常重要的现实意义。综上所述，在物流系统中如何优化定位一配给问题和车辆路线问题 有重要的理论价值和现实意义。 图1 1定位( l o c a t i o n ) 、分配( a l l o c a t i o n ) 、路线( r o u t i n g ) 三者之间的关系 1 2l r p 问题概述 在一般情况下，l r p 可以描述为：给定一系列客户点和一系列潜在的设施点，客 户点数量、位置、需求量都是己知或可以估算出的；潜在设施点位置己知，现从这些潜 在设施点中确定出一系列的设施数量和位置，即选取最佳的设施数量及位置，同时还要 确定出一套从各个选中设施点到各个客户点的运输线路【1 6 1 。确定的依据是满足问题的目 标函数( 通常是总的费用最小) 。目标函数( 总费用) 一般包括设施点建设成本、运作成本 以及车辆的固定成本、运输成本等。约束条件包括：货物由一个或多个设施点供应，每 个客户点只接受来自一个设施点的货物；设施点和运输车辆有容量和数量的限制；客户 点有交货时间窗口限制等。l r p 示意图如图1 2 所示。 3 第一章绪论 图中，表示选中的设施；表示未被选中的设旌；o 表示客户点；一表示运输线路 图1 2l i l p 示意图 1 3 l r p 问题国内外研究现状 关于l i 冲概念的研究可以追溯到1 9 6 1 年v o nb o v e n t e r 关于运输问题中运输成本和设 施选址成本的相互关系【l7 1 ，但早期研究一般是集中在l r p 的复杂性方面，后来才逐渐意 识到选址定位和运输决策间的协调性问题。直至r j 2 0 世纪7 0 年代，定位和路线问题的相互 依赖关系才被认识到。c o o p e r n 踟把定位问题与运输问题结合起来，提出了运输一定位问 题( t r a n s p o r t a t i o n l o c a t i o np r o b l e m ，t l p ) 。在这个阶段，学者们对l r p 的研究还是 相当肤浅的，还没有真正涉及运输路线安排问题。到了7 0 年代中期，一些学者在研究 运输一定位问题时，开始加入v r p 的多点运输的特征，w a t s o n - g a n d y 和d o h r n n 叩是最早进 行这方面工作的学者。但由于l r p 问题的解决比通常的运输以及定位模型的难度要大得 多，因此研究的进展相当缓慢。 到7 0 年代末，8 0 年代初，伴随着集成物流系统概念的出现，l r p 才开始逐渐被重 视。相对于研究广泛的纯定位问题和纯v r p 问题以及它们的变形，对l r p 的研究仍非常 有限。直到8 0 年代以后，由于实际应用的迫切需要和计算机的快速发展，l r p 的研究 才有了真正意义上的发展，典型的代表应属1 9 8 6 年l a p o r t e 关于l r p 精确解法的描述 【2 0 1 。除了l r p 问题本身的复杂性，一些相关变量如车辆容量、设施容量以及设施潜在位 置数量等的变化也被加入到l r p 问题中需要加以解决，求解l r p 问题变得更加复杂。因 此，近似解法在求解l r p 问题中比精确解法得到广泛应用便不足为奇了。许多的研究， 例如g o l d e ne ta l 1 ，o r 工与p i e r s k a l l a 吲，j a c o b s e n 和m a d s e n 1 ，s r i k a r 和 s r i v a s t a v a 1 3 1 ，p e r l 和d a s k i n 口3 2 钉已经为求解l r p 以及带有如容量限制、最小成本、 最长旅行长度等边界约束的l r p 问题建立了模型和算法。在求解l r p 问题的过程中，可 以将l r p 问题看成以下三个子问题的集成n 别：( 1 ) 定位问题( f a c i l i t yl o c a t i o n ) ；( 2 ) 4 长安大学博上学位论文 需求配给问题( d e m a n da l l o c a t i o n ) ； ( 3 ) 车辆路线问题( v e h i c l er o u t i n g ) 。分开求 解这些子问题的最优解得到的往往不是l r p 问题的最优解，然而，将这三个子问题合并 一起计算是不现实的。为了更有效地求解l r p 问题，两种类型的连续方法被广泛采用： ( 1 ) 定位一指派一路线( 1 0 c a t i o n a 1 1 0 c a t i o n r o u t i n g ，l a r ) ，例如文献 8 ，9 中描 述的方法；( 2 ) 指派一路线一定位( a l l o c a t i o n r o u t i n g 一1 0 c a t i o n ，a r l ) ，如文献 9 ，1 3 中所述。除了启发式解法，l a p o r t ee ta l 在求解l r p 问题的精确解法方面做出了一系 列重要贡献j 6 2 量2 6 打1 ，如l a p o r t e 在文献 1 6 中介绍了一种方法，它将多站点车辆路径 问题( m u l t i d e p o tv e h i c l er o u t i n gp r o b l e m ，m d v r p ) 和l r p 通过应用图的形式转化 为相应的约束指派问题，并应用分支定界法给予了求解。在文献 2 7 中l a p o r t ee ta l 介绍了一种随机l r p 模型，该问题中只有当车辆到达客户点的时候才知道客户的需求量， 开始阶段不考虑客户的需求量进行l r p 决策，当违背路线上容量限制的时候，在第二阶 段采取适当罚金的方式加以补偿，文中提出了该问题的数学模型并求得优化解。但是由 于精确解法的内在特性，建立设施的数量和客户点的数量在确切模型中是非常有限的， ， 所以这些确切的模型只适用于较小规模的问题。p e r l 和d a s k i n 在文献 2 3 中第一次系 统的描述了仓库定位一运输路线安排问题( w a r e h o u s el o c a t i o n r o u t i n gp r o b l e m ， w l r p ) ，经过对w l r p 做一些变形，之后又提出了一种以连续的方式求解变形w l r p ( m o d i f i e dw l r p ) 的方法心4 。h a n s e n 恻等介绍了一种更为有效的求解变形w l r p 的方法。 s r i v a s t a v a 和b e n t o n 在 2 9 中研究了可能影响配送系统设计的一些环境影响因素。文 献 3 0 中，c h i e n 介绍了一种求解l r p 问题的优化方法，他在计算路线成本的过程中应 用了对两个不同的估计值预测路线的长度，从而估计路线的运输成本。s a l h i 和f r a s e r 提出了一种迭代方法，在定位阶段和路线阶段之间不断交换，直到遇到一个合适的停止 准则。该文介绍了一种更为符合实际的l r p 问题，车辆的容量可以不同。n a g y 和s a l h i 口2 删 应用了嵌套算法( n e s t e dm e t h o d ) 的概念来求解l r p 问题，思路是将路线问题看作一 个较大规模定位问题的子问题来处理。m i ne ta 1 在 3 4 中综合了过去的研究和建议提 出了一些未来l r p 问题的发展方向。碱h i sw u ，c h i n y a ol o w 和j i u n n - w e ib a i l l 2 1 ( 2 0 0 2 ) 将l r p 问题分解为l a p 和v r p 两个子问题分别进行求解。l i u ，s c 和l i n ，c c d s i ( 2 0 0 4 ) 研究了求解定位路线和库存控制组合优化l = - j 题的启发式算法。m a r i a 【3 6 】( 2 0 0 5 ) 对一种 简单的l r p 模型给出了严格的解界限。w a n g ，x u e f e n g ；s u n ，x i a o m i n g ；f a n g ，y a n g 【j ，j ( 2 0 0 5 ) 运用两阶段混合启发式搜索方法对l r p 进行了求解，b o u h a f s ，l y a m i n e l 3 8 1 ( 2 0 0 6 ) 用模拟退火和蚁群组合算法求解了带容量约束的定位路线问题。m a r i aa l b a r e d a 、e l e n a 5 第一章绪论 f e r n d n d e z 、g i i b e r tl a p o r t e 啪1 ( 2 0 0 7 ) 研究了随机l r p 问题，并建立了两阶段模型， 提出了两阶段启发式算法和下界求法。b a r r e t o ，s e r g i o m l ( 2 0 0 7 ) 用聚类分析法解决 了带容量约束的定位一路线问题。r o s e m a r yt 、c o l l e t t er 、m a r ks h ( 2 0 0 7 ) 用分枝 定价( b r a n c h a n d p r i c e ) 算法求解了具有1 0 个潜在设施、i 0 0 个客户节点的l r p 问题。 r o b e r tr u s s e l l 、w e n c h y u a nc h i a n g 、d a v i dz e p e d a 位1 ( 2 0 0 8 ) 采用禁忌搜索算法针对 l r p 中涉及大量多品种印刷品且有时间窗约束的配送问题进行了有效求解。 9 0 年代以来物流系统管理的概念被越来越多的企业所接受，同时伴随着全球贸易的 快速增长，提高分销效率成为企业生存与发展的必由之路，l r p 的研究在各相关领域得 到了特别关注和快速发展。但遗憾的是我国关于这方面的研究报道尚不多见，2 0 0 0 年管 理科学学报汪寿阳 4 】等介绍了国外研究l r p 的概况，2 0 0 3 年东北大学学报张潜3 】 等介绍了l r p 优化算法评述，2 0 0 4 年管理工程学报林岩【4 3 】等介绍了l r p 研究评述， 2 0 0 4 年计算机工程与应用张长星m j 等介绍了有关l r p 的遗传算法，2 0 0 4 年工业 工程与管理黄春雨 4 5 】等研究了基于缩短物流多阶响应周期的l r p 模型，2 0 0 5 年物 流技术章海峰【4 6 】等分析了一类节点带两重容量限制的l r p 问题，即在物流网络受物 流中心吞吐能力和物流网络节点最大单批处理能力两重约束的情况下，如何进行物流中 心选址和运输路线安排，使总的费用最小；2 0 0 6 年科技导报马小伟一刀建立了一类 带时间窗口的定位路径问题的数学模型，并用节约法求解了客户分配和路线优化问 题。2 0 0 7 年系统工程理论与实践胡大伟阻踟等运用遗传和禁忌搜索组合算法对l r p 小规模问题实现了有效求解。但总体上来讲我国在l r p 方面的研究仍处于初始阶段， 多为国外资料的一些介绍和翻译，缺乏系统性研究，特别是关于模型的普适性验证和算 法的标准性测试方面仍处于空白。 1 4 本文的主要研究内容 l r p 的研究虽然已经取得了一定的发展，但随着实际物流系统集成的程度越来越 高，物流决策者面临的问题也越来越复杂，相应的求解要求也有所提高，因此现有的研 究成果仍有待进一步深入，如模型适应性及其系统性研究，新算法和新技术应用，