可视化三维图形集装系统的设计
|
摘要
装箱问题广泛存在于工业领域,在铁路货车车厢装载、集装箱装载、轮船装配和仓库储存等情况中普遍存在,在实际装箱工作中,装箱问题空间利用率的解决效果直接影响着物流运输业的成本和收益。装箱问题是物流环节的核心问题,实现装箱问题的优化对于提高物流效率、降低物流成本具有重要意义。目前为止,国内外学者对装箱问题,尤其是三维装箱问题进行了大量的研究,但大部分研究主要是针对算法优化等理论研究,对其进行可视化的研究相对较少。在此背景下,本人在前人研究的基础上,开发设计了可视化三维图形集装系统。
本课题针对待装载货物种类较多的复杂三维装箱问题设计开发了可视化三维图形集装系统,该系统是基于C语言对容器内待装载物品种类繁多、尺寸不固定的组合装载问题提供了一种有效的解决方法。它能够根据各种待装载物品的形状、尺寸、数量、重量等信息,确定一种可行的堆码方式,使得在满足给定的体积约束、承重能力约束、稳定性约束、装载顺序等约束的情况下,集装容器中所包含的物品的总体积尽可能的大,也就是说其填充率尽可能的大,从而在物流过程中更加有效地利用运输容器的空间,降低运输成本,提高物流效率,获得更好的经济效益和社会效益。
论文在分析系统需求功能的基础上,通过三维图形可视化实现技术对系统功能模块进行了详细设计,实现了系统图形处理功能的可视化,最后对系统使用过程进行了测试。本课题利用VC++6.0直接编写程序,从原理上对三维图形进行建模仿真,开发设计了三维可视化装箱软件,该系统能够有效地解决待装载物品种类较多的复杂装箱问题,并为其他相关问题的研究和拼箱软件的开发提供了参考依据和借鉴经验。
Bin packing problem exists widely in the industrial field, for example, in railway freight train loading, container loading, ship assembly and warehouse storage. And in the actual packing work, the space utilization of container directly affects the costs and benefits of logistics transportation. Bin packing problem is the core issue of the logistics links, and it is important to improve logistics efficiency and reduce logistics cost that realizing the optimization of bin packing problem. Up to now, many studies have been carried out on the problem by scholars at home and abroad, but most of the studies focus on algorithm optimization and its visualization study is relatively small. In this context, this paper finishes the development of the3D visualization of bin packing software on the basis of predecessors' research.
The3d visualization of bin packing software was developed aiming at the complex packing problem which has different sizes of goods. As C language a platform, this system offers an effective method to combined loading problems which have multi-containers. According to the cargo size, weight and other information, it could confirm a feasible stacking way which meets the given volume constraint, bearing capacity constraint, stability constraint, packing constraint and other constraints. And the total volume of goods in container would be as large as possible, that is to say, the filling rate is as high as possible. Thus, there would be a high effective utilization of container space, low transport costs and high logistics efficiency in logistics activities, and we can gain considerable economic and social benefits
This paper points out the research background and significance at first, and then introduces the importance and necessity of the three-dimensional visualization bin packing software. After studying the system requirement, function models are designed, and the visualization of graphic system is gotten, and at last we test the system by example. As VC6.0environment a development platform, programming, modeling and graph visualization are implemented in this paper. The system can effectively solve the complex packing problems with different categories of goods to be loaded, and it provides reference and experience to developing encasement software and the related issues.
本课题针对待装载货物种类较多的复杂三维装箱问题设计开发了可视化三维图形集装系统,该系统是基于C语言对容器内待装载物品种类繁多、尺寸不固定的组合装载问题提供了一种有效的解决方法。它能够根据各种待装载物品的形状、尺寸、数量、重量等信息,确定一种可行的堆码方式,使得在满足给定的体积约束、承重能力约束、稳定性约束、装载顺序等约束的情况下,集装容器中所包含的物品的总体积尽可能的大,也就是说其填充率尽可能的大,从而在物流过程中更加有效地利用运输容器的空间,降低运输成本,提高物流效率,获得更好的经济效益和社会效益。
论文在分析系统需求功能的基础上,通过三维图形可视化实现技术对系统功能模块进行了详细设计,实现了系统图形处理功能的可视化,最后对系统使用过程进行了测试。本课题利用VC++6.0直接编写程序,从原理上对三维图形进行建模仿真,开发设计了三维可视化装箱软件,该系统能够有效地解决待装载物品种类较多的复杂装箱问题,并为其他相关问题的研究和拼箱软件的开发提供了参考依据和借鉴经验。
Bin packing problem exists widely in the industrial field, for example, in railway freight train loading, container loading, ship assembly and warehouse storage. And in the actual packing work, the space utilization of container directly affects the costs and benefits of logistics transportation. Bin packing problem is the core issue of the logistics links, and it is important to improve logistics efficiency and reduce logistics cost that realizing the optimization of bin packing problem. Up to now, many studies have been carried out on the problem by scholars at home and abroad, but most of the studies focus on algorithm optimization and its visualization study is relatively small. In this context, this paper finishes the development of the3D visualization of bin packing software on the basis of predecessors' research.
The3d visualization of bin packing software was developed aiming at the complex packing problem which has different sizes of goods. As C language a platform, this system offers an effective method to combined loading problems which have multi-containers. According to the cargo size, weight and other information, it could confirm a feasible stacking way which meets the given volume constraint, bearing capacity constraint, stability constraint, packing constraint and other constraints. And the total volume of goods in container would be as large as possible, that is to say, the filling rate is as high as possible. Thus, there would be a high effective utilization of container space, low transport costs and high logistics efficiency in logistics activities, and we can gain considerable economic and social benefits
This paper points out the research background and significance at first, and then introduces the importance and necessity of the three-dimensional visualization bin packing software. After studying the system requirement, function models are designed, and the visualization of graphic system is gotten, and at last we test the system by example. As VC6.0environment a development platform, programming, modeling and graph visualization are implemented in this paper. The system can effectively solve the complex packing problems with different categories of goods to be loaded, and it provides reference and experience to developing encasement software and the related issues.
引文
[1]韩孟江.集装箱配载关键问题的高效能求解算法[D].成都：电子科技大学,2011
[2]陈云东.基于多配送点限制集装箱装载问题研究及应用[D].天津：天津大学,2008
[3]雍文君.多约束三维装箱问题的研究及实现[D].西安：西安理工大学,2008
[4]Eley M. A bottleneck assignment approach to the multiple container loading problem[M]//Container Terminals and Automated Transport Systems. Springer Berlin Heidelberg,2005:359-374
[5]Eley M. Solving container loading problems by block arrangement[J]. European Journal of Operational Research,2002,141(2):393-409
[6]马广焜.集装箱装入新算法的研究与软件实现[D].沈阳：沈阳工业大学,2004
[7]朱颢东,钟勇.一种改进的模拟退火算法[J].计算机技术与发展,2009(06)：32～35
[8]Lv P, Yuan L, Zhang J. Cloud theory-based simulated annealing algorithm and application[J]. Engineering Applications of Artificial Intelligence,2009,22(4):742-749
[9]Bortfeldt A, Gehring H. A hybrid genetic algorithm for the container loading problem[J]. European Journal of Operational Research,2001,131(1):143-161
[10]张彩明,杨兴强,李学庆.计算机图形学[M].北京：科学出版社,2005.86
[11]杨青生.基于OpenGL的三维可视化研究[[)].西安：陕西师范大学,2002
[12]刘文文,杜江.3DMAX自由立体显示功能的实现[J].合肥工业大学学报,2008,31(4)
[13]Woo M, Neider J, et al. OpenGL programming guide[J].1999
[14]Hohne K H, Bomans M, Pommert A, et al.3D visualization of tomographic volume data using the generalized voxel model[J]. The Visual Computer,1990,6(1):28-36
[15]Kaufman A. Volume visualization[J]. The Visual Computer,1990,6(1):1
[16]Dollner J, Hinrichs K. An object-oriented approach for integrating 3D visualization systems and GIS[J]. Computers & Geosciences,2000,26(1):67-76
[17]Guccione S A. WebScope:A circuit debug tool[M]//Field-programmable logic and applications from FPGAs to computing paradigm. Springer Berlin Heidelberg,1998: 308-315
[18]http://www.webscope.com/
[19]Fei Y, Ningning D, Bingjia X. WebScope:A new tool for fusion data analysis and visualization[J]. Plasma Science and Technology,2010,12(2):253
[20]Honda Y, Matsuda K, Rekimoto J, et al. Virtual society:extending the www to support a multi-user interactive shared 3d environment[C]//Proceedings of the first symposium on Virtual reality modeling language. ACM,1995:109-116
[21]Kauff P, Schreer O. An immersive 3d video-conferencing system using shared virtual team user environments[C]//Proceedings of the 4th international conference on Collaborative virtual environments. ACM,2002:105-112
[22]Anupam V, Bajaj C L. Shastra:multimedia collaborative design environment[J]. Multimedia, IEEE,1994,1(2):39-49
[23]Anupam V, Bajaj C. SHASTRA-an architecture for development of collaborative applications[C]//Enabling Technologies:Infrastructure for Collaborative Enterprises,1993. Proceedings., Second Workshop on. IEEE,1993:155-166
[24]Cliff A D, Ord J K. Spatial processes:models & applications[M]. London:Pion,1981
[25]Samet H. Applications of spatial data structures[J].1990
[26]Zeid I. CAD/CAM theory and practice[M]. McGraw-Hill Higher Education,1991
[27]陈俊,周来水.一种基于Web的CAD/CAM系统开发方案[J].机械设计与制造工程,2002,31(1)：27～29
[28]汪海志,陈定方.基于IntraWeb的SolidWorks标准件库图文信息系统[J].武汉理工大学学报(交通科学与工程版),2004,28(4)
[29]Core M R, Stube J W. Computers and information sysetms. McGraw-Hill Book ComPnay, 2000
[30]朱剑飞.网络环境下三维模型的协同浏览,查询和批注技术研究[D].西安：西北工业大学,2003
[31]陈泽峰.产品协同设计工具集的研究和开发[D].西安：西北工业大学,2004
[32]曾文萱.基于Web技术的三维模型库系统的设计与开发[D].合肥：合肥工业大学,2005
[33]戴晟.地质体三维可视化研究与系统实现[D].上海：华东师范大学,2008.
[34]张海墨.三维图形可视化实现技术研究[D].昆明：昆明理工大学,2011.
[35]http://baike.baidu.com/view/3462282.html
[36]王东爱,王岭松,乔志霞.集装箱装箱优化与纸箱优化设计[J].包装工程,2005,26(5)：123～125
[37]陈满儒,戴杰明MaxLoad Pro:包装产品混合集装优化软件[J].包装工程,2004,25(6)：205～207
[38]陈满儒.TOPS Pro——一个功能强大的包装优化设计软件[J].包装工程,2004,25(2)：135～137
[39]陈满儒,山静民.美国包装结构优化设计软件TOPS Pro的CASY功能[J].包装工程,2005,26(3)：117-118
[40]肖锭LoadExper软件在集装箱装箱中的应用[J].物流技术与应用,2009,14(3)：110-111
[41]Wu Y, Li W, Goh M, et al. Three-dimensional bin packing problem with variable bin height[J]. European Journal of Operational Research,2010,202(2):347-355
[42]Kucuk M, Ermis M. A new hybrid evolutionary algorithm for three-dimensional packing problems[C]//Systems Man and Cybernetics (SMC),2010 IEEE International Conference on. IEEE,2010:4029-4034
[43]韩运实.装箱问题方法研究及其集成应用[D].青岛：中国海洋大学,2004
[44]孟唯娟,孙诚,黄利强等.托盘装载优化系统的研究与开发[J].包装工程,2010(1)：54～56
[45]乐千桤.多约束装箱优化模型的研究与系统开发[D].成都：电子科技大学,2006
[46]李巴津.C语言与交互式计算机辅助图形应用软件的开发[J].内蒙古工业大学学报：自然科学版,1994,13(1)：18～26
[47]谭浩强,崔武子.C语言程序设计[M].北京：清华大学出版社,2000
[48]http://baike.baidu.com/view/1219.html
[49]杨新锋,黄宪通.谈C语言中的图形模式[J].电脑知识与技术(技术论坛),2005(7)
[50]赛奎春,张雨,阮伟良等.Visual C++工程应用与项目实践[M].北京：机械工业出版社,2005
[51]刘蓉Matlab与VC混合编程技术与实现[J].电脑编程技巧与维护,2010(008)：15～16
[52]刘世霞,胡事民,汪国平等.基于三视图的三维形体重建技术[J].计算机学报,2000,23(2)：141～146
[53]苏海云,秦秀婵.矿床体视化技术中几何造型模式的探讨[J].黄金科学技术,2004,12(2)
[54]王小彬,焦圣喜,祝永志.用C语言实现三维图形[J].吉林化工学院学报,2003,20(1)：78～81
[55]陈元琰,张睿哲,吴东.计算机图形学实用技术[M].北京：清华大学出版社,2007.113-116
[56]张丽娟.浅议坐标变换与图形变换的区别和联系[J].中小企业管理与科技(上旬刊),2011,2：140
[57]王渊,龙华,邵玉斌等.一种图形透视投影矩阵的推导及编程实现[J].甘肃科学学报,2011,23(4)：127～129
[58]吴迪,黄文骞,王莹.计算机图形学中的透视投影变换矩阵[J]. Journal of Dalian Naval Academy,2003,26(2)
[59]程晓旭,耿鲁静,张海.C语言算法速查手册[M].人民邮电出版社,2009
[60]朱仁芝,太美花,邓益民.三维形体消隐和相贯线的一种新算法[J].中国科学技术大学学报,1992,22(3)：295～302
[61]孙家广.计算机图形学(第三版)[M].北京：清华大学出版,2001.298
[62]蒋亚军.三种常用颜色模型的比较研究[J].湖南科技学院学报,2007,28(4)：37～38
[63]王向慧,刘文光.颜色模型浅析[J].科技信息,2010(016)：10197
[64]侯其锋,李晓华,李莎.Visual C++数据库通用模块开发与系统移植[M].北京：清华大学出版社,2007.195-199
[65]和青芳.计算机图形学原理及算法教程(Visual C++版)(第二版)[M].北京：清华大学出版社,2010.297～299
[2]陈云东.基于多配送点限制集装箱装载问题研究及应用[D].天津：天津大学,2008
[3]雍文君.多约束三维装箱问题的研究及实现[D].西安：西安理工大学,2008
[4]Eley M. A bottleneck assignment approach to the multiple container loading problem[M]//Container Terminals and Automated Transport Systems. Springer Berlin Heidelberg,2005:359-374
[5]Eley M. Solving container loading problems by block arrangement[J]. European Journal of Operational Research,2002,141(2):393-409
[6]马广焜.集装箱装入新算法的研究与软件实现[D].沈阳：沈阳工业大学,2004
[7]朱颢东,钟勇.一种改进的模拟退火算法[J].计算机技术与发展,2009(06)：32～35
[8]Lv P, Yuan L, Zhang J. Cloud theory-based simulated annealing algorithm and application[J]. Engineering Applications of Artificial Intelligence,2009,22(4):742-749
[9]Bortfeldt A, Gehring H. A hybrid genetic algorithm for the container loading problem[J]. European Journal of Operational Research,2001,131(1):143-161
[10]张彩明,杨兴强,李学庆.计算机图形学[M].北京：科学出版社,2005.86
[11]杨青生.基于OpenGL的三维可视化研究[[)].西安：陕西师范大学,2002
[12]刘文文,杜江.3DMAX自由立体显示功能的实现[J].合肥工业大学学报,2008,31(4)
[13]Woo M, Neider J, et al. OpenGL programming guide[J].1999
[14]Hohne K H, Bomans M, Pommert A, et al.3D visualization of tomographic volume data using the generalized voxel model[J]. The Visual Computer,1990,6(1):28-36
[15]Kaufman A. Volume visualization[J]. The Visual Computer,1990,6(1):1
[16]Dollner J, Hinrichs K. An object-oriented approach for integrating 3D visualization systems and GIS[J]. Computers & Geosciences,2000,26(1):67-76
[17]Guccione S A. WebScope:A circuit debug tool[M]//Field-programmable logic and applications from FPGAs to computing paradigm. Springer Berlin Heidelberg,1998: 308-315
[18]http://www.webscope.com/
[19]Fei Y, Ningning D, Bingjia X. WebScope:A new tool for fusion data analysis and visualization[J]. Plasma Science and Technology,2010,12(2):253
[20]Honda Y, Matsuda K, Rekimoto J, et al. Virtual society:extending the www to support a multi-user interactive shared 3d environment[C]//Proceedings of the first symposium on Virtual reality modeling language. ACM,1995:109-116
[21]Kauff P, Schreer O. An immersive 3d video-conferencing system using shared virtual team user environments[C]//Proceedings of the 4th international conference on Collaborative virtual environments. ACM,2002:105-112
[22]Anupam V, Bajaj C L. Shastra:multimedia collaborative design environment[J]. Multimedia, IEEE,1994,1(2):39-49
[23]Anupam V, Bajaj C. SHASTRA-an architecture for development of collaborative applications[C]//Enabling Technologies:Infrastructure for Collaborative Enterprises,1993. Proceedings., Second Workshop on. IEEE,1993:155-166
[24]Cliff A D, Ord J K. Spatial processes:models & applications[M]. London:Pion,1981
[25]Samet H. Applications of spatial data structures[J].1990
[26]Zeid I. CAD/CAM theory and practice[M]. McGraw-Hill Higher Education,1991
[27]陈俊,周来水.一种基于Web的CAD/CAM系统开发方案[J].机械设计与制造工程,2002,31(1)：27～29
[28]汪海志,陈定方.基于IntraWeb的SolidWorks标准件库图文信息系统[J].武汉理工大学学报(交通科学与工程版),2004,28(4)
[29]Core M R, Stube J W. Computers and information sysetms. McGraw-Hill Book ComPnay, 2000
[30]朱剑飞.网络环境下三维模型的协同浏览,查询和批注技术研究[D].西安：西北工业大学,2003
[31]陈泽峰.产品协同设计工具集的研究和开发[D].西安：西北工业大学,2004
[32]曾文萱.基于Web技术的三维模型库系统的设计与开发[D].合肥：合肥工业大学,2005
[33]戴晟.地质体三维可视化研究与系统实现[D].上海：华东师范大学,2008.
[34]张海墨.三维图形可视化实现技术研究[D].昆明：昆明理工大学,2011.
[35]http://baike.baidu.com/view/3462282.html
[36]王东爱,王岭松,乔志霞.集装箱装箱优化与纸箱优化设计[J].包装工程,2005,26(5)：123～125
[37]陈满儒,戴杰明MaxLoad Pro:包装产品混合集装优化软件[J].包装工程,2004,25(6)：205～207
[38]陈满儒.TOPS Pro——一个功能强大的包装优化设计软件[J].包装工程,2004,25(2)：135～137
[39]陈满儒,山静民.美国包装结构优化设计软件TOPS Pro的CASY功能[J].包装工程,2005,26(3)：117-118
[40]肖锭LoadExper软件在集装箱装箱中的应用[J].物流技术与应用,2009,14(3)：110-111
[41]Wu Y, Li W, Goh M, et al. Three-dimensional bin packing problem with variable bin height[J]. European Journal of Operational Research,2010,202(2):347-355
[42]Kucuk M, Ermis M. A new hybrid evolutionary algorithm for three-dimensional packing problems[C]//Systems Man and Cybernetics (SMC),2010 IEEE International Conference on. IEEE,2010:4029-4034
[43]韩运实.装箱问题方法研究及其集成应用[D].青岛：中国海洋大学,2004
[44]孟唯娟,孙诚,黄利强等.托盘装载优化系统的研究与开发[J].包装工程,2010(1)：54～56
[45]乐千桤.多约束装箱优化模型的研究与系统开发[D].成都：电子科技大学,2006
[46]李巴津.C语言与交互式计算机辅助图形应用软件的开发[J].内蒙古工业大学学报：自然科学版,1994,13(1)：18～26
[47]谭浩强,崔武子.C语言程序设计[M].北京：清华大学出版社,2000
[48]http://baike.baidu.com/view/1219.html
[49]杨新锋,黄宪通.谈C语言中的图形模式[J].电脑知识与技术(技术论坛),2005(7)
[50]赛奎春,张雨,阮伟良等.Visual C++工程应用与项目实践[M].北京：机械工业出版社,2005
[51]刘蓉Matlab与VC混合编程技术与实现[J].电脑编程技巧与维护,2010(008)：15～16
[52]刘世霞,胡事民,汪国平等.基于三视图的三维形体重建技术[J].计算机学报,2000,23(2)：141～146
[53]苏海云,秦秀婵.矿床体视化技术中几何造型模式的探讨[J].黄金科学技术,2004,12(2)
[54]王小彬,焦圣喜,祝永志.用C语言实现三维图形[J].吉林化工学院学报,2003,20(1)：78～81
[55]陈元琰,张睿哲,吴东.计算机图形学实用技术[M].北京：清华大学出版社,2007.113-116
[56]张丽娟.浅议坐标变换与图形变换的区别和联系[J].中小企业管理与科技(上旬刊),2011,2：140
[57]王渊,龙华,邵玉斌等.一种图形透视投影矩阵的推导及编程实现[J].甘肃科学学报,2011,23(4)：127～129
[58]吴迪,黄文骞,王莹.计算机图形学中的透视投影变换矩阵[J]. Journal of Dalian Naval Academy,2003,26(2)
[59]程晓旭,耿鲁静,张海.C语言算法速查手册[M].人民邮电出版社,2009
[60]朱仁芝,太美花,邓益民.三维形体消隐和相贯线的一种新算法[J].中国科学技术大学学报,1992,22(3)：295～302
[61]孙家广.计算机图形学(第三版)[M].北京：清华大学出版,2001.298
[62]蒋亚军.三种常用颜色模型的比较研究[J].湖南科技学院学报,2007,28(4)：37～38
[63]王向慧,刘文光.颜色模型浅析[J].科技信息,2010(016)：10197
[64]侯其锋,李晓华,李莎.Visual C++数据库通用模块开发与系统移植[M].北京：清华大学出版社,2007.195-199
[65]和青芳.计算机图形学原理及算法教程(Visual C++版)(第二版)[M].北京：清华大学出版社,2010.297～299