（交通运输规划与管理专业论文）配送中心货物优化配装问题的模型与算法研究.pdf

北京交通大学硕士学位论文中文摘要 中文摘要 摘要：随着市场经济的发展和物流专业化水平的提高，物流配送业得到了迅速发 展。在物流配送业务中，货物配装闯题的涉及面较广，需要考虑的因素较多，对 配送企业提高服务质量、降低物流成本、增加经济效益的影响也较大。在现实生 产和生活中，集装箱装箱问题、车辆、船舶、飞机的装载问题等都可以抽象为货 物配装问题。 配送中心货物配装问题作为一个n p 难题，随着待装货物规格数量的增加，可 选的装载方案数量将以指数速度急剧增长。因此，当货物规格数量较少时选用动 态规划法可以解决货物配装问题，但当货物规格数量较多时用启发式算法求解该 问题就成为人们研究的一个重要方向。 本文围绕配送中心货物配装问题的模型和算法开展研究，主要做了以下工作： ( 1 ) 分析了研究配送中心货物配装问题对于配送企业提高服务质量、降低物 流成本、增加经济效益和增强市场竞争力的重要现实意义，进而对配送中心货物 配装问题的结构要素进行了系统分析。 ( 2 ) 建立了考虑客户需求优先级的单车货物配装问题的数学模型，构造了求 解该问题的两阶段算法，并通过实例计算验证了算法的有效性。 ( 3 ) 分别建立了单车二维、单车三维及多车三维货物配装问题的数学模型， 在此基础上分别设计了求解上述问题的遗传算法，进而通过实验计算说明了算法 的良好性能。 关键词：货物配装：遗传算法；动态规划；配送中心 分类号：u 4 9 2 3 北京交通大学硕士学位论文 a b s t r a c t a b s t r a c t a b s t r a c t ：w i t ht h e d e v e l o p m e n t o fm a r k e t e c o n o m y a n d l o g i s t i c s p r o f e s s i o n a l i z a t i o n ，p h y s i c a ld i s t r i b u t i o ne n t e r p r i s e sd e v e l o p e dr a p i d l y a m o n g p 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 sr 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 y ，r e d u c el o g i s t i c s c o s ta n di n c r e a s eb e n e f i t s i nr e a l i t y ，t h ef r e i g h tl o a d i n gi nc o n t a i n e r ，v e h i c l e ，s h i p a n dp l a n e ，e t ca l lc a nb es e e na sf r e i g h tl o a d i n gp r o b l e m s f r e i g h tl o a d i n gp r o b l e mb e l o n g st on p h a r dp r o b l e m w i t ht h ei n c r e a s i n go ft h e f r e i g h ts p e c i f i c a t i o n st ob el o a d e d ，t h es o l u t i o np r o j e c t so f t h ef r e i g h tl o a d i n gp r o b l e m w i l li n c r e a s e b ye x p o n e n ts p e e d t h e r e f o r e ， w h e nt h ea m o u n to ft h e f r e i g h t s p e c i f i c a t i o n si sf e w ，t h ed y n a m i cp l a n n i n ga l g o r i t h mc a nb eu s e dt os o l v et h ef r e i g h t l o a d i n gp r o b l e m w h e n t h ef r e i g h ts p e d f i c a t i o n si sv e r yd i v e r s i f y ，s o m eh e u r i s t c ss u c h a sg e n e t i ca l g o r i t h mm u s tb eu s e dt os o l v et h ef r e i g h tl o a d i n gp r o b l e m f o c u so nt h em o d e l sa n da l g o r i t h m sf o rt h ef r e i g h tl o a d i n gp r o b l e m s ，t h i sp a p e r m a i n l yi n c l u d e st h ef o l l o w i n g c o n t e n t s ( 1 ) t h ei m p o r t a n c eo ft h ef r e i g h tl o a d i n gp r o b l e mf o rd i s t r i b u t i o ne n t e r p r i s et o i m p r o v es e r v i c eq u a l i t y ，r e d u c el o g i s t i c sc o s ta n di n c r e a s em a r k e tc o m p e t i t i o nc a p a c i t y i s a n a l y z e d t h e nt h ee l e m e n t so ft h ef r e i g h tl o a d i n gp r o b l e ma r es y s t e m a t i c a l l y a n a l y z e d ( 2 ) o nt h eb a s i so fm o d e l i n gt h eo 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 mc o n s i d e r i n g t h en e e d i n ge m e r g e n c yo ft h ec u s t o m e r s ，at w o - p h a s ea l g o r i t h mi sd e s i g n e dt os o l v e t h ep r o b l e m t h e nt h ev a l i d i t yo ft h e a l g o r i t h mi sp r o v e db ys o m ee x p e r i m e n t a l c o m p u t a t i o n s ( 3 ) b a s e do nm o d e l i n gt h eo n e - v e h i c l et w o d i m e n s i o nf r e i g h tl o a d i n gp r o b l e m o n e v e h i c l et h r e e - d i m e n s i o nf r e i g h tl o a d i n gp r o b l e ma n dm u l t i - v e h i c l et h r e e - d i m e n s i o n f r e i g h tl o a d i n gp r o b l e m ，t h eg e n e t i ca l g o r i t h m sf o rt h e s ep r o b l e m sa r ed e s i g n e d a n d t h ee f f i c i e n c yo f t h e s ea l g o r i t h m si sa l s ov e r i f i e db ys o m ee x p e r i m e n t a lc o m p u t a t i o n s k e y w o r d s ：f r e i g h tl o a d i n g ；g e n e t i ca l g o r i t h m ；d y n a m i cp l a n n i n g ；d i s t r i b u t i o nc e n t e r c l a s s n 0 ：i h 9 2 3 致谢 值此论文定稿之际，衷心感谢导师郎茂祥老师。在我两年半的攻读硕士学位 期间，郎老师在学习和科研上给予了我悉心的指导，生活上给予了无私的关怀， 论文的字里行间无不凝聚着老师的心血。郎老师严谨求实的治学作风、诲人不倦 的师者风范时刻激励着我克服困难，认真完成本论文的工作。他求是创新的科研 精神和言传身教的师者风范，将使我在以后的工作中受益匪浅。他热情随和、宽 大为怀的个性修养更将使我受益终身! 感谢两年多来和我一起共事过的同门们，他们是：张炯、石洪波、白晓勇、 燕娟，葛瑞、刘春启，翟健峰。感谢他们给予我的鼓励、帮助与启发。特别感谢 自晓勇同学在遗传算法编程方面对我的帮助! 感谢挚友岳威、仇恒东、李风玲，感谢室友孟獭、曹丽华，郁竹君，感谢他 们在生活上对我的关心和支持，尤其要感谢室友孟狲给予我诸多的无私帮助。永 远难忘读研期间和他们共同度过的这段美好时光。并祝愿他们在今后的人生路上 一帆风顺! 最后感谢我的父母对我多年的培养，他们殷切的期望和无尽的关怀是鼓励我 不断进取的动力。浓浓亲情，无以吉报! 感谢我的姐姐和姐夫，他们多年来给予 我精神上和物质上的支持，是我漫漫求学路上的力量源泉。感谢我的男友，在我 读研期间给了我很多鼓励与支持。正是他们无私的奉献和深深的爱，才使我得以 顷利完成学业，我愿与他们共享收获的喜悦! 谨以此文献给所有关心、帮助和支持过我的人们! 北京交通大学硕士学位论文 1 绪论 1 1 选题背景和研究意义 1 绪论 当前，现代物流已被公认为是企业在降低物质消耗、提高劳动生产率以外创 造利润的第三个重要源泉，也是企业降低生产经营成本，提高产品市场竞争力的 重要途径【l j 。据专家测算，现代物流成本约占企业经营成本的3 0 - 5 0 ，当一个有 效的物流系统与企业主要商业系统集成之后，可使仓储量降低5 0 ，准时交货率 提高4 0 ，营业收入增加1 0 以上 2 1 。在经济发达国家和一些经济水平较高的发 展中国家，现代物流水平已成为影响企业竞争力的关键因素。 与发达国家相比，我国的物流产业效率较低。根据全国第三产业普查资料， 我国交通运输、仓储、代理和批发等行业的成本费用之和占国民生产总值的比重 为1 5 左右，据2 0 0 5 年统计数据显示，全社会物流费用支出约占国民生产总值的 1 9 左右。而美国的全社会物流费用支出仅占其国民生产总值的1 0 左右。另据有 关资料，目前我国一般工业品从产品出厂经过装卸、储存、运输等各个物流环节 到消费者手中的流通费用约占商品价格的5 0 左右；而新鲜水果、易变质食品、 某些化工产品的流通费用有的高达商品售价的7 0 - 8 0 ；我国汽车零配件的生产 中，其加工装配时间仅占2 。而9 8 的时间是原材料、零配件的储存、装卸和搬 运时间；在各种产品的生产和流通环节中还有大量原材料、零部件和产品的“库存”。 这些费用和时间上的消耗和大量存在的“库存”正是潜在的实施物流管理的领域，这 为物流的发展留下了巨大的空间。在这种形势下，研究如何通过实施科学的物流 管理，以提高物流效率、降低物流成本、提高服务质量是十分必要的。 据统计，2 0 0 5 年全国物流总收入为1 8 7 9 1 亿元，同比增长1 2 7 ，其中配送 收入为2 1 9 亿元，同比增长2 8 【3 】，即配送收入的增长速度明显高于全国物流总收 入的增长速度。提高配送效率，可以有效降低物流成本，提高物流效率。 配送是物流系统中的一个重要环节，它是指按客户( 包括零售商店、用户等) 的订货要求( 包括在货物种类、数量和时间等方面的要求) ，在配送中心进行分货、 配货工作，并将配好的货物及时送交收货人的物流活动。配送过程主要包括以下 作业环节：从生产工厂进货或运达并集结的集货作业；根据各个客户的不同需求， 在配送中心将所需要的货物挑选出来的分货和配货作业；考虑配送货物的重量和 体积，充分利用车辆的载重量和容积的货物配装作业；合理确定车辆配送路线并 及时送货的配送作业。可见，物流配送是一种集集货、分货、配货、配装、送货 北京交通大学硕士学位论文1 绪论 等多种功能为一体的物资流通方式【4 】。 配送是现代物流中一个重要的直接与消费者相连的环节，是货物从物流结点 送达收货人的过程。配送是在集货、配货的基础上，按货物种类、品种搭配、数 量、时间等要求所进行的运送，是配”和“送”的有机结合。 随着物流系统的集约化、一体化的发展，需要将配送的各环节综合起来，其 核心部分是配送车辆的集货、货物配装及送货过程。货物配装是配送的基础环节， 配装质量的好坏直接关系到配送的效率，进一步影响到整个配送中心运作的效益。 货物配装问题是货物运输中的关键阅题之一，货物配装问题解决碍好坏直接关系 到车辆空间、载重的利用率和物流成本的高低，因此，货物配装问题的合理解决 可为压缩物流成本提供巨大的空间。本文将配送车辆货物配装问题作为研究对象， 具有一定的理论和现实意义。 1 2 配送中心货物配装问题概述 1 2 1配送中心货物配装问题的描述 配送中心货物配装问题可以描述为：在配送中心，有若干需要送给不同客户 且有不同装载要求的货物，有若干台车辆，要求合理安排货物的装车顺序、合理 安排货物在车辆空间的装载位置，从而在给定的约束条件下，把所需配送的货物 合理装入车辆中，并使目标函数取得优化。 1 2 2 配送中心货物配装问题的构成要素 配送中心货物配装问题主要包括货物、车辆、配送中心、客户、约束条件和 目标函数等要素。 ( 1 ) 货物。货物是配送的对象。可将每个客户需求的货物看成一批货物。每 批货物都包括品名、包装、重量、体积、要求送到的时间和地点、能否分批配送 等属性。 货物的品名和包装，是选用配送车辆的类型以及决定该批货物能否与其它货 物装在同一车辆内的依据。例如，一些货物因性质特殊需要使用专用车辆装运； 一些货物因性质特殊不能与其它货物装在同一车辆内；一些货物虽然性质特殊， 但由于包装条件很好，故也能与其它货物装在同一车辆内。 货物的重量和体积是进行车辆装载决策的依据。当某个客户需求货物的重量 2 北京交通大学硕士学位论文 l 绪论 或体积超过配送车辆的最大装载重量或容积时，则该客户将需要多台车辆进行配 送。 货物的送到时间和地点是制定配送顺序的依据。 允许货物分批配送，是指某个客户需求的货物可以用多辆车分批送到，即使 其需求量在一辆车的装载量以下。 ( 2 ) 车辆。车辆是货物的运载工具。其主要属性包括：车辆的类型、装载量 等。 车辆的类型有通用车辆和专用车辆之分，通用车辆适于装运大多数普通货物， 专用车辆适于装运一些性质特殊的货物。 车辆的装载量是指所用车辆的最大装载重量和最大装载容积，是进行车辆装 载决策的依据。在某配送系统中，车辆的装载量可以相同，也可以不同。 ( 3 ) 配送中心。是进行集货、分货、配货、配装、送货作业的地点。 在某配送系统中，配送中心的数量可以只有一个，也可以有一个以上；配送 中心的位置可以是确定的，也可以是不确定的。对于某个配送中心，其供应的货 物可能有一种，也可能有多种；其供应的货物数量可能能够满足全部客户的需求， 也可能仅能满足部分客户的需求。 ( 4 ) 客户。也称为用户，包括分仓库、零售商店等。客户的属性包括需求货 物的数量、需求货物的时问、需求货物的次数及需求货物的满足程度等。 在某配送系统中，某客户需求货物的数量可能大于车辆的最大装载量，也可 能小于车辆的最大装载量；而该系统全部客户的货物需求总量可能超过全部车辆 的总装载量，也可能低于全部车辆的总装载量。 某客户需求货物的时间，是指要求货物送到的时间，对配送时间的要求可分 为以下几种情况：无时间限制；要求必须在指定的时间区间( 也称为时间窗) 内送到：有时间限制，但可以不遵守，只是不遵守时要给予一定的惩罚。 某客户需求货物的次数可能仅有一次，即只需一次配送服务；也可能为多次， 即需要多次配送服务。 某客户对需求货物满足程度的要求可分为两种情况：要求全部满足；可 以部分满足，但不满足时要给予惩罚。 客户的位置是决定货物装车顺序的重要因素，根据“先至后装”原则，一般应将 后到客户的货物装在车辆的前端( 里端) ，而将先到客户的货物装在车辆的后端0 1 , 端) 。 ( 5 ) 约束条件。配送中心货物配装问题应满足的约束条件主要包括： 满足所有客户对货物品种、规格、数量的要求。 满足货物装载顺序要求。 北京交通大学硕士学位论文 l 绪论 满足货物在装载空间内的放置方向的要求( 如有的货物只能立放) 。 满足货物装载层数的要求( 如有的货物因怕压只能单层装载等) 。 车内装载货物的总重量不得超过车辆的最大允许载重量，车内装载货物的 总体积不得超过车辆的有效容积。 尽量做到均衡装载，即使货物总重心控制在一定范围内，以保证车辆运行 的安全和平稳。 ( 6 ) 目标函数。对配送中心货物配装问题，可以只选用一个目标，也可以选 用多个目标。经常选用的目标函数主要有： 配装车辆的载重量利用率最高。当配装货物的密度均较小时，提高车辆的 载重量利用率可以减少使用车辆的数量，从而降低物流成本。 配送车辆的容积利用率最高。当配装货物的密度均较大时，提高车辆的容 积利用率可以减少使用车辆的数量，从而降低物流成本。 配送车辆的载重量和容积均得到充分利用。当配装货物的密度有大有小时， 应通过组织轻重配装，使配送车辆的载重量和容积均得到充分利用。 配装综合费用最低。降低配装综合费用是实现配送经济效益的基本要求。 在配送业务中，与货物配装有关的费用包括：车辆相关费用、装卸机械相关费用 和配装有关人员费用等。 1 2 ，3 配送中心货物配装问题的分类 配送中心货物配装问题可按照其构成要素划分为不同的种类。 ( 1 ) 按货物在装载空间的装载维数分，有二维货物配装问题( 即因货物为密 度很大的重质货物或易碎怕压货物有特殊装载要求只能装载一层，在车辆内只能 单层装载) 和三维货物配装问题( 货物在车辆内可以多层装载) 。 ( 2 ) 按车辆载货状况分，有满载问题( 由于客户需求货物的数量大于或等于 车辆的载重量，故完成一项配送任务需要一辆及其以上的配送车辆，配送车辆需 要满载运行) 、非满载问题( 由于客户需求货物的数量小于车辆载重量，多项配送 任务可共用一辆配送车辆，车辆在配送过程中经常处于不满载状态) 以及满载和 非满载混合问题( 由于一部分客户需求货物的数量大于或等于车辆的载重量，而 另一部分客户需求货物的数量小于车辆的载重量，造成一些配送车辆需要满载运 行，而另一些车辆则经常处于不满载状态) 。 ( 3 ) 按客户对货物配送时间的要求分，有无时限问题( 客户对货物送到的时 间无具体要求) 和有时限问题( 客户要求将需求的货物在规定的时间内送到) 。 ( 4 ) 按车辆的数量分，有单车货物配装问题( 即配送中心只有一辆车用于货 北京交通大学硕士学位论文 l 绪论 物的配装) 和多车货物配装问题( 即配送中心有多台车辆用于货物的配装) 。 ( 6 ) 按车辆类型分，有单车型问题( 所有用于配装货物的车辆的载重量和容 积均相同) 和多车型问题( 用于配装货物的车辆的载重量和容积不完全相同) 。 ( 7 ) 按优化目标分，有单且标问题( 仅考虑一个配装优化目标) 和多目标问 题( 同时考虑多个配装优化目标) 。 1 2 4 对本文所研究的配送中心货物配装问题的界定 如1 2 3 所述，现实中的配送中心货物配装问题是十分复杂的，为了方便建 模和求解，需要对现实问题进行一些抽象和简化。现对本文研究的配送中心货物 配装问题做如下界定： ( 1 ) 从个配送中心向多个客户送货：配送中心供应的货物，能够满足所有 客户的需求。 ( 2 ) 单车型货物配装问题，即研究多车货物配装问题时车辆的载重量和容积 均相同。 ( 3 ) 各个客户需求的货物均可以相互混装；每个客户需求货物的重量不超过 配送车辆的最大载重量，体积不超过配送车辆的有效容积；每个客户的送货要求 必须满足，且仅能由一台车辆完成，不允许分批配送。 ( 4 ) 根据货物的情况，可以二维或三维配装。 ( 5 ) 每台配装车辆的最大载重量一定，不允许超重，装载容积一定，不允许 超过车辆的允许装载容积。 ( 6 ) 对于客户要求将需求货物送到的时间，分别考虑以下两种情况：无时 间限制；要求在指定的时间内完成送货任务，不允许提前或拖后。 根据以上界定，本文所研究的配送中心货物配装问题均属于单配送中心、非 满载的多维货物配装问题 1 3 配送中心货物配装问题的研究现状 配送车辆的货物配装问题与集装箱的装箱问题为同一类问题，都可以归结为 如何最大限度的发挥装载空间的容积和载重量( 承载能力) 从而降低配送成本的 问题。人们将如何最大限度地发挥装载空间的容积和承载能力从而降低配送成本 的问题称为货物配装问题。由于问题本身具有重要的理论价值和广泛的实际应用 背景，引起了国内外许多研究人员大量的相关研究。目前求解货物配装问题的常 北京交通大学硕士学位论文1 绪论 见方法主要有数学规划法、图论法、启发式方法和人工智能方法等。s m i t h t 5 】和 s c h e i t h a u e r l 6 1 先后提出了不同的四分区算法以解决二维货物配装问题。b i s c h f f 平口 d o w s l a n d 在四分区算法思想的基础上，提出用五分区方法求解单品种货物配装问 题，但该方法需要检验大量的可能模式，而且对于剩余载重量的处理并未论及l7 1 。 w r i g h t 采用了底盘装载曲线方法，他将集装箱的长和宽对应曲线的x 与y 坐标轴， 一种可行的布局方案由曲线上对应的( x ，y ) 点确定【8 1 。d o w s l a n d 对二维货物配 装问题进行了详细的划分，并就影响问题求解的若干因素进行了分析【9 】。 b h a t t a c h a r y a 等采用深度优先搜索算法能有效解决小规模的货物配装问题，但是由 于该算法的计算量随装入货物规格数目的增加而呈指数增长，因而不适合求解大 规模的货物配装问题1 1 引。王金敏等讨论了约束底盘装载问题，并提出了一种基于 计算机的启发式方法【i ”。段园林等对集装箱箱内货物装载布局提出了一种利用三 叉树结构表达，基于空间分解的启发式算法t 坨】。刘小群等研究了装载能力有限条 件下多品种货物的配装问题，通过容重比指标同时考虑了货车的容积和载重【1 3 l 。 孙焰和李致中【1 4 】采用多项式近似算法求解多品种货物的配装问题，算法复杂性小， 收敛性较好。本文结合配送中心货物配装实际工作中的一些约束条件，提出应用 动态规划法和遗传算法解决配送中心货物配载问题。 1 4 本文的主要研究内容 如前所述，论文的第1 章分析了研究配送中心货物配装问题对于配送企业提 高服务质量、降低物流成本、增加经济效益和增强市场竞争力的重要现实意义， 并对配送中心货物配装问题的结构要素进行了系统分析，从而为建立配送中心货 物配装问题的数学模型奠定了基础。第l 章还对货物配装问题的研究现状作了综 述。 论文的第2 章研究用二阶段算法求解考虑客户需求优先级的单车货物配装问 题。在对考虑客户需求优先级的货物配装问题进行描述的基础上，建立了该问题 的数学模型。设计和实现了求解考虑客户需求优先级的货物配装问题的两阶段算 法，并通过实验计算验证了该算法的良好性能。 论文的第3 章研究用遗传算法求解单车二维货物配装问题。在对单车二维货 物配装问题进行描述的基础上，建立了该问题的数学模型。在概述遗传算法的基 本原理的基础上，设计和实现二维货物配装问题的遗传算法。并通过实验计算研 究了该遗传算法的性能。 论文的第4 章研究用遗传算法求解单车三维货物配装问题。在对单车三维货 6 北京交通大学硕士学位论文 1 绪论 物配装问题进行描述的基础上，建立了该问题的数学模型，进而设计和实现了求 解该问题的遗传算法，并通过实验计算研究了该遗传算法的性能。 论文的第5 章研究用遗传算法求解多车三位维货物配装问题。在对多车三维 货物配装问题进行描述的基础上，建立了该问题的数学模型，进而设计和实现了 求解该问题的遗传算法，并通过实验计算证明了该算法的有效性。 论文的第6 章总结了本文所作的主要工作和研究结论，并对需要进一步研究 的问题进行了简要说明。 北京交通大学硕士学位论文2 考虑顾客优先级的单车货物配装问题的模型与算法 2 考虑客户需求优先级的单车货物配装问题的模型与算法 2 1 考虑客户需求优先级的单车货物配装问题的数学模型 2 1 1对考虑客户需求优先级的单车货物配装问题的描述 客户需求优先级可用客户需求优先系数( 也可称为客户需求紧急系数) 表示。 客户需求优先系数是指客户对货物需求紧急程度的大小。如果客户a 要求将货物 在l 小时之内送到，而客户b 要求将货物在4 小时之内送到，则客户a 的需求优 先系数要大于客户b 的需求优先系数。也就是说，客户需要将货物送到的时间越 早，则其需求优先系数越高，其需求货物的配装优先级也就越高。 客户需求优先系数可根据客户要求将货物送到的时问按表2 1 取值。 表2 - 1 客户需求优先系数表 t a b 2 - lt h ep r io f c u s t o m e r s n e e d 客户要求将货物送到的时间客户需求优先系数 客户需求紧急程度 1 小时内 4 特急 2 小时内 3 急 4 小时内2较急 6 小时内1一般 1 0 小时内 0 5 不急 考虑客户需求优先级的单车货物配装问题可以描述为： 设配送中心有n 个客户需求的货物，其重量分别为g ，岛，体积分别为 v l ，v ：，各客户的货物需求优先系数分别为a t ，a 2 ，用于配送货物的货车 的载重量为g ，有效容积为矿，要求在优先配装特急、急和较急需求的客户的货 物的前提下，制定优化的配装方案，使货车的载重量利用率或有效容积利用率最 高。 2 1 ，2 考虑客户需求优先级的单车货物配装问题的数学模型的建立 根掘对考虑客户需求优先级的单车货物配装问题的描述，可建立该问题的数 学模型如下： 北京交通大学硕士学位论文2 考虑顾客优先级的单车货物配装问题的模型与算法 月 z = o t m a x 晶薯+ f l m a x v f t ，。lf = i 约束条件为： 晶t - g e q t 矿 t = l 或0扛l ，2 ，刀 x i = 1 v a , 2 ( 2 1 ) ( 2 2 ) ( 2 3 ) ( 2 4 ) ( 2 5 ) 上述模型中，式( 2 1 ) 为目标函数，当要求载重量利用率最大时盯= 1 ，f l = o ， 要求容积利用率最大时口- - - 0 ，f l = l ；约束条件( 2 2 ) 表示所配装货物的总重量不 能超过车辆的载重量；约束条件( 2 3 ) 表示所配装货物的体积不能超过所用车辆 的有效容积；约束条件( 2 4 ) 表示当客户i 需求的货物装入车辆时，取工= 1 ，当 不装客户i 需求的货物时，取暑= o ；约束条件( 2 5 ) 表示当碡2 2 时，客户i 的货 物需求紧急程度为特急、急或较急，必须优先装车，因此取x = l 。 2 2 动态规划法的基本原理 2 。2 1 动态规划法的起源 动态规划法是运筹学的一个分枝，它是求解多阶段决策过程的最优化的一种 数学方法。大约产生于2 0 世纪5 0 年代初，美国数学家贝尔曼( r b e l l m a n ) 等人根 据一类多阶段问题的特点，把多阶段决策过程转化为一系列互相联系的单阶段决 策问题，然后进行逐个求解。与此同时他提出了解决这类问题的“最优性原理”， 研究了很多实际问题，从而创建了解决最优化问题的一种新方法动态规划法 【i 卯。 虽然动态规划法主要用于求解以时间划分阶段的动态过程优化问题，但一些 与时间无关的静态规划如线形规划或非线形规划，只要人为引进时间因素后，把 它们看成多阶段过程，也可以用动态规划方法求解。在求解最短路径、库存管理、 资源分配、设备更新、排序、装载等问题时，用动态规划方法非常方便l 】“。 近几十年来，动态规划在理论、方法和应用等方面都取得了很大进展，并在 工程技术、经济、工业生产与企业管理、军事工程等领域得到了广泛的应用。 北京交通大学硕士学位论文2 考虑顾客优先级的单车货物配装问题的模型与算法 2 2 2 动态规划法的基本概念 ( 1 ) 多阶段决策问题 多阶段决策过程，是指这样一类特殊的活动过程：问题可以按时间顺序分解 成若干相互联系的阶段，在每一个阶段都要做出决策，全部过程的决策是一个决 策序列1 1 7 1 。要使整个活动的总体效果达到最优的问题，称为多阶段决策问题。 ( 2 ) 决策过程的分类 阶段通常用时间表示，在各个时间段，采用不同的决策，即决策随时间而变 动，这就是“动态”的含义【i 引。动态规划就是要在时间的推移过程中，在每个时间 阶段选择适当的决策，以便整个系统达到最优。 根据过程的时间变量是离散的还是连续的，决策过程可分为离散时间决策过 程( 即多阶段决策过程) 和连续时间决策过程：根据过程的演变是确定的还是随 机的，决策过程可分为确定性决策过程和随机性决策过程，其中应用最为广泛的 是确定性多阶段决策过程。 2 2 3 动态规划模型的基本要素 一个多阶段决策过程最优化问题的动态规划模型通常包含以下要素： ( 1 ) 阶段 阶段是对整个过程的自然划分。通常根据时间顺序或空间特征来划分阶段， 以便按阶段次序解决优化问题。描述阶段的变量称为阶段变量，常用k 表示。阶段 的划分一般是根据时间和空间的自然特征来划分的。 ( 2 ) 状态 状态表示每个阶段开始时过程所处的自然状况。它应该能够描述过程的特征 并且具有无后向性，即当某阶段的状态给定时，这个阶段以后过程的演变与该阶 段以前各阶段的状态无关，即每个状态都是过去历史的一个完整总结。通常还要 求状态是直接或间接可以观测的。描述状态的变量称为状态变量，常用五( & ) 表示 第k 阶段的状态变量。 ( 3 ) 决策 当个阶段的状态确定后，可以做出各种选择从而演变到下一个阶段的某个 状态，这种选择手段称为决策，在最优控制问题中也称为控制。描述决策的变量 称为决策变量，常用a s k ) 表示第k 阶段当状态变量处于墨时的决策变量。 ( 4 ) 策略 策略是一个按顺序排列的决策组成的集合。可供选择的的策略有一定范围， 北京交通大学硕士学位论文2 考虑顾客优先级的单车货物配装问题的模犁与算法 此范围称为允许策略集合，用p 表示。从允许策略集合中找出达到最优效果的策略 称为最优策略。 ( 5 ) 状态转移方程 状态转移方程是确定过程由个状态到另一个状态的演变过程。在确定性决 策过程中，一旦某阶段的状态和决策已知，则下一个阶段的状态便完全确定。可 用状态转移方程表示这种演变规律。 ( 6 ) 指标函数和最优值函数 指标函数是用来衡量过程优劣的一种数量指标，它是定义在全过程和所有后 部予过程上确定的数量函数，常用k 。表示。 最优值函数就是指标函数的的最优值，记为l ( s 。) ，它表示从第k 阶段的状态吼 丌始n n 阶段的终止状态的过程，采取最优策略所得到的指标函数。 2 2 4 动态规划的基本思想 一般将前文提到的具有明显的阶段划分和状态转移的动态规划称为标准动念 规划。这种标准动态规划是在研究多阶段决策问题时推导出来的，具有严格的数 学形式，适合进行理论分析。在实际应用中，许多问题的阶段划分并不明显，这 时如果刻意地划分阶段反而更麻烦。一般来说，只要该问题可以划分成规模更小 的子问题，并且原问题的最优解中包含了子问题的最优解，就可以考虑用动态规 划解决 埘。 动态规划的是实质是分治思想和解决冗余。动态规划是一种将问题实例分解 为更小的、相似的子问题，并存储子问题的解而避免计算重复的子问题，以解决 最优化问题的算法策略【2 0 1 。 动态规划法所针对的问题一般都有一个显著的特征，即它所对应的子问题树 中的子问题呈现大量重复。动态规划法的关键在于，对于重复出现的子闯题，只 在第一次遇见时加以求解，并把答案保存起来，以后再遇到时可直接引用，不必 重新求解。 2 2 5 动态规划的基本步骤 动态规划一般包括如下四个步骤： ( 1 ) 划分阶段 按照问题的时间或空间特征，把问题分为若干个阶段。这若干个阶段必须是 有序或者可以排序的( 即无后向性) ，否则问题就无法用动态规划法求解。 北京交通大学硕士学位论文2 考虑顾客优先级的单车货物配装问题的模型与算法 ( 2 ) 选择状态 将问题发展到各个阶段时所处的各种客观情况用不同的状态表示出来。同样， 状态的选择要满足无后向性。 ( 3 ) 确定决策并写出状态转移方程 ( 4 ) 写出规划方程( 包括边界条件) 动态规划的基本方程是规划方程的通用形式化表达式。 用动态规划法解决实际问题时，通常按照以下几个步骤进行： ( 1 ) 分析最优解的性质，并描述其结构特征。 ( 2 ) 递归地定义最优解。 ( 3 ) 以自底向上的方式或自顶向下的记忆化方法计算出最优值。 ( 4 ) 根据计算最优值时得到的信息，构造一个最优解。 2 3 考虑客户需求优先级的单车货物配装问题的两阶段算法 2 3 1 算法的设计 本章采用两阶段法求解考虑客户需求优先级的单车货物配装闯题，第一阶段 对客户的需求优先级进行排序，将需求优先级高( 即客户要求将货物在1 小时、2 小时或4 小时之内送到) 的货物优先装车，第二阶段对需求优先级较低的货物利 用动态规划法求出最优配装方案。 设某配送中心有一待配装车辆，其载重量和有效容积分别为g 、v ，待配装货 物的重量分别为蜀，9 2 ，岛，且有m a x g l ，晶，s g ，体积分别为 h ，v 2 一，且有m a x v 1 ，1 2 ， sv ，客户需求优先系数分别为a 】，a 2 ，a n 。 考虑客户需求优先级的单车货物配装问题的两阶段算法思路： 第一阶段：优先配装需求优先级高的k 件货物，求出已装的k 件货物的总重量 及体积，可以得到车辆剩余可利用的总重量和总体积g 2 、以。 第二阶段：对剩余的编号为k + 1 至n 的货物用动态规划法制定优化的配装方案， 使车辆的载重量或容积得到充分利用。先将装剩余的( n k ) 件货物看作为( n - k ) 个阶段完成，用，u = l ，2 , - - - , n k ) 表示阶段；( x ，y ) 表示二维变量，表示第二阶 段车辆中装入货物总重量为x ，总体积为y 时状态。最优值函数lc x ，y ) 表示当总重 量不超过x ，总体积不超过y ，车辆中装入前j 件货物的最大重量( 或体积) 。显然有 t + ，k + ， z ( x ，y ) = c r m a x 岛+ f l m a x j = l ，2 ，一一k ( 2 6 ) 北京交通大学硕士学位论文2 考虑顾客优先级的单车货物配装问题的模型与算法 约束条件为： k + l g q x q x j = l ，2 ，一，疗一k q f f i k + l k + j k y j = l ，2 ，z k q = l + k ( 2 7 ) ( 2 8 ) 其中为o 一1 变量若货物q 装车则= 1 ，否则= 0 。因而只需求出五一。( g 2 ，) 即可。具体算法的求解是从第一个阶段开始依次向后推。其相应的最优策略由反 推运算即可以求出。 具体的步骤如下： 第一阶段：优先配装需求优先级高的货物。 s t e p l ：输入待配装货物的重量、体积和需求优先系数，n ( g ) = g l ，g z ，邑 ， ( v ) = ( v t , v 2 ， ，n ( a ) = a i ，a z ， 。输入货车的最大载重量g ，有效容积v 。 s t e p 2 ：对待配装货物按需求优先系数由高到低的顺序进行排序，得到新的体 积集( v ) = “，v 2 ，) ，重量集n ( g ) = g l ，9 2 ，岛 ，需求优先系数集 n ( a ) = a j ，呜，) ，使其满足a i2 a 2 吒。 s t e p 3 ：如果q 2 则取t = l ，货物装入货车，设a k 2 ，ak + i 2 。 s t e p 4 ：求货车内已装货物的总体积、总重量，即k = 】v ，g i = x , g ，。求 t女 出车辆剩余的可用体积、重量，即= v - z x t v ，g z = g 一岛。 l i l ，= l 第二阶段：对剩余的编号为k + 1 至1 3 _ 的货物用动态规划法制定优化的配装方案 使车辆的载重量或容积得到充分利用。 s t e p 5 ：在车辆中装入第k + l 件货物，其最大值是： z ( g 2 ，匕) = a m a x 鼠+ l 孔“+ , o m a x v i + 1 “ ( 2 9 ) s t e p 6 在车辆中装入第k + 2 件货物，其最大值是 五( g 2 ，) = o r m a x g i + 2 h + 2 + z ( g 2 一吼+ 2 以+ 2 ，吒一u + 2 坼+ 2 ) + m a x + 2 屯+ 2 + 石( g ：- g k + 2 + 2 ，k u + 2 & + 2 ) ( 2 ，1 0 ) s t e p ( n k “) ：在车辆中装入第n - k 件货物，其最大值是： 北京交通大学硕士学位论文2 考虑顾客优先级的单车货物配装问题的模型与算法 z 。i ( g 2 ，) = t z m a x g x + z n ( g 2 一晶矗，一矗) + m a ) 【 矗+ 正一h ( g 2 - g x ，k 一) ) ( 2 1 1 ) s t e p ( n k + 5 ) ：输出已装货物集合p = ( 五，屯，矗) ，实际装载货物的总重量 吒= 毋薯，总体积吃。= v f t 。 t = lj l i 2 3 2 算例及算法分析 某配送中心现有多批待配送货物，各批货物的重量、体积和需求优先系数见 表2 2 ，用一辆载重量为3 3 t ，有效容积为1 3 7 m 3 的车辆进行货物配送。要求在考虑 客户需求优先级的前提下，制定合理的配装方案，使车辆的载重量得到充分利用。 按客户需求优先系数由大到小的顺序对货物重新排序，得到的结果见表2 3 。 表2 2 配装货物数据表 货物编号i货物的需求优先系数q货物重量蜀( f )货物体积一( m ) l 4 o 5l 22ll 3 l o 5 2 4l 13 5 1 o 5 4 6 3 0 53 7 0 5 l l 8l0 64 根据考虑客户需求优先级的单车货物配装问题的两阶段算法求解，可得如下 计算结果： p = ( 玉，x 2 ，x 3 ，x 4 ，屯，而，黾) = “1 ，1 010 ，1 ，0 ) ， s8 g 。= 薯蜀= 3 2 ，= v j = 1 3 。 i = l，2 l 计算结果表明，在保证将客户需求优先系数大于等于2 的货物优先配装的前提 下，该配装方案使车辆的载重量和有效容积得到了充分利用。 通过以上实例计算，可以得出动态规划算法的以下特点： ( 1 ) 该算法是一种精确算法，可以得到所求问题的最优解； ( 2 ) 该算法本质上是一种枚举搜索算法，收敛速度相对较慢； 1 4 北京交通大学硕士学位论文2 考虑顾客优先级的单车货物配装问题的模型与算法 ( 3 ) 对于规模较小的问题，该算法的寻优效果很好，但随着问题规模的增大， 计算量也将呈指数增长，从而使其应用范围受到限制。 表2 3 排序后的数据表 t a b 2 3d m aa f t e rs o r t e d 货物编号i 货物的需求优先系数q货物重量g ( ，)货物体积( 肼) l4 o ，5l 2 30 53 321l 4 lo ，5 3 5lo 6 4 61o 52 71o 6 4 80 5ll 北京交通大学硕士学位论文 3 单车二维货物配装问题的模型与算法 3 单车二维货物配装问题的模型与算法 3 1单车二维货物配装问题的数学模型 3 1 1对单车二维货物配装问题的描述 二维货物配装问题也称单层货物配装问题。是指在一定约束条件限制下，将 不同客户需求的货物在不超过车辆装载限制( 载重量、容积、车厢尺寸) 的前提 下在车辆中进行合理的单层装载，使车辆的载重量和( 或) 容积利用率达到最大。 在配送中心的货物配装工作中，当待装货物全部为密度很大的重质货物或怕压、 易碎货物时( 货物有特殊装载要求只能单层装载) ，货物必须单层装载。设配送中 心有n 件待装货物，其重量分别为蜀，g ：，岛，体积分别为v l ，v 2 ，oo ，长度分 别为，2 ，n ，宽度分别为，心，高度分别为矗，红，吃用于装载货物 的货车的载重量为g ，有效容积为y ，货车车箱内部的长、宽、高分别为l 、w 、 h ，要求在满足货车最大载重量和有效容积约束，及满足车箱长、宽、高约束的情 况下，使货车装载货物后其载重量和( 或) 有效容积的利用率最高。即在已知车 辆的载重量、有效容积和车厢尺寸的情况下，求充分利用车辆载重量和( 或)