|
|
论文:2016,Vol:34,Issue(4):708-713 |
|
|
引用本文： |
|
|
郑炜, 刘文兴, 杨喜兵, 袁绪龙, 王文鹏. 一种基于启发式算法的货物装载问题的研究[J]. 西北工业大学学报 |
|
|
Zheng Wei, Liu Wenxing, Yang Xibing, Yuan Xulong, Wang Wenpeng. Research on the Problem of Cargo Loading Based on Heuristic Algorithm[J]. Northwestern polytechnical university |
|
|
|
|
|
|
|
| 一种基于启发式算法的货物装载问题的研究 |
|
| 郑炜1, 刘文兴1, 杨喜兵1, 袁绪龙2, 王文鹏1 |
|
1. 西北工业大学 软件与微电子学院, 陕西 西安 710072;
2. 西北工业大学 航海学院, 陕西 西安 710072 |
| 摘要: |
| 文章旨在解决多车辆车厢合理、高效装载问题，即给定一批大小不同的货物和一批车厢大小不同的车辆，在满足货物装载约束条件下实现自动化装载。文章首先分析借助计算机实现自动化装载存在的难点，在此基础上提出一种基于平面分割理论的启发式搜索算法，以解决自动化装载问题，并给出算法优化方法以提高算法的效率与实用价值。最后，为了得到满足货物装载约束条件的最优装载方案，文章也提出了结合遗传算法解决货物装载问题的改进思路。 |
| 关键词:
成本降低
三维货物装载
多车辆
多货物
平面划分
遗传算法
启发式算法
|
|
| Research on the Problem of Cargo Loading Based on Heuristic Algorithm |
|
| Zheng Wei1, Liu Wenxing1, Yang Xibing1, Yuan Xulong2, Wang Wenpeng1 |
|
1. School of Software and Microelectronic Engineering, Northwestern Polytechnology, Xi'an 710072, China;
2. School of Marine Science and Technolgoy University, Xi'an 710072, China |
| Abstract: |
| Cargo loading is a key link in the process of cargo transportation. The effective realization of rational loading of cargoes can save enormous manpower and material resources cost. But in practical work, most of the loading is directed by experience, time-consuming and unsatisfactory loading scheme ultimately. With the development of information technology, rational loading scheme can be generated automatically by computer, which can guide the actual loading. But it has been proved that the automated loading is a NP-HARD problem, how to use computer to generate automated loading to meet the constraints and possible near-optimal loading solution is a hotspot of current research. The purpose of this paper is to solve the problem of rational and efficient loading of vehicle compartments, that is, given a number of different sizes of cargoes and a number of vehicles with different sizes of compartments, automatic loading will be realized under the condition of meeting the cargo loading constraints. This paper firstly analyzes the difficulties in the realization of automatic loading by computer, then, a heuristic search algorithm based on plane segmentation theory is proposed to solve the problem of automatic loading. In order to improve the efficiency and practical value of the algorithm. This paper also puts forward the method of improving the efficiency of the algorithm. Finally, in order to accomplish the optimal loading scheme under the condition of meeting the cargo loading constraints, such as achieving a balanced loading of cargoes in a fixed number of vehicle compartments, this paper also puts forward the improved idea of combining genetic algorithm to solve the problem of cargoes loading. |
| Key words:
cost reduction
dimensional cargo loading
multi-vehicle
multi-cargo
plane division
genetic algorithm
heuristic algorithm
|
|
| 收稿日期: 2016-04-14
修回日期:
|
| DOI: |
| 基金项目: 国家自然科学基金（61402370）与中央高校基本科研业务费专项资金资助 |
| 通讯作者:
Email： |
| 作者简介: 郑炜(1975-),西北工业大学副教授,主要从事软件工程及软件测试的研究。
|
|
|
|
|
|
|
|
参考文献: |
|
|
[1] Raymond Edward Miller, James W Thatcher. Complexity of Computer Computations[M]. New York: Plenum Press, 1972: 85-103
[2] 雷定猷,陈德良. 平衡装载问题的优化模型与算法[J]. 系统工程学报, 2004,19(3): 251-257 Lei Dingyou, Chen Deliang. Optimizing Model and Its Algorithm of Balanced Loading Problems[J]. Journal of System Engineering, 2004, 19(3): 251-257 (in Chinese)
[3] Dyckhoff H. A Typology of Cutting and Packing Problems[J]. European Journal of Operational Research, 1990, 44(2): 145-159
[4] Bortfeldt A. A Genetic Algorithm for the Container Loading Problem[C]//Proceedings of the Conference on Adaptive Computing and Information Processing, London, 1994: 25-32
[5] Bischoff E E, Ratcliff M S W. Issues in the Development of Approaches to Container Loading[J]. Omega, 1995, 23(4): 377-390
[6] 李鹏,汤勇. 三维货物装箱问题的研究进展[J]. 南京林业大学学报,2015, 12(5): 1235-1238 Li Peng, Tang Yong. Research Progress of Three Dimensional Packing of Goods[J]. Journal of Nanjing Forestry University, 2015, 12(5): 1235-1238 (in Chinese)
[7] Goldberg D E. Genetic Algorithms in Search,Optimization and Machine Learning[M]. Boston, Addison-Wesley Professional, 1989
[8] Dwmkerr.SharpGL[EB/OL](2014-3-31)[2016-6-27].http://sharpgl.codeplex.com |
|
|
|
|
|
|
|
