考虑货物分拆装卸的装箱策略研究
开篇：润墨网以专业的文秘视角，为您筛选了一篇考虑货物分拆装卸的装箱策略研究范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！
[摘 要] 针对一类需要进行货物往返运输的运输问题，建立了货物装箱模型，并设计了一种货物的拆分策略。货物装箱模型考虑了中心站点货物数量和各个配送站点货物数量，使得运输车辆可以进行往返运输。货物的拆分策略对数量比较多的货物进行拆分，保证了货物装入运输车辆的可运输性和其他运输车辆的满载性。最后对所提出的模型和策略进行了实验。
doi ： 10 . 3969 / j . issn . 1673 - 0194 . 2016. 23. 082
[中图分类号] F511.41 [文献标识码] A [文章编号] 1673 - 0194（2016）23- 0153- 04
0 引 言
装箱问题（Bin Packing Problem）广泛存在于服务业、运输工业、建筑工业、金属制造业等领域，是许多重要实际优化问题的基础。在实际的货物运输过程中，对于货物如何在运输车辆上分配装载，装箱问题得到了广泛的应用。
装箱问题属于典型的NP难问题，难以精确求解，只能得到问题的近似解，在某些极端情况下，结果很不理想。在实际的货物装载过程中，很多货物的总量由于超出了运输工具的容量或者本身数量较大，因此无法直接使用装箱问题的模型。
本文针对现有的货物装配问题的实际情况，结合装箱问题模型的思想，提出一种考虑货物装卸的货物分拆装箱策略。该装箱策略首先考虑运输车辆在每个站点卸货和装货的总运量来确定运输车辆的数量，然后通过货物组合模型对货物进行装箱分配，再对数量较大的货物进行拆分，使得车辆能够满载运输。
1 问题描述
本文研究的运输系统如下：在整个运输系统中，有一个中心站点和若干配送站点。中心站点可以是仓库或者加工中心，对各种货物进行储存或者加工操作。配送站点是提供服务的地点，货物从中心站点被运送到各个配送站点。在每个配送站点都有需要运回中心站点的货物，每辆车在该站点将需要运回中心站点的货物装车后，去往下一个配送点，最后所有的配送站点都经过后，运输车辆返回中心站点。
运输货物的车辆都集中停放在中心站点。每次运输过程中，管理者通过管理信息系统收集中心站点中对应每个配送站的货物的数据，以及每个配送站中货物的数据。根据这些数据，管理者制定车辆装配货物的方案以及每个车辆经过的配送站点。
为了节约成本，运输车辆每次运输要求完成一次性运送和装卸任务，即运输车辆从中心站点出发，装上货物后，一次性的经过货物需要卸载的配送站点且只经过一次。每经过一个配送站点的时候，运输车辆首先在该配送站点卸下该站点的货物，然后装上该配送站点需要运回中心站点的货物。然后，运输车辆去往下个配送站点。全都结束后，运输车辆返回中心站点。
这种衣物配送计划需要考虑需要卸下的货物和需要装载的衣物之间的关系，能够是的使得货物卸载后在运输车辆上有足够的空间来盛放后来装载上来的货物。
2 模型
2.1 符号
模型中各个符号说明如下：
CSi，配送站点i；
CsiNum，配送站点i中存放的待运输的货物数量；
WS，中心站点；
WsiNum，中心站点WS中对应于配送站点i的待运输货物数量；
VC，运输车辆能够盛装的货物的最大数量；
TSnum，WS的货物数量总和；
TFnum，CSi的货物数量总和。
2.2 货物装箱模型
对于N个配送站，x表示模型的一组解，其中X=（X1，X2，…，XN）。在这里xi表示配送站点i被选中的状态。在模型中，Xi表示运输车辆是否经过CSi，即是否盛装该配送站点的货物。如果运输车辆经过CSi则Xi=1；不经过CSi则Xi=0。
当Xi=1时，如果运输车辆经过CSi，则说明在WS中如果有对应CSi的待运送货物，则需要将其装上运输车辆，若没有则不装载；同时，在CSi中如果有待运输的货物，则需要将其送上运输车辆，若没有则不装载。
对于每次装载运输车上的货物的数量总和都不能超过运输车辆容量。因此从中心站点WS运出货物的总和不能超过运输车辆容量；从各个站点CSi运回中心站点WS货物的总和不能超过运输车辆容量
模型的目标函数根据实际的货物数量决定。如果由于WS货物数量多于CSi的货物数量，则目标函数为WS货物数量优先满载；相反如果CSi的货物数量多于WS货物数量，则目标函数为CSi货物数量优先满载。下文表示为CSi货物数量优先满载。
考虑货物装卸的货物分拆装箱策略中的一个重要问题是处理WS中WsiNum和每个CSi中CsiNum之间的关系。
对于运输车辆的运输方案来说，为了保证运输车辆一次性经过每个CSi，需要在CSi先卸货，同时在该CSi装货，需要考虑WsiNum和CsiNum之间的关系：
（1）当一个车辆所运输的所有CSi的货物，有WsiNum>CsiNum，则表示卸下的货物比装上的货物多，不会发生车上剩余空间无法容纳需装载货物的情况；
（3）当一个车辆所运输的所有CSi的货物，既有WsiNumCsiNum，则需要首先对WsiNum>CsiNum的进行货物的装卸，然后再对WsiNum
2.3 货物的拆分策略
首先根据待运货物的情况确定最少的运输车辆数量Max{「TSnum/VC，TFnum/VC}。然后通过分组模型（2.2）来获得分组结果，如果分组的数量与最少的运输车辆数量相同，则分组结束；否则，则需要对某些待送数量较多的站点的货物拆分到其他车辆上，使得最后的车辆总数等于最少的运输车辆数量。
因为待送货物数量较多的站点不容易与其他站点组合，所以从未被装车的货物中选择数量最多的货物进行拆分。
分组后待送货物的总数如果等于车辆容量，则该组分配完毕。如果分组后待送货物的总数如果小于车辆容量，则可以从未被装车的货物中选择数量最多的货物进行拆分，使得车辆运输满负荷。
3 实验
本实验说明2.2中所提出的模型和算法的效果，模型程序的实现工具是Matlab。程序运行环境为Intel Core2 Duo 2.2 GHz/2 GB RAM/Windows XP。实验所需要数据为随机产生如表1所示。
基于实验数据表1，通过模型2.2计算，实验结果如表2所示。前面进行装车的货物，由于存在工作站货物数量=0或者衣物收集站货物数量=0的情况，所以在组合的时候，可以能够容纳较多数量的CSi。 从第3组开始后面的组合时，由于没有了上述前提，因此每个车辆所盛装的CSi的数量逐渐减少。
4 结 语
本文建立了货物装箱模型，并设计了一种货物的拆分策略。货物装箱模型考虑了中心站点货物数量和各个配送站点货物数量，使得运输车辆可以进行往返运输。货物的拆分策略对数量比较多的货物进行拆分，保证了货物装入运输车辆的可运输性和其他运输车辆的满载性。本文提出的货物装箱模型避免了传统装箱问题求解困难，具有较强的实用性，可以为实际的货物运输装箱计划提供参考。
主要参考文献
[1]Dyckhoff H.A Typology of Cutting and Packing Problems[J]. European Journal of Operational Research ， 1990， 44（2）：145-159
[2]李敬峰，叶艳，傅惠.面向货物装卸需求的越库仓门分配和货车排序[J].工业工程，2016（2）.
[3]MIAO Z，CAI S，XU D. Applying an Adaptive Tabu Search Algorithm to Optimize Truck-dock Assignment in the Crossdock Management System[J].Expert Systems with Applications，2014，41（1） ： 16-22.
[4]余小兵. 基于改进粒子群算法的多目标应急物资调度[J]. 工业工程， 2014， 17（ 3） ： 18-21.
[5]KUO Y.Optimizing Truck Sequencing and Truck Dock Assignment in a Cross Docking System[J].Expert Systems with Applications，2013，40（14）：5532-5547.
[6]邵飞牛.一维装箱问题启发式算法的设计与分析[D].沈阳：东北大学，2013.
[7]LEE K，KIM B S，JOO C M. Genetic Algorithms for Doorassigning and Sequencing of Trucks at Distribution Centers for the Improvement of Operational Performance[J]. Expert Systems with Applications，2012，39（1）：12975-12973.
[8]汤岩.遗传算法在装箱问题中的应用[D].大连：大连海事大学，2005.
[9]LIAO T W，EGBELUA P G，CHANG P C. Simultaneous Dock Assignment and Sequencing of Inbound Trucks under a Fixed Outbound Truck Schedule in Multi-door Cross Docking Operations[J].International Journal of Production Economics， 2013， 141 （1）：212-229.
[10]A Bettinelli， A Ceselli， G Righini.A Branch-and-price Algorithm for the Variable Size Bin Packing Problem with Minimum Filling Constraint [J].Annals of Operations Research，2010，179（1）：221-241.
[11]杜少波，张国基，刘清. 一种新的多约束尺寸可变的装箱问题[J].计算机工程与应用，2011，47（19）： 242-244
[12]虞才珠，邵志清.一种基于最优个体保存策略的服务组合优化选取方法[J].华东理工大学学报：自然科学版，2010（5）.