（载运工具运用工程专业论文）mdlrppd模型构建及其启发式组合优化算法研究.pdf

摘要 对物流系统进行优化设计，从而为相关企业提供物流优化解决方案，对物流研 究者来说始终是一个重要研究领域。本文研究的多站点集货配送一体化的定位一路 线问题( m u l t i d 印o tl o c a t i o nr o u t i n gp r o b l e mw i t l lp i c k 呻sa i l dd e l i v e r i e s ， u 冲p d ) 是物流系统优化中的一个重要研究方向，是任何一个大型物流配送企 业都必然要面临、期待解决的问题。文中分析了物流系统中选址、集货配送一体化 运输的互相制约关系，从物流系统总体成本最小的角度，分析了m d l i 蹬p d 的数学 模型，并探索其组合优化启发式解法。 本文在u 心( l o c a t i o nr o u t i n gp r o b l e m ) 数学模型的基础上建立了多站点集货 配送一体化的定位一路线问题( m d u 冲p d ) 的数学模型，在小规模数据情形下用 l i n g o 软件对所建立数学模型的正确性进行了验证。因其n p - h a r d 属性，本文设计 了禁忌模拟退火组合优化算法对m d u 心p d 数学模型进行求解，首先在满足设施 集货配送容量约束( 即设施服务的客户点的总需求和总供应量都不能超过设施的容 量限制) 的前提下随机产生多站点定位一配给问题( m u h i d 印o t l 0 c a t i o na l l o c a t i o n p r o b l 锄，m d l 心) 的初始解，采用禁忌搜索算法对m d l 心进行优化，将结果作 为集货配送一体化车辆路线问题( v e l l i c l ei b u t i n gp r o b l e mw i t hp i c k u p s 瓶d d e l i v e r i e s ，v l 姆p d ) 的输入，在姆p d 求解过程中，首先以客户需求量为基数， 对选中设施服务的客户进行排序，根据集货配货容量限制依次对客户进行判断，如 果客户进入路线以后，在服务车辆卸下其需求物品后，能顺利的将其供应物资装上， 那么将该客户纳入本条路线，如此循环直至所有客户都被纳入到相应线路中，从而 产生冲p d 初始解；然后采用模拟退火算法通过插入法、路线间交换、路线内部 交换、2 o p t 法对v 】p d 进行优化，之后再将冲p d 结果返回到m d l a p 阶段通 过插入法、站点间客户交换法、站点交换法产生m d u 心优化解的邻域解作为 强p d 的输入，按照特定的终止原则在m d l a p 和妞p d 阶段反复循环迭代，保 存迭代的最优解，作为m d l r p p d 的优化解。借助c + + 程序语言对该组合优化算法 进行编程。然后，对同组小规模数据分别采用l i n g o 软件和本文设计的组合优化算 法c + + 程序进行实例计算，二者计算结果的费用、设施选取与路线安排方案均一致； 最后，利用该组合优化算法程序对中等规模和较大规模测试数据进行了仿真计算。 结果表明使用本文设计的禁忌一模拟退火组合优化算法求解m d u 渖p d 快速有效， 在可接受的时间范围内求解较大规模的m d u 冲p d 是可行有效的。通过对不同规模 实例的反复仿真测试发现：随着问题规模的扩大，算法中所涉及的迭代次数、初始 温度、降温系数、禁忌长度、邻域解数量等参数逐渐变大，计算机处理时间急剧增 加，但算法的稳定性和收敛性不变。并且问题规模与算法计算时间呈指数变化关系， 问题规模变化对算法计算时间的影响比参数变化带来的影响要大得多。 关键词：物流工程，定位路线问题，集货配送一体化，模拟退火，禁忌搜索 a b s t r a c t t h eo p t i m i z a t i o n锄dd e s i g no ft h e l o 百s t i c ss y s t e mp r i v i d i n g f o rr e l a t e d c o m p a n y sl o g i s t i c s0 p t i m i z a t i o ns o l v i i l gs c h e m ea n dc o n s u l t i n gi sa l w a y sam a i l l r e s e a r c hf i e l df o ft h el o 百s t i c sr e s e a r c h e r m d l r p p d ( m u l t i d e p o tl o c a t i o nr 0 u t i i 唱 p r o b l e mw i t hp i c k u p sa n dd e h v e r i e s ) t ob es t u d i e di l lt h i sp a p c ri so n eb r a n c ho fm e 1 0 百s t i c ss y s t 锄o p t i i i l i z a t i o n ，a n da l s 0am a i nr e s e a r c hd i r e c t i o no f1 0 西s t i c ss y s t e m o p t i m i z a t i o n 趿dap r o b l e mt h a tab i g1 0 百s t i c sd i s t r i b u t i o nc o m p 肌ym u s tb ef a c e dw i n l 觚dw 眦st os 0 1 v e h ln l i sp a p e r t h ec o m p l e m e n t a r yr e s 慨n t r e l a t i o n 幽pb e 铆e e nd 印0 t s e l e c t i o i l 舰n s p o r t s ，p i c h l p s 锄dd e l i v 丽e si sa i l a l y z e d ，a n d 丘0 mm ep o i n to f t h el o w e s t t o t a l c o s t ，i t e s t a ：b l i s h e st h em a t h e m a t i c a l 瑚1 0 d e l 砒l dd e v e l o pt l l ec o m b i n a t o d a l o p t i m i z a t i o na l g o r i t h mo fm d l i 冲p d sp a p e re 鼬l i s h c sm em 拙c l i l a t i c a lm o d c lo fm d l r p p db a s e d0 nt h em o d e lo f u 心趾dt h ev e r i 丘c a t i o no fc o 玎e c n l e s so fm a t l l e m a t i c a lm o d e le s t a b l i s h e dt l 啪u 曲t h e 印p l i c a t i o no fl g os o 胁a r cl l i l d e rt h ec o n d i t i o no fs m a l l s c a l ed a t ai sc o n d u c t e d b e c a u s eo fi t sn p h a r dp r o p e r t y ，m ep a p e rp u t sf o 刑a r d st h et a b o o s i m u l a t e d 锄e a l i n g c o m b i n a t o a lo p t i m i z a t i o na 1 9 0 础 1 i i lt os o l v em d l r p p d a tf i r s t ，t h j sp 印e rg e t s 埘t i a l 瓶s w c ro fm d u 心r 锄d o m l y1 1 i l d e rt l l ec o n d i t i o no fc a p a c i t yr e s t r i c t i o n 7 r h e ni tu s e st h e t a b o os e a r c ha l g o r i t l 埘t oo p t i m i z em d i a pt h e ng e t st l l er c s u l t s 嬲v r p p d si n p u t h l t l l ep r o c e s so fs o l v i n gv r p p d ，t h ep a p e ra r r a g e sn l es e l e c t e dc l i e n t si i lo r d e rb 勰e do n 戗l ed e m a n d so ft h ec l i e n t s w 1 l e nm e e t i n gw i t hac l i e n t ，i fs e r y i c e 饥l c kc a i le q u i pt h e c l i e n t s9 0 0 d sa r e r 眦l o a d i n gt h ec a 】r 9 0 ，t l l ec l i 钮t9 0 e si n t ot h er o u t e 1 1 1 e ni tc 沁1 e sl i k e n l i s 衄t i la 1 1t h ec l i e n t s9 0 e si 1 1 t 0 1 er o u t e 1 1 1 er e s u l t sa r ev r p p d si 1 1 i t i a la 1 1 s w 既t h e n i tu s e st h es i m u l a t e da l l l l e a l i n ga l g o r i t h mt 0o p t i m i z ev r p p dw i t hi i l s e r tm e t h o d s ，r o u t e s i m e r c h a n g e ，r o u t en e r c h 孤g e 趾d2 一o p tt h e i lg e t st h er e s u n s i tm a ：k e st h er e s u n s r e n 脚：l i n gt ot h em d l a pp r o d u c i n gt h en e a ra i l s w e r so fo p t i m i z a t i o no ft h em d l a p 弱 t 1 1 ei n p u to f r p p da d o p t i n gi n s e r tm e t l l o d s ，c l i 锄l t s 证t e r c h a n gb e 觚e e i l 也ep 1 i d t sa n d p l o t 缸e r c h a i l g nc 妣l e sb e 帆e e i lm d l a p a n dv i 灌p du i l d e rc e n a i nt 锄su n t i lg e t st 1 1 e r e s u l ta st h eo p t i m i z a t i o ns 0 1 v eo fm d l r p p d t m sp 印e ra p p l i e sc + + l a l l g u a g e p r o 掣韧知m i n gt 0r e a l i z et h i sc o m b i n a t o r i a lo p t i m i z a t i o na l g o r i t h m t bt h es 觚l es m a l l s c a l e sd a t h i sp 印e ra p p l i e st h em e m i o n e dc o m b i n a t o r i a lo p t i m i z 撕o na l g o d t h l i la l l d l i n 9 0t 0i tr e s p e c t i v e l ya 1 1 dt h ec o s t ，f a c i l i t i e sa 1 1 dr o u t i n g sa r ee x a c t l ym es 锄e e i 嬲e d o nt h i s ，m ep a p e r 印p l i e s l em e t h o dt o “d m ea n dl a r g es c a l ed a t a t h er e s u l t ss h o w s t h a ti ti se 虢c t i v ea n de 伍c i e n tt 0u s et h et a b o o s i m u l a t e d 锄e a l i n gc o m b i n 舢嘶a 1 o p t i m i z a t i o na l g o r i t h mt 0s o l v em d l i 强p dw i t h i i l 锄a c c 印t a b l et i m e w h e l l 印p l 灿g t h em e t h o d st od i 琢珊e n ts c a l ec 弱e s ，i td i s c o v e r st l l a ta l t e m a t i o nt i l i l e ，b e 西疵n g t e m p e r a t u r e d r o p i n gt e m p e r a t l l r ec o e 伍c i e m ，t a _ b o o1 e n 垂h 勰dn e i 曲b o u rs o l v i n gi s b i g g e rw h e nt h es c a l eo ft h ep r o b l e mi sl a r g e r ，a n dt h ec o m p e t i n gt i i l l eo fc o m p u t e r s h a 印l yi n c r e 嬲e s ，b u tt h ea l g o r i t l l l i l ss t a b i l i t ya n d 弱t r i n g e n c yr e s t r a i l l i n gi s 蚰c h a i l g e k | e y w o r d s ： l o g i s t i c se n 舀n e 咖g ， 1 0 c a t i o n r o u t i n gp r o b l 锄，p i c k u p sa m d d e l i v 舐e s ， s i m u l a t e d 锄e a l i n g ， t a b o os e a r c h 论文独创性声明 本人声明：本人所呈交的学位论文是在导师的指导下，独立进行研 究工作所取得的成果。除论文中已经注明引用的内容外，对论文的研究 做出重要贡献的个人和集体，均已在文中以明确方式标明。本论文中不 包含任何未加明确注明的其他个人或集体已经公开发表的成果。 本声明的法律责任由本人承担。 论文作者签名：“救咩炳 聊罗年y 月伊日 论文知识产权权属声明 本人在导师指导下所完成的论文及相关的职务作品，知识产权归属学 校。学校享有以任何方式发表、复制、公开阅览、借阅以及申请专利等 权利。本人离校后发表或使用学位论文或与该论文直接相关的学术论文 或成果时，署名单位仍然为长安大学。 ( 保密的论文在解密后应遵守此规定) 论文作者签名：砖游勰 导师签名：磊一t 韦 日 e】t 何彳， 月 f 。 l 1 钲产 9 7 彤 川 加 长安大学硕士学位论文 1 1 问题的提出 第一章绪论 随着新技术的迅速发展，特别是电子商务的风起云涌，为我国经济的快速发展提供 了契机；随着社会的不断进步，人民的生活需求也朝向多样化、个性化方向发展，加上 贸易全球化的发展趋势，作为“第三利润源泉 的物流行业的重要性逐渐彰显，对经济 发展的影响也日益突出，己成为生产、流通行业最重要的竞争领域之一【l 捌。许多发达国 家已经形成了比较成熟的物流管理理念，掌握了先进的物流技术和高效的物流运营系统。 然而，随着生产消费的发展变化，物流服务客户的需求已经不仅仅只是以前的单一供应 或需求，已经演变为每个客户既有需求又有供应的模式。应用现有的运输模式，对同一 客户就会因为其既有需求又有供应出现重复服务，而造成重复运输、二次运输等不合理 物流现象，这就对现有的物流运作模式提出了挑战。本文研究的m d u 啦p d ( m u l t i d 印o t l o c a t i o nr 0 u t i n gp r o b l e mw i t hp i c k u p s 觚dd e l i v 嘶e s ) 就是针对这一现状，通过对物流系 统的设施定位、集配货一体化运输路线问题的优化，来解决上述不合理物流问题。 在物流这个大系统中包含了运输、储存、包装、装卸搬运、流通加工和信息六个主 要功能要素，而其中运输起着尤为重要的作用。在物流过程中，运输是实现物质实体由 供应方向需求方的转移，是创造空间价值的过程。我国自1 9 9 1 年以来物流相关因素费用 与物流总费用占g d p 比例如表1 1 所示。 表1 1 中国社会物流总费用组成及其与g d p 比例( ) 【3 】，【4 1 年度运输费用保管费用管理费用物流总费用 1 9 9 11 3 37 53 22 4 1 9 9 21 2 77 23 12 3 1 9 9 31 2 86 632 2 ，4 1 9 9 41 1 66 83 12 1 4 1 9 9 51 0 67 33 22 1 2 1 9 9 61 0 77 23 22 1 1 1 9 9 7 l o 47 43 32 1 1 1 9 9 81 0 3 6 73 22 0 2 1 9 9 9l o 663 31 9 9 2 0 0 0 1 0 163 21 9 4 2 0 0 19 95 93 11 8 8 2 0 0 2 1 06 12 91 8 9 第一章绪论 2 0 0 31 0 45 92 61 8 9 2 0 0 41 0 65 62 61 8 8 2 0 0 51 0 25 82 5 1 8 6 2 0 0 61 0 05 92 41 8 3 2 0 0 71 0 06 1 2 31 8 4 2 0 0 89 56 3 2 31 8 1 根据表1 1 的内容可以发现，我国物流总费用占g d p 比重高达2 0 左右，而发达 国家比例一般不到1 0 ；据测算，由于物流费用削减具有乘法效应，所以物流费用降低 1 2 个百分点，将产生社会效益l o o o 一2 0 0 0 亿元f 5 】。因此，控制物流费用，降低运输成本 对我国的经济建设有着十分重要的意义。通过表1 1 可以发现运输费用大约占社会物流 总费用的5 5 ，可见，运输费用是影响物流总费用的重要因素；另外，还发现保管费用 大约占物流总费用的3 3 ，对物流总费用的影响也很显著，而保管费用又体现为物流设 施的成本。综上表明，物流总费用主要与设施成本和运输费用直接相关，密不可分。相 比发达国家而言，我国物流总费用还有很大的压缩空间，而这部分压缩主要来源于设施 成本和运输费用的缩减，针对我国物流发展现状：存在很多不合理运输，比如重复运输、 迂回运输、过多运输等等。 例如，我国以提供运输、储存为主的第三方物流企业，由于其客户的地域分布特性， 在全国各地拥有成百上千的货物集散点。其运作模式如下：根据货量以及货物流向确定 相对稳定的运输路线，首先将到达货物送到各个集散点；然后，再将各个集散点新收的 货物装运回分拣中心；这样就不可避免的产生了很多重复、迂回运输造成运力浪费；如 果能够提倡集货配送一体化的运作模式，利用先进的信息平台对车辆进行优化调度，肯 定能够更进一步地节约成本，提高客户服务水平。同样，对于制造业来说，既需要把原 材料从供应商处运到仓库，同时又要把生产出来的产品配送到客户处；例如啤酒厂商 矿泉水厂商既需要把啤酒矿泉水运送到客户或销售商处，同时有需要把客户用完的空酒 瓶水桶回收到工厂循环利用。在这些情况下，采用集货配送一体化的思想都能很大程度 的节约成本。因此，在现实物流系统中提倡集货配送一体化的思想有着很大的应用空间 和前景。 在传统的物流决策模型中，定位一配给问题( l 0 c a t i o n 舢l o c a t i o np r o b l e m ，l 心) 、 车辆路线问题( 垤h i c l er 0 u t i n gp r o b l e m ，强) 是最值得关注的两个方面【6 】。由于物流成本 具有效益背反的特性；因此，在整个物流系统中，一种功能成本的削减，可能引起其他 2 长安大学硕十学位论文 功能成本的增加，鉴于各种物流成本的相互关联性，必须考虑整体效益最佳。定位配给 问题考虑设施( 工厂、库存点、分销中心) 的选址与客户配给之间的相互关系，目的是 对设施的数量和位置进行决策使设施的运作成本及车辆的运输成本最低，其缺点是它一 般认为设施到客户的运输路线是放射线状的，车辆由设施点到达客户点后随即返回，因 此在确定设施的位置时，忽视了对车辆路线的考虑，这样可能使得运输车辆的装载能力 不能完全发挥，导致车辆利用率不高，运输成本增加。车辆路线问题是指在设施位置已 知的前提下，确定车辆从设施点到一个或多个客户之间的行程路线，使运输路线最短或 运输成本最低。在v 1 冲中，考虑了车辆在各个客户点间巡回访问的特性，使提高运输效 率成为可能，也与实际情形相吻合。但在婢中，未分析设施的选址问题，这将会使得 整个物流系统成本不易达到最低。 设施定位、车辆路线各自作为单独的问题，国内外已有较多学者进行了研究，这些 研究为物流管理的优化决策奠定了坚实的基础。但是企业物流贯穿于采购、供应、制造 加工、销售以及废弃物回收等各个环节，涉及到供应商、用户等多个执行个体及其生产 经营的方方面面，因此，如果能够实现面向整个物流过程的管理，那么不仅可以大大提 高企业的物流绩效水平，而且还能够有效地改善企业的生产经营管理水平并进一步提高 在市场中的竞争地位。另一方面，组成物流系统的各个环节之间存在着“效益背反现 象，要想较多地达到某个方面的目的，必然会使另一方面的目的受到一定的损失，也就 是一方成本降低，而另一方成本必然增大。例如减少库存站点数量、降低库存，势必使 库存补充变得频繁，必然增加运输次数，导致运输费用增加；建立较多的设施点，可以 减少运输成本，但是增加的设施建设费用却不容忽视。而企业管理者希望能够协调物流 系统中的各个环节，以最低的价格、最好的服务来满足顾客的需要。由此，在上述物流 决策模型的基础之上，产生了集成物流管理系统的概念【7 1 ，其目标就是要提高物流配送 效率。应用这种集成物流管理系统的概念，国外一批学者对设施定位一运输路线问题 ( l i 冲) 和集货配送一体化的车辆路线问题( v c 她c l er o u t i n gp r o b l e mw i t l lp i c k u p sa i l d d e l i v 耐e s ，v 1 冲p d ) 进行了综合研究，而目前对多站点集货配送一体化的定位路线问题 ( i ，r p p d ) 的研究还较少。m d l r p p d 是在考虑同时对客户集货和配送的前提下， 优化定位路线问题。相比单一的物流系统优化问题，u 冲p d 在其基础上又有了进一 步的完善，所以对它的研究是物流系统优化问题的必然趋势之一。 3 第一章绪论 按照集成化物流管理概念，对整个物流系统进行优化是企业降低物流成本的关键。 合理的选址和恰当的配送中心数量能够减少运输成本、库存成本，能够协调基建投资成 本与运输成本间的“效益背反 关系；合理的运输路线安排能缩短运输距离、降低运输 成本。因此，选址、运输是决定物流管理绩效水平的两个主要驱动因素，如果在物流系 统优化中同时考虑对选址和运输的决策，则两者的集成优化可进一步提高物流管理水平。 由于现实物流环境存在如下问题：客户网点繁多，地理位置分布无规则，同一地点既有 需求也有供给，运输线路复杂多变，规模效应不显著等；因此，综合研究多站点集货配 送一体化的定位路线组合优化问题，对进一步优化整个物流系统，降低系统成本具有一 定的的理论价值和现实意义，并且存在着很大的应用空间和发展前景。 1 2 问题概述 1 2 1 问题描述 ( 1 ) 定位一路线问题( l r p ) 在一般情况下，u 冲可以描述为：给定一系列客户点和一系列潜在的设施点，客户 点数量、位置和需求量都是已知或可以估算出的；潜在设施点位置己知，现从这些潜在 设施点中确定出一系列的设施数量和位置，即选取最佳的设施数量及位置，同时还要确 定出一套从各个选中设施点到各个客户点的运输线路。确定上述决策的依据是满足问题 的目标函数( 通常是总费用最小) 。目标函数总费用一般包括设施点建设成本、运作成本 以及车辆使用的固定成本、运输成本等。约束条件包括：货物由一个或多个设施点供应， 每个客户点只接受来自一个设施点的货物，每个客户点只由一辆车服务，每辆车的起止 点必须是同一个设施；设施点和运输车辆都有容量和数量的限制等。u 心示意图如图1 1 所示。 口 口 表示选中的设施，口表示未被选中的设施，o 表示客户点，一表示运输线路 图l - 1l r p 示意图 4 长安大学硕士学位论文 ( 2 ) 集货配送一体化的车辆路线问题( v e l l i c l er o u t j h gp r o b l e mw i t hp i c k u p sa n d d e l i v e r i e s ，v r p p d ) 集货配送一体化的车辆路线问题可以描述为：同一个站点处用多台车辆将客户需要 的货物从中心站点送到该站点服务的各个客户，并将各个客户供应的货物从客户处收集 回到中心站点。其中，每个客户的位置一定，客户处需要配送和收集的货物数量一定， 且事先已知或可以预算出来，每台配送车辆的载重量定，求车辆路线的合理安排，使 目标函数得到优化。v r p p d 示意图如图1 2 所示： 表示中心设施站点，o 表示仅有需求的客户点，表示仅有供应的客户点， 表示既有需求又有供应的客户点，一表示运输线路 图1 2 灌p d 示意图 ( 3 ) 多站点集货配送一体化的定位一路线问题( m u l t i d e p o tl o c a t i o ni b u t i n g p r o b l e m 埘t l lp i c k u p s 锄dd e l i v e r i e s ，m d l i 强p d ) 多站点集货配送一体化的定位一路线问题是研究从一定数目潜在设施点中确定出一 系列的设施数量和位置，并把各个客户配给相应的选中设施，即确定最佳的设施数量、 位置及客户分配，同时还要确定出一套从各个选中设施点到它服务的客户点的运输线路， 保证服务于该路线的车辆既能满足客户的需求又能接受客户点的供应，从而使定位和运 输费用的系统总费用最小。m d l l 冲p d 由两个子问题组成：多站点设施定位问题 ( m d l a p ) 和集货配送一体化车辆路线问题( v i 冲p d ) 。其目标是把这两个子问题综合 为一个系统问题来考虑，从而达到整个物流系统总成本最低。多站点集货配送一体化的 定位一路线问题示意图如图1 3 所示： 5 第一章绪论 口 口 表示选中的设施，口表示未被选中的设施，o 表示仅有需求的客户点， 表示仅有供应的客户点，表示既有需求又有供应的客户点，一表示运输线路 图1 3 瑚l 础p p d 示意图 1 2 2 问题分类 1 l i 心问题分类嘲 h o k e ym i n 等学者对l i 冲问题的研究中，详细描述了该问题所涉及到的各方面内容， 并结合l i 心问题的内容特征和算法对l r p 问题进行了详细的分类。 ( 1 ) 根据内容特征对l r p 问题分类 按内容对l r p 问题进行分类如表1 2 所示。 表1 2 根据内容特征l r p 问题分类表8 1 内容特征编号 l r p 问题的内容特征 ab 1 物品流向单向双向 2 供需特征确定 随机 3 设施数量单个设施多设施 4 运输车辆数量单个车辆多车辆 5 车辆装载能力不确定确定 6 设施容量 不确定 确定 7 设施分级单级 多级 8 计划期间单期多期 9 时间限制无时间限制时间限制 1 0 目标数单目标多目标 1 l 模型数据类型假设值实际值 h o k e y 对表1 2 中，各分类标准解释如下： 1 ) 商品流向，单向商品流向问题指的是所有设施进行输入( 供应) 或者只进行输出 6 长安大学硕十学位论文 ( 回收) 的操作；而双向商品流向问题涉及的设施中只有一部分既要输入又要输出。 2 ) 供需特征，确定型的是指商品的供应需求量是已知的并在一定时期内相对稳定： 随机型的是指供应需求量是不确定的。 3 ) 设施数量，指求解问题要求设施的数量，分为单一设施和多设施两种。 4 ) 运输车辆数量，是指有多少车辆为一个设施服务的标准，同时也确定了从一个设 施出发的路线数。分为单一车辆和多种车辆两种。 5 ) 车辆装载能力，是指是否要考虑车辆装载能力的限制。不确定型是指对这个问题 所涉及的每条路线的货物总量很小，不会超出车辆的装载量，所以不用考虑车辆的装载 能力；确定型是指每条路线上货物总量可能超出车辆的装载能力，所以要把车辆的装载 限制作为一个参数引入问题。 6 ) 设施容量，是指是否考虑各个设施的容量限制。分为确定型和不确定型。 7 ) 设施分级，可以把设施分为两种：总站型和中间转运站型。总站型设施是那些车 辆的出发点和终点；中间转运站型是指商品的中间站，货物运入后还要运出。有了中转 站，就产生了设施分级的问题，货物从总站型设施运入中间转运站型设施，经过简单处 理后运到客户点。单级设施问题是指不考虑设施的分级，所有设施均为同级；而多级中 心设施问题则考虑设施的分级。 8 ) 计划期间，单期间问题把整个期间作为一个时间段，是静态问题；多期间问题是 把整个时间段按问题要求分为多个期间，是动态问题。 9 ) 时间限制，主要是指满足客户要求或货物要求，而对u 冲是指从客户接收货物 的时间限制，分为无时间约束和有时间约束两种。 1 0 ) 目标数量，u 口的目标通常是总费用( 包括建设费用和车辆运输费用等) 最小， 但有时也需要考虑其他目标，比如满足顾客的特殊需要、总体利润最大化等。如果是多 目标问题，经常会出现各目标之间的冲突。 1 1 ) 模型数据类型，在有些情况下，模型中的数据( 如商品需求量等) 是来源于实 际的；而有些情况下，这些数据是在实际中没有的，需要对其进行假设。根据模型数据 类型的不同，把u 心分为假设型和实际型两类。 ( 2 ) 求解u 冲问题的算法分类 国外很多学者对u 冲的算法进行了大量的研究，主要分两类： 7 第一章绪论 1 ) l i 冲问题的精确算法 u 心的精确算法可以分为以下的四种： 直接树状搜索法分支界定法( d i r e c t 讹es e a r c h b r a i l c ha i l d b o u i l d ) ； 动态规划法( d ”锄i cp r o 伊a i r l i i l i n 曲； 整数规划法( n e g e rp r o g r a m m i n 曲； 倒 线形规划法( n o n l i n e a rp r 0 鲈姗1 1 l l i n 曲。 精确算法可以求得模型的精确解，但只能解决较小规模的问题，即客户数和设施数 都比较少的情况，并且用精确算法来求解问题所需时间较长。所以精确算法在实际情况 下很难得到应用，对于这方面的研究有不断减少的趋势。 2 ) u 冲问题的启发式算法 由于l 心和诤都已经被证实为n p h a r d ( n o n d e t 锄i i l i s t i cp 0 1 y n o m i a lh a r d ) 问题 【3 3 1 ，基于u 冲问题的复杂性，对于这类问题其核心在于数学模型的建立和算法求解，一 般情况下用精确算法难于解决。所以引入启发式算法，启发式算法的思想是将主问题分 解为多个子问题，然后依次应用启发式算法或精确算法进行求解。求解定位一路线问题 的启发式算法可分为以下四种： 先解决定位一配给问题，再解决运输路线问题； 先解决运输路线问题，再解决定位一配给问题； 费用降低插值算法； 路线扩展交换算法。 2 u p d 问题分类 对u 心p d 模型的分类情况可以参照表1 2 模型分类标准，另外，再结合集配货的组 合方式进行划分： ( 1 ) 集配货地点一致( 即所有的客户点既有需求又有供应) ； ( 2 ) 集配货地点严格分开( 即每个客户点只能接受需求、供应当中的任何一种服务) ； ( 3 ) 集配货地点混合分布( 即每一个客户至少需要满足需求和供应的一种服务) ； 由于u o p d 和u 冲同属于双重n p h 盯d 问题，所以关于对u o p d 算法分类与上 长安大学硕士学位论文 述u 冲算法分类一样都分两大类：精确解法( 处理小规模问题) 和启发式解法( 处理较 大规模问题) 。 对于集货配送一体化定位一路线问题由于国内外研究才刚刚起步，研究文献较少，目 前对该问题还没有明确的分类标准和分类方法。 1 3 国内外研究动态 1 3 1 国外研究现状 国外近年来对于u 心问题的研究已经取得了一些成果，目前主要集中在两个方面： 一是u 冲问题的求解算法研究；二是比较复杂的l r p 模型研究，使模型在规模和复杂 性方面更接近于实际问题，有利于运用模型来解决实际问题。 t u z u i l 等9 1 提出了两阶段禁忌搜索启发式算法求解l r p 问题，其算法结构能对解空间进 行有效搜索，但其模型未考虑设施容量约束。y | u p oc h 锄和、矾1 1 i 锄b c a n e r 等【l o 】人运用s f c ( s p a c ef i l l i n gc u r s e ) 法来求解多设施、多运输车辆的随机型l r p 模型。w u 等【l l 】采用两阶段 模拟退火启发式算法求解具有多种类型车辆且数量给定的u 问题。b o l l l l a 矗，l y 锄i l l e 【1 2 】 用模拟退火和蚁群组合算法求解了两阶段定位路线问题。l i n ，c k y 和k w o k ，r c w 【1 3 】对 模拟退火算法和禁忌搜索算法求解定位路线问题进行了比较。s c l i u ，s b l e e 【1 4 】建立了 考虑库存策略的多站点定位路线问题的数学模型，并用两阶段启发式解法进行了求解。 l i u ，s c 和“n ，c c 【1 5 谰禁忌搜索和模拟退火混合启发式算法求解了定位路线和库存组合 优化问题。 表1 3 以列表的形式总结了国外l r p 发展过程中所研究过的各种问题： 表1 3l r p 拓展问题研究历程 问题类型相关文献 随机l r p l a p o n ee ta 1 ( 1 9 8 9 ) 动态l r pl a p o r t e 肌dd e j a x ( 1 9 8 9 ) h a m i l t o n i a np 中值b 瑚m c oa i l dc o e l h o ( 1 9 9 0 ) 道路一车辆路线s e m e t ( 1 9 9 5 ) 车辆路线配给问题( v r a p ) n a s c i i n e m oa i l db e a s l e y ( 1 9 9 6 ) 多点对多点的l r p 问题 n a g ) ，卸ds a l l l i ( 1 9 9 8 ) e u l e r i a n 定位问题 g h i a i l ia i l dl a p o n e ( 1 9 9 9 ) 带混合车队的l r p 问题w u e ta j ( 2 0 0 2 ) 定位一路线一库存l i u 锄d l e e ( 2 0 0 3 ) 工厂循环定位问题p c l p l a b b ? e ta l ( 2 0 0 4 ) 9 第一章绪论 多点对多点的l r p 问题w a s n e ra n dz 螽p f e l ( 2 0 0 4 ) 多级定位路线仓储问题 a 口1 b r o s i n oa i l ds c u t e l l ? ( 2 0 0 5 ) 确定型l r p a l b a r e d a s a i 】出o l ae ta 1 ( 2 0 0 5 ) v r a p ( 中值环问题p )l a b b ? e ta 1 ( 2 0 0 5 ) 带非线性成本的l r p 问题 m e l e c h o v s 埘e ta 1 ( 2 0 0 5 ) 平面l r p ( 单设施点) s c h w a r d ta i l dd e 眦o f ! f ( 2 0 0 5 ) 多约束的v r a pg u n n a r s s o ne ta 1 ( 2 0 0 6 ) 平面l r p ( 多设施点)s a m ia l l d n a g ) r ( 2 0 0 7 ) 虽然u 冲的发展已经经历了一段时间的研究，但是由于u 冲涉及内容的多样性与 复杂性，仍然有很多问题没有解决。无论是在学术上还是在实际应用的研究上，对u 心 拓展分支问题的模型建立与启发式算法研究都具有很强的潜在价值等待挖掘。通过表1 3 可以看到，对l r p 的一部分分支已经有学者做了相关研究。 但是，对作为u 冲拓展问题u 心p d 的研究较少。目前，只有美国的b u r k s ，r o b 融e ，j r ， p h d 在文献【1 6 】中对l r p p d 做了一定的研究，文中主要对带时间窗和集配货一体化的定位 路线问题采用禁忌搜索算法进行了求解，但是从其采用的数据结构来看，每个客户点都仅 仅是独立的需求或供给点，属于集配货客户点严格分开型；这与现实情况存在较大的差距， 忽略了既是供给点又是需求点这类客户的存在。而本文的每个客户点可以既是需求点又是 供给点，也可以只是供、需点中任意一类客户点，较之文献【1 6 更加切合实际。本文对客 户点作如下两个方面的定义：一是物流服务的每一个客户个体；二是将配送区域划分为若 干个集配货小区，将每一个集配货小区作为一个客户点。显而易见，通过引入第二种客户 定义方式，理论与实践的结合更加容易实现，既减少了客户的数量，便于优化计算；又使 物流过程更加简洁、物流线路更加合理有序。从很大程度上节约了物流成本。 1 3 2 国内研究现状 国内关于u 冲问题的研究文献较少，只有少数几位学者对该类问题进行了研究。汪寿 阳、赵秋红是最早在国内开始l r p 问题研究的学者，文献【1 7 】详细介绍了国外对于集成物 流管理系统中u 冲问题的研究进展，分析了u 心的主要内容和特征，提出有关求解问题的 算法分类，并对以后该领域的研究方向提出了几点建议。张潜、高立群【1 8 】等从算法优化的 角度出发，对u 心问题中的定位配给、运输车辆路线安排、定位一运输路线安排三类问题 的具体优化方法进行了分析和比较，并在此基础之上提出两阶段启发式算法来求解l r p 问 题。张长星【1 9 】等用遗传算法求解了定位一运输路线问题。张潜、高立群【2 0 1 等提出了基于最 小包络聚类分析及带有控制开关的遗传算法的两阶段启发式算法来解决u 心问题。邱晗 1 0 长安大学硕士学位论文 光、张旭梅【2 1 】运用基于遗传算法、模拟退火算法的改进粒子群算法，对一个开放式定位 一运输路线问题进行了求解。但是由于这些文献都没有考虑客户集货配送一体化问题，跟 现实当中的实际问题还缺少一些衔接。 胡大伟【2 2 1 在文献 2 2 】中已经提出了在建立多阶段l r p 模型时，同时考虑集货、配送问 题是未来研究方向之一，但通过检索到目前国内还没有关于这方面的研究文献。 综上所述，目前在国内外文献中，对u 强拓展分支问题研究的文献还不多，尤其是考 虑设施容量、车辆容量约束和集货配送一体化的文献更少。国内关于对集货配送一体化的 定位一路线问题的研究几乎处于空白，国外仅有少量学者对此做了研究，但是其问题模型 也还存在着一定的局限性。 1 4 本文主要研究内容 本文在学习定位一路线问题数学模型、禁忌搜索启发式算法、模拟退火算法的基础上 探索多方物流运作在垂直方向的集成，即考虑集货配送一体化对设施的容量、数目和选址 的影响，以及集货配送一体化对运输路线安排的影响，研究多站点集货配送一体化的定位 一路线组合优化问题的数学模型，探索一种适合这类问题求解的组合启发式算法，最后用 数据进行试验计算，得出相关结论。本文共分四章，各章的主要内容如下： 第一章分析了定位一路线问题( l r p ) 和集货配送一体化的车辆路线问题分别作为一个 独立问题进行研究时存在的缺陷和不足，通过分析各因素之间的“效益悖反 关系，参照 组合优化问题的重要性。分析当前集成化物流管理系统概念和集货配送一体化策略下，研 究定位配给和集配货一体化车辆运输路线组合优化问题的必要性。此外，对定位一路线问 题和集货配送一体化的定位一路线问题进行总结分类，还介绍了国内外相关问题的研究现 状，尤其是国内学者的研究成果，并指出了其不足之处。 第二章论述集货配送一体化的定位路线组合优化问题的理论基础。介绍集货、配送的 基本概念；还将介绍多站点定位配给和集货配送一体化车辆路线两个基本问题；分析多站 点定位配给和集货配送一体化路线之间的相互影响关系；介绍组合优化问题技术及其求解 方法，阐明对于实际物流系统中的大规模问题，启发式算法是最合适的求解方法。 第三章分析并建立多站点集货配送一体化的定位路线问题的数学模型，并用l i n 9 0 1 0 0 对该数学模型进行验证；证明本文数学模型的正确性。 第四章针对多站点集货配送一体化