基于K-means与关键点的组合行李码放算法
|
摘要
目的为了解决当前航空行李码放流程中存在的劳动密集、效率低下的问题,开展行李码放算法研究。方法搭建含有重量、体积和货舱空间约束的航空行李码放数学模型,采用聚类、排序、关键点构建策略,设计一种K-means聚类与"关键点"思想相结合的组合式算法。结果采用100件真实旅客行李数据进行了实验,结果表明算法给出的布局方案规划合理,垛型左右两侧质量之差低于1%,满足了货舱的空间约束与载重平衡约束。结论算法具备在复杂环境下得到优良布局方案的能力,K-means聚类的引入也将机器学习领域的聚类算法引入装箱问题,架起了机器学习算法与传统装箱算法的桥梁,为今后装箱问题算法的设计提供了一条新思路。
The paper aims to study the luggage stacking algorithm to solve the labor-intensive and inefficient problems in the current flight luggage stacking process for check-in. In this paper, a mathematical model of flight luggage with weight, volume and cargo compartment constraints was built. By using clustering, ranking and key point construction strategy, a new algorithm combining K-means clustering and "key point" idea was designed. Experiments on 100 pieces of real passenger baggage showed that the layout plan given by the algorithm was reasonable. The difference of mass between the left and right sides of the stack was less than 1%, which satisfied the space constraint and load balancing constraint of the cargo compartment. The algorithm has the ability to obtain excellent layout scheme in complex environment. The introduction of K-means clustering algorithm establishes a bridge for machine learning algorithm and traditional packing problems, and provides a new idea for design of bin-packing problem algorithm in the future.
The paper aims to study the luggage stacking algorithm to solve the labor-intensive and inefficient problems in the current flight luggage stacking process for check-in. In this paper, a mathematical model of flight luggage with weight, volume and cargo compartment constraints was built. By using clustering, ranking and key point construction strategy, a new algorithm combining K-means clustering and "key point" idea was designed. Experiments on 100 pieces of real passenger baggage showed that the layout plan given by the algorithm was reasonable. The difference of mass between the left and right sides of the stack was less than 1%, which satisfied the space constraint and load balancing constraint of the cargo compartment. The algorithm has the ability to obtain excellent layout scheme in complex environment. The introduction of K-means clustering algorithm establishes a bridge for machine learning algorithm and traditional packing problems, and provides a new idea for design of bin-packing problem algorithm in the future.
引文
[1]CRAINIC T G,PERBOLI G,TADEI R.Extreme Pointbased Heuristics for Three-dimensional Bin Packing[J].Informs Journal on Computing,2008,20(3):368-384.
[2]CRAINIC T G,PERBOLI G,TADEI R.TS2PACK:ATwo-level Tabu Search for the Three-dimensional Bin Packing Problem[J].European Journal of Operational Research,2009,195(3):744-760.
[3]游伟,雷定猷,朱向.三维装箱问题的偏随机密钥混合遗传算法[J].计算机工程与应用,2014,50(22):265-270.YOU Wei,LEI Ding-you,ZHU Xiang.Biased Randomkey Hybrid Genetic Algorithm for Three-dimensional Loading Problem[J].Computer Engineering and Applications,2014,50(22):265-270.
[4]张莹,刘二超,戚铭尧.考虑支撑面约束的三维装箱问题快速求解方法[J].交通运输系统工程与信息,2014,14(2):192-198.ZHANG Ying,LIU Er-chao,QI Ming-yao.Quick Algorithm for the Three-dimensional Bin Packing Problem with Support Surface Constraints[J].Journal of Transportation Systems Engineering and Information Technology,2014,14(2):192-198.
[5]朱向,雷定猷.带平衡约束三维装箱问题的双层混合遗传算法[J].交通运输系统工程与信息,2015,15(2):203-209.ZHU Xiang,LEI Ding-you.Bi-level Hybrid Genetic Algorithm for Three-dimensional Container Loading Problem with Balancing Constrains[J].Journal of Transportation Systems Engineering and Information Technology,2015,15(2):203-209.
[6]SRIDHAR R,CHANDRASEKARAN M,PAGE T.Multi Objective Optimization of Heterogeneous Bin Packing using Adaptive Genetic Approach[J].Indian Journal of Science and Technology,2016,9(48):1-9.
[7]MAHVASH B,AWASTHI A,CHAUHAN S.A Column Generation-based Heuristic for the Three-dimensional Bin Packing Problem with Rotation[J].Journal of the Operational Research Society,2018,69(1):78-90.
[8]KAABI J,HARRATH Y,BOUOUDINA H E,et al.Toward Smart Logistics:A New Algorithm for a Multi-objective 3D Bin Packing Problem[C]//Smart Cities Symposium 2018.IET,2018:1-5.
[9]MANTOVANI S,MORGANTI G,UMANG N,et al.The Load Planning Problem for Double-stack Intermodal Trains[J].European Journal of Operational Research,2018,267(1):107-119.
[10]ZHOU K.The Pallet Loading Method of Single Category Cargo Based on Railway Containerized Transport[C]//Proceedings of the 2018 10th International Conference on Computer and Automation Engineering,ACM,2018:243-249.
[11]郑斐峰,梅启煌,刘明,等.基于遗传算法与贪婪策略的多港口集装箱配载研究[J].运筹与管理,2018,27(5):1-7.ZHENG Fei-feng,MEI Qi-huang,LIU Ming,et al.Research on Genetic Algorithm and Greedy Method of Stowage Planning in Multiple Ports[J].Operations Research and Management Science,2018,27(5):1-7.
[12]闫肃,闫鹏程,孙江生,等.武器维修器材分层装箱算法研究[J].包装工程,2012,33(9):81-84.YAN Su,YAN Peng-cheng,SUN Jiang-sheng,et al.Research of Layer Packaging Arithmetic for Weapon Servicing Equipment[J].Packaging Engineering,201233(9):81-84.
[13]郑琰,李鹏.求解非标准货物货机群装载问题的启发式搜索算法[J].科学技术与工程,2018,18(23):64-74.ZHENG Yan,LI Peng.A Heuristic Algorithm for Solving the Cargo Aircrafts Group Loading Problem with Non-standard Goods[J].Science Technology and Engineering,2018,18(23):64-74.
[14]RAMOS A G,SILVA E,OLIVEIRA J F.A New Load Balance Methodology for Container Loading Problem in Road Transportation[J].European Journal of Operational Research,2018,266(3):1140-1152.
[15]BRANDT F,NICKEL S.The Air Cargo Load Planning Problem-a Consolidated Problem Definition and Literature Review on Related Problems[J].European Journal of Operational Research,2019,275(2):399-410.
[16]LURKIN V,SCHYNS M.The Airline Container Loading Problem with Pickup and Delivery[J].European Journal of Operational Research,2015,244(3):955-965.
[2]CRAINIC T G,PERBOLI G,TADEI R.TS2PACK:ATwo-level Tabu Search for the Three-dimensional Bin Packing Problem[J].European Journal of Operational Research,2009,195(3):744-760.
[3]游伟,雷定猷,朱向.三维装箱问题的偏随机密钥混合遗传算法[J].计算机工程与应用,2014,50(22):265-270.YOU Wei,LEI Ding-you,ZHU Xiang.Biased Randomkey Hybrid Genetic Algorithm for Three-dimensional Loading Problem[J].Computer Engineering and Applications,2014,50(22):265-270.
[4]张莹,刘二超,戚铭尧.考虑支撑面约束的三维装箱问题快速求解方法[J].交通运输系统工程与信息,2014,14(2):192-198.ZHANG Ying,LIU Er-chao,QI Ming-yao.Quick Algorithm for the Three-dimensional Bin Packing Problem with Support Surface Constraints[J].Journal of Transportation Systems Engineering and Information Technology,2014,14(2):192-198.
[5]朱向,雷定猷.带平衡约束三维装箱问题的双层混合遗传算法[J].交通运输系统工程与信息,2015,15(2):203-209.ZHU Xiang,LEI Ding-you.Bi-level Hybrid Genetic Algorithm for Three-dimensional Container Loading Problem with Balancing Constrains[J].Journal of Transportation Systems Engineering and Information Technology,2015,15(2):203-209.
[6]SRIDHAR R,CHANDRASEKARAN M,PAGE T.Multi Objective Optimization of Heterogeneous Bin Packing using Adaptive Genetic Approach[J].Indian Journal of Science and Technology,2016,9(48):1-9.
[7]MAHVASH B,AWASTHI A,CHAUHAN S.A Column Generation-based Heuristic for the Three-dimensional Bin Packing Problem with Rotation[J].Journal of the Operational Research Society,2018,69(1):78-90.
[8]KAABI J,HARRATH Y,BOUOUDINA H E,et al.Toward Smart Logistics:A New Algorithm for a Multi-objective 3D Bin Packing Problem[C]//Smart Cities Symposium 2018.IET,2018:1-5.
[9]MANTOVANI S,MORGANTI G,UMANG N,et al.The Load Planning Problem for Double-stack Intermodal Trains[J].European Journal of Operational Research,2018,267(1):107-119.
[10]ZHOU K.The Pallet Loading Method of Single Category Cargo Based on Railway Containerized Transport[C]//Proceedings of the 2018 10th International Conference on Computer and Automation Engineering,ACM,2018:243-249.
[11]郑斐峰,梅启煌,刘明,等.基于遗传算法与贪婪策略的多港口集装箱配载研究[J].运筹与管理,2018,27(5):1-7.ZHENG Fei-feng,MEI Qi-huang,LIU Ming,et al.Research on Genetic Algorithm and Greedy Method of Stowage Planning in Multiple Ports[J].Operations Research and Management Science,2018,27(5):1-7.
[12]闫肃,闫鹏程,孙江生,等.武器维修器材分层装箱算法研究[J].包装工程,2012,33(9):81-84.YAN Su,YAN Peng-cheng,SUN Jiang-sheng,et al.Research of Layer Packaging Arithmetic for Weapon Servicing Equipment[J].Packaging Engineering,201233(9):81-84.
[13]郑琰,李鹏.求解非标准货物货机群装载问题的启发式搜索算法[J].科学技术与工程,2018,18(23):64-74.ZHENG Yan,LI Peng.A Heuristic Algorithm for Solving the Cargo Aircrafts Group Loading Problem with Non-standard Goods[J].Science Technology and Engineering,2018,18(23):64-74.
[14]RAMOS A G,SILVA E,OLIVEIRA J F.A New Load Balance Methodology for Container Loading Problem in Road Transportation[J].European Journal of Operational Research,2018,266(3):1140-1152.
[15]BRANDT F,NICKEL S.The Air Cargo Load Planning Problem-a Consolidated Problem Definition and Literature Review on Related Problems[J].European Journal of Operational Research,2019,275(2):399-410.
[16]LURKIN V,SCHYNS M.The Airline Container Loading Problem with Pickup and Delivery[J].European Journal of Operational Research,2015,244(3):955-965.