基于整数线性规划方法的集装箱装载布局优化问题研究

文献：基于整数线性规划方法的集装箱装载布局优化问题研究①文献的研究背景经济学家和企业界将现代物流称之为“第三利润源泉”，而现代物流对我国经济发展的影响越来越大，扮演着越来越重要的角色。经济全球化是当今世界经济发展的客观进程，经济一体化是实现经济全球化这一目标必经的历史阶段。几十年以来，随着经济一体化进程的推进，贸易全球化以及国际航运业的快速发展，现代物流水平已然成为影响企业竞争力的关键因素，我国的物流行业面临着前所未有的发展机遇。集装箱是现代物流中最常用的运输方式之一，被广泛地应用在铁路运输，轮船装载，给运输业带来了新的变革，具有显而易见的优越性。集装箱运输(containertransport)，是指以集装箱这种大型容器为载体，将货物集合组装成集装单元，以便在现代流通领域内运用大型装卸机械和大型载运车辆进行装卸、搬运作业和完成运输任务，从而更好地实现货物“门到门”运输的一种新型、高效率和高效益的运输方式。我国集装箱运输业欣欣向荣。十六大以来，随着国际化、工业化、城镇化进程的深入，我国对外贸易交流日益频繁，沿海港口作为我国对外物资交流的重要窗口，发挥了重要的支撑保障作用。目前，我国己经成为世界港口大国，全国港口货物吞吐量和集装箱吞吐量连续九年位居世界第一位。2011年下半年我国港口经济保持良好发展态势,港航生产继续保持较快增长，并逐步趋于平稳。2011年，沿海港口完成货物吞吐量73.3亿吨，比2001年的16亿吨净增约57.3亿吨，年均增量约5.7亿吨，年均增长16.4%。煤炭、原油、铁矿石和集装箱四大货类的吞吐量分别达到17.1亿吨、4亿吨、11.5亿吨和1.6亿吨，分别是2001年的4.2倍、2.5倍、7.4倍和6.1倍。在全球排名前20名的亿吨大港中，我国占了12个。目前，大陆有8个港口进入世界港口吞吐量的前十位，5个港口进入世界港口集装箱吞吐量的前十位，上海港货物吞吐量、集装箱吞吐量均居世界第一。集装箱吞吐量占全球港口集装箱总吞吐量的近1/4。公路、航空、铁路、水运、管道是五种主要的现代化运输方式。这五种不同的运输方式使用了不同的运输工具、不同的运输设备、线路，水运中最常使用的现代化运输工具之一——集装箱，历经了一个漫长的发展过程，从初始阶段经过发展阶段，最终达到成熟阶段，其全面应用时间还不长，存在利用率不高的问题。据调查，一个20英尺集装箱，容积是33m^3，一般可装载的容积为25m^3，集装箱利用率约为75%；—个40英尺集装箱，容积是67m^3、一般装55m^3，集装箱利用率约为82%。而在某些情况下，又会存在包装箱本身装载不饱满，那就会使集装箱实际利用率更低，造成很大的浪费，这是当下运输的现状。因此，如何能最大限度提高集装箱管理水平，提高集装箱利用率，已成为当务之急。②文献阐述的主要内容集装箱装载问题具有现实意义。本文主要针对单个集装箱、弱异类货物的问题，做了详细分析和研究。目前，求解集装箱问题常用的方法是启发式算法，通过在解的空间域内不断搜索寻找最优解，启发式算法存在局限性。集装箱装载问题属于组合优化问题，用整数线性规划求解在理论上是可行的，例如生产规划、调度、路由、投资问题以及一些复杂的组合优化问题都可以用整数线性规划方法求解。整数线性规划方法可以将数值约束与目标结合应用到规划领域中。本文基于装箱问题的实际约束条件，建立装箱问题的数学模型，增强装箱方案的实用性，尝试采用整数线性规划方法求解集装箱装载问题，通过布局约束转换，将装箱模型进行线性化处理，求解可行域内的最优解。对于模型求解，本文采用CPLEX优化软件，其提供了解决实际的大型优化问题所需的能力，能够以最快的速度最可靠地实现基本算法以解决困难的数学优化问题，为有限时间内得到可行域内的最优解提供了可能。本文的另一个重要工作是集装箱装载布局优化仿真平台的设计及构建。经过布局优化计算，获得了不同类型、同一类型货物在集装箱内的空间位置及方向约束，对于计算规模数量较大的箱体而言，一方面需要验证装箱货物在理论指导的前提下布局的有效性，如避免悬置、重叠现象；另一方面，也需要将最终结果给生产现场以实际指导，辅助工人又快又好的完成整个装载过程。本文所设计的布局优化仿真实验平台，具有开放式数据接口。不仅适用本文所提出的方法，也适用于其他优化方法所获得的实验结果。文献内容安排如下：第一章绪论论述本文的研究背景、意义及集装箱装载布局优化领域的国内外研究状况，进一步概述装箱问题的研究方法及其存在问题，为本文的研究工作做好铺垫。第二章集装箱装载布局优化问题综述介绍了集装箱装载问题，并重点分析了装箱问题的一般数学模型以及在装箱过程中涉及的约束条件，并按照不同的标准別装箱问题进行分类。第三章集装箱装载布局优化问题的算法综述归纳总结现有的解决集装箱装载问题的常用算法，介绍了各个算法的相关知识，并介绍了这些算法的研究与应用现状。第四章整数线性规划方法求解集装箱问题基于前二章对集装箱装载布局优化问题的充分了解以及对己有的求解方法的分析。本章通过了解问题具有的约束及使用资源的性质，进而建立装箱问题的数学模型，包括设计己知变量、决策变量，实现各种约束的表达以及线性化处理等，最终应用CPLEX进行程序实现。第五章集装箱装载布局优化仿真实现搭建仿真平台，仿真实现装箱过程，给出货物装载效果图，采用不同算例进行性能测试。第六章总结与展望总结本文所做的重点工作，对今后的研究工作进行展望。③文献中运用的模型或方法文献采用整数线性规划方法求解集装箱装载问题，探索集装箱装载问题的数学本质，将实际问题转化为数学模型，将目标函数、约束条件线性化，然后通过数学方法，利用优化软件IBMILOGCPLEXOptimizationStudio(CPLEX)进行求解。整数线性规划解决组合优化问题在理论上足可行的，例如生产规划、调度、路由、投资问题以及一些复杂的组合优化问题都可以用整数线性规划方法求解。用整数线性规划求解组合优化问题的优势主要有以下几点：第一，整数线性规划方法能提供一种自然的方法；第二，它允许将数值约束与目标相结合，应用到规划领域中。整数线性规划方法的描述：本文采用基于整数线性规划方法求解集装箱装载问题，因此对于数学模型首先需要做线性化处理。为了便于计算与求解，我们对问题做如下假设：①货物的尺寸是整数；②货物只可以沿着集装箱的坐标轴放置，即垂直放置或是水平放置；③采用的坐标系为三维笛卡尔坐标系，集装箱的长、宽、高分别对应笛卡尔坐标系的X、Y、Z轴方向。④(x，y，z)货物在集装箱的左前下角坐标点；⑤在装载过程中，放入集装箱的货物可以向下、向前、向左移动，直到它的底面、前面、左面与其它货物或是集装箱相邻；⑥货物到达同一目的地；⑦可忽略货物本身的挤压变形；⑧货物的重心为其几何中心。集装箱装载问题的数学模型描述如下：(1)l，w，h，g分别表示第i(i=1,……m)类货物的长度、宽度、高度、重量，L，W，H，G分别表示集装箱的长度、宽度、高度、最大承载重量。本文装箱问题的目标函数为最大化集装箱的空间利用率，由于集装箱的容积是固定的，所以最大化集装箱空间利用率，即最大化装入货物的体积，如公式4.1所示：(2)（x，y，z）满足以下集合：(3)集装箱装载容积的约束，装入货物的总体积要小于或等干集装箱的最大装载容积，如公式4.5所示：(4)集装箱的承重能力的约朿，装入货物的总重量不能超过集装箱的最大承载重量，如公式4.6：本文将利用CPLEX进行求解，首先对集装箱装载问题的数学模型做线性化处理，引进如下变量：（iiizyx,,）：货物的左后下角坐标；（iiiihwllZYZX,,,）：二进制变量，判断货物i是如何平行与集装箱坐标轴摆放的，可以决定货物/的放置方向，长度方向。若平行于x轴，则ilX=1，否则尤ilX=0；长度方向若平行于Z轴，则ilZ=1，否则ilZ=0；宽度方向若平行Y轴,则iwY=1，否则iwY=0；高度方向若平行于z轴，则ihZ=1，否则ihZ=0。（ijijijcba,,）：二进制变量，定义货物i与货物j的相对摆放位置，若货物i在货物j的前面、右面或是上面，则变量分别为1，否则为0；模型线性化后的约束条件如下：公式(4.12)-(4.14)保证货物i和货物j彼此不重叠。公式(4.15)-(4.17)iiiihwllZYZX,,,用来计算货物的长、宽、高与集装箱的x、yz轴的相对对位置夭系，保证了货物不超过集装箱。(4.18)限制了两个货物i与j的相对位置。(4.19)-(4.26)保证了决定货物位置的二进制变量可以恰当取值以反应实际货物的位置。要求：参考第一题文献中的模型或方法试给出一个研究初步方案（三级研究提纲）题目：基于整数规划的轿车物流配载优化的研究摘要第一章绪论1.1课题研究背景、目的及意义1.1.1研究背景1.1.2目的及意义1.2国内外研究现状1.2.1配载优化问题简介1.2.2配载优化的相关问题1.2.3国内外配载优化的研究现状1.2.3.1规则货物装载问题1.2.3.2不规则货物装载问题1.2.3.3轿车物流配载优化问题1.3目前研究存在的问题1.4本文的研究目标和研究内容1.4.1主要研究目标1.4.2主要研究内容第二章轿运车配载优化系统的总体方案设计2.1引言2.2系统设计需求分析2.3系统解决方案分析2.3.1配载模型描述2.3.2解决方案选取2.3.3系统功能框图2.4系统开发环境分析2.5本章小结第三章基于整数规划的轿运车最大运能优化的研究3.1引言3.2商品车和轿运车的建模3.2.1商品车建模方法与实现3.2.2轿运车建模方法与实现3.3轿运车最大运能优化3.3.1整数规划算法3.3.2上层装载面最大运能优化3.3.3下层装载面最大运能优化3.3.4商品车坐标的确定3.4算法有效性分析与验证3.4.1装载实例分析3.4.2算法的精度与速度3.5本章小结第四章系统应用实例第五章全文总结与展望