Journal of the Korea Institute of Information and Communication Engineering (한국정보통신학회논문지)

The Korea Institute of Information and Commucation Engineering (한국정보통신학회)
권호 표지
DOI QR코드

DOI QR Code

An Optimal Algorithm for Weight Balancing in a 3D Mesh Architecture

3D 메쉬 구조에서 무게 균형을 위한 최적 알고리즘

  • So, Sun Sup (School of Computer Eng., Kongju National University) ;
  • Son, Kyung A (UNIST Innovative Education Center, Ulsan National Institute of Science and Technology (UNIST)) ;
  • Eun, Seongbae (Dept. of Information and Communication Eng., Hannam University)
  • Received : 2020.06.12
  • Accepted : 2020.07.03
  • Published : 2020.08.31
Download PDF
⟨ Previous Next ⟩

Abstract

Vessels or aircraft should be loaded with containers or cargo to maintain weight balance in order to be stable when navigating the route. The container loading algorithm is known as the NP problem and several heuristic methods have been studied. Containers can be characterized by the uniform volume and weight, which makes it easier to find an optimal loading method. In this paper, we propose an algorithm for weight balance when the volume and weight of an object are uniform. It is assumed that the loading space has a special structure of m * n mesh (where m and n are both odd). In this case, we designed a greedy algorithm and proved that the algorithm is optimal in that it can always find a loading position that maintains a weight balance regardless of the number of objects. Our algorithm can be used in many engineering problems, such as loading algorithms and load balancing problems.

선박이나 항공기의 안정성 유지를 위하여 컨테이너나 화물의 무게 균형을 유지하도록 적재해야 한다. 컨테이너의 적재 알고리즘은 NP 문제로 알려져 있으며 몇 가지 휴리스틱 방법이 연구되었다. 선박이나 비행기에 보관할 컨테이너는 부피와 무게가 균일하다는 특징이 있는데 이를 이용하면 좀 더 쉬운 적재 방법을 찾을 수 있다. 본 논문에서는 물체의 부피와 무게가 균일할 때 무게 균형을 위한 알고리즘을 제안한다. 적재 공간은 m * n 메쉬의 특수한 구조라고 가정한다 (이때, m과 n은 모두 홀수이다). 이 경우, 본 논문에서는 Greedy 알고리즘을 제안하였고 물체의 개수가 몇 개이든 언제나 무게 균형을 유지하는 적재 장소를 찾을 수 있다는 점에서 그 알고리즘이 최적임을 증명하였다. 제안된 알고리즘은 적재 알고리즘 및 부하 균형 문제와 같은 여러 공학 문제에서 활용될 수 있다.

Keywords

References

  1. S. Eun, J. Jung, Y-S Yun, S. Cha, and S-S So, "A mathematical Study on Weight Balancing in 2D Meshed and It's Application to Engineering Problems," Proc. of 2019 International Conference on Green and Human Information Technology, Jan. 2019.
  2. K. Kwon, "Development of speeding up 2D digital image correlation measurement system by using center of gravity algorithm and the measurement of strain nano fiber mat," Master Dissertation, Chonbuk National University, Feb. 2018.
  3. J. Cho, "Study of center of gravity on the 3D character animation: Focus on humanoid character," Master Dissertation, Kookmin University, Feb. 2006.
  4. B. Korte, and J. Vygen, "Bin-Packing Combinatorial Optimization: Theory and Algorithms," Algorithms and Combinatorics 21. Springer. doi:10.1007/3-540-29297-7_18. ISBN 978-3-540-25684-7, pp. 426-441.
  5. M. Costa, and M. Captivo, "Weight distribution in container loading: a case study," International Transactions in Operational Research, 23, pp.239-263, 2016. https://doi.org/10.1111/itor.12145
  6. A. Sciomachen, and E. Tanfani, "The master bay plan problem: a solution method based on its connection to the three‐dimensional bin packing problem," IMA Journal of Management Mathematics, vol. 14, no. 3, Jul. 2003.
  7. F. Liu, M. Low, S. Huang, and W. Hsu, "Stowage Planning of Large Containership with Tradeoff between Crane Workload Balance and Ship Stability," Proc. of International Multi-Conference of Engineers and Computer Scientists 2010, vol. III, Mar. 2010.
  8. M. P. Seixas, A. Mendes, M. Barretto, C. Cunha, M. A. Brinati, R. Cruz, Y. Wu, and P. A. Wilson, "A heuristic approach to stowing general cargo into platform supply vessels," The Journal of the Operational Research Society, vol. 67, no. 1, pp. 148-158, Jan. 2016. https://doi.org/10.1057/jors.2015.62
  9. J. Li, Y. Zhang, J. Ma, and S. Ji, "Multi-Port Stowage Planning for Inland Container Liner Shipping Considering Weight Uncertainties," IEEE Access, Digital Object Identifier 10.1109/ACCESS.2018.2878308, Oct. 2018.
  10. L. Zheng, S. Ji, J. Li, and Y. Zhang, "Solving inland container ship stowage planning problem on full route through a two-phase approach," International Journal of Shipping and Transport Logistics 12(1/2):65 Jan. 2020. https://doi.org/10.1504/IJSTL.2020.105863
  11. Airplane Flying Handbook, U.S. Department of Transportation FEDERAL AVIATION ADMINISTRATION Flight Standards Service, 2016.
  12. V. Lurkin, and M. Schyns, "The Airline Container Loading Problem with Pickup and Delivery," 26th European Conference on Operational Research, Rome, pp. 1-4, Jul. 2013.
  13. Application Korea Patent, KR1020150168071A events, unmanned aerial vehicle with object loading function, 2015.
  14. A. Sharma, A. Roy, S. Ghosi, R. Chaki, and U. Bhattacharya, "Load Balancing in Cellular Network: A Review," Proc. of 2012 Third International Conference on Computing, Communicaiton and Networking Technologies, pp.1-5, 2012.