进出口公司的货物装运策略
摘要
本文针对进出口公司经常需要将销售的货物通过货运飞机进行运输的经济效益问题，将货物装运问题等价为空间排样问题，以空间间隙为目标函数，以货物载重和体积为约束变量，建立线性规划和优化模型进行求解，最终给出相应的装运策略。
针对问题1，首先根据各货物的前50个历史需求量求出相应货物的平均值，并按照该平均值来组织货源。货物量以及货物体积、装载容量、运输及销售价格均已知，以货物载重和体积作为约束变量，以空间间隙作为目标函数，建立整数线性规划模型进行求解出，初步确定其装运方案，为达到方案的有效性，通过反向检验确定我们的模型是否合理，最终确定其装运方案。
针对问题2，根据问题一的预处理的数据信息将货物分为需集装箱类和非需集装箱类，装入集装箱的货物需要考虑空间利用率最大，通过直接装入，按照排样寻优算法但对一个集装箱可以装入的最多货物最终所留空隙进行迭代，最终比较出该四种需要装入集装箱的货物的所在最佳集装箱，及空间利用率最大；最后通过数学模型计算得出四种货物所需集装箱的个数，然后转换为单纯的货物装运问题，建立空间利用率最高的单目标优化模型最后得出具体的装运方案：采用小飞机装运，运输货物共需367架次。
针对问题3，集装箱不留空隙意味着剩余的空间可以通过2m3 以上的货物进行填充，这样会占用飞机的重量，会增加飞机的货运次数，但成本较大；故改变装运货物方案思想，结合实际经济效益，将目标函数可设为集装箱的利用率，飞机的空间利用率，飞机的架次/总利润。
针对问题4，针对货物销售量随机现象，采用马尔科夫模型描述此类随机现象，并对下一周期的货物量进行预测，通过问题1,问题2得到对装运方案的最大约束变量是载重约束，故对货仓与货物体积这一方面的约束不再考虑，进一步优化模型，最终在可靠性为95%的前提下，计算出最大的利润值为：8709150元，飞机总架次为：87架次。
针对问题5，沿用问题4的求解思路和模型算法，将可靠性改为75%，最终对下一个周期的销售量进行预测，求解出最大利润为：10781740元；飞机总架次108架。
关键词：整数线性规划 随机模拟 启发式算法 单目优化模型 马尔科夫模型
一、问题的重述
1问题的背景
随着经济的快速发展和社会的不断进步，国际贸易在“一带一路”的时代背景下稳固发展。在此过程中，贸易经济为航空运输业注入了新鲜的血液，在制造业和电商产品环境的孕育下，越来越多的公司迫切需要一个高效率、低成本的货物装运策略来助力公司的经济增长。航空运输行业现状分析，2017-2020年8月中国中部地区民航货邮吞吐量占比稳步增长，而其他地区波动变化，2019年中部地区民航货邮吞吐量达到占比124.7万吨，占比7.3%;到2020年1-8月份中部地区民航货邮吞吐量达到占比77.7万吨，占比8.0%，同比增长2.4%，是国内唯一实现民航货邮吞吐量正增长的区域。2014-2019年中国民航运输总周转量呈逐年增长态势，2019年中国民航运输总周转量1293.2亿吨公里，比上年增加86.8亿吨公里;尽管2020年因疫情影响，民航运输总周转量有所下降，但航空运输行业现状分析，2020年上半年中国民航运输总周转量仍有319.2亿吨公里。
全球航空货运在2010-2012年处于徘徊状态，从2013年起有所起色，到2019年货运量在近十年内首次出现负增长，从2018年的6330万吨减少至2019年的6130万吨，同比下降3.2%，不断加剧的贸易摩擦是导致全球航空货运量大幅减少的主要原因。
图 1 2010-2019年全球航空货物运输量（单位：万吨，%）
尽管贸易摩擦会影响全球形式，但随着中国的“一带一路”战略性的部署，我国的航空运输的发展前景十分的可观，我们面临的既是机遇同时也是挑战。无论是航空货运公司还是独立企业，在货运装运方面都进行了深入的探索和研究，旨在通过合理高效的装运策略来减少运输所产生的损耗和成本，最终达到利润最大化。不仅仅是商业价值的体现，同时也是国家战略的深入部署。最为体现的就是对外贸易重要组成部分——中欧班列，在“一带一路”的建设和推进下，基本形成了布局合理、设施完善、运量稳定、便捷高效、安全畅通的综合服务体系，在国家的大力扶持和建设下，航运体系不断的在完善，但是仍然存在一些问题，资源利用率低、运输成本超出预期、货物装运策略不够合理等等，因此如何确定航运货物的装运策略对运输的效率和货物的净利润有很大的提升和改变。
图 2 2019年中国航空货运行业运力结构分布情况
2问题的提出
现有货运飞机大、中、小三种类型，飞机均有前、中、后三个货舱，每个货仓给定了容积和载重的约束限制。货物可以单装也可以多种混装在一个货仓。为保证飞机正常平稳运行，实际载重需要不得大于理论载重，详细数据见附件1。货物类型有10种，均为长方体，已知货物尺寸、体积（立方米）、重量（吨）、运输单价。进出口公司为了精确营销，收集了前50个周期的每种货物的销售量以及下一个周期的销售价格。下一个周期货物的销售量是随机的，但销售价格是已知的，货物装运成本为销售价格的40%；若货物在规定周期不能销售，只能按照销售价的30%清仓甩卖。数据见附件2。
请结合附件的数据，建立数学模型，解决下列问题：
（1） 假定只有大、中、小三种类型的货运飞机各一架，货物可以直接装入货仓，并按照前50个周期销售量的均值来组织货源。问如何装运，可以使得货运飞机尽量不留空隙？
（2） 继续按照前50个周期销售量的均值来组织货源，要求体积在2m3以下的货物必须用集装箱装载。集装箱为长方体，厚度为5厘米，数据见附件3。集装箱尽量不留空隙，货运飞机尽量不留空隙，基于这种思路，请分析确定使用哪种机型最为合适，至少需要多少架次，并给出各架次的具体装运方案。
（3） 接第2问，进出口公司总觉得以集装箱尽量不留空隙、货运飞机尽量不留空隙作为为货物装运的思路影响了他们的经济效益。请你帮助他们调整一下装运方案，以满足他们的经济期望，并计算最佳利润。
（4） 市场对产品的需求是不确定的，在一个周期内组织多少货源是有风险的。为安全起见，进出口公司希望能够得到在可靠性为95%下的最大利润值，以及为实现这个利润值应该实施的货运装运策略。请帮助其实现他们的目标。
（5） 如果将可靠性95%改为70%，最大利润值和装运策略将如何改变？
3目的及意义
航空公司从事航空货物运输时，由于收益取决于货运量的多少，因此如何在一定货运量的情况下减少货物运输成本，或者如何在一定数量的装载设备情况下装入更多的货物是迫切需要关注的问题。全球经济的快速发展，促使了贸易的需求量增长，同时带动世界航空货物运输量以更快的速度增加，但航空货物运输量的增加并不代表公司利润的上涨。伴随激烈的市场竞争，货主需要不断减少运输成本，他们致力于花费更少的钱获得更大的收益。[1] 目前，航空公司装载人员主要依靠操作习惯和经验来确定货物的装载方式，缺乏一定的科学性，装载方式比较随意。而且从整个航空物流系统来看，货物装载的环节不仅影响货运的成本，还会影响系统后续的作业。特别是需要的中转货物，最初的装载方式决定了中转机场的操作，若同一集装器的货物目的地不相同，就必须拆箱、理货再重装，直接影响了货运的效率和成本。航空货运装载过程涉及到多目标、多约束条件，计算量较大，是一个具有跨学科、交叉性、综合性和边缘性的研究课题，由于该问题是一个带有复杂约束的多目标组合优化问题，涉及了众多的模糊和随机因素，所以迄今还没有满意的有效方法解决航空货物装载的问题。飞机货舱的利用率、货运的装载问题。飞机货舱的利用率、货运的效率与集装器的使用、货物的装载问题密切相关，因此对航空货运装载问题作进一步的研究有着重要的理论价值和现实意义。[1]
二、符号说明
三、模型假设
由于货物类型众多，为保证航空货运的安全性，航空货物运输条件、货物类型、飞机设备，现作以下假设：
货物可以任意摆放和混装；
不考虑重心约束和方向约束；
货物之间不存在镶嵌、包含现象；
货物均为长方体，且质量分布均匀；
用泡沫和棉花填充集装箱剩下的空隙；
不考虑在运输过程中集装箱在飞机货仓内的颠簸所造成的安全问题；
货物属于普通货物，包装好后货物外形为矩形体，不考虑形状对货运影响；
四、建模准备与问题分析
4.1 线性整数规划
整数规划是对全部或部分决策变量为整数的最优化问题的模型、算法及运筹学的研究。整数规划问题是带整数变量的最优化问题，同时也属于线性整数规划，即在受约束或不等式的条件下最大化或者最小化一个全部或者部分变量的为整数的最优化问题。[2]本文基于货物装运实际问题将其转换为空间排样问题，最终转化为数学问题，建立数学模型进行求解。
在线性规划问题中，有些最优解可能是分数或小数，但对于某些具体问题，常要求某些变量的解必须是整数。例如，当变量代表的是机器的台数，工作的人数或装货的车数等。为了满足整数的要求，初看起来似乎只要把已得的非整数解四舍五入就可以了。但是这样的未必是最优解，所以应该有特殊的方法来求解整数规划。在整数规划中，如果所有变量都限制为整数，则称为纯整数规划；如果仅一部分变量限制为整数，则称为混合整数规划。
4.2 三维空间分割启发式算法
三维装箱问题本身具有一定的复杂性, 同时为了满足实际应用中的需求, 必须使用启发式算法来生成有效的装载方案。优秀的启发式算法应具备在较短的时间内生成高质量的解, 同时还应具有适应不同需求的灵活性。[3] 针对我们的实际装运方案我们需要利用三维空间分割启发式算法进行装运方案的制定。
启发式算法的内容分为定序规则、定位规则、空间分割规则、空间合并规则，使得货物的装运过程有序可控。
4.3 混合遗传模拟退火算法
根据相关研究, 遗传算法在求解NP-hard问题中有着较好的全局搜索能力, 但在局部搜索与收敛速度方面效果不是很明显, 而模拟退火算法则在局部搜索中展现出较好的能力。本文采用二者结合的方法来解决三维装箱问题, 并且算法中融入了最优解保存策略来提高性能。
4.4 马尔科夫模型
一个马尔科夫过程就是指过程中的每个状态的转移只依赖于之前的 n个状态，这个过程被称为 n阶马尔科夫模型，其中 n是影响转移状态的数目。利用该模型来解决我们问题4和问题5的货物量需求的不确定性，最终建立我们下一个周期的货物量预测模型，引入我们的约束变量，寻找最优解及合理方案。
五、问题解决与模型求解
5.1 问题1
按照前50个周期的货物平均值来组织货源，将货物直接装入飞机货仓，不考虑货物的分类情况，故可以将一个货物单独装入一个货仓或者混装在同一个飞机货仓当中，最后如何装运使得空间利用率最大且符合实际需求和经济价值效应。
通过对飞机和货物数据进行比对，我们发现飞机机舱的载重限制相比较于其体积限制要更加严格，所以载重对货物运输的数量影响较大。我们以空隙最小为目标函数，以载重约束和体积约束为主建立整数规划模型，并使用MATLAB求解出装运货物的大致数量。之后，再通过反向检验来判断我们的模型是否合理，如果合理，则确定其装运方案；如果不合理，则进一步采取逐步调整，调整个别货物的装配情况以达到在满足一定的条件下，该装运方案使得空隙最小。
5.2 问题1模型求解
首先我们根据附件2所提供的数据信息，根据题目所给定的不变参数，分别求出前50个周期的货物平均销售量、货物的体积、成本价、清仓价，最后将所有的已知信息和求算数据汇总在下表中：
表 1 货物数据信息表
5.2.1 线性整数规划模型建立
以飞机的最大载重和容积为约束变量，我们首先规定大飞机的前、中、后仓，分别是1号、2号、3号仓；中飞机的前、中、后仓，分别是4号、5号、6号仓；小飞机的前、中、后仓，分别是7号、8号、9号仓；每种货物在各货舱的数量。
决策变量：
每种货物在各货仓中的数量用表示第种货物在第号舱的数量；=1,2,3,4,5,6,7,8,9,10表示HW1……HW10货物类别，=1,2,3,4,5,6,7,8,9表示1号舱…..9号舱属性。
由于数量为非负整数，所以给定。
目标函数：使用货仓空间总间隙最小化作为目标函数，转换为空间体积最大化：假定每个货仓的货物数量已知为，已知每个货物的体积为，以大飞机为例，最后得出空间最大的目标函数如下：
根据实际情况我们得知载重约束是首当其冲的；但是我们必须要考虑前后舱的载重比例约束，这样才能使得我们的飞机在运输过程中，安全性能得到保障，前后舱的载重比例应该趋近，如此才是符合我们的运输规则和安全保障。
结果显示发现我们的小型飞机的空间利用率比较高，大于其他两架飞机，而大飞机的实际载重高于其他两架机型。
通过反向检验判断是否需要调整我们的方案，经检验发现我们的方案合理，且体积限制非常小，且满足我们的摆放的种类较多，故确定上述方案为我们的最终货物装运方案。
5.3 问题2解决
5.3.1 集装箱的选取
Step1：数据预处理
首先，根据货物的尺寸信息，再次计算出各货物的体积，并将货物分为需集装箱类和非需集装箱类，货物具体体积信息如下表所示：
表 3货物体积表
由表 3 可知，体积在 2m3以下的货物共有 4 种，分别是 HW2，HW6，HW7，HW10，这四种货物将用集装箱进行装载。本题货物的销售量为前 50个周期货物销售量的平均值，前 50个周期货物的销售量已知，故本次所需货物量如表 3 所示：
表 4 问题二所需装运的货物量
Step2:集装箱利用率的计算由于体积在 2m3以下的货物要被放进集装箱中，为了减少集装箱空间的间隙，
将 HW2，HW6，HW7，HW10 依次放入 7 种集装箱，计算相关的集装箱空间利用率，为 4 种货物选择依次最佳的集装箱进行装载，具体的利用率情况如表 4 所示：
由表 4 可知，HW2 用集装箱 Y4 进行装运，HW6、HW7 和 HW10 都用集装箱 Y7 进行装运。
Step3：集装箱所需个数的计算
已知 HW2，HW6，HW7，HW10 所需的货物数量和其相对应的集装箱，由于集装箱可以重复使用，所以下面计算具体需要使用的集装箱次数，计算结果如图 5 所示：
表 6 货物所需集装箱个数
因此，集装箱的选择已确定，可将集装箱等同于货物，将问题二简化为单纯的货物装运问题。
5.3.2 空间利用率最高的单目标优化模型的建立
由问题一的三种飞机的各机舱空间利用率结果计算比较来看，小型飞机的空间利用率明显比大型和中型高很多，所以，本题直接确定最佳机型为小型飞机，将集装箱等同于货物，进行货物的装运。下面开始模型的建立：
