（系统工程专业论文）配送中心选址模型与算法研究.pdf

配送中心选址模型与算法研究 摘要 在物流网络中，配送中心连接着供货点和需求点，是两者之闻的轿粱，在物流系统中有着举足 轻重的作用，因此搞好配送中心的选址将对物流系统作用的发挥乃至物流经济效益的提高产生重要 的影响。 本论文在综述配送中心选址问题研究现状的基础上，通过对配送中心选址特点的分析，对配送 中心选址的模型和算法进行了研究。全文主要内容如f ： ( i ) 详细介绍了有关配送中心选址问题的研究现状，分析了配送中心选址问题的基本理论与方 法，其中对于本文研究相关的方法作了重点介绍，为下文进一步研究配送中心选址问题奠定了基础。 ( 2 ) 定性研究了配送中心选址问题，通过对影响配送中心选址影响因素的分析。构建了配送中 心选址评价的指标体系，在此基础上，运用多层次灰色评价方法建立了配送中心选址多层次灰色评 价模型。最后通过实例分析表明该模型能很好地处理配送中心选址问题，为决策者提供一种有效的 优化工具。 ( 3 ) 研究了配送中心的连续性选址问题，将小生境粒子群优化算法和a l a 方法相结合，提出 了解决此类模型的混合粒子群优化算法。通过算例表明该方法能有效解决配送中心的连续性选址问 题。 ( 4 ) 提出了有竞争的配送中心选自 模型，崩常规启发式算法对有竞争的物流配送中心选斛闯题 进行求解时，经常会陷入局部优化解。针对这一情况，本文引用d r e z 2 n e r 算法的思想，提出了解决 此类模犁的混合遗传算法。该算法充分利用d r e z n e r 算法的局部搜索能力和遗传算法的全局优化能 力。使计算结果能更接近全局最优解。最后通过实例分析表明该算法能很好地处理有竞争的物流配 送中心选址问题，为决策者提供一种有效的优化t 具。 ( 5 ) 超出了基于“成本服务型”战路的配送中心选址模型，该模型是在有距离约束的p - m e d i a n 问题的基础上建立起来。结合该模型的特点，本文提出了一种求解该模犁的免殪算法，通过实例分 析，该算法能有效地求得问题的优化解和近似优化解。 ( 6 ) 研究了一类考虑躅定成本的配送中心选址方法，针对该模型及其算法复杂的特点，引入了 二重结构编码的方法，与运输问题的算法相结合，提出了一种混合的遮传算法。该方法有效地解决 了约束条件的限制，提高了算法的搜索效率。实验表明，该算法贝有较好的收敛能力，能够快速地 进化到最优解附近。 ( 7 ) 提出了一种综合g a h p 和目标规划的配送中心选自p 摸璎，物流系统配送中心选计所涉及 的影响因素众多，这些因素中既有定性丙素，义有定颦冈索。本文首尢用灰色层次分析法对这些影 响因素进行处理，得到了各备选点的权值。针对灰色层次分析法无法解决条件约束问题，提出了用 灰色层次分析法和目标规划方法相结合用于物流配送中心选打卜的模犁a 晟后通过示例表明该模型能 有效地处理物流配送中心选址问题。 关键词：配送中心，选址，灰色系统理论小生境，粒子群优化算法，d r e z n e r 算法，遗传算法，免 疫算法，灰色层次分析法，目标规划 i i r e s e a r c ho nt h el o c a t i o nm o d e l sa n d a l g o r i t h m so fd i s t r i b u t i o nc e n t e r s a b s t r a c t d i s t r i b u t i o nc e n t e ri sab r i d g ec o n n e c t i n gp r o v i d e r sa n dc l i e n t si n l o g i s t i c sn e t w o r k i tp l a y sa l l i m p o r t a n tr o l e i nl o g i s t i c ss y s t e m g o o dl o c a t i o no ft h ed i s t r i b u t i o nc e n t e r sh a sap u s h i n ge f f e c to nt h e f u n c t i o no f d i s t r i b u t i o nc e n t e r sa n dt h ei m p r o v e m e n to f e c o n o m i cb e n e f i t s b a s e do ns u m m a r i z i n gt h er e s e a r c h i n ga c t u a l i t i e so fl o c a t i o np r o b l e mo fd i s t r i b u t i o n c e n t e r s ，t h e a u t h o ra n a l y z e st h ec h a r a e t e r i a t i co f d i s t r i b u t i o nc e n t a l o c a t i o na n dr e s e a r c h e st h em o d e l sa n da l g o r i t h m s o f d i s t r i b u t i o nc e n t e r s t h em a i nc o n t e n t so f t h i st h e s i sa r ea sf o l l o w e d ： ( 1 ) t h er e s e a r c h i n ga c t u a l i t yo f d i s t r i b u t i o nc e n t e r sl o c a t i o ni si n t r o d u c e da n dt h eb a s i ct h e o r ya n d m e t h o d so fd i s t r i b u t i o nc e n t e r sl o c a t i o n a r ea n a l y z e d t h em e t h o d sa b o u tt h er e s e a r c ho ft h i st h e s i sa r e i n t r o d u c e di nd e t a i l t h i sp r o v i d e sab a s eo ns t u d i n gd i s t r i b u t i o nc e n t e r sl o c a t i o n ( 2 ) t h eq u a l i t a t i v ed i s t r i b u t i o nc e n t e r sl o c a t i o ni sr e s e a r c h e d t h ei n d e xs y s t e mo fl o c a t i o n a s s e s s m e n tt od i s t r i b u t i o nc e n t e r si sc o n s t r u c t e db ya n a l y z i n gi n f l u e n c i n gf a c t o r so fd i s t r i b u t i o nc e n t e l l o c a t i o no nt h eb a s i so fi t , ah i e r a r c h yg r e yc o m p r e h e n s i v ea s s e s s m e n tm o d e lo fd i s t r i b u t i o nc e n t e r s l o c a t i o ni se s t a b l i s h e d b yu s i n gh i e r a r c h yg r e yc o m p r e h e n s i v ea s s e s s m e n tm e t h o d a n e x a m p l e d e m o n s t r a t e st h a tt h em o d e lc a ns o l v et h ep r o b l e mo f d i s t r i b u t i o nc e n t e r sl o c a t i o na n dp r o v i d em e f f e c t i v e d e c i s i o nt o o lf o rd e c i s i o n m a k e n ( 3 ) t h ec o n t i n u o u sl o c a t i o nm o d e lo fd i s t r i b u t i o nc e n t e r si sr e s e a r c h e d n i c h ep a r t i c l es w a r m o p t i m i z a t i o ni sp u tf o r w a r da n dt h e nh y b r i dp a r t i c l es w a r mo p t i m i z a t i o ni sc o n t r u c t e dc o m b i n gw i t ha l a a l g o r i t h mt or e s o l v et h i sm o d e l e x a m p l e ss h o wt h a tt h ea l g o r i t h mc a l lb eu s e de f f e c t i v e l yt os o l v et h e c o n t i n u o u sl o c a t i o nm o d e lo f d i s t r i b u t i o nc e n t e r s ( 4 ) t h ec o m p e t i t i v el o c a t i o nm o d e lo f d i s t r i b u t i o nc e n t e r si sp r e s e n t e d t h el o c a lo p t i m a ls o l u t i o ni s o r e ng o tb yt h eg e n e m lh e u r i s t i ca l g o r i t h mf o rc o m p e t i t i v el o c a t i o nm o d e l t os o l v et h i s p r o b l e m ，t h e p a p e rc i t e sd l e z n e ra l g o r i t h mt oc o n s t r u c tah y b r i dg e n e t i ca l g o r i t h m t h ec o m p u t i n gr e s u l to ft h e a l g o r i t h mi sn e a r e rt ot h eg l o b a lo p t i m a ls o l u t i o nb yc o m b i n i n gl o c a ls e a r c ho fd r e z n e ra l g o r i t h ma n d g l o b a lo p t i m i z a t i o no f g e n e t i ca l g o r i t h m a ne x a m p l ed e m o n s t r a t e st h a th y b r i dg e n e t i ca l g o r i t h mc a ns o l v e t h ep r o b l e mo f c o m p e t i t i v el o c a t i o no f l o g i s t i c sd i s t r i b u t i o nc e n t e r sa n dp r o v i d e sa l le f f e c t i v ed e c i s i o nt o o l f o rd e c i s i o n m a k e l ( 5 ) t h el o c a t i o nm o d e lo fd i s t r i b u t i o nc e n t e r sc o n s i d e r i n gb o t hs e r v i c ea n dc o s ti sb r o u g h tf o r w a r d n i i ti sb a s e do np - m e d i a np r o b l e mw i t hd i s t a n c er e s t r i c t e d ，t h i sd i s s e r t a t i o ns u g g e s t sa ni m m u n ea l g o r i t h m f o ri tb yc o m b i n gt h ef e a t u r eo ft h i sm o d e l t h eo p t i m a la n dn e a r l yo p t i m a ls o l u t i o nt ot h em o d e lc a i lb e f o u n de f f e c t i v e l yw h i c hi ss h o w nb yt h ee x p e r i m e n t s ( 6 ) t h el o c a t i o nm o d e lo fd i s t r i b u t i o nc e n t e r sc o n s i d e r i n gt h ef i x e dc h a r g ei sr e s e a r c h e df o rl h e c h a r a c t e r i s t i co ft h i sm o d e la n di t sc o m p l e xa l g o r i t h m ，t h i sp a p e rs u g g e s t sah y b r i d g e n e t i ca l g o r i t h m c o m b i n i n gb i l e v e ls t r u c t u r a lc o d i n gw i t ht r a n s p o r t a t i o np r o b l e m t h ea l g o r i t h mr e s o l v e dt h er e s ”i c t i o no f c o n s t r a i n t se f f e c t i v e l ya n di m p r o v e di t ss e a r c h i n ge f f i c i e n c y t h et e s td e m o n s t r a t e st h a tt h ea l g o r i t h mh a s g o o de f f o r t st or e a c ht h er o u n do f o p t i m a ls o l u t i o n ( 7 ) al o c a t i o nm o d e lb yc o m b i n i n gg a h pa n dg o a lp r o g r a m m i n gi sp r e s e n t e d d i s t r i b u t i o nc e n t e r s l o c a t i o ni nl o g i s t i cs y s t e mi n v o l v e sal o to ff a c t o r s ，s o m eo fw h i c ha f eq u a n t i t a t i v e ，o t h e r so f w h i c ha r e q u a l i t a t i v et h i sp a p e rf i r s t l yg e t st h ew e i g h to fe a c hd i s t r i b u t i o nc e n t e r sb yu s i n gg a h po nt h eb a s i so f a n a l y z i n gt h ef a c t o r s f o rg a h p c a nn o ts o l v et h ep r o b l e mw i t hc o n s t r a i n t , al o c a t i o nm o d e ii s d r o p o s e d b yc o m b i n i n gg a h pa n dg o a lp r o g r a m m i n g t h em o d e lf o rl o c a t i o no fd i s t r i b u t i o nc e n t e r si n i o g i s t i c s y s t e mi sp r o v e dt ob ee f f e c t i v eb ye x a m p l e s k e y w o r d s ：d i s t r u t i o nc e n t e r s ，l o c a t i o n ，g r e ys y s t e mt h e o r y , n i c h e ，p a r t i c l es w a r mo p t i m i z a t i o n ，d r e z n e r a l g o r i t h m ，g e n e t i ca l g o r i t h m ，i m m u n ea l g o r i t h m ，g r e ya n a l y t i ch i e r a r c h yp r o c e s s ，g o a lp r o g r a m m i n g v 东南大学学位论文独创性声明 本人声明所里交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他入已经发表或撰写过的研究成果，也不包含为获得东南大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 研究生签名：日期： 兰竺：! 三二! ! 东南大学学位论文使用授权声明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位 论文的复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人 电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文外，允许论 文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分内容。论文的公布( 包 括刊登) 授权东南大学研究生院办理。 研究生签名：獬师签名：7 盟日 期：丝业 绪论 0 1 引言 绪论 现代物流业是把握竞争优势的有效方式，将为国民经济在高起点上持续发展，提供基础动力。 在经济全球化和信息化的推动下，现代物流业已从为社会提供传统运输服务，扩展到以现代科技、 管理和信息技术为支柱的综合物流系统。目前。许多发达国家和地区已形成了比较成熟的物流管理 理念、先进的物流技术和高效的物流运营系统。进入2 1 世纪的中国必将加快现代物流的发展。以 此增强企业的竞争能力、优化资源配置，提高经济运行质量，实现中国经济体制与经济增长方式的 两个根本性转变，从而推动中国经济的持续健康发展。 物流的概念最早产生了美国，其后在欧洲和日本也得王0 了j “泛的应用。目前，我国物流理论研 究和实践都处于起步阶段，同国外先进水平相比仍有相当大的差距。改革开放以来，我们以合资或 独资的方式建立起了一定数量较有特色的物流企业，借鉴或引进了部分先进的物流经营形式和管理 思想。但由于我国企业经营的环境与国外著距较大，国外物流管理的一些思想和方法并不一定完全 适用于我国的具体情况，必须对国外物流理论和实践的成果进行消化、改进和吸收，在这一过程中， 我国自身的物流研究起着十分重要的作用。应该说，经过多年的努力，我国物流理论研究已取得了 很大进步。首先，理论界已突破了传统仓储和运输业的界限将物流理解为包含有运输、仓储、包 装、装卸搬运、流通加工和配送等诸多功能要素的综合服务系统，认为物流不仅仅是以上功能要素 的简单相加，而是将它们进行箍合，在内涵上进行拓展以后所产生的一种全新的服务形式。物流概 念已从流通领域延伸到了生产领域，甚至在1 ：程管理、设备维护等请多方面部得到了应用。 物流规划技术是物流战略管理的重要内容，也是物流定量化研究的主要方面。我国研究物流规 划技术的成果主要体现在如下几个方面”： ( 1 ) 将原有各功能要素的研究模型进行整合，以供应链思想为指导，从追求小系统的局部最优 转变为追求较大系统的接体最优。 ( 2 ) 引进和开发了部分物流规划的专门技术，比如物流网点布局的模拟方法、物流中心规划的 启发式方法等等。 ( 3 ) 计算机技术在物流规划中得到，“泛应用，使复杂的模型运用于实践成为可能。 我国现代物流企业的经营形式，大多是从借鉴国外经验开始的，与之对应的各种优化管理方法。 一直是物流理论研究的重点。目前，人们对物流合理化问题的研究主要集中在四个方面： ( 1 ) 运用线性规划、非线性规划制定最优运输计划，实现物流合理化。 ( 2 ) 运用系统分析技术选择货物的虽佳配比及线路，实现物流的优化配送。 ( 3 ) 运用存储论，确定经济合理的库存鼍，实现物流的优化存储。 ( 4 ) 运用模拟技术，对整个物流系统进行研究实现物流系统的最优化。同时。还将以上研究 成果与计算机技术结合起来，开发了一些物流企业管理的商用软件，使我国物流企业逐步走上了现 代化管理之路。 应该看到，我国物流理论研究还存在着很多方面的不足。不论是同国外先进水平相比，还是从 东南人学博i + 学位论文 我国经济发展的客观要求出发。理论研究的水平都显得相对落后在某些方面甚至出现了理论滞后 于实践的情况。今后物流的发展趋势主要体现在以下几个方面f ” ： ( 1 ) 物流的系统化 物流是从原料到最终商品的流动的庞大的系统，对采购、供应、制造、销售广义制造过程中产 品、服务及其相关信息的流动与储存进行规划、执行和控制。随着全球竞争和全球制造的日益加剧， 越来越多的制造企业意识到，要想获得长期发展，不仅要降低生产成本，更重要的还要为顾客提供 及时、准确、具有个性化的产品和服务。很多研究和实践表明，通过合理设计和管理物流系统，可 以达到提高企业竞争优势的目的。 ( 2 ) 物流的信息化 随着全球经济的一体化趋势，当前的物流上e 向全球化、信息化、一体化发展。商品与生产要素 在全球范围内以空前速度自由流动与配置。电子商务技术与互联网的虑用使物流效率的提高更多地 取决于信息管理技术。物流的信息化包括：商品代码和数据库的建立、运输网络合理化、销售网络 系统化、物流中心管理电子化。 ( 3 ) 仓储、物流装备的现代化 物流离不开物流装备与仓储，仓储现代化要求高度机械化、自动化、标准化，组织起高效的人 机物系统。物流装备正向大型化、自动化和智能化发展。 ( 4 ) 物流与商流、信息流一体化 按照流通规律，商流、物流、信息流是三流分离的。但是现代社会不同的产品形成不同的流通 方式与营销形式，比如生产资料不仅有直达供货与经销制，还有代理制、配送制，与人民生活有关 的产品还有连锁经营，这就要求物流随之而变化。许多国家的物流中心、配送中心实现了商流、物 流、信息流的统一。 ( 5 ) 物流系统的柔性化 随着市场经济的发展，计划经济时期的嘲定物流运作模式转变为多样化。市场的多变性，产品 的小批鼋、多品种要求物流系统具有对这种物流运作方式的适应性以满足生产企业和用户对产品 的需求。 ( 6 ) 物流系统的仿真技术 物流系统是一个庞大的系统，其实施需要巨大的资金和人力投入。为保障其实施的科学性和可 靠性，需要在实施之前进行仿真研究。 0 2 配送中心的概述睁1 0 l 0 2 1 配送中心的概念 配送中心是从供应者手中接受多种人晕的货物，进行包装、分类、保管、流通加l 和情报处理 等作业，然后，按照众多需要者的订货要求各齐货物，以令人满意的服务水平，进行配送的设施。 配送中心是一种末端物流的节点设施。通过有效地组织配货平送货。使资源的最终配置得以完成。 是一种以丰七会分i ：为基础的、综合的、完善化和i 现代化的送货活动。货物在从其生产地至批发、零 2 绪论 售网点并最终销售给消费者的流动过程中，一般要在配送中心中进行一定的分类、保管和流通加工 等处理，配送中心已成为连接生产和零售的一个纽带。 0 2 2 配送中心在物流系统中的主要职能 配送中心是集货物包装、加工、仓储、装卸等多项服务功能的现代物流基础设施，是执行货物 配送为主要职能的物流据点。在物流系统中，配送中心作业过程如图o 1 所示。 图0 1 配送中心作业流程图 ( 1 ) 集货职能 集货职能是配送中心最基本的职能。配送中心把各个供给点供给的货物集中和进行相应的物流 作业。如仓储、加工，包装等，然后根据用户的不同需求进行不同的配送a 货物进入配送中心到进 行分货之前，配送中心发挥的是集货职能，必须具备以仓库为基础的仓储设施，能对各种货物进行 保管、贮藏等 ( 2 ) 加1 ：包装职能 加工包装职能是配送中心的重要职能。货物在配送中心集中之后，人都要进行不同稃度的加1 二 包装，这样可以使货物配送的效率提高，从而为顾客提供快速准时的配送a ( 3 )分货职能 分货职能是配送中心的核心职能。配送中心是一个中介服务结构，货物在配送中心集中和进行 物流作业之后，最终都要根据需求点的要求，进行相应的分货，然后配送到各个需求点 0 2 3 配送中心的分类 ( 1 ) 零售供货配送中心 这是专门为某个集团企业组织供货的配送中心。零售企业发展到一定的规模后，就会从增强企 业的核心竞争力的高度去研究建设配送中心的问题。 ( 2 )专业配送中心 这类配送中心多见于制造业的销售配送系统，用以降低流通费用、提高售后服务质觜和及时地 3 东南大学博f 学位论史 将预先配齐的成组元器件运送到规定的加工和装配工位。 ( 3 ) 共同配送中心 这是以城市范闱为配送圈的配送中心，近几年营返情况良好的厂商联合的配送中心就属此类。 众多厂商通过配送中心的共同配送，向众多的零售店配送商品。它的特点是，返距短、反麻速度快、 反应能力强，能从事多品种、少批量、多用户的配送。 ( 4 )区域性配送中心 这是以较强的辐射能力和库存能力向周边范围的配送据点或用户拣选配送的大型配送中心。 这种配送中心的规模较大，用户也较多，配送批量也较大，而且往往是给下一级配送据点或营业所、 批发商、商场等配送。 当然，如果按功能来分类，还有存储型配送中心、中转型配送中心、加工型配送中心等。 随着国民经济的发展，物流业越来越被人们重视，许多城市都把物流业作为重点发展的产业。在 大力发展物流业的同时，人们面i 临着一个共同的问题配送中心如何进行合理地选址。在物流网 络中，配送中心连接着供货点和需求点，是两者之间的桥梁，在物流系统中有着举足轻重的作用， 合理的物流配送中心选计能育省费用，加快货物的流通，增加物流企业的收益。因此，物流配送中 心的选址决策对于整个物流系统的优化是个十分重要的问题。 0 3 问题的提出 现代化物流配送是社会化大生产、国民经济发展的客观要求，它的发展状况对经济发展、商品 流通和大众消费起着重要的促进或制约作用。物流配送中心选址，是物流系统优化环节中关键的一 环。好的配送方案，不仅能够节约物流成本，提高商品运动的速度，而且还由于它能有效连接生产 与消费，从而既有利于物流服务和商品附加价值的实现，又能有效促进生产商按需生产，真上e 使物 流的管理建立在实需经营的基础上。 由于配送中心选址的决策不仅直接关系到日后配送中心自身的运营成本和服务水平，而且关系 到整个社会物流系统的合理化，因此配送中心选址是配送中心建没项目规划中至关重要的问题。同 时配送中心选址决策属于物流系统的长期规划，建设地点一日进定则很难改变，因此在进行配送中 心选址决策中通常要全面考虑众多影响冈素，这使得配送中心选坩问题一般都竹常复杂，难以解决， 通常需要将定性和定量技术结合起来以寻求最合适的解决方案。 根据这种情况，本文对几种配送中心的选址模型进行了研究，并结合模型的特点设计出了相应 的算法。 0 4 配送中心选址的研究概况 0 4 1 选址问题的早期研究 许多选址问题的早期理论是由土地经济学家和区域地理学家提出的。运输成本在选址决策中的 重要作用是贳穿所有这些早期研究的共同主题。晟早的选址问题是由w e b e r 在1 9 0 9 年提出的。他所 考虑的选坩问题是确定一个仓库付置。从而使仓序与各处客户之间的总运输距离最短。对丁这一问 4 绪论 愿，l s a r d 于1 9 5 8 年结合了上业选址、土地使_ e i j 和相笑问题进行了重新研究。另一个较早的选址问 题是由h o t e l l i n g 于1 9 2 9 年提出的。h o t e l l i n g 是一个经济学家。他提出的问题是在一条直线上两个 竞争供应商的选址。随后s m i t h i e s 和s t e v e n s 对这一问题进行了扩展。 在1 9 世纪5 0 年代和6 0 年代初，许多人在研究设施布置和设计问题，l o s c h 和m o s e s 认为经济 困索与生产中心选址是有关系的。m i c h l e 则研究使网络内的连接砭度最小化的问题。在1 9 世纪6 0 年代中期以前，选址理论的研究工作是在各个不相关的领域内展开的，因此并没有形成统一的理论。 直到1 9 6 4 年，h a k i m i 对选址问题进行了更加理论化的研究，他考虑了带有一般性的问题，就是在 一个网络中选顶一个或多个设施的位置，使得总距离或设施与点之间的最大距离最小。至此，选址 理论已有了很大发展并扩展到很多实际应用中 1 连续性选址模型1 1 5 - 2 9 1 连续性选址模型具有如下两个属性；孵空间是连续的；距离是可测的。连续性选址需要计 算待建设施的坐标，它的目标函数是使设施和给定需点的距离之和最小。 w e b e r 问题就是选择单个设施的地址，使得设施与给定需点的加权距离之莆嘬小。该问题一般 用类梯度算法进行求解。该算法最早由w e i s z f e l d 提出，后来m i e h l e 对其进行了进一步改进对于 有三个需点的w e b e r 问题，w e b e r 在他1 9 0 9 的论著中就有所叙述，所以后来该问题就以他的名字来 命名。1 9 9 3 年w e s o l o w s 姆对w e b e r 闯题的发展情况进行了综述。 该问题的扩展模型是需要设置多个设施并向各需点提供服务该问题称为多源w e b e r 问题 ( m w pm u l t i s o u r c e p r o b l e m ) ，该问题是个n p 难题。p o s i n g 和m e r l e 提出了求解该问题的精确算 法，t a i l l a r d 、h a n s e n 和b r i m b e r g 提出了启发式算法。对于选择两个设施的特例，o s t r e s h 、d m z n e r 、 r o s i n g 和c h e n 进行了分析。另外许多学者对该模型进行了进一步的研究和分析( h a m a e h e r 和n i c k e l ， 1 9 9 4 ；k a f e r 和n i c k e l 2 0 0 1 ；k l a m r o t h ，2 0 0 1 ；m e l a c h r i n o u d i s ，1 9 9 8 ；e r k u t 和n e u m a r i 1 9 8 9 ； b r i m b e r g 和m e h r e z ，1 9 9 4 ：c h e n ，1 9 9 2 ：k r a r u p 和p m z a n ，1 9 7 9 ；l o v e 等，1 9 9 8 ：f r a n c i s 等，1 9 9 2 ) 2 网络选址模型【3 ”】 在网络模型中。距离按照图中的最短路进行计算。顶点对廊各需求点，可能的选址地点对应于 顶点或边上的点。 网络选址模型中对应丁二连续性多源w e b e r 问题的模型是p - m e d i a n 问题。在p - m e d i a n 问题中。p 个设拖必须建立在图上，使得图中的顶点到离它最近的设施的距离最小。h a k i m i ( 1 9 6 4 ，1 9 6 5 ) 指 出，在距离函数是凹函数的情况下，选址点的集合可在图的顶点中获得关于该问题的算法已有不 少学者进行了研究( c h r i s t o f i d e s 和b e a s l e y ，1 9 8 2 ；h a n j o u l 和p e e t e r s ，1 9 8 5 ，b e a s l e y ，1 9 9 3 ：k l o s e 。 1 9 9 3 ) 。 p - c e n t e r 问题的目标函数是设置p 个设施，使得设施到需点的最大距离最小化。一些学者 ( h a n d i e r 1 9 7 9 ：d o m s e h k e 和d r e x l ，1 9 9 6 ) 对该问题进行了研究，认为p - c e n t e r 问题可转化为一 系列覆盖问题。 有竞争的设施选址模型最早由h o t e l l i n g 于1 9 2 9 提出，有关学者( e i s e l t ，1 9 9 3 ：d o b s o n 和 k a r m a r k a r ，1 9 8 7 ：b a u e r 等，1 9 9 3 ) 对该问题进行了分析和分类。该问题可描述为：两家公；习a 和 b 为顾客提供有竞争的产品，公司a ( b ) 想建，( p ) 个设施为顾客提供服务。起初。市场上没有 生产该产品的公司介入，公司a 建造了r 个设施，然后b 公司介入，建造p 个设施，在这种情况下。 5 东南大学博学位论文 市场需求量就需要在公司a 和公司b 之间重新分配。关于该问题的研究目前已有不少这方面的文章 ( h a k i m i ，1 9 8 3 ；r e v e l l e ，1 9 8 6 ：b e n a t i 和l a p o r t e ，1 9 9 4 ) 。 3 混合整数规划模型 给定一个被选设施地址的集合许多选址问题都可归为混合格数规划模型。这类离散的设施选 址模型可粗略分为以下几类：( a ) 单阶段模型和多阶段模型：( b ) 无容量约束模型和有容量约束模 型；( c ) 多源模璎和单源模型；( d ) 单一产品模犁和多品种产晶模型；( e ) 静态模型和动态模型：( f ) 不考虑路径选址模型和路径选址模型。下面主要介绍几种与配送中心选址密切相关的模型。 ( 1 ) 无容量约束的选址模型 4 2 4 7 1 该类模型中最简单就是u f l p 模型( u n e a p a e i t a t e df a c i l i t yl o c a t i o np r o b l e m ) ，这类模型的设施 没有容量限制。e f r o y m s o n 和r a y 利用拉格朗日松弛方法对该模型进行了求解；e r l e n k o t t e r 和k o r k e l 提出了分支定界算法；g o l d e n g o r i n 提出了改进分支定界算法。 与u f l p 模型相近的模型还有a p l p 模型( a g g r e g a t ec a p a c i t yp l a n tl o c a t i o np r o b l e m ) 和m c l p 模型( m a x i m u m c o v e r i n g l o c t i o n p r o b l e m ) 。对于a p l p 模型，r y u 和o u i g n a r d ( 1 9 9 2 b ) 、t h i z y ( 1 9 9 4 ) 以及k l o s e ( 1 9 9 8 ) 给出了该模型的精确算法。对于m c l p 模型，b a l a s 和p a d b e r g ( 1 9 7 6 ) 、s c h i l l i n g 等( 1 9 9 3 ) 、d a s k i n ( 1 9 9 5 ) 和g a l v a o ( 1 9 9 6 ) 进行了研究并给出了相应的算法。 ( 2 ) 有容量约束的选计模型p “” 当设施的容量有限制，而且需求点的地址和需求母以及设置设施的数目均以确定的情况下，可 采用c f l p 法( c a p a c i t a t e df a c i l i t yl o c a t i o np r o b l e m ) ，从设施的备选地点中选出多个设施使得总费 用最小。 对于此类模型，很难用精确算法进行求解。该模型通常用拉格朗1 5 1 松弛算法进行求解( g e o f f r i o n 和m c b r i d e ，1 9 7 8 ：n a t l s s ，1 9 7 8 ：c h r i s t o f i d e s 和b e a s l e y ，1 9 8 3 ；g u i g n a r d 和k i m 1 9 8 3 ；b a r e e l o 和c a s a n o v a $ ，1 9 8 4 ；k l i n c e w i e z 和l u s s ，1 9 8 6 ：b e a s l e y ，1 9 8 8 ，1 9 9 3 ：s h e t t y 1 9 9 0 ：b a r e e l o 等 1 9 9 0 ：c o m u e j o l s 等1 9 9 1 ；r y u 和o u i g n a r d ，1 9 9 2 a ：s r i d h a r a n ，1 9 9 3 ，1 9 9 5 ：h o l m b e r g 等1 9 9 9 ： d i a z 和f e r n a n d e z ，2 0 0 1 ) ，另外，v a n r o y ( 1 9 9 8 ) 和w e n t g e s ( 1 9 9 4 ，1 9 9 6 ) 提出了分解算法；s h m o y $ ( 1 9 9 7 ) 、g u h a 和k h u l l e r ( 1 9 9 8 ) 、k o r u p o l u 等( 1 9 9 8 ) 、c h u d a k 和w i l l i a m s o n ( 1 9 9 9 ) 以及c h u d a k 和s h m o y s ( 1 9 9 9 ) 提出了近似算法。 ( 3 ) 考虑路径问题的选址模璎1 4 7 0 】 考虑路径的选t 1 1 ：n 题包含3 个部分：设施选址、需求分配和乍辆路行问题。目前已有许多不同 的路径与选址的综合模型，但是由于该模型是由两个n p 难题结合而成。使得该模氆很难求解。m i n ， j a y a r a m a n 和s f i v a s t a v a ( 1 9 9 8 ) 按照问题的特点和求解方法对该问题进行了分类。其中一种分类方法就 是按照设施的层数进行分类。典型的3 层问题是产品从工厂到配送中心再到用户，而两层问题是从 配送中心到用户p e d ( 1 9 8 3 ) 以及p e r l 和d a s k i n ( 1 9 8 5 ) 对3 层路径和选址综合问题进行了研究，提 出了求解该模型的3 阶段启发式算法。第一阶段找到最小费川路径，第一二阶段决定选择哪个备选地 址和第一阶段得到的路径如何在选中的地址中安排。第二阶段通过在不同的设施中调整用户的需求 量和反复计算路径问题来提高解的质颦。与3 层问题类似，l a p o n e 等在用辂数线性规划求解车辆路 径问题的基础上，对2 层选自p 和路径结合问题进行了研究。 ( 4 ) 考虑库存的选址模喇1 7 1 - 7 4 1 6 绪论 c f l p 模型忽视了设施选址中库存的影响，它只是处理了设施建造费用和运输费用之问的矛盾。 建造费用随着设施数目的增加而增加，运输费用随着设施处理能力的增大而减少，但是库存费用却 随着设施处理能力的增大而增加。针对这一现象。b a u m o l 和w o l f e ( 1 9 5 8 ) 提出了提出了考虑库存 的选址问题。随后，e p p e n ( 1 9 7 9 ) 、s h e n ( 2 0 0 0 ) 、s h e n ，c o u l l a r d 和d a s k i n ( 2 0 0 3 ) 对此问题做了进 一步的研究。 0 4 2 配送中心选址几种常用模型比较 在物流系统分析与设计时，物流中心的选址常需得到模型化、数量化方法的支持，经常用到运 筹学的模型及方法，如动态规划、整数规划、网络技术等。 ( 1 ) 重心法模型 重心法( c e n t r o i dm e t h o d ) 是解决单设施选址的一个常用模型。所谓重心法是将物流系统的需 求点看成是分布在某一平面范围内的物体系统。备点的需求量和资源分别看成是物体的重鼍，物体 系统的重心将作为物流网点的最佳设置点。利用确定物体重心的方法来确定物流网点的位置。 重心法是解决只设置一个配送中心的简单模型，这是一连续刑模型相对丁二离散醚模型来说， 对流通中心的选择不加特定限制。有自由选择的长处。可是，从另一方面看，重心法模型的自由度 多也是一个缺点。因为迭代计算求得的最佳地点实际上是很难找到的。有时是不能实现的。有的地 点可能在江河中间、街道中间或处于人口稀少、环境恶劣的地区。流通中心和发送地点的数目很多 数学模型的建立十分困难，求解的计算也很复杂。在这种情况卜，可以用逐次逼近法来求解。 ( 2 ) b a u m o i - w o l f e 模型 b a u m o l 和w o l f e 构造了一个整数规划模型：在满足供戍及需求约束下，追求由运输费、输送费 及可变费用组成的总费用最低。以此选定物流中心，此模型的优点是：( a )