（管理科学与工程专业论文）配送中心规则货物配装问题的优化模型研究.pdf

l i i i l lri l l ll iti r l r l li if i l l f y 19 0 2 4 11 重庆交通大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究 工作所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人 或集体已经发表或撰写过的作品成果。对本文的研究做出重要贡献的个人和集体， 均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名： 胡韶姊日期：硎年耳月吁日 重庆交通大学学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保 留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。 本人授权重庆交通大学可以将本学位论文的全部内容编入有关数据库进行检索， 可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。同时授权中国科 学技术信息研究所将本人学位论文收录到中国学位论文全文数据库，并进行信 息服务( 包括但不限于汇编、复制、发行、信息网络传播等) ，同时本人保留在其 他媒体发表论文的权利。 学位论文作者签名：淝梯 日期：矧年今月7 日 指导教师签名： 日期：压c f 年( p月f 弓日 本人同意将本学位论文提交至中国学术期刊( 光盘版) 电子杂志社c n f d 系 列数据库中全文发布，并按中国优秀博硕士学位论文全文数据库出版章程规 定享受相关权益。 学位论文作者签名：胡招娣 日期：矧年斗月) 7 日 指导教师签名： 日期1 声“年 y 一 够月r 7 日 摘要 在物流配送业务中，货物配装问题的涉及面较广，需要考虑的因素较多，对 配送企业提高服务质量、降低物流成本、增加经济效益的影响也较大。货物配装 是物流配送的重要环节，其方案的优劣对提高整个物流系统的效率和降低运输成 本都有着重大的影响。合理的配装方案将会提高车辆的载重量利用率和容积利用 率，从而降低配送中心的物流成本，增强企业的竞争力，同时为企业带来巨大的 经济效益。 本课题对配送中心规则货物配装问题进行了优化研究，针对配送中心规则货 物配装问题提出了一个合理的布局及配装方案，以同时提高客货两用车车厢的载 重利用率和容积利用率。本文首先介绍了课题研究的背景和意义，配送中心货物 配装问题的概述，为货物配装问题模型的建立奠定了基础。其次，针对配送中心 多车型的货物配装问题，建立了选车模型，并用层次分析法进行求解，通过实例 验证了该方法用于车辆选择的有效性，本章为配送中心多车型货物的配装问题提 供了有效的选车方法。然后，建立了单一车型货物配装模型，为配送车辆的车厢 的门在后端的情况提出了块的划分法，并用动态规划法和遗传算法相结合的两阶 段算法进行求解，并通过实例比较验证了该算法比传统的配装方法更优。最后， 建立了多车型货物配装模型，通过第二章介绍的选车方法首先为待配装货物选择 合适的车型进行配装，接下来设计了动态规划法和遗传算法相结合的两阶段算法 对具体的配装问题进行求解，通过实例验证了该方法用于求解多车型货物配装问 题比传统的配装方法更优。该论文为配送中心多车型货物在配装前提供了有效的 选车方法和货物如何配装的具体的配装方法和更优的求解算法，具有一定的实际 应用价值。 关键词：货物配装； 层次分析法；动态规划法；遗传算法 a b s t r a c t a m o n gp h y s i c a ld i s t r i b u t i o nb u s i n e s s ，f r e i g h tl o a d i n gp r o b l e mi s r e l e v a n tt om a n yf a c t o r sa n d i si m p o r t a n tf o rd i s t r i b u t i o ne n t e r p r i s e st oi m p r o v es e r v i c eq u a l i t yr e d u c el o g i s t i c sc o s ta n di n c r e a s e b e n e f i t s i ti st h ei m p o r t a n te l e m e n tf o rl o g i s t i c sd e l i v e r yt h a tt h eg o o d sa r el o a d e di nc o n t a i n e r s ， t h e q u a l i t yo fi t ss c h e m eh a sg r e a ti n f l u e n c et oi m p r o v et h ee f f i c i e n c yo ft h e w h o l el o g i s t i c s s y s t e ma n dr e d u c et h et r a n s p o r tc o s t f r e i g h tl o a d i n gp r o b l e mp l a y sa ni m p o r t a n tr o l e i np h y s i c a l d i s t r i b u t i o n ar e a s o n a b l el o a d i n gp l a nc a ni m p r o v et h el o a da n ds p a c eu t i l i z a t i o nr a t i oo fv e h i c l e s ， r e d u c el o g i s t i c sc o s to fd i s t r i b u t i o ne n t e r p r i s e s ，i n c r e a s et h e i rc o m p e t i t i o nc a p a c i t y ，a n dw i l lb r i n g h u g ee c o n o m i cb e n e f i t st ot h e m a n da tt h es a m et i m ec r e a t em o r ev a l u ef o r t h ew h o l es o c i e t y t h i ss u b j e c to p t i m i z e sm u l t i v e h i c l ef r e i g h tl o a d i n gp r o b l e ma n dp u t sf o r w a r da r a t i o n a l p a c k i n ga n dl o a dt oi m p r o v et h el o a da n ds p a c eu t i l i z a t i o nr a t i oo fv e h i c l e s f i r s t l y , t h e s u b j e c t i n t r o d u c e st h e b a c k g r o u n d a n d s i g n i f i c a n c e o ft h e s t u d y , s u m m a r i z e sf r e i g h tl o a d i n g p r o b l e m ，e s t a b l i s h e st h eo p t i m a lm a t h e m a t i c sm o d e la b o u tf r e i g h tl o a d i n gp r o b l e m s e c o n d l y , t h e v e h i c l ec h o o s i n gp r o b l e mb e f o r ef r e i g h tl o a d i n gi sd e f i n e da n ds o l v e db yt h ea n a l y t i ch i e r a r c h y p r o c e s sa c c o r d i n gt ot h ed e c i s i o n m a k i n gc h a r a c t e r i s t i c so ft h ep r o b l e m a n dt h ee f f i c i e n c yo ft h i s m e t h o di sa l s ov e r i f i e db ya l le x p e r i m e n t a lc o m p u t a t i o nc a s e t h i sc h a p t e rp r o v i d e se f f e c t i v e c h o o s i n gm e t h o df o r d i s t r i b u t i o nc e n t e ro fm u l t i t y p e sl o a d i n gg o o d s t h i r d l y , t h e s u b j e c t e s t a b l i s h e so n e v e h i c l ef r e i g h tl o a d i n gp r o b l e m ，i ss o l v e db yt h ed y n a m i cp r o g r a m m i n g a n dg e n e t i c a l g o r i t h mw h i c ha l eu s e dt o g e t h e ra n dp r o p o s e sab a c k - e n db l o c kd i v i s i o nm e t h o df o rt h ec a r r i a g e d o o rd i s t r i b u t i o nv e h i c l e a n dt h e m o r ee f f i c i e n c yo ft h i sm e t h o dt h a nt h et r a d i t i o n a lm e t h o do f o p t i m a li s a l s ov e r i f i e db ya ne x p e r i m e n t a lc o m p u t a t i o nc a s e f i n a l l y , t h es u b j e c te s t a b l i s h e s m u l t i v e h i c l e f r e i g h tl o a d i n gp r o b l e m c h o o s e st h e a p p r o p r i a t et y p ef i t t i n g sb y t h em e t h o d p r e s e n t e da n di ss o l v e db yt h ed y n a m i cp r o g r a m m i n g a n dg e n e t i ca l g o r i t h mw h i c ha r eu s e dt o g e t h e r a n dt h em o r ee f f i c i e n c yo ft h i sm e t h o dt h a n t h et r a d i t i o n a li sa l s ov e r i f i e db ya ne x p e r i m e n t a l c o m p u t a t i o nc a s e t h i sp a p e rp r o v i d e s a ne f f e c t i v ec h o i c eo fv e h i c l em e t h o d sa n dh o wl o a d i n g g o o d sa n dm o r eo p t i m a la l g o r i t h m t h i sp a p e r h a sc e r t a i np r a c t i c a lv a l u ef o rp r a c t i c a lp r o b l e m s k e yw o r d s ：f r e i g h tl o a d i n g ；t h ea n a l y t i ch i e r a r c h yp r o c e s s ；d y n a m i cp r o g r a m m i n g g e n e t i ca l g o r i t h m 目录 第一章绪论1 0 1 选题背景和意义1 1 2 货物配装问题的概述2 1 3 货物配装问题的研究现状4 1 3 1 国外配装问题的研究现状4 1 3 2 国内配装问题的研究现状6 1 4 本文的主要研究内容8 1 5 创新点。8 第二章配装中的选车问题9 2 1 货物配装的选车模型9 2 1 1 货物选车问题的描述9 2 1 2 货物配装选车问题的模型建立9 2 2 货物配装选车问题的层次分析法的求解1 2 2 2 1 层次分析法( a h p ) 的基本原理介绍1 2 2 2 2 建立层次结构图1 3 2 2 3 标度与描叙一1 4 2 2 4 构造判断矩阵1 4 2 2 5 求最大特征值及特征向量1 6 2 2 6 一致性检验1 9 2 2 7 层次总排序与总一致性检验_ = o o ooo ooooo oooooo0 2 0 2 3 算例及结果分析2 3 2 4 小结。2 5 第三章单一车型的货物配装问题2 6 3o l 单一车型货物配装问题的数学模型2 6 3 1 1 单一车型货物配装问题的描述2 6 3 1 2 单一车型货物配装问题数学模型的建立。2 6 3 2 单一车型货物配装问题的动态规划法和遗传算法两阶段算法求解2 8 3 2 1 动态规划法的基本原理介绍2 8 3 2 2 遗传算法的基本原理介绍。3 1 3 2 3 单一车型货物配装问题的两阶段求解3 7 3 3 算例及结果分析4 2 3 4 小结吖4 6 第四章多车型的货物配装问题4 7 4 1 多车型货物配装问题的数学模型4 7 4 1 1 多车型货物配装问题的描述4 7 4 1 2 多车型货物配装问题数学模型的建立4 8 4 2 多车型货物配装问题的动态规划和遗传算法两阶段算法求解4 9 4 2 1 多车型货物配装问题的两阶段求解及算法设计4 9 4 3 算例及结果分析5 4 4 4d 、结6 0 第五章结论与展望6 1 5 1 本文的主要工作和研究结论6 1 5 2 有待于进一步研究的问题6 1 致谢6 3 参考文献6 4 附录。6 7 在校期间的科研成果及发表的论文。8 0 第一章绪论 1 1 选题背景和意义 第一章绪论 衡量一个国家物流业发展水平的重要指标是物流成本占g d p 的比重，而物流 业越发达，物流效率越高，物流成本越低，物流总成本占g d p 中的比重就越小， 因此，物流成本在国民经济中具有不可忽视的作用。配送是物流活动的一项重要 内容，配送成本对物流成本的影响很大。配装和运输是物流配送过程中的两个主 要环节，合理地选车并有效地配装能充分地利用车辆的使用空间和载重量以降低 车辆的配送成本，从而降低了物流成本。因此，越来越多的配送中心力求通过优 化配送成本来降低物流成本，而货物的配装是配送的主要问题，如何配装将成为 影响配送成本的关键。 现阶段，无论是对于货源比较单一、品种较少的情况，还是对服务对象较多， 货物品种相对繁杂的情况，大多数企业都是凭借员工的经验来装车，而用计算机 软件进行货物配装的企业非常少，前者的弊病是在装载运输货物时，经常未能按 预先的装载量将货物装上车，这样就使得货物不能及时送达客户手中，并且增加 了企业的配送成本，另外不合理的配装造成了较大地货损率，从而也增加了企业 的物流成本。因此，物流企业要节约物流成本，合理地配装是企业配送的一个不 可忽视的环节而且有利于提高车辆的装载利用率，从而减少货物损坏同时也减少 了车辆对道路的占用率。物流配送中心在选择运输车辆完成配送业务时，如果能 充分考虑车辆的空间和载重量，实行合理的配装方案，即使载重方面达到满载， 又充分利用车辆的有效容积，从而可以大大降低物流配送中心的配送运输成本的。 影响配送中心的配送成本的关键因素与运输成本有关，而运输成本与车辆有 很大关烈。配送中心在选择合适的车辆完成配送业务时，应充分考虑车辆的空间 和载重量，尽量做到满装满载，使车辆的载重利用率和空间利用率达到最大，这 是降低车辆运输成本的重要途径之一。另外由于配送的货物品种繁多，包装形态、 储运性能不一，在容重方面的差距很大。例如，如果待装货物的容重比较大，虽 然配送车辆的载重量很容易满足，但车辆的内部空间剩余很多；如果待装货物的 容重比较小，虽然配送车辆的内部空间很容易满足，但车辆的载重量可能就不尽 理想，这两种情况都造成了一定程度的浪费。因此，实行合理的配装方案，不仅 可以充分利用车辆的载重利用率和容积利用率，而且可以取得一定的经济效益和 社会效益。 2 第一章绪论 为了降低企业的物流成本，研究车辆的配装利用率对经济的发展和社会的进 步显得尤为重要，由此，配送中心的货物配装研究便提上日程。同时，物流配送 因为其直接影响着物流成本和客户的满意度而备受关注。物流配送中心要在获得 大量业务的同时减少物流配送成本，核心问题是配送车辆的选择、货物配装及运 输过程的系统化。因此，对物流配送中的配装问题进行优化研究，建立能即时定 量反映运输车辆配装状态的系统，是提高保障企业竞争能力和资源利用率的重要 课题。 1 2 货物配装问题的概述 配送中心货物配装问题可以描述为：配送中心现有多台不同车型的车辆，需 要将多种具有不同装载要求的货物送给不同需要的客户。在给定的约束条件下， 要求考虑货物在车辆空间的具体的装载位置和货物装车的先后顺序以使货物合理 地装入选定的车辆中并送给相应地客户，根据建立地模型对目标函数进行优化以 取得最优解。 配送中心根据货物配装问题的构成要素划分为以下不同的类型1 2 j 。 1 ) 根据客户对货物配送时间的需求分为有时限问题( 在规定的时间内将客户 需求的货物送到) 和无时限问题( 客户对需求的货物送达的时间无具体要求) 。 2 ) 根据车辆的数量分为单车货物配装问题( 即考虑理想状态下，配送中心只有 一辆送货车辆来配装货物) 和多车货物配装问题( 即配送中心拥有多辆来配装货 物) 。 3 ) 根据货物在装载空间的装载层数分为单层货物配装问题( 在车辆内将密度很 大的重质货物和易碎、怕压的货物单层装载) 和多层货物配装问题( 在装载层数上没 有太多限制的货物多层装载1 ) 。 4 ) 根据货物装载状况分为满载问题( 当需要配送的货物量等于或超出单车的载 重量，就需要一辆或及其以上的配送车辆来完成配送任务，其中车辆就需要满载 行驶) 、非满载问题( 当需要配送的货物量达不到单车的载重量，车辆在完成多项任 务的配送时处于非满载的状况) 以及满载和非满载混合问题( 当一部分需要配送的 货物量等于或超出车辆的载重量，而另一部分需要配送的货物量不足装满车辆的 载重空间，这时一部分车辆处于满载状态，而另一部分车辆处于非满载状态) 。 5 ) 根据车辆类型分为单车型问题( 用来配送货物的车辆的型号完全相同) 和多 车型问题( 用来配送货物的车辆的型号完全不同) 。 6 ) 根据优化目标的数量具体分为单目标问题( 优化目标只有一个) 和多目标问 题( 优化目标不止一个) 。 第一章绪论 3 构成配送中心货物配装问题的要素分类 构成配送中心货物配装问题的要素包括货物、车辆、客户、配送中心、约束 条件和目标函数等。 1 ) 货物。把配送给一个客户的货物看成是一批货物。每批货物都有其特有的 属性，例如品名、包装、重量、体积、要求送到的时间和地点、是否可以分批配 送等。货物的属性决定了选用的配送车型和货物能否与其他货物混装在同一辆车 内，例如，有些液体的货物需要专车配送，而有些具有挥发性的货物不能与其他 货物混装在同一辆车内，另外有些货物本来不能与其他货物混装，但由于包装、 密闭性良好而可以和其他货物混装。货物的数量是选择配送车辆的数量的依据。 2 ) 车辆。车辆是配送货物的工具。根据其类型可分为通用车辆和专用车辆， 大多数普通货物需通用车辆来装载，而一些性质特殊的货物需专用车辆来装载。 在货物配装时，车辆的最大装载量和最大空间是选择车辆载重量的依据。配送系 统中的车辆随车型的不同而不同。 3 ) 客户。包括分销商、零售商等。需求货物的数量、时间、次数及需求货物 的满足程度等是客户属性的划分依据。例如，某配送中心，有些客户需求货物的 数量可能不足或是超出车辆的最大装载量；而该配送中心所有客户的货物需求总 量可能超出或不足全部车辆的总装载量。客户需求货物的时间是指要求货物送达 的时间，对需求货物的时间要求包括以下几类：a 没有时间限制；b 有时间区间 限制f 即时间窗内送到，需求的货物在时间区间内送到) ；c 有时间限制( 这个时间 可以不遵守，不遵守就要给予一定的惩罚) 。客户对需求货物的次数可能仅有一次， 也可能为多次。客户对需求货物满足程度的要求包括以下两类：a 全部满足；b 一部分满足( 不满足时需受惩罚) 。客户的地理位置是影响货物装车顺序的重要因 素。按照“先送后装”的原则，将先送的货物装在车辆的后端；而将后送的货物 装载车辆的前端。 4 ) 配送中心。主要进行货物的集中、分类、包装、装卸、配送等。配送系统 中配送中心的数量可以是一个也可以是多个；配送中心的地理位置可以固定也可 以不固定；配送的货物类型可以是一种也可以是多种等。 5 ) 约束条件。待装货物的配装问题有以下约束： a 配装时需考虑待装货物的品种、数量等特性； b 配装时需考虑待装货物的优先级； c 配装时需考虑货物在车厢内的放置方向。 对本文研究的配送中心货物配装问题有如下界定 实际的配送中心的货物配装问题千差万别，为了方便建模和求解，对现实的 货物配装问题进行了一些简化和抽象化处理。 4 第一章绪论 配送中心向一个或是多个客户供货，且能满足所有客户的需求。 多车型货物的配装问题，即配送中心用来配装货物的车辆有多种类型。 每个客户需求的货物重量不超过车辆的最大载重量，货物的体积不超过车 辆的最大容积；所有客户需求的货物都可以混装在同一辆车内；所有客户的货物 均不允许分批配送。 每辆车装载的货物量不能超过车辆的最大载重量和最大装载体积； 客户对需求货物的送到时间考虑以下两类情形： 1 ) 没有时间限制；2 ) 在规定的时间准时送货。 根据以上界定，本文所研究的是一个配送中心、非满载的多层货物配装问题 优化。 1 3 货物配装问题的研究现状 1 3 1 国外配装问题的研究现状 在实际中，为了产品的安全和便于运输，很多产品在生产出来后就被装入到 各种尺寸的矩形木箱或纸箱汇总，然后这些箱子再被装入集装箱进行运送，集装 箱是一种很重要的集装化方式，它有利于货物的装卸和运输管理。中外广大研究 者对配装问题进行了深入研究，将其理论应用到实际生活中，并取得了不少成就。 其中对集装箱配装问题的研究更是系统和深入，集装箱装载问题( 简称c l p ) 在学 术上属于非常繁琐的几何组合优化问题( g e o m e t r i c c o m b i n a t o r i a l o p t i m i z a t i o n ) 。 在理论上，集装箱装载问题被划分为n p 完全问题。集装箱装载问题也是布局问题 领域的三维问题。集装箱问题是矩形货物在集装箱中的摆放安排问题，以最大化 集装箱空间的使用率为目标。一般情况下，称这类问题为三维装箱问题。根据已 有的文献，同时考虑集装箱和货物，将集装箱配装划分为四种类型：同体积货物 的配载、不同体积货物的配载、单集装箱的配载和多集装箱的配载等。集装箱问 题广泛地出现在铁路货车车厢装载，汽车车厢装载、轮船装载，集装箱装载中。 集装箱装载是配送过程的关键环节，托盘装载以及卡车等运输车辆的装载与集装 箱装载具有相似性。如果给出一个合理的布局及装载方案，在保证运输的稳定性、 多目的运送、负责限制、箱体内的重量分布、装箱效率等问题的基础上，使集装 箱的空间利用率最大，是这类问题的主要目标。 d y c k h o f f 在文献( 3 】中提出将集装箱装载划分为单集装箱配装与多集装箱的配 装( d y c k h o f f , 1 9 9 0 ) 。b o r t f e l d t 又将体积不相同的货物的配装细分为弱差异情形 ( w e a k l yh e t e r o g e n e o u s ) 与强差异情形( s t r o n gh e t e r o g e n e o u s ) 1 4 1 。s i m t ha 等提出 了不同的四分区算法以解决二维的货物配装问题【5 1 。b i s c h o fe t 6 】等对单品种货物的 第一章绪论 5 配装问题的求解采用了五分区算法，该算法基于四分区算法思想，该算法的不足 之处是没有解决剩余载重的问题，并需要大量的可能模式进行验证。d o w s l a n dk a 【7 l 对影响二维配装问题的因素进行了深入研究并对二维配装问题进行了分类。 b h a r m c h a r y as t 8 】等对小规模的货物配装问题提出了比较有效地深度优先搜索算 法，该算法的不足在于计算量的增长呈指数形式，因此不太适合大规模的货物配 装问题。 c h e n ( 1 9 9 5 ) 针对集装箱一般装载问题( 用一定数量的集装箱装载给定的货物) 给出了0 - 1 整数线性规划模型，考虑了货物和集装箱的不同规格、货物的方向、放 置因素，并分析了一些特殊情况，如单个集装箱装载、载重分布等1 9 j 。d a v i d p i s i n g e r ( 2 0 0 2 年) 【1 0 】提出了基于墙壁支撑的集装箱装入启发式方法，把整个集装箱 分解成若干层，每一层又分解成若干条。层由一系列垂直或水平的条所组成，层 的深度也就是每条的厚度由分枝定界法解决，而条的布局可转化为等宽或登高的 一维背包问题来处理。m i c h a e le l e y ( 2 0 0 2 年) 【1 1 】提出了一个建立相同方向物体的同 质块算法，把相同的物流按照同样的方向组合成块，然后由这些同质块填充集装 箱。但是d a v i dp i s i n g e r 和m i c h a e le l e y 的方法计算代价十分庞大，而且不论是 组成层、块，都要求同种或尺寸相似的物体有足够的数量，若是对于同种物体个 数少，物体的种类较多，尺寸差异较大地散装货物的情况并不适用。 目前，发达国家在配装方面已经做了很多研究，并取得了相当的成果。对配 送车辆线路优化问题，国内外许多学者按照不同的标准进行了分类： 按照任务特征，可分为纯装、纯卸及装卸混合问题；按照任务性质，可分为 对弧服务、对点服务以及混合服务问题；按照单个货运节点所需货物量来分，有 满载问题( 单个节点需货量大于等于车辆的装载容量，完成一项任务需多辆车) 和非满载问题( 单个节点需货量小于车辆的装载容量，一辆车完成多项货运任务) ； 按照物流中心的数目，分为单物流中心和多物流中心问题。 2 0 世纪8 0 年代末，许多发达国家真正认识到了配装的重要性。这种态度认识 的极大转变，给企业创造出更多盈利机会。在观念发生变化的同时，配装方式和 手段也有很大发展。 1 ) 为满足用户配送要求，出现了配送企业车辆利用率低，不同配送企业之 间交错运输，交通紧张，事故频繁等许多方面不合理现象。但近年来的发展，上 升到从更大范围考虑配送合理化，致力于推行整个城市所有企业的优化配装问题。 2 ) 一改往日完按顾客要求办事，而并不是按客户的合理要求办事的局面。 制定合理计划是高水平计划配送的一大进展。计划有效的促进了配送合理化。由 于可采用减少收费，也受到用户的欢迎。 6 第一章绪论 3 ) 配送区域的扩大。美国已经开展了洲际配送，日本不少配送时在全国范围 或是更大去也范围进行的，如同本东京的三味柱式会社的全国性配送系统，日本 a s i c a 配送系统、日本资生堂配送系统等都是全国性的配送系统。 4 ) 不经过物流基地中转，在足够批量且不增加用户库存情况下，配送在“直 达 领域中找到了优势。 5 ) 随着规模的扩大和计算机的微型化，计算机管理配送取得很大进展，这个 进展突出表现在以下三个方面：a 信息传递与处理，建立了e d i 系统。b 计算机辅 助决策，如辅助进货决策，辅助选址决策等，美国i b m 公司率先建立了配送车辆 计划和配装的计算机软件。c 计算机与其他自动化装置的操作控制，如无人搬运车， 陪送中心的自动分拣系统等。 1 3 2 国内配装问题的研究现状 我国自加入w t o 后，很多领域相继对外开放，更多的跨国企业将进入我国参 与市场竞争；我国的物流配送业出现了一些新的变化趋向。 专业化趋向。企业内部物流交由专业物流公司经营，这必然导致第三方物 流比重的增大。 规模化、集团化趋向。国内的中小型物流企业，有一部分将利用拥有国内 网络及设施、人力资源成本低等本土优势，与国外大型物流企业建立战略合作伙 伴关系；一部分将可能被大型物流公司收购、兼并；还有的将进行战略性重组和 改造，向综合物流发展，为大型跨国物流企业配套，成为供应链的重要组成部分。 多元化趋向。我国物流市场今后将呈现出一个国有、集体、个体、中资、 外资等各种所有制物流企业相互依存、同台竞争、相互促进的局面。 国际化趋向。由于世界制造业和o e m 中心在向我国转移，以及经济一体化 进程的加快，未来我国与世界各国之间的物资、原材料、零部件与制成品的进出 口运输，无论是数量还是质量都会发生很大变化。为适应这一变化，要求我国必 须在物流技术、装备、标准、管理、人才方面与世界对接。因此，我国物流配送 在国际化方面将会发展很快。 传统运输与仓储企业加快向第三方物流转变，由于国外物流企业纷纷来到 中国，再加之香港、台湾地区的中小企业进入内地，给国内的传统运输与仓储企 业加快向第三方物流转变。 物流配送信息化建设步伐加快。现代物流以信息技术为支撑，没有信息化 就没有现代物流的发展。目前国内外的一些大型物流企业，都在规划建立自己的 配送中心，改善物流配送信息服务技术，以提高企业的物流配送能力。 我国配送的发展应该说还处于很不成熟的状态，需要深刻分析，研究解决的办 法。我国对配送理论有一定研究，应用研究十分缺乏，基于多车型多包装的货物 第一章绪论 7 配载配装问题更是很少有问题，尽管有一些关于配装或配载方面的研究，也大多 是关于集装箱配载的算法，应用到实际问题当中并不多见。 青岛大学的宫佩珊( 1 9 9 7 ) 对没有配装限制的单品种货物配装问题提出了递 归方法【1 2 】，并取得了良好的效果。天津商学院的杨传民对于立体包装件的混装问 题， 提出了只适用于小规模的离散优化的方法【1 3 1 。段国林等【1 4 】用三叉树结构来表 示集装箱箱内货物装载的问题，并用启发式算法来求解。刘小群等【1 5 1 【1 6 1 对多品种 货物的配装问题考虑装载能力有限的前提下，首先采用容重比指标( 即同时考虑 货车的容积和载重) 来解决多品种货物的装载问题，该方法的不足之处在于没有 考虑货物的包装类型和规格。 孙焰和李致中在前人研究的基础上，对多品种货物的配装问题应用了多项式 近似算法来求解，该算法具有复杂性小并且收敛性较好的特点，但不足之处求解 时优先考虑了待装货物的体积或重量，没有优先考虑其他影响因素i l7 1 。北方交通 大学的何大勇【1 8 1 、山东师范大学的王静莲【1 9 1 等对集装箱配装问题采用遗传算法进 行了研究。西南交通大学的卜刮2 0 1 对零担货物装载进行了研究。阎威武等【2 1j ( 2 0 0 2 年) 在研究集装箱时通过考虑一些实际应用中的约束条件，提出了一种三维集装 箱装载的启发式算法。在算法中采用了三空间分割、平均高度装载、货物合并等 策略，考虑了方向、重量、优先顺序等约束条件，逐步淘汰差的装载方案，最后 达到满意的实载。乐千楷( 2 0 0 6 年) 以空间利用率的优化以及运算效率的提高为 目标，根据装载过程中的实际约束条件，采用分层装载思想以及空间划分合并原 则，结合启发式算法和遗传算法，提出三层次优化策略1 2 2 。 通过对国内外文献进行研究，虽然在货物配装的问题上有了一定的成果，并 且在建立模型时也考虑了许多约束条件，求解过程也应用了不同的算法。但是对 于特定的配送中心如烟草配送中心，由于配送线路的固定，而且配送的针对性较 强，配送的货物种类比较少数量相对较多，货物可以视为单集装箱弱差异情形这 类问题研究的很少，不足表现在以下几个方面： 大多数文献在建模过程中所考虑的约束条件有限，已有的文献对解决配送 车辆在载重量和空间利用率都达到最优时的合理配装几乎没有研究，少数文献只 是研究了在载重量利用率达到最大或是空间利用率达到最大时的配装方案。 已有的文献研究的配送车辆的门在侧面和后面都有，这样在考虑客户送货 顺序优先级时对配装的要求不是很高；有的文献根本就没有考虑客户送货顺序优 先级，这样对货物装车就没有顺序要求；极少量的文献考虑了配送车辆的门在后 面的情况，但在考虑客户送货顺序优先级时对如何将货物装车却没有研究。 8 第一章绪论 1 4 本文的主要研究内容 论文的主要内容如下： 第一章绪论：阐述本文研究的背景和意义；概述了货物配装问题；综述了货物 配装问题的国内外研究现状；最后介绍了本文的主要研究内容。 第二章配装中的选车问题：对配送中心货物配装选车问题进行了描述并建立 了相应的模型，最后用层次分析法对模型进行了求解并通过具体的算例进行了分 析并对本章进行了小结。 第三章单车型的货物配装问题：对单一车型货物配装问题进行了描述并建立 了相应的模型，利用动态规划法和遗传算法对模型进行了求解，最后通过具体的 算例进行了分析并对本章进行了小结。 第四章多车型的货物配装问题：对多车型货物配装问题进行了描述并建立了 相应的模型，利用动态规划法和遗传算法对模型进行了求解，最后通过具体的算 例进行了分析并对本章进行了小结。 第五章结论与展望：本文的主要工作和研究结论；有待进一步研究的问题。 1 5 创新点 对配送车辆车厢的门在后端的货物配装情况，提出了将车厢划分成“块 的方法，解决了在考虑客户送货顺序优先级的前提下，使得货物的装卸更方便。 针对配送中心货物配装问题的目标函数，采用动态规划法和遗传算法相结 合的两阶段算法对目标函数进行了求解。即在第一阶段考虑客户送货顺序优先级 的条件下用动态规划法使车辆的载重利用率达到最优，在第二阶段用遗传算法对 第一阶段求得的结果在考虑容积利用率达到最优时对问题进行求解，从而保证了 车辆的载重利用率和容积利用率都达到最优，并通过具体的算例验证了该算法的 有效性，两阶段算法很好地解决了配送中心货物配装问题。传统的配装方法只考 虑了载重利用率达到最优或是容积利用率达到最优，两阶段算法使配送车辆的载 重利用率和容积利用率都得到了相应程度地提高，从而节省了配送中心的运力， 为企业和社会创造了价值。 第一二章配装中的选车问题 9 第二章配装中的选车问题 2 1 货物配装的选车模型 2 1 1 货物选车问题的描述 汽车是公路运输中用来配送的最主要工具，用来配送的车型种类繁多，选择合 适的车型对配送中心来说无疑具有重要意义。但是如何选择车型是配送中心的一 大难题。配送中心为了降低配送成本，在货物配装之前，根据货物的特性来选择 合适的车型是货物装车前所需解决的问题。因此，配装的前提是选车，车辆选择 的好坏直接影响配送的经济性。把货物配装中的选车问题定义为根据送货优先顺 序和货物的特性，选择合适的车型，将货物完好地送达客户手中并尽可能使车辆 满载行驶i 列。 选车问题具体为【2 4 j ： 配送中心现有n 辆车负责i 个目的地的配送，每辆车的载重量为己，现有m 批货物需要送到j 个目的地，每批货物的重量为q 。，具体要实现的目标是：如何 选择合适的车辆来配送这批货物，尽可能充分利用车辆的最大载重量和有效容积， 即提高车辆的里程利用率，降低配送中心的配装成本等。 2 1 2 货物配装选车问题的模型建立 由于选车问题需要考虑的因素较多，所以在建立模型前，我们考虑如下假设 条件： 配送中心有多种车型参与配送，所有配装货物的车辆都属于配送中心自有。 为了充分利用配送车辆，对不同的货物应合理地选择相应车型的车辆进行配装。 若货物量大于一车的可以拆分为多车，使之转化为一车一货的问题进行研究。 配装车辆信息的表示为g = g ，g ：，g 。 ，待装货物的信息为 c = c ，c ：，c 。 ，配送中心有n 辆车，且车辆足够多，待配装的货物量为m ，且 货物量也是足够大。 尽可能降低配送中心的成本，保证送货的及时性和货物能够安全地到达客 户手中，即在保证货物及时、安全地送达客户手中的同时提高配送中心的经济性。 目标函数是要选择合适的车型来配装货物。为了设计一个综合评价指标， 对所有满足货物要求的车型计算其指标值，然后从中挑选最优的车作为匹配结果 t 2 5 - 2 8 1 。 1 0 第二章配装中的选车问题 假设第i 辆配装车辆的信息表示为c ，包括以下详细信息：配装车辆类型表 示为c 、配装车辆送货的最晚时间表示为c r , 、配装车辆车主的道德素养和服务 水平表示为c c ，、配送中心距离到客户的距离，即配装车辆的送货距离表示为c s ；、 配装车辆的最大装载量表示为c 彬、配装车辆的最大装载容积表示为c k 。所有的 信息记为 c j = 【c y , ，c 互，c s f ，c 形，c k 沁= 1 , 2 ，n ) 式( 2 1 ) 假设需要配送的货物批数用j 来表示，第j 批待装货物的信息表示为g ，包 括以下详细信息：待装货物适合装载的配装车辆类型表示为g k 、待装货物送到客 户手中的最晚时间表示为g t ，、待装货物从配送中心运到客户点的距离表示为 g s ，、待装货物的重量表示为g 形，、待装货物的体积表示为g v i 。所有的信息记 为 g = 1 g y ：，g l ，g s j , g ，a v , j ( _ = 1 , 2 ，m ) 式( 2 2 ) 根据待装的第j 批货物的特性，被选择的配装车辆i 需满足以下条件l2 9 】： 根据货物的特性对应的合适的车辆类型约束表示为： a y , = c 式( 2 3 ) 上式表示待装货物需要的车辆类型与选择的配装车辆的类型一致。 客户要求的时间和货物送达的时间约束： g i c 正 式( 2 4 ) 上式表示配送车辆送货的时间应该在客户期望的时间期限内。 待装货物的体积与配送车辆的容积约束： g v , sc v , 式( 2 5 ) 上式表示货物的体积需在配送车辆的容积限制内。 待装货物的重量与配送车辆的载重量之问的约束： g w j s c 彬 式( 2 6 ) 上式表示配送车辆的载重量需大于待装货物的总重量。 对满足以上、约束条件的配装车辆选择使下列指标达到最优的 配送车辆i 。第i 辆配送车辆的主要优化指标因素及其表达式如下： 吨百公里油耗 x = m i n 芦 d l 1 1 1 芦 弘 式( 2 7 ) 0 ；第i 运次所耗的油量( 吨) ，l ；第i 运次行驶的里程数( 百公里) ， 卢运次数。该指标从车主和社会物流角度考虑，油耗的多少不仅影响物流成 第二章配装中的选车问题 本，而且对环境也有很大影响，选车的目标之一是相同条件下车辆的油耗尽可能 少。 车辆利用率 x 一堕二竺j 式( 2 8 ) a ，：兰一 al 厶o ， 一 c s f 车辆的利用率方面主要考虑的是载重利用率和容积利用率