（计算机软件与理论专业论文）有时间窗物流配送路径优化问题的算法研究.pdf

， ， 嘴 一 ) 有时间窗物流配送路径优化问题的算法研究 摘要 随着经济全球化的发展，带动了物流业的全球化，而物流业的发展也影响着经济 的发展。因而，在经济发展中，物流业发展的也显得越来越重要。物流配送在物流运 输中占有很大比重，也就是说物流配送的成本很大程度决定着物流运输的成本，而物 流配送的成本取决于物流配送路径优化的好坏。如何提高物流配送的效率，就是当前 要解决的问题。因此，物流配送路径优化是物流系统中的关键一环，选择恰当合理的 配送路线，可以降低物流配送成本，提高物流配送的效率。本文主要做了如下两个方 面的工作： ( 1 ) 通过分析物流配送和市场资源优化配置，提出了一种并购算法。通过学习 与研究现有能够求解有时间窗物流配送路径优化问题的多种算法，比较它们之间的优 点和缺点。在此基础上，我们提出了一种新的算法，即并购算法。分别介绍并购算法 思想、要素和分类等，并建立并购算法的模型，以及对算法的性能做进一步的分析。 ( 2 ) 对并购算法模型及其性能进行试验验证和分析。此部分是本文研究的重点： 首先，建立有时间窗物流配送路径优化问题的数学模型基础。其次，利用并购算法构 造有时间窗物流配送路径优化问题的并购算法模型和有时间窗物流配送路径优化问 题的混合并购算法模型。最后，利用这两种算法模型分别在s o l o m o n 数据集上进行多 次模拟实验，获取有时间窗物流配送路径优化问题的最优解或近似最优解，并对实验 的结果进行分析、比较和总结。 关键词：时间窗；物流配送；并购算法 、l ，g 土l五，ili毋 r e s e a r c ho na l g o r i t h mo fo p t i m i z i n go fp h y s i c a l d is t r i b u t i o nr o u t i n gp r o b l e mw i t ht i m e w i n d o w s a b s t r a c t w i t ht h ed e v e l o p m e n to fe c o n o m i cg l o b a l i z a t i o n ，i tb r i n g sa b o u tt h eg l o b a l i z a t i o no f t h el o g i s t i c si n d u s t r y , a n dt h ed 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 ya l s oa f f e c t se c o n o m i c d e v e l o p m e n t t h u s ，t h el o g i s t i c si n d u s t r yp l a y sa ni n c r e a s i n g l yi m p o r t a n tr o l ei ne c o n o m i c d e v e l o p m e n t p h y s i c a ld i s t r i b u t i o nh a v eal a r g ep r o p o r t i o ni nt h el o g i s t i c st r a n s p o r t a t i o n ， w h i c hm e a n st h a tt h ec o s to fp h y s i c a ld i s t r i b u t i o nd e t e r m i n e st h e c o s to fl o g i s t i c s t r a n s p o r t a t i o ni nal a r g ee x t e n t ，s ot h ec o s to fp h ) i r s i c a ld i s t r i b u t i o nd e p e n d so no p t i m i z i n g o fp h y s i c a ld i s t r i b u t i o nr o u t i n g h o wt oi m p r o v et h ee f f i c i e n c yo fp h y s i c a ld i s t r i b u t i o ni s t h ec u r r e n tp r o b l e mt ob es o l v e d t h u s ，o p t i m i z i n go fp h y s i c a ld i s t r i b u t i o nr o u t i n gi sa k e y l i n ki nl o g i s t i c ss y s t e m t h ea p p r o p r i a t ed i s t r i b u t i o nr o u t i n gs e l e c t e dc a nr e d u c et h ec o s to f p h y s i c a ld i s t r i b u t i o na n di m p r o v et h ee f f i c i e n c yo fp h y s i c a ld i s t r i b u t i o n d ot h ef o l l o w i n gt w oa r e a s ： ( 1 ) am e r g e r s & a c q u i s i t i o n sa l g o r i t h mw a sp r o p o s e da c c o r d i n gt oa n a l y z i n g p h y s i c a ld i s t r i b u t i o na n dr e i n t e g r a t i o nt om a r k e tr e s o u r c e b ys t u d y i n ga n dr e s e a r c h i n g c u r r e n tm u l t i p l ea l g o r i t h m so fo p t i m i z i n go fp h y s i c a ld i s t r i b u t i o nr o u t i n gp r o b l e m 、析t h t i m ew i n d o w s w ec o m p a r et h e i ra d v a n t a g e sa n dd i s a d v a n t a g e sw i t he a c ho t h e r o nt h a t b a s i s ，w ep r o p o s ean e wa l g o r i t h m ，m e r g e r s & a c q u i s i t i o n s ( m & a ) a l g o r i t h m w ew i l l i n t r o d u c em & a i d e a s ，e l e m e n t sa n dc l a s s i f i c a t i o n se t c ，e s t a b l i s ht h em o d e lo fm & a a l g o r i t h m ，a n da n a l y z ef u r t h e rt h ep e r f o r m a n c eo fm & a a l g o r i t h m ( 2 ) m & am o d e la n di t sp e r f o r m a n c ew e r ev e r i f i e da n da n a l y z e db ye x p e r i m e n t s r e s e a r c ho nt h ep a p e rw i l li m p o r t a n t l yf o c u so n ：f i r s t l y , w ew i l lc o n s t r u c tt h em a t h e m a t i c m o d e lo fo p t i m i z i n go f p h ，r s i c a ld i s t r i b u t i o nr o u t i n gp r o b l e mw i t ht i m ew i n d o w s s e c o n d l y , w ec o n s t r u c tt h em o d e lo fo p t i m i z i n go fp h y s i c a ld i s t r i b u t i o nr o u t i n gp r o b l e mw i t l lt i m e i i ) 、， a b s t r a c t w i n d o w sb a s e do nm & a a l g o r i t h ma n dt h em o d e lo fo p t i m i z i n go fp h v r s i c a ld i s t r i b u t i o n r o u t i n gp r o b l e mw i t ht i m ew i n d o w sb a s e do nh y b r i dm & a a l g o r i t h m f i n a l l y , w em a k e r e s p e c t i v e l ys o m ee x p e r i m e n t so nt h es o l o m o nd a t ab a s e do nt h eb o t hm o d e l so ft h e a l g o r i t h m s ，o b t a i nt h eo p t i m a lo rn e a r l yo p t i m a ls o l u t i o n so fo p t i m i z i n go fp h y s i c a l d i s t r i b u t i o nr o u t i n gp r o b l e mw i t ht i m ew i n d o w s ，a n dh a v et h eo p t i m a ls o l u t i o na n a l y z e d ， c o m p a r e da n ds u m m a r i z e d k e yw o r d s ：t i m e w i n d o w s ；p h y s i c a ld i s t r i b u t i o n ；m e r g e r s & a c q u i s i t i o n s a l g o r i t h m i i i 矗；h 0 l - l 一，譬 ，i，ii一 i 歹 “ ) 目录 摘要i a b s t r a c t i i 目勇专 1 、引言。1 1 1 研究背景和意义1 1 2 问题的提出2 1 3 国内外研究现状3 1 4 本文研究的主要内容及组织结构。5 2 、并购算法简介7 2 1 并购算法( m e r g e r s & a c q u i s i t i o n sa l g o r i t h m ) 的基本思想7 2 2 并购算法7 2 3 并购算法的基本要素8 2 4 混合并购算法1 0 2 5 混合并购算法的基本要素1 1 2 6 两种并购算法的联系与区别1 3 2 7 并购算法的性能分析1 4 3 、并购算法在有时间窗物流配送路径优化问题中的应用2 l 3 1 有时间窗物流配送路径优化问题的描述2 1 3 2 有时间窗物流配送路径优化问题的数学模型2 2 3 3 并购算法在有时间窗物流配送路径优化问题中的应用2 4 3 4 混合并购算法在有时间窗物流配送路径优化问题中的应用2 9 4 、实验及结果分析3 3 4 1s o l o m o n 标准库简介3 3 4 2 并购算法实验3 4 4 3 混合并购算法实验3 7 4 4 并购算法的实验结果分析与比较4 6 5 、论文总结与研究展望4 8 5 1 论文总结4 8 5 2 研究展望4 9 参考文献5 1 攻读学位期间取得的研究成果5 6 i v 目录 致谢5 7 浙江师范大学学位论文独创性声明5 8 学位论文使用授权声明5 8 浙江师范大学学位论文诚信承诺书5 9 v 尹 i l ， 嶂 一 l ， ： 譬 1 、引言 随着市场经济的发展与繁荣，物流配送在货物运输成本中占比重也越来越高。因 而，如何降低物流运输成本，提高物流运输效率等问题，日益凸显重要，成为影响物 流业发展中的重要一环。特别是，商业竞争的残酷性，使得客户对时间的要求更为苛 刻。因此，如何解决有时间窗物流配送路径优化问题，也相应地凸显迫切。 1 1 研究背景和意义 物流是指利用现代信息技术和设备，将物品从供应地向接收地准确的、及时的、 安全的、保质保量的、门到门的合理化服务模式和先进的服务流程。在我国国家标准 物流术语的定义中指出：物品从供应地到接收地的实体流动过程，根据实际需要， 将运输、储存、装卸、搬运、包装、流通加工、配送、信息处理等基本功能实施有机 厶士厶 多日口o 在第三届中国企业采购国际论坛上，中国物流与采购联合会副会长丁俊发表示， 当前我国物流产业发展现状主要呈现四大特点，其中之一就是社会物流需求快速上 升，幅度明显高于同期g d p 增幅。1 9 9 1 2 0 0 2 年，我国社会物流货物总额从3 万亿元 上升为2 3 3 万亿元，增长了6 7 倍，年均增长2 0 4 ，大大高于同期g d p l 5 4 的年 均增速，2 0 0 3 年为2 9 6 万亿元。在社会物流货物总额中，工业品物流总值比重最大， 幅度最高，2 0 0 3 年占社会物流货物总额的8 4 6 。这组数字说明，物流发展与一个国 家的经济总量成正比，与一个国家的经济发展水平成正比，也说明经济发展对物流依 赖程度越来越高。但与欧美和日本发达国家相比，我国物流成本占g d p 的比重过高， 欧洲、同本一般在1 0 左右，而美国一般都低于1 0 。社会物流总成本由运输成本、 保管成本与管理成本构成，其占g d p 的比重是衡量一个国家经济发展水平，特别是 1 、引言 综合国力的一个重要指标。从上面的数据可以反映出我国物流运作水平是极为粗放 的，社会化、专业化水平低，经济增长付出的物流成本太高。 物流配送是物流中的一种特殊的、综合的活动形式，是商流与物流紧密结合。而 配送中心在物流配送担任重要角色，具有集货中心、分货中心的职能。由于物流配送 在区域或全球范围内要完成物流配送的工作条件复杂，可能会遇到货运网点多、货物 品种繁多、运输道路网复杂、客户配送点分布不均匀、时间窗宽窄不均匀等问题。因 此，如何降低物流配送的成本，就是一个比较实际的问题。要降低物流配送成本，就 要选择一个合理、经济实惠的配送路线方案，具体要做到减少参与配送货物的车辆数、 降低配送的总里程、最大程度地满足客户要求的配送时间等要求，只有这样才能降低 物流配送成本，提高物流配送效率。 所以，研究物流配送路径优化问题能够解决现实问题，特别是有时间窗物流配送 路径优化问题，更贴近实际问题，能够带来更直接的经济价值与效益，具有研究的价 值和实际意义。 1 2 问题的提出 物流配送路径优化问题，即是车辆路径问题( v e h i c l er o u t i n gp r o b l e m ，v i 冲) ， 是d a n t z i g 和r a m s e r t l l 于1 9 5 9 年提出的。具体来说，就是根据物流配送的已知条件 和目标约束条件，寻找一般最符合条件的配送路线，使物流配送成本最小化。目前， 物流配送路径问题应用范围十分广泛，物流运输、交通建设、通信等。随着物流业的 发展，根据现代物流业发展的需求，车辆路径问题又进一步发展了有时间窗车辆路径 问题( v e h i c l er o u t i n gp r o b l e mw i t ht i m ew i n d o w s ，v r p t w ) ，或有时间窗物流配送 路径优化问题，也即是在物流配送路径优化问题上，增加客户对配送时间的要求，目 标仍然是求解问题的最优解，使得物流配送成本最小化。 物流配送路径优化问题是从旅行商问题( t r a v e l i n gs a l e s m a np r o b l e m ，t s p ) 发 展而来。旅行商问题是由h a m i l t o n 爵士和英国数学家t h o m a sp e n y n g t o nk i r k m a n 于 1 9 世纪提出的。旅行商问题这样描述：已知若干个城市和任何两个城市间的距离， 一个旅行商从一个城市出发，要求经过每一个城市而且每一个城市只能经过一次，最 2 产 i l - ，li，l毒 1 、引言 终到达出发城市，目标就是寻找一条最短的路线，使其旅行的成本最低。 物流配送路径优化问题是已经被证明了的，都是n p ( n o n d e t e r m i n i s t i c p o l y n o m i a l ) - h a r d 问题。目前，这类问题的求解还没有一种有效的算法，即是很难找 到一个最优解，一般找到的近似最优解。因此，寻找一种有效的算法来解决物流配送 路径优化问题，是研究者一直在做的工作。 1 3 国内外研究现状 d a n t z i g 和r a m s e r t l 】于1 9 5 9 年提出车辆路径问题( v e h i c l er o u t i n gp r o b l e m ，v r p ) ， 自此以来，对物流配送路径优化问题的研究不断深入与发展，并取得了很好的效果， 而且得到了广泛的应用，并在社会经济的发展中发挥重要作用。现在对物流配送路径 优化问题的研究，从大的范畴分为两种，一是物流配送路径优化问题，二是有时间窗 物流配送路径优化问题。有时也可以从某一个角度，再根据具体的约束条件分类。如 有时间窗物流配送路径优化问题，也可以分为两种，一是软时间窗( s o f tt i m e w i n d o w s ) 约束的物流配送路径优化问题，二是硬时间窗( h a r dt i m ew i n d o w s ) 约 束的物流配送路径优化问题。 1 3 1 物流配送路径优化问题国内外研究现状 物流配送路径优化问题可以描述为：有一个物流配送中心，从配送中心出发，用 若干辆汽车向多个客户配送货物，最后再返回配送中心。配送中心的位置和每个客户 的位置、需求量一定，每辆汽车的载重一定，要求每条路线的客户需求量之和不能超 过车辆的最大载重，而且每个客户点的配送必须且只能有一个车辆来完成( 原则上一 个客户的需求量不会大于车辆的最大载重) ，通过合理配送路线，使总运行距离最短 或总成本最低。 1 9 6 2 年，b a l i n s k i 等人t 2 1 首先提出的车辆路径问题的集分割，并在此基础上建立 了车辆路径问题的模型。1 9 7 1 年，e i l o n 等人【3 】提出的动态规划法解决固定配送车辆 数的车辆路径问题。1 9 7 4 年，g i l l e t t 等人【4 1 提出的扫描法( s w e e p ) ，利用平面几何和 极坐标的方法，对各个客户点进行顺时针或逆时针方向扫描。1 9 7 6 年m o l e 等人提出 把节约法和最邻近法相结合，即是插入法。1 9 8 1 年，c h r i s t o f i d e s 等人【5 】提出的k 度 3 l 、引言 中心树和相关算法。1 9 8 6 年，g l o v e r 等人【6 】首先提出了禁忌搜索思想的雏形。1 9 9 1 年，g e n d e a n 等人【7 】最先把禁忌搜索算法运用到解决车辆路径问题的研究中。之后， e t a i l l a r d 等人【8 】利用角度和路径中心的几何方法对问题的空间进行分割，再用禁忌搜 索和模拟退火算法求救问题。19 91 年，t h a n g i a h 首先将遗传算法应用到求解车辆路 径问题中。 国内学者也对物流配送路径优化问题做了很多工作，并取得了很多成效的研究成 果。1 9 9 9 年，姜大立等人【9 】在启发式算法的基础上，通过改进遗传算法，对染色体进 行可行化影射，取得了不错的效果。与此同时，张涛等人1 1 0 】也是改进了遗传算法，运 用3 - o p t 算法来加强遗传算法的局部收敛性，同时保证搜索的全局性，也取得了很 好的效果。2 0 0 0 年，肖鹏等人1 1 1 】也是对遗传算法进行改进，采用基因换位算子对染 色体重组，即后来所称的新颖单亲遗传算法。2 0 0 2 年，张丽萍等人【1 2 】同样是对遗传 算法进行改进，通过引进交叉算子，以解决传统遗传算法的“早熟 问题或“陷入局 部最优”问题，也使遗传算法在求解车辆路径问题上得到进一步改进和提高。2 0 0 3 年，纪寿文等人【1 3 】采用神经网络的方法，成功地对车辆优化调度进行了试验研究。2 0 0 4 年，陈湘州等人【1 4 1 进一步改进遗传算法，引进一种进化逆转算子，提高算法的局部搜 索能力。 除此之外，物流配送路径优化问题与前沿学科相结合，如人工智能、神经网络等 学科，也取得了不错的效果。其中，蚁群算法就是一个典型的人工智能思想，在求解 物流配送路径优化问题上，获得较好的结果。 1 3 2 有时间窗物流配送路径优化问题国内外研究现状 有时间窗物流配送路径优化问题是在物流配送路径优化问题的基础上，增加有时 间窗的约束条件。目前，对物流配送路径优化问题的研究，也越来越趋于成熟。 1 9 6 4 年，c l a r k 和w r i g h t t ”1 提出c l a r k w r i g h t 算法( 节约法) ，即是按节约值大小 的顺序构造路径，依次把一个不在路线上的客户点增加到路线中，直到所有客户点都 在路线中为止。随后，p a e s s e n s 等人【1 6 】对节约法进行改进，建立相关算法模型。1 9 6 8 年，r a o 等人【1 7 】在b a l i n s k i 提出的v r p 集分割基础上引入了列生成方法进行求解。1 9 8 1 年，f i s h e r 等人【1 8 1 提出的三下标车辆流方程。1 9 9 1 年t h a n g i a h 1 9 】和1 9 9 3 年j o e l 2 0 1 都用 4 l l 、引言 遗传算法来求解有时间车辆路径问题，1 9 9 4 年t h a n g i a h t 2 又改进了算法，取得了不 错的效果。1 9 9 5 年，r o c h m ，y 等人【2 2 】运用概率多元化算法，拓展了求解有时间车辆 路径问题的领域，也能够解决有时间车辆路径问题。1 9 9 6 年，j l a w r e n c e r 2 3 1 利用遗传 算法来求解车辆路径问题，也有效地解决了有时间窗的车辆路径问题。1 9 9 7 年， t a i l l a r d ，e 等人【2 4 1 采用的禁忌算法，同样在解决有时间车辆路径问题上取得不错的效 果。1 9 9 9 年，h o m b e r g e r , j 等人1 2 5 1 采用的进化启发式算法，在求解有时间车辆路径问题 上也非常有效。1 9 9 9 年，g a m b a r d e l l a lm 等人【2 6 】提出m a c s v r p t w ，该算法就是 以蚁群算法为基础，介绍了种新的优惠多重目标函数的方法，对于求解有时间车辆 路径问题上非常有效。 在国内，有时间窗物流配送路径优化问题的研究，起步相对比较晚，但也越来越 热。1 9 9 8 年，李大卫等人1 2 7 1 利用求解t s p 的最佳距离搜索启发式算法，并对其进行 改进，提出了一个求解有时间窗车辆路径问题的启发式算法。2 0 0 0 年，谢秉磊等人【2 8 】 通过改进遗传算法的编码方式为自然数编码，处理了软、硬时间窗约束的车辆路径问 题，获得了较佳的效果。2 0 0 1 年，周贤伟和李光远【2 9 】把遗传算法和车辆装载g p s 相 结合，建立了有时间窗车辆路径问题的模型。2 0 0 2 年，张丽萍等人【3 0 】通过引入新颖 的交叉算法，改进遗传算法，并建立相应的模型，解决了遗传算法的“早熟 问题。 2 0 0 3 年，宋厚冰和蔡远利【3 1 1 通过把分组信息与染色体结合，并辅以交换局部搜索技 术，改进遗传算法，取得了较佳的效果。2 0 0 4 年，刘小兰等人【3 2 】改进了原有大规模 邻域搜索算法在求解有时间窗车辆路径问题上的缺陷，引入“短路径优先策略 ，并 建立相关的大规模邻域搜索算法模型，对解决大规模问题起到加速的效果。 1 4 本文研究的主要内容及组织结构 首先，在学习与研究国内外学者在物流配送路径优化问题上的研究成果，着重对 有时间窗物流配送路径优化问题进行研究，尤其是传统算法在求解此问题上的研究成 果，如：遗传算法1 3 3 - 3 6 1 、蚁群算法 3 7 - 3 8 1 、禁忌搜索算法【3 蜥1 等；其次，着重学习与研 究国内外学者在求解物流配送路径优化问题的方法或算法，并在传统算法和最新研究 算法学习的基础上，提出并购算法，建立完整的并购算法模型，以及由并购算法发展 来的混合并购算法模型，并对算法性能做比较与分析；最后，通过并购算法的研究， s 1 、引言 构建基于并购算法的有时间窗物流配送路径优化问题模型和基于混合并购算法的有 时间窗物流配送路径优化问题模型，并借助m a t l a b 平台模拟实验，获得较好的物 流配送方案，即获得了有时间窗物流配送路径优化问题的最优解或近似最优解。具体 每个章节的研究重点如下： 第一章节：引言。主要是对课题背景的学习与研究，包括国内外在物流配送路径 优化问题上研究的现状与趋势，以及在有时间窗物流配送路径优化问题上研究的现状 与趋势，特别是当前国内外在求解物流配送路径优化问题上的方法或算法，也是做本 课题预备工作的重点。 第二章节：并购算法简介。主要介绍并购算法思想、定义、分类、模型、以及性 能分析。具体介绍并购算法思想的由来，定义两种并购算法，即并购算法和混合并购 算法，并建立完成的并购算法模型和混合并购算法模型，分别介绍构成两种并购算法 模型的几个重要要素，以及对这两种并购算法联系与区别进行分析。最后分别介绍了 两种并购算法的流程步骤，以及对两种并购算法的性能进行分析、比较与总结 第三章节：并购算法在有时间窗物流配送路径优化问题中的应用。首先，介绍了 有时间窗物流配送路径优化问题的描述，以及建立有时间窗物流配送路径优化问题的 数学模型。其次，也是本章节的重点，分别把并购算法和混合并购算法应用到有时间 窗物流配送路径优化问题中，即建立基于并购算法的有时间窗物流配送路径优化问题 模型和基于混合并购算法的有时间窗物流配送路径优化问题模型。 第四章节：实验及结果分析。本章是对前两章研究结果的检验，主要是针对第三 章节的基于并购算法的有时间窗物流配送路径优化问题模型和基于混合并购算法的 有时间窗物流配送路径优化问题模型，在m a t l a b 平台下模拟实验，获得实验结果， 即获得有时间窗物流配送路径优化问题的最优解或近似解。最后，分析实验结果，包 括对在两种并购算法下的实验结果比较与分析，以及分别与目前的获得最优解作比较 与分析。 第五章节：论文总结与研究展望。主要对本文作全面的总结，特别是对并购算法 在求解有时间窗物流配送路径优化问题的发展，做出期许与展望，以及并购算法对可 能解决其它领域的问题，也做出期许与展望。 6 l 叠 冉 0 2 、并购算法简介 在本章节中，主要介绍并购算法思想、定义、分类、模型、以及性能分析。具体 介绍并购算法思想的由来，定义两种并购算法，即并购算法和混合并购算法，并建立 完成的并购算法模型和混合并购算法模型，分别介绍构成两种并购算法模型的几个重 要要素，以及对这两种并购算法联系与区别进行分析。最后分别介绍了两种并购算法 的流程步骤，以及对两种并购算法的性能进行分析、比较与总结。 2 1 并购算法( m e r g e r s & a c q u isitio n saig o rit h m ) 的基本思想 并购算法是通过并购、重组操作达到资源整合、优化配置的企业并购行为，它是 基于企业并购思想之上所形成的一种优化方法。企业并购f 4 1 1 ，是在市场经济环境下， 根据市场自身规律，企业在诞生、发展、灭亡的过程中，所形成的市场行为之一一并 购行为，是资源再整合，也是优化市场资源配置的市场自身调节行为。正是基于企业 并购思想形成的方法称为并购算法。并购算法主要有企业生态编码、初始化企业生态、 预处理企业生态、劣信度评估、并购操作、重组操作、选择操作等主要要素组成。 根据并购算法中的并购操作的不同，分为并购算法( 或称单一并购算法) 和混合 并购算法。混合并购算法与并购算法的最大不同，就在并购操作上，其中并购算法采 用的并购操作对象是单个的，也称为单个并购操作，所以此并购算法也称单一并购算 法。而混合并购算法中的并购操作，是单个并购操作的基础上，又增加了多个并购操 作，二者交叉互补，即称为混合并购操作，所以此并购算法也称混合并购算法。 2 2 并购算法 并购算法，是基于并购算法的基本思想，由企业生态编码、初始化企业生态、预 处理企业生态、劣信度评估、并购操作、重组操作、选择操作等七大要素组成。其中， 并购操作采用单一的单个并购操作，并购算法流程图( 见图2 1 ) 。 7 2 、并购算法简介 2 3 并购算法的基本要素 2 3 1 企业生态编码 图2 1 并购算法流程图 用一组数字解的形式来表示不同企业个体，由不同的数字解所形成的序列，就构 成了一条企业生态链，多条企业生态链编码就是构成了企业生态编码。编码的方法很 多，如自然数、二进制等方法。本文采用自然数编码，每一个数字代表一个企业个体。 2 3 2 初始化企业生态 一条企业生态链有若干个企业集团组成，一个企业集团有若干个企业个体组成， 根据某种编码方式，随机产生若干条企业生态链就构成了一个企业生态( 市场) ，即 完成了企业生态的初始化。 r 尊 母 j ， ； 2 、并购算法简介 2 3 3 预处理企业生态 根据具体的求解问题，在初始化企业生态的同时，先对企业生态进行预处理，便 于后面的操作或目标实现，一般是简化或弱化求解问题的约束条件，可以加快算法的 收敛，提高求解问题的效率，优先获得求解问题的相对初始最优解。 2 3 4 劣信度评估 劣信度是企业个体、企业集团和企业生态链在不同环境下生存或经营状况的反 映，也是作为评估企业个体、企业集团和企业生态链优劣性的依据。劣信度的评估有 3 个部分，包括对企业个体、企业集团和企业生态链的评估。所以，针对不同的对象， 不同的求解问题，劣信度代表不同的含义。 企业个体劣信度评估，只局限于某个企业集团内部。企业个体劣信度在劣信度高 的企业集团出售某个企业个体时，作为选择出售( 被并购) 企业个体的参照依据，同时 也是企业集团内部重组时的重要依据。企业个体劣信度高低的判断依据，主要源于企 业个体在企业集团中发挥的作用大小。 企业集团劣信度评估，只局限于某个企业生态链上，是企业生态链上的各个企业 集团经营状况的反映，作为企业集团间进行并购时的重要参考依据。在并购操作时， 劣信度低的企业集团优先并购劣信度高的企业集团内部的某个企业个体。企业集团劣 信度高低的判断依据，主要源于企业集团在企业生态链上发挥的作用大小。 企业生态链劣信度评估，只针对某个生态链而已，是反映企业生态中当前企业生 态链上发展的优劣。企业生态链劣信度高低的判断依据，主要源于企业生态链上各个 企业集团或所有企业个体发展的总体状况。 2 3 5 并购操作 在并购算法中，并购操作是重要的操作之一。在企业生态链中，遵循以企业集团 劣信度从高到低，企业个体劣信度从高到低的原则，逐步出售( 被并购) 企业个体。 并购的企业集团则是按从低到高的原则收购出售的企业个体。每次并购操作，只局限 于单个企业个体，也正是因为如此，才将这样的并购操作称为单个并购操作。通过企 业集团问的并购，使资源得到优化配置。 9 2 、并购算法简介 2 3 6 重组操作 在并购算法中，重组操作也是重要的操作之一。企业集团间完成并购操作后，在 企业生态链上，所有企业集团都要做重组操作，以达到集团内部资源的优化配置。重 组的形式是根据企业个体在企业集团内部的定位和作用，合理地分配其所在位置，充 分发挥企业个体在企业集团中的作用，提高企业集团的整体竞争力，而企业个体的定 位和作用是通过其在企业集团内部的企业个体劣信度来判断的。 2 3 7 选择操作 选择操作是在当前企业生态中，选择出符合目标需求的企业生态链作为当前最佳 目标的一种操作。在每次并购操作、重组操作之后，要判断每一条企业生态链劣信度 是否降低，如果降低，则更新企业生态链，否则，不更新。同时，在当前企业生态中， 记录符合要求的企业生态链，暂时作为当前企业生态中最佳的企业生态链。 2 4 混合并购算法 混合并购算法，也是基于并购算法的基本思想，由企业生态编码、初始化企业生 态、预处理企业生态、劣信度评估、混合并购操作、重组操作、选择操作等七大要素 组成。其中，并购操作采用单个并购操作和多个并购操作交叉结合的方式，即混合并 操作，混合并购算法流程图( 见图2 2 ) 。 1 0 ， 一 2 、并购算法简介 图2 2 混合并购算法流程图 2 5 混合并购算法的基本要素 2 5 1 企业生态编码 用一组数字解的形式来表示不同企业个体，由不同的数字解所形成的序列，就构 成了一条企业生态链，多条企业生态链编码就是构成了企业生态编码。编码的方法很 多，如自然数、二进制等方法。本文采用自然数编码，每一个数字代表一个企业个体。 2 5 2 初始化企业生态 一条企业生态链有若干个企业集团组成，一个企业集团有若干个企业个体组成， 根据某种编码方式，随机产生若干条企业生态链就构成了一个企业生态( 市场) ，即 完成了企业生态的初始化。 2 5 3 预处理企业生态 2 、并购算法简介 根据具体的求解问题，在初始化企业生态的同时，先对企业生态进行预处理，便 于后面的操作或目标实现，一般是简化或弱化求解问题的约束条件，可以加快算法的 收敛，提高求解问题的效率，优先获得求解问题的相对初始最优解。 2 5 4 劣信度评估 劣信度是企业个体、企业集团和企业生态链在不同环境下生存或经营状况的反 映，也是作为评估企业个体、企业集团和企业生态链优劣性的依据。劣信度的评估有 三部分，包括对企业个体、企业集团和企业生态链的评估。所以，针对不同的对象， 劣信度代表不同的含义。这里的劣信度评估分为两部分，根据并购操作的不同，定义 不同的劣信度。如果是单个并购操作，则劣信度评估同上2 3 4 。如果是多个并购操 作，则分别定义如下： 企业个体劣信度评估，只局限于某个企业集团内部。企业个体劣信度在劣信度高 的企业集团出售某个企业个体时，作为选择出售( 被并购) 企业个体的参照依据，同时 也是企业集团内部重组时的重要依据。但不同于2 3 4 的是，每一个集团都要参与出 售部分企业个体，而不在是单个企业个体。企业个体劣信度高低的判断依据，虽然主 要是源于企业个体在企业集团中发挥的作用，但考虑的因素要比2 3 4 稍微复杂些， 企业个体劣信度的具体定义要符合多个并购操作的需求而定义。 企业集团劣信度评估，不影响并购的具体操作，只是局限于某个企业生态链上， 是链上的各个企业集团经营状况的反映，作为企业集团间进行并购时的重要参考依 据。在混合并购操作时，劣信度低的企业集团优先并购劣信度高的企业集团内部的某 个企业个体。企业集团劣信度高低的判断依据，主要源于企业集团在企业生态链上发 挥的作用大小。同上2 3 4 。 企业生态链劣信度评估，也不影响并购的具体操作，只是反映企业生态中企业生 态链上发展的优劣。企业生态链劣信度高低的判断依据，主要源于企业生态链上各个 企业集团或所有企业个体发展的总体状况。同上2 3 4 。 2 5 5 混合并购操作 在混合并购算法中混合并购操作，分为单个并购操作和多个并购操作，但两者不 是同时运用的，而是以单个并购为主，多个并购为辅，交叉使用。单个并购操作就是 1 2 2 、并购算法简介 并购算法中的并购操作，同上2 3 5 。多个并购操作定义如下： 多个并购操作是由于单个并购操作不能使并购算法继续收敛或并购算法易于“陷 入局部最优”，为了改进并购算法而提出的。在企业生态链上，每一个企业集团都参 与出售，同时也参与并购。而且出售的个体不再是单个，而是多个或不定个，具体出 售的个数，是根据企业集团内部的企业个体劣信度而具体确定的。 2 5 6 重组操作 在混合并购算法中，重组操作也是重要的操作之一。企业集团间完成混合并购操 作后，在企业生态链上，所有企业集团都要做重组操作，以达到集团内部资源的优化 配置。重组的原则是，根据企业个体在企业集团内部的定位和作用，合理地分配其所 在位置，充分发挥企业个体在企业集团中的作用，提高企业集团的整体竞争力，而企 业个体的定位和作用是通过其在企业集团内部的企业个体劣信度来判断的。 2 5 7 选择操作 选择操作是在当前企业生态中，选择出符合目标需求的企业生态链作为当前最佳 目标的一种操作。在每次混合并购操作、重组操作之后，要判断每一条企业生态链劣 信度是否降低，如果降低，则更新企业生态链，否则，不更新。同时，在当前企业生 态中，记录符合要求的企业生态链，暂时作为当前企业生态中最佳的企业生态链。 2 6 两种并购算法的联系与区别 并购算法和混合并购算法的联系，从名字就可以猜到二者的联系，是显然易见的。 并购算法是混合并购算法的基石，混合并购算法是在并购算法的基础上发展而来的， 混合并算法发展了并购算法，也是对并购算法的一个补充和完善，二者是相辅相成的。 两种并购算法的发展，是伴随着问题的发展，而不断发展和延伸过来的，前后统一。 并购算法和混合并购算法的区别，可以从以下两个方面介绍。其一，从算法的构 成要素上看，重要的区别是在并购操作要素上，并购算法采用的是单个并购操作，而 混合并购算法采用的单个并购操作和多个并购操作形成的混合并购操作。主要原因 是：并购算法只采用单个并购操作，有可能在程序还没有到达终止条件，就“陷入局 部最优”，而此时也没有更好的措施使算法继续收敛。因而，引入了混合并购操作， 13 2 、并购算法简介 即增加了多个并购操作，当单个并购操作“陷入局部最优”时，多个并购操作可以打 破僵局，使算法继续向着我们需要的结果发展；其二，劣信度的定义有不同之处，主 要是发生在企业个体劣信度身上。主要原因是：当混合并购算法执行多个并购操作时， 参与并购的主体和出售的主体都发生了变化，不再是单一的企业集团，也不是单一的 企业个体。出售的主体是多个企业集团的多个企业个体集合，而这些并购原则的变化， 相应地要调整衡量影响企业个体在并购中发挥作用的要素标准，显然考虑的要素相对 前者复杂些。 2 7 并购算法的性能分析 2 7 1 并购算法的步骤 s t e p l ：参数说明和初始化。 企业生念链条数n r ；循环的迭代次数n c = 1 ；最大迭代次数i 眦；当前出售企 业个体所隶属的企业集团标识g r o u p m a r k = o n e s ( n r ，1 ) ，g r o u p m a r k 的选择顺序是根 据s t e p 6 中“企业集团劣信度 从高到低排列；当前出售企业个体在所隶属的企业集 团g r o u p m a r k 中的标识s i n g l e m a r k = o n e s ( n r ，1 ) ，s i n g l e m a r k 的选择顺序受s t e p 4 中 的并购操作中s o m e 函数影响；m a s i n g l e s u m 是当前g r o u p m a r k 所指企业集团中被临 时选为参与并购操作的部分企业个体数目的最大值，也受s t e p 4 中的并购操作中s o m e 函数影响；g r o u p c h a i n 表示坼个企业生态链；g r o u p s u m 表示当前企业链上企业集 团的数目；根据某种编码方式，随机生成坼条企业生态链，每一条链上有刀个企业 个体，这些企业生态链就构成了一个企业生态( 市场) ，即g r o u p c h a i n 。其中，o n e s 是赋值为l 的函数