货物配装与配载.doc

安联物流配载与配装优化研究1 绪论1.1 研究背景和意义1.1.1 背景配载与配装是物流配送的一个重要环节。配送与一般送货的重要区别在于，配送是通过集合、分拣、配货等环节来使送货达到一定规模，以利用规模优势取得较低的送货成本。而在我们实际操作过程中，单个用户配送数量不能达到车辆的有效载运负荷时，应集中合理分配来配送货物以充分利用运输能力，从而降低配送成本。同时我们也应该为了确保配送服务质量，还应该选择适宜的配送车辆类型。因此，在物流配送决策中，同一时间内有很多不同货物需要配送而且有多种可供选择运输车辆，对于一定量的货物如何选择合适的运输车辆以最小的运输成本合理、快速的实现配送是一个亟待解决的问题。随着全球经济一体化及信息技术的发展，企业面临的生存与发展环境日趋复杂。为了获得竞争优势，企业必须不断地采用创新的理念与技术。物流作为“第三利润源泉”，受到人们的广泛重视。物流的发展水平已经成为衡量一个国家综合能力的重要标志之一。在现代化运输业的发展过程中，世界上许多国家有一个共同的发展规律，即海运、铁路运输发展在先，公路运输则后来居上，20世纪60年代以后，其发展速度大大超过铁路和其他运输方式。自20世纪70年代以来，公路运输在各种运输方式中的主导作用日益增强。美国、日本和西欧各国以货物量计的公路运输比重已超过80，我国也于20世纪90年代初达到75。目前，美国、日本及欧盟国家物流业均发展到了较高水平。就这些国家物流成本支出占GDP的百分比而言，均低于目前的世界平均水平，居世界领先地位。由于物流规模和物流成本在不断上升，人们对货物运输提出了更高的要求，如何快速有效地将货物配载与配装成为各生产行业迫切需要解决的一个重要问题。物流中货物配载与配装即是在满足客户需求的条件下，为客户配送合理的数量，有效利用车辆空间，派遣最少的车辆数量，使配送车辆运输时间少和运输费用低，将车辆有效的使用，使商品能在最短的时间内送到顾客的手中。解决货物配载与配装问题，将直接降低运输成本，为生产部门和运输部门带来巨大的效益。因而，研究和解决货物配载与配装问题也就有了非常重要的现实意义。从理论角度来看，研究和解决货物配装问题也会影响到许多领域的优化策略问题。货物配装问题实际上是一类三维物理空间拼装问题。而从广义上讲，并不仅仅是物理空间才存在拼装问题。如果我们把拼装问题抽象化，会发现对这类问题的研究广泛适应于其它许多领域，这种进一步的理解为探讨这类问题注入了新的活力。同时，也为解决其它许多同类的三维布局问题提供了方法。1.1.2 意义本论文想通过货物的配载与配装问题的研究，解决目前安联物流配送过程中货物品种繁多、车型复杂而造成的配载与配装难以合理，配送效率不高，从而产生较高成本的难题。首先研究不同车型的配载问题，期望通过对公司拥有的不同车型进行研究，选择合理的车辆配载方案来解决配载问题。然后研究货物的配装问题，基于选定的车辆，通过对不同包装的货物配装的研究使得车辆在保证载重和容积的情况下达到空间利用率最大，进而减少配送成本。最后将两者结合起来完成货物的配载与配装的研究。1.2 研究主要内容如何从不同的车型之中选择出合理的车辆来实现优化配载，以及针对不同的货物如何使得车辆的空间利用率最大，这就是本论文研究的主要问题。先通过对实际中的数据进行归类统计，然后比较理论的方案，从中选择出实用的与实际相结合的方案。首先对该公司车库车辆信息进行统计调查，选择适宜的配送车辆类型，利用车辆配载技术来充分保证货物的质量和数量完好的前提下，同时考虑卸货的先后顺序情况，尽可能使车辆满载行驶，也就尽量不要空驶。根据货物要求运输的实际情况，建立相应的模型，采用层次分析法来解决问题。然后对该公司经常配装的货运进行分析，货物配装问题主要包括货物、车辆、配送中心、客户、约束条件和目标函数等要素。在配送过程中，有若干需要送给不同客户有不同装载要求的货物，有若干台车辆，通过运用启发式算法来解决问题，要求合理安排货物的装车顺序、合理排货物在车辆空间的装载位置，从而在给定的约束条件下，把所需配送的货物理装入车辆中，并使目标函数取得优化，进而了解配送车辆的装载能力之后来进行合适的有效的配装。1.3 研究思路绪 论（研究背景、研究内容）研究现状与发展趋势配载与配装的概念安联公司配载与配装现状配载与配装问题分析优化方法的选择安联公司的配载与配装优化配载的优化配装的优化模型求解过程（遗传算法、计算机实现）模型建立（目标设定、条件分析、函数构建）方案实施检验结论（解决问题）图1.1 论文结构图2 配载与配装概述2.1 配载与配装的概念2.1.1 配载一般在单个客户配送数量达不到车辆的有效装载载荷时，应集中统一配送路线上的其他客户的配送货物进行搭配装载。以提高车辆运力的利用率。这样就实现了提高配送效率降低配送成本的目的。但是由于配送货物品种繁多，特性各异，在运输过程中的作业要求和操作工艺不可能完全一样，为保证配送服务质量，就应该选择合适的配送车辆类型，必要时还可能要分别配送。车辆配载技术要解决的主要问题就是，在充分保证货物质量和数量完好的情况下，尽可能使车辆满载行驶。2.1.2 配装由于配送作业本身的特点，配送工作的运输工具一般为汽车。因需要配送的货物的体积、形状、包装形式和比重各异，因此在装车时，不但要考虑车辆的载重，还要考虑车辆的容积，使得车辆的载重和容积利用率最大。车辆配装技术要解决的主要问题就是在充分保证货物的质量、外形和包装完好的情况下，尽可能地提高车辆的载重和容积利用率，以提高车辆的利用率，达到节约运输费用节省运力的目的。配装的主要解决问题是有效利用车辆容积和载重这两个因素的问题。2.1.3 配载与配装的区别配载与配装都是为了尽可能地提高车辆的利用率。但是，配装强调的是装车环节，强调如何有效利用车辆的装载空间，它的研究对象主要是货物装载过程。而配载强调的是从装车后一直到货物送达这整个过程中某一车辆的有效荷载是否被有效利用，它研究的是车辆的配载过程。配装强调的是装，货物如何装车就是配装需要解决的问题，而配载强调的是载，如何更好地调度车辆进行搭配就是配载要研究的问题。2.2 研究现状我国配送的发展应该说还处于很不成熟的状态，需要深刻分析，研究解决的方法。我国对配送理论有一定研究，应用研究却是十分缺乏。尽管有一些关于配载与配装方面的研究，也大多是关于集装箱配载的算法，应用到实际问题当中的不多见。现在常采用人工估计拼装方法，往住在确保全部装下的前提下，需要保留足够空间，浪费了宝贵的货运空间。而且在配装过程中，往往凭借经验，没有统一的计划，有时需反复进行装卸才能成功，浪费大量的人力和物力。因此，降低运输成本，提高集装箱利用率以及装箱效率，将显现出可观而直接的经济价值和社会价值。利用计算机强大的数据处理功能可以生成科学、高效的配装方案。配装问题就是从该应用背景中抽象出来的模型问题。通过利用最优化数学方法，构造货物配装方案的优化软件，并用计算机来实现配送调度，实现降低配送成本、提高配送效率的要求。2.3 发展趋势自我国加入WTO以后，更多的跨国企业进入我国参与市场竞争，物流配送要想在竞争中不被淘汰，就必须有一些新的变化呈现一些较好的发展趋势：专业化、规模化、集团化、多元化。同时也需要国际化，由于世界经济一体化进程的加快，未来我国与世界各国之间的物资、原材料、零部件与产成品的进出口配送运输，无论是数量还是质量都会发生很大的变化。为了适应这一变化，要求我国必须在物流技术、装备、标准、管理、才人方面与世界接轨。还要使得物流配送信息化建设步伐加快，现代物流以信息技术为支撑，没有信息化就没有现代物流的发展。目前国内外的一些大型物流企业，都在规划建立自己的配送中心，改善物流配送信息服务技术，以提高企业的物流配送能力。迈向21世纪的物流技术，不仅是企业战略的“商务物流”，而且是向整个社会实现物资供给的“社会物流”。从微观物流看，对于一个工业、商业企业来说，物流不仅是“第三利润源泉”，物流能力还被视为企业的核心能力，成为企业获取竞争优势的战略资源。在今天的经营环境中，企业通过在生产过程中降低成本获得竞争优势的空间已经非常有限了，因此，许多工业、商业企业在搞好技术开发和进行产品全面质量管理的同时，把寻求成本优势和差别优势的目光转向生产前后延伸的物流领域。中国加入WTO意味着更深层次的开放和更为激烈的竞争,特别是在现代物流这个最能体现当今社会生产专业化分工和高效运作特点的服务领域中，加入WTO后服务贸易的自由化将使欧美发达国家已相当成熟的现代物流业对刚刚起步的中国物流业提出严峻的挑战。同时，中国物流业也将因国外先进物流理念、物流操作与管理技术的流入而面临着积极的发展机遇。这种情况下，有效控制和全程管理，真正实现了资源利用的最大化，降低了企业的物流成本，增强了企业的竞争力，使货物流、信息流、资金流和人才流达到统一。现代的物流业，将呈现信息化、网络化、智能化、柔性化、标准化和社会化的特征，因此，可以预见21世纪将是国际化物流大发展的时代。3 安联公司配载与配装的现状3.1 安联公司的概况安联物流服务有限公司于2003年3月1号在湖南省长沙市成立。安联物流公司现有员工近 80多人， 安联公司拥有和整合各种运输车辆 100余台，先进的物流设备40套，仓库、分拨场地2000多平方米。并在湖南省各个城市建立了合作网络公司，与多家企业建立了长期的合作关系。安联物流凭着稳定、可靠、安全的运营网络、科学的资源整合、先进的管理技术，可为各类企业提供全方位的物流服务，我们将一如既往地坚持“以客为本、服务领先” 的经营理念，为客户提供门对门、仓对仓的一站式服务。安联物流有限公司是物流配送、汽车运输、铁路运输、仓储、城际配送于一体，跨区域、网络化、信息化、智能化、具有供应链管理能力的综合性物流公司。图3.1公司业务范围图公司以长株潭地区等湖南省各城市为主干线，同时面向广东、江西等省份，承担整车、零担业务，公司自行开设了30多条长途专线及短途专线。通达全国40多个城市，做到天天发车、准点发车、准点到达、保证低价、全程高速，安全、快速、送货及时。表3-1主要线路运输类型目的地专线运输货盘类型最迟装运日短途运输株洲是公路货盘1湘潭是公路货盘1岳阳否公路货盘1长途运输郴州是公路货盘2韶关是公路货盘3广州是铁路货盘3南昌否公路货盘3多年来，安联在公司的领导下，抢抓机遇、敢想敢为，艰苦创业、与时俱进，以果敢的胆识，通过启动社会资源，与不拘一格提拔人才，成功走出一条具有新邦特色的发展之路。3.2 安联公司的配载与配装现状需要配载与配装的货物品种多样化，但是对于多样化的货物，运输包装件的尺寸是有一定的界限的。运输包装有保障产品的安全，方便储运装卸，加速交接的作用。运输包装件通用尺寸长宽高分别小于3540mm、1600mm、1650mm。装车后运输包装件最高离地不得超过4000mm。用于配送的运输工具中，汽车是最普遍也是最便利的运输工具。在安联公司，汽车种类主要有以下几种：（1）普通货车。按载重量的不同分为轻型货车（2吨以下）、中型货车（28吨之间）、重型货车（8吨以上）；按有无车厢分为平板车、标准挡板车和高档板车。轻型货车主要用于市内运输、集货、配送、宅配运输等，中型货物主要用临近城市与城市之间的运输，重型货物主要用于长途干线的运输。（2）厢式货车。厢式货车具有载货车厢，还具有防雨、隔绝等功能。对于不同的货物，我们需要的包装也不同，而车辆承载也是存在界限的。表3-2 公路运输包装件的尺寸界限车型长宽高最小最大最小最大最小最大中型货车3540795022052490-重型货车4900810022502500-厢式货车375073001920249018032160安联公司实际操作中仍然是根据经验进行配载与配装。我们需要不断完善管理，加强技术的更新，努力提高员工素质，来提升服务质量和运用能力。配载和配装是物流配送中心的重要环节，配送中心开展配送业务，运输成本占配送成本的比重较大，而运输成本与车辆有很大关系，理想的配送运输车辆载重量利用率应该达到较高水平，配送中心在选择运输车辆完成配送业务时，应该充分考虑车辆的容积和载重量，做到满载就是配送配送运输成本的重要途经，但由于实际配送过程中产品繁多，包装形态储运性能不一，在容重方面也有较大差别。3.3 主要问题分析对货物的分拣不够合理1) 外观相近、容易混淆的货物没有分开装载2) 没有注意将散发出异味的货物与具有吸收性的食物混装3) 将渗水性货物与易潮性货物混装在一起了4) 没有能对具有尖角或其他突出物的货物进行处理装载，容易损坏其他货物5) 要注意危险货物要单独装载装车不够合理1) 没有考虑重不压轻，大不压小的原则，造成货物积压损坏2) 没能做到货物堆放后前后、左右、上下重心平衡，容易造成翻车事件3) 应该尽量做到先送后装4) 货物与货物之间、货物与车辆之间应留有空闲并适当衬垫，防止货物损坏5) 应该在门端采取适当的稳固措施，以防开门卸货货物倾倒送货没有达到一定规模1) 货物数量周期性浮动，需要按阶段制定配载计划2) 没有制定有效的运输路线，导致配送时间不够合理3) 当货物品种繁多、不是单一客户的时候，要注意合理配载，以最有效的方法来节约成本车辆的配装空间利用率不够1）由于人工靠经验来进行装载，容易导致装载不够合理2）空驶率较高，不能合理安排好车辆往返的运输任务3.4 选择方法问题的提出采用的是理论与实际相结合的方法。现有的解决相关问题的算法主要有整数规划法、启发式算法、遗传算法、图论发、容重比平衡法、层次分析法等等。本论文选用层次分析法和启发式算法，利用层次分析法解决配载问题，利用启发式算法解决配装问题。4 安联公司配载与配装的优化4.1 安联公司配载的优化4.1.1 模型假设（1）以公路运输为背景，针对一定货物，有多种车型可供选择的优化配载问题。这里就可以看成是一车一货的优化配载问题。若货物批量大于一车的可以拆分为多车，进而转化为一车一货的优化配载问题。（2）设车辆信息集合C=(C1,C2,Cn),货物信息集合G=(G1,G2,Gn),车辆数n和货物批量数m足够大，即有足够的车货源信息，直接保证优化陪载的优势（3）从配送的利益出发，从经济性、快速性、安全性的角度进行系统的设计，达到现代物流多赢目标的实现。4.1.2 制约因素分析公路运输配载的制约因素有很多，从货主、车主、社会三个不同角度所关心的因素进行分析。就某一个配送重心而言，那么货主就是他的客户，车主就是配送中心本身。货主所关心的主要因素有运输价格、运输方向、运输时间、车主信誉度等。车主所关心的主要因素有运输价格、货物类型、运输方向、运输时间、车辆利用率、车辆空驶率。对于社会而言，为提高整体物流运作水平，希望有较高的车辆利用率和较低的车辆空驶率。分析从不同角度所关心的因素，有：（1）货主和车主所关心的因素具有相同性，体现在车辆类型、运输方向和运输时间三个方面。在实际配载过程中，该三个因素必须相互一致，才有配载的可能，从而可以认为该三个因素是配载系统中的基本约束因素，其他因素可以认为是优化目标因素。（2）货主和车主所关心的因素具有对立性，即运输价格和车主信誉度两个因素。作为车主，希望运输价格越高越好；而作为货主，希望运输价格越低越好。由于当前货运市场是买方市场，车多货少，从而多车型优化配载应以车辆为研究对象，向货主提供优化配载服务，运输价格低和车主信誉度的车辆具有竞争优势。（3）社会关系的因素和车主关心的因素具有一致性。提高车辆利用率、降低车辆的空驶率，不仅为车主带来利益，还会提高我国社会物流的运作水平，因此，在优化配载指标中，车辆利用率和车辆空驶率是必须要优化的指标。上述所列的各因素，总结起来无非就是车辆的安全性、经济性、快速性等问题。以这三个为准则，配载主要考虑七个因素，其中车辆种类、运输路线和运到期限为基本约束因素，加上车辆的载重量、容积和车主的报价等，是配载进行的前提条件。车辆投保、出发日期、运费、车辆利用率、空驶率为优化目标因素，就在配载时要优化的指标。4.1.3 模型的建立建模之前要设计一个综合评价的指标。对所有满足货主要求的车辆计算其指标值，从中挑选最优者作为匹配结果。设已知第i车辆的信息Ci有：车辆最低运价CPi、车辆类型CYi、车辆运输方向CDi、车辆最晚运到时间CTi、车辆信誉度（出发日期、车辆投保）CCi、车辆到原目的地距离CSi、车辆最大载重量CWi、车辆最大容积CVi。Ci=（CPi，CYi，CDi，CTi，CCi，CSi，CWi，CVi）T i=1,2,3,n第j批货物的信息Gj有：货物最高愿意运价GPj、货物要求车辆类型GYj、货物最终运送方向GDj、货物最晚运到时间GTj、货物运到终点距离GSj、货物重量GWj、货物容积GVj。Gj=（GPj，GYj，GDj，GTj，GSj，GWj，GVj）T j=1,2,3,n对于一批货物j，求货物i，要使得车辆最安全 Ni为车主i历史配载总次数，Qi则为总配载次数中有投保的次数，二者的比值可以作为车辆安全配载的评价。出发日期最准时 Ni为车主i历史配载总次数，Qi则为总配载次数中按规定时间出发的次数，二者的比值可以作为车辆按时配载的评价。运价最低 车辆利用率最大 空驶率最小 满足用加权平均将模型化为单目标优化问题：其中4.1.4 模型求解层次分析法（AHP）是美国运筹学家沙旦在20世纪70年代提出的。80年代初开始引入我国。AHP法较适合于处理那些难以量化的复杂问题，较好的体现了定性与定量分析结合的思想。在决策过程中，决策者直接参与决策，决策者的定性思维过程被数学化和模型化，并且还有助于保持思想过程的一致性。由于层次分析法具有系统性、灵活性、实用性等特点特别适合于多目标、多层次、多因素的复杂的决策系统决策，近年来已经受到人们越来越多的重视，以被广泛地应用于社会、经济、军事、科技、规划等很多领域的评价、决策、预测、规划等。层次分析法的基本原理是：首先将复杂的问题所涉及的因素分成若干层次，以同一层次分析的各要素按照某一准则进行两两判断，比较其重要性，以此计算个层次要素的权重，最后根据组合权重按最大权重原则确定最优方案。层次分析法的一个基本出发点是：在针对某一目标进行决策时，往往难以把影响目标的各因素做出精确的量化排序，这样往往给决策者带来难度。我们往往对各因素之间的重要程度了然于心，层次分析法就是根据对各因素之间的重要程度进行量化，在通过对量化结果的处理得到各因素对于总目标的影响的一个排序。此排序是以数字的形势表现出来的，它们清晰的现实了对总目标的重要程度，给我们的决策带来了极大的便利。建立层次结构图的方法是先对问题所涉及的因素进行分类，然后构造一个各因素之间相互联结的层次结构图。因素分类：一为目标类A，本问题中的目标就是为货物j寻找车i；二为准则类B，这是衡量目标是否实现的标准，本问题中的车辆安全性、快速性、经济性就是准则类；三为措施类C，是实现目标的方案、手段、方法等，在本问题中的车辆投保、出发日期、运费、车辆利用率、空驶率等即为措施类。那么本问题的层次结构如下图：A为货物j选择车辆iB1安全性B2经济性B3快速性C1空驶率C2里程利用率C3货运费用C4车辆利用率C5服务水平图4.1 层次结构图构造判断矩阵:判断矩阵表示针对上一层中某元素，本层中与之有关的因素之间相对重要性的比较。对公路货物配载中多车型配载问题，下面是根据调研和实测而形成的各判断矩阵。A-B判断矩阵是对于为实现为货物j寻找车i的目标，各准则如安全、经济、快速等方面的重要性比较。表4-1 A-B判断矩阵AB1B2B3B1131/2B21/311/6B3261B1-C判断矩阵是对于安全性准则下各层次的各相关因素指标的重要性比较。表4-2 B1-C判断矩阵B1C1C2C112C21/21B3-C判断矩阵是对于经济性准则下各层次的各相关因素指标的重要性比较。表4-3 B3-C判断矩阵B3C3C4C5C313/22C42/314/3C51/23/41求特征向量：根据A-B判断矩阵计算=1*3*=1.5,= =1.1447=*1*=0.05,= =0.3684=2*6*1=12,= =2.2894对向量=（，）T=(1.1447，0.3684，2.2894）T作正规化处理=1.1447+0.3684+2.2894=3.8025则：W1=0.3010同理：W2=0.0968 W3=0.6032即W=（W1，W2，W3）T=(0.3010，0.0968，0.6032）T为对应判断矩阵的特征向量求最大特征值：CW=则（CW）1=1*0.3010+3*0.0968+*0.6032=0.893同理：（CW）2=0.2975 （CW）3=1.786那么：=+=3类似地，对于B3-C判断矩阵有W=（W1，W2）T=(0.667， 0.333）T2B2-C判断矩阵有W=（W1，W2，W3）T=(0.4416，0.3375，0.2208）T3.044.1.5 一致性检验AHP的有点事将决策者的定性思维过程定量化，在人们对复杂事物的各因素采用两两比较时，不可能做到判断的完全一致性，而存在估计误差，这必然导致特征值与特征向量也有偏差。反映到判断矩阵C上，即要求各元素Cij应满足：对任意的1KN,有Cij=Cik /Cjk,这是对应判断矩阵最大特征值的特征向量为因素权重的前提条件。若判断矩阵C的所有元素Cij皆满足Cij=Cik /Cjk，则称判断矩阵满足完全一致性，而实际情况给出的Cij值和理想值难免有偏差，因此，引进以个参数，用以衡量在什么条件下判断矩阵可以被认为基本上满足一致性。当矩阵不具有完全一致性时，因此在AHP中引入判断矩阵最大特征值以外的其余特征值的负平均值CI作为度量判断矩阵偏离一致性的指标，CI=。当判断矩阵具有一致性时，CI=0，CI值越大，判断矩阵的完全一致性越差，一般只要CI0.1,就认为判断矩阵的一致性可以接受，否则重新进行两两比较。判断矩阵的维数越大，判断的一致性就越差，故应该放宽对高维判断矩阵的一致性的要求。于是引入修正值RI，对CI进行休整，令修正平均值CR=,并取更为合理的CR为衡量判断矩阵一致性的指标。A-B判断矩阵的检验： CI=0所以A-B判断矩阵具有较满意的一致性。同理，对于B1-C判断矩阵有： CI=0所以B1-C判断矩阵具有较满意的一致性。对于B3-C判断矩阵有：（ n=3 RI=0.58） CI=0.02CR=0.0340.1所以B3-C判断矩阵具有较满意的一致性。因此，3个判断矩阵的一致性检验都得到通过。4.1.6 层次总排序与总一致性检验最终判断矩阵如下表：表4-4 A-B判断矩阵AB1B2B3权重B1131/20.301B21/311/60.0968B32610.6032表4-5 B1-C判断矩阵B1C1C2权重C1120.667C21/210.333表4-6 B3-C判断矩阵B3C3C4C5权重C313/220.4416C42/314/30.3375C51/23/410.2208由于3个矩阵都通过了一致性检验，下面进行总排序表4-7 重要性排序表 BCB10.301B20.0968B30.6032最终总权重W重要性排序C10.6670.20073C20.33310.19704C30.44160.26631C40.33750.20352C50.22080.13325下面进行总一致性检验。CI= =0.301*0+0.0968*0+0.6032*0.02=0.012RI= =0.301*0+0.0968*0+0.6032*0.58=0.3498CR=0.0340.1满足总一致性检验4.1.7 配载问题的解决 安联公司有一批日用品需要配送，该批货物的信息表如下所示。现在车库里面四辆不同车型的车可以用来配载，各车的相关信息如下表。现假设该配载问题的层次结构图如上，配载问题的层次总排序如上，求最优配载车辆。表4-8 货物信息表货名质量发货日期运费（元/t）目的地保险日用品84月20日50郴州是表4-9 车库车辆信息表车号车型载重量发货日期运费（元/t）目的地里程利用率保险1EQ14054.2055郴州0.95是2EQ14054.2150郴州0.95否3CA1544.2262郴州0.92是4CA1140104.2055郴州0.97否解 根据每辆车的具体情况，对每一项指标按具体的计划分规则计分，然后将计分乘以权重，最后相加得到一个总分，排名第一的即为最适合配载的车辆。对于该问题，具体的计分规则制定如下：（1）车辆保险C1，采用百分制。投保车辆记100分，未投保车辆记为60分。（2）出发日期C2，采用百分制。通常与发货日期同期为100分，第二天发车可以为60分，第三天发车可记20分，再以后不予考虑。（3）货运费用C3，采用百分制。运费当然越低越好。这里规定与给定运费相差不足5元的，记100分，与给定运费相差超过5元（含5元），不足10元的，记60分，与给定运费相差超过10元的（含10元），不足15元的，记30分，再往后不予考虑。（4）车辆利用率C4，采用百分制。这里车辆的利用率即实载率。实载率就是待装货物重量与车辆额定载重量之比。货物重量车辆额定载重量时：C1=1/实载率*100-20 （5）空驶率C5，采用百分制。规定空驶率C3=100*（1-里程利用率）最后总分=C1*0.2007+C2*0.1970+C3*0.2663+C4*0.2035+C5*0.1332根据上面的记分法则，对上表中的各个车辆进行分别记分。表4-10 记分详表（一）车辆编号C1C2C3C4C5总分11001006042564.962606010042559.1053100203030839.174601006080364.39由表可见，1号车的总分最高，因此选择1号车进行配载，在1号车装载完毕后，还剩下的3t货物在2，3，4号车之间继续选择最优配载车辆。具体情况如下：表4-11 记分详表（二）车辆编号C1C2C3C4C5总分2606010060563.373100203075848.334601006030354.22由表4-10可见，2号车的总分最高，因此剩下的3t货物在2号车进行配载。因此，最优配载方案为：先用1号车配送5t货物，再用2号车配送剩下的3t货物。4.2 安联公司配装的优化4.2.1 模型假设公司现有封闭式货车，其最大载重量是G，最大容积是V，用于配送N种包装不同的货物。货物的重量集为N(g)=（g1,g2,，gn），体积集N(v)= （v1,v2,，vn）,要求合理选择待装的货物以充分利用车辆的容积和载重并使得车厢的空间利用率最大。表4-11 货物的信息货物x1x2xn重量g1g2gn长l1l2l3宽d1d2d3高h1h2h3体积v1v2v3表4-12 车辆的信息最大载重量最大容积车厢长车厢宽车厢高GVLDH（1）假设每种货物的包装都可以测出长、宽、高，那么就可以假定都为矩形包装货物，只是大小尺寸不同。（2）每种包装的货物不超过公路运输包装件的尺寸界限。（3）按矩形体积由大到小的顺序从下到上的装车。（4）货物的包装材料相同，且遵循配载的原则。4.2.2 制约因素分析（1）重量约束：所有装入的货物的重量之和不得超过车辆的载重量giG（2）体积约束：所有货物的体积之和不得超过车辆的最大装载容积viV（3）方向的约束：在装载的过程中，货物的摆放方向受约束，一般货物装载时的方向约束可归纳为三种约束，即任意旋转、水平旋转、不能旋转。（4）货物的位置约束：货物的种类千差万别，包装形状各异，有些货物不可以任意摆放，有些货物不能摆放在其他货物的位置之上。（5）货物的装载顺序：不同的货物在装载中应按不同的优先顺序装载，因此装载顺序相应的不同，先到站的货物要后装。（6）容重比平衡约束：对货物i，起体积vi和重量gi的比值即为容重比ci,同样，货物的容重比c=v/g；比较待装货物的总容重比即C=Vi/Gi与货车的容重比c，如果c=C最好，所以这里要求选择最接近的一个最佳。即选择满足minC-c的组合进行配装。4.2.3 模型的建立目标函数：maxZk=lidihi/LDH其中，Zk表示的空间利用率，这里要求的是车厢的空间利用率最大。li,di,hi分别是第i种包装规格的货物的长、宽、高。L，D，H分别表示车厢的内部尺寸长、宽、高。所装入的货物的总体积与车厢的容积之比即为车厢的空间利用率。这里的空间利用率最大值是1，即Zk14.2.4 约束条件的处理（1）方向约束。引入变量R，代表货物的方向属性。方向约束性R=1，2，3，若R=1,则货物可任意旋转，若R=2则货物可水平旋转，若R=3,则货物不能旋转。（2）货物位置约束。引入变量Pl,代表货物的配置属性。货物的配置位置属性Pl=1，2，3，属性值小的不能摆放在属性值大的货物上面。同种属性的货物之间不受限制。（3）装载顺序约束。引入变量Pr，表示货物的装载顺序属性，装载顺序属性Pr=1，2，3，属性值较大的优先权限低，应先装载。（4）重心平衡约束。货物装载结束后，车厢的重心应在限定的范围内，车厢重心（Xg,Yg,Zg）可用一组空间来约束。即Xg（a1,b1）, Yg（a2,b2）, Zg（a3,b3）,即Xg=mi(xi+li/2)/mi, Yg=mi(yi+di/2)/mi, Zg=mi(zi+hi/2)/mi这里i只表示车厢内的货物数目，m代表i件货物的质量，Xi,Yi,Zi,分别表示代表i件货物的总的在X,Y,Z方向的坐标。装载结束后，如果重心超出约束范围，则这种装载方案被放弃。4.2.5 配装策略三空间分割：当一个货物摆放入车厢后，该车厢被分为三个空间，分别为前空间，边空间和上空间。同理，每个子空间在填充过程中，被摆放入货物后，同样被继续分割为三个空间，而原空间消失。货物在充填剩余逐层摆放，摆放完一层后，对于每一个剩余空间，选用满足条件的使得剩余空间的利用率为最高的货物进行填充，在货物摆放时，货物的边与车厢的边应相平行，优先考虑长边，选择货物的哪一方与车厢空间的边平行，要依赖于货物的方向约束，即R=1时，max(li,di,hi)max(L,D)，货物R=2，max(li,di)max(L,H)，货物R=3，liL,diD,hiH。正上方剩余空间前方剩余空间右方剩余空间图4.2 当前货物对应的三个剩余空间空间整合：在空间不断分割的过程中，必须对每个新产生的分支空间是否能与相邻的空间合并进行判断，对于可以合并的空间先合并，然后再摆入货物。假定货物之间高度相同，则在下一个摆入之前，必须将两个物品的上空间进行合并。4.2.6 启发式算法求解下面构造启发式算法解决货物配装问题的程序结构图根据货物的包装规则选择车辆按优先顺序Pr的大小升序摆放货物计算车的容重比和待装货物总的容重比接近者进行装载是Pr相同的货物按体积大小降序排序并保存在序列Gi中按序列中的顺序在Gi中选择货物按策略装载判断重心是否超出规定区间否保留方案，结束图4.3 货物配装问题的程序结构图4.2.7 模型验证现以公司日常配载货物进行货物数据来验证。表4-13 车辆信息表车辆种类车厢长（mm）车厢宽（mm）车厢高（mm）最大容积（m3）最大载重（kg）厢式400025002500256000表4-14 货物信息表货物名称数量（箱）长宽高重量（kg）装载顺序限制配置位置层限方向约束纯净水400400450200350021122牛奶400300300250200012121解 计算空间利用率Zk=23.24/25=92.96%本例题是在完成了程序框图里面的前两项的情况下给出的即按照货物的包装规格及个数选择车型这一步已经完成，另外车的容重比与所有特装货物的容重比也已经是经过计算后安排的本例题中的数据，其中车的容重比：C=V/G=25/6=4.17(m3/吨)总的待装货物的容重比：C=xivi/xigi=23.24/5.5=4.23(m3/吨)比较C与c可以看出，两者相差得很小，这说明在选择数据之前笔者已经选择了相差最小的一组货物。所以本例题省去了两个步骤。那么，在本例题中主要求解的就是如何摆放货物的问题，根据启发式算法的约束条件及装载策略逐步进行。详细情况如下：由表中信息可知，纯净水的装载顺序是2，牛奶的装载顺序是1，根据装载顺序约束Pr大优先权低，应该先装载。所以可以判断要先装纯净水，而牛奶要放在牛奶的上面。 从表中的方向约束可知，纯净水的方向约束是R水=2，牛奶的方向约束是R奶=1，所以纯净水只能水平旋转，而牛奶不可以任意旋转。 从表中的配置位置约束可知，的配置位置属性值小于牛奶，所以纯净水只能放下牛奶的下面。 然后按具体的装载策略进行装填。进行三空间分割，具体分割情况如下： 坐标原点定在车厢的后面左侧的一角，然后车厢的长度方向为X轴，宽度方向为Y轴，高度方向为Z轴。先摆入一箱纯净水，那么这箱纯净水的放置要满足空间分割时的具体策略，即：R=2时，max(li,di)max(L,H),此时可以计算： 在车长方向，即X轴可以摆放纯净水的箱数为4000/400=10箱在车宽方向，即Y轴可以摆放纯净水的箱数为2500/450=5箱,剩余宽度250mm在车高方向，即Z轴可以摆放纯净水的箱数为400/（10*5）=8层。刚好摆放好。摆放好纯净水之后，要摆放牛奶。牛奶的R=1,此时max(li,di,hi)max(L,D)在车长方向，即X轴可以摆放牛奶的箱数为4000/300=13箱，剩余宽度100mm在车宽方向，即Y轴可以摆放纯净水的箱数为2500/300=8箱,剩余宽度100mm第九层装入的牛奶的箱数为13*8=104箱在车高方向，即Z轴可以摆放纯净水的箱数为400/104=3层又88箱。至此，货物装填完毕。装填完毕后要对重心平衡进行验证。首先计算车的几何中心：其几何中心的坐标为（2000，1250，1250），再计算所装货物的重心。利用前面的重心约束给出的公式，计算出的货物的重心在规定区间内，所以可以装载。本题