一种求解一维装箱问题的近似算法的研究.zip
一种求解一维装箱问题的近似算法的研究,各位速速来围观啊，这可是一篇拿过省优秀本科论文的，里面有源代码和程序，绝对好用，论文的思路和程序都是独创的，不多说，这个对你觉得有收获，下面是具体的论文目录：摘要一维装箱问题来源于人们的长期以来的生产实践，是一种组合优化问题。给定有穷个物体，每个物体的重量是已知的正实数。给定足够多个空箱子，问题是要在满足两个约束条件的...
该文档为压缩文件,包含的文件列表如下:
内容介绍
原文档由会员 违规15 发布
¸÷λËÙËÙÀ´Î§¹Û°¡£¬Õâ¿ÉÊÇһƪÄùýÊ¡ÓÅÐã±¾¿ÆÂÛÎĵģ¬ÀïÃæÓÐÔ´´úÂëºÍ³ÌÐò£¬¾ø¶ÔºÃÓã¬ÂÛÎĵÄ˼·ºÍ³ÌÐò¶¼ÊǶÀ´´µÄ£¬²»¶à˵£¬Õâ¸ö¶ÔÄã¾õµÃÓÐÊÕ»ñ£¬ÏÂÃæÊǾßÌåµÄÂÛÎÄĿ¼£º
Õª Òª
һάװÏäÎÊÌâÀ´Ô´ÓÚÈËÃǵij¤ÆÚÒÔÀ´µÄÉú²úʵ¼ù£¬ÊÇÒ»ÖÖ×éºÏÓÅ»¯ÎÊÌâ¡£¸ø¶¨ÓÐÇî¸öÎïÌ壬ÿ¸öÎïÌåµÄÖØÁ¿ÊÇÒÑÖªµÄÕýʵÊý¡£¸ø¶¨×ã¹»¶à¸ö¿ÕÏä×Ó£¬ÎÊÌâÊÇÒªÔÚÂú×ãÁ½¸öÔ¼ÊøÌõ¼þµÄÇ°ÌáÏ£¬½«ËùÓÐÎïÌå·Åµ½Ïä×ÓÖÐÈ¥£¬Ê¹µÃËùÓÃÏä×ӵĸöÊý¾¡¿ÉÄܵØÉÙ¡£Á½¸öÔ¼ÊøÌõ¼þÊÇ£ºµÚÒ»£¬Ã¿¸öÎïÌå¾ù±£³ÖÍêÕû£¬Ç¡ºÃ·Åµ½Ò»¸öÏä×ÓÖÐÈ¥¡£²»Äܽ«ÎïÌå·Ö¸î³É¼¸¿é¡£µÚ¶þ£¬Ã¿¸öÏä×ÓÖÐËù·ÅµÄÎïÌåµÄÖØÁ¿Ö®ºÍ¾ù²»Ä@@¬¹ýÒ»¸öÏàͬµÄÉÏÏÞ£¬Õâ¸öÉÏÏÞÊÇÒ»¸öÒÑÖªµÄÕýʵÊý¡£
һάװÏäÎÊÌâ¾ßÓкܸߵÄÀíÂÛ¼ÛÖµºÍʵ¼Ê¼ÛÖµ¡£Ò»·½Ã棬ѧÕßÒѾ֤Ã÷һάװÏäÎÊÌâÊÇÒ»¸öNPÄѶÈÎÊÌ⣬Òò´ËһάװÏäÎÊÌâ¾ßÓкܸߵÄÀíÂÛ¼ÛÖµ¡£ÁíÒ»·½Ã棬һάװÏäÎÊÌâ³öÏÖÔÚʵ¼ÊÉú²úµÄһЩÁìÓò£¬Òò´ËÒ²¾ßÓкܸߵÄʵ¼Ê¼ÛÖµ¡£
Æù½ñΪֹ£¬¹úÄÚÍâѧÕßÌá³öÁËÐí¶àÓÃÀ´Çó½âһάװÏäÎÊÌâµÄÑϸñËã·¨ºÍ½üËÆËã·¨¡£Ò»·½Ã棬ÑϸñµÄ×îÓÅËã·¨Ëù»¨Ê±¼äÌ«³¤£¬Êµ¼Ê²¿ÃÅÎÞ·¨ÈÌÊÜ¡£ÁíÒ»·½Ã棬½üËÆËã·¨ÓÉÓÚ¿ÉÄÜ¿ìËÙµØÉú³É×îÓŽâ»òÕß½Ó½ü×îÓŽâ¶øΪʵ¼ÊÉú²ú²¿ÃÅËù¹ã·º²ÉÓá£
ÈËÀà°ÑÎïÌåÍùÈÝÆ÷ÖÐ×°£¬ÒÑÓм¸Ç§ÄêÒÔÉϵľÑé¡£ÕâЩÉú»î¾Ñé¿ÉÒýµ¼³ö¸ßЧÂʵÄËã·¨¡£±¾ÎÄÌá³öÁËÒ»ÖÖÄâÈËËã·¨¡£Ëã·¨ÓÉÈý¸ö²¿·Ö×é³É¡£µÚÒ»²¿·ÖÊǽµÐò×î¼ÑÊʺÏËã·¨£¬ÓÃÓÚÉú³É³õʼ½â¡£µÚ¶þ²¿·ÖÊÇÁÚÓòËÑË÷Ëã·¨¡£¸ø¶¨Ò»¸ö½â£¬ÓÃÁÚÓòËÑË÷Ëã·¨¿ÉÒÔͨ¹ýµü´ú¸Ä½øÕâ¸ö½â¡£±¾ÎĵÄÁÚÓò¶¨ÒåµÄ˼ÏëÀ´Ô´ÓÚ¡°ÌìÖ®µÀËðÓÐÓà¶ø²¹²»×㡱¡£µÚÈý²¿·ÖÊÇÌø¿Ó²ßÂÔ¡£Ìø¿Ó²ßÂÔÓÃÓÚÌø³ö¾Ö²¿×îÓŽ⣬½«ËÑË÷ÒýÏòÓÐÏ£ÍûµÄÇøÓò£¬´Ó¶øÌá¸ßËã·¨µÄЧÂÊ¡£Ìø¿Ó²ßÂÔµÄ˼ÏëÀ´Ô´ÊÇ¡°ÈýÊ®Áù¼Æ×ßΪÉÏ¡±¡£
±¾ÎĵijÌÐò¼ÆËãÁËÒ»×é¹²17¸ö¹ú¼Ê¹«ÈϵÄÎÊÌâʵÀý¡£Õâ×éÎÊÌâʵÀý·ÖΪÁ½Àà¡£µÚÒ»ÀàΪ8¸öÎÊÌâʵÀý£¬Ä¿Ç°ÉÐδȷ¶¨Æä¿Í¹Û×îÓŽ⡣µÚ¶þÀàΪ9¸öÎÊÌâʵÀý£¬Ä¿Ç°ÒѾȷ¶¨ÁËÆä¿Í¹Û×îÓŽ⡣ÄâÈËËã·¨¶ÔµÚÒ»ÀàÎÊÌâʵÀýÖеÄ6¸öÎÊÌâʵÀýÕÒ³öÁËÓ뵱ǰÒÑÖª×îºÃ½âÖÊÁ¿ÏàͬµÄ½â¡£ÄâÈËËã·¨»¹Ö¤Ã÷ÁËTEST0068Õâ¸öÎÊÌâʵÀýµÄÄ¿Ç°ÒÑÖª×îºÃ½âÕýÊǿ͹Û×îÓŽ⡣ÄâÈËËã·¨¿ìËÙµØÕÒ³öÁ˵ڶþÀàÎÊÌâʵÀýÖÐÈ«²¿9¸öÎÊÌâʵÀýµÄ¿Í¹Û×îÓŽ⡣
¼ÆËã½á¹û±íÃ÷£¬ÄâÈËËã·¨ÊÇÒ»ÖÖÓÐЧµÄÇó½âһάװÏäÎÊÌâµÄ½üËÆËã·¨¡£
¹Ø¼ü´Ê£º NPÄѶȣ» ÄâÈË£» ÁÚÓòËÑË÷£» Ìø¿Ó£» ×°Ïä
Abstract
The one dimensional bin packing problem, which is a famous combinatorial optimization problem, comes from long term practice of human being. The definition of the one dimensional bin packing problem discussed in this paper is as following. Given items and enough identical bins, the weight of each item is a known positive real number. The capacities of all bins are equal. The problem is to pack all items into the bins with the objective of minimizing the number of occupied bins, subject to two following constraints. (1) Each item is packed into exact one bin. Each item cannot be divided into several parts and put into different bins. (2) The sum of weight of all items of each bin cannot exceed its capacity.
The one dimensional bin packing problem is of both highly theoretical and practical values. On one hand, the one dimensional bin packing problem has been proved to be NP-hard. On the other hand, the one dimensional bin packing problem appears in some real world factories.
So far, many exact algorithms and approximation algorithms have been proposed to solve the one dimensional bin packing problem. Exact algorithms require too much computing time and cannot be accepted by workers. On the other hand, approximation algorithms are widely used by workers, since they may give optimal or near optimal solutions quickly.
Mankind have more than several thousands of years of experience to pack items into containers. The experience can induce efficient algorithm. A quasi-human algorithm is presented in this paper, which is composed of three parts. The first part is best fit decreasing algorithm to generate initial solution. The second part is local search algorithm. Given a solution, local search algorithm is used to improve this solution by iterative steps. The idea of the definition of the neighborhood comes from a Chinese motto ¡°It is the Way of Heaven to diminish superabundance, and to supplement deficiency¡±. The third part is off-trap strategy, which is used to jump off local optimum and guide the search into promising areas, so as to improve the algorithm. The idea of the off-trap strategy comes from a Chinese motto ¡°decamping being the best¡±.
Computational experiments are carried out on a set of 17 benchmark problems. This set of 17 benchmark instances can be divided into two classes. The first class consists in 8 instances whose optimal solutions are still unknown. The second class consists in 9 instances whose optimal solutions are already known. For 6 out of 8 instances of the first class, our algorithm finds out solutions which are equal to the best known solutions up to now. Our algorithm proves that the best known solution for benchmark instance named as TEST0068 up to now is optimal. For all 9 instances of the second class, our algorithm finds out optimal solutions quickly.
The results show that the quasi-human algorithm is an efficient algorithm for the one dimensional bin packing problem.
Keywords: NP-hard; Quasi-human; Local search; Off-trap; Bin packing
-b..
Õª Òª
һάװÏäÎÊÌâÀ´Ô´ÓÚÈËÃǵij¤ÆÚÒÔÀ´µÄÉú²úʵ¼ù£¬ÊÇÒ»ÖÖ×éºÏÓÅ»¯ÎÊÌâ¡£¸ø¶¨ÓÐÇî¸öÎïÌ壬ÿ¸öÎïÌåµÄÖØÁ¿ÊÇÒÑÖªµÄÕýʵÊý¡£¸ø¶¨×ã¹»¶à¸ö¿ÕÏä×Ó£¬ÎÊÌâÊÇÒªÔÚÂú×ãÁ½¸öÔ¼ÊøÌõ¼þµÄÇ°ÌáÏ£¬½«ËùÓÐÎïÌå·Åµ½Ïä×ÓÖÐÈ¥£¬Ê¹µÃËùÓÃÏä×ӵĸöÊý¾¡¿ÉÄܵØÉÙ¡£Á½¸öÔ¼ÊøÌõ¼þÊÇ£ºµÚÒ»£¬Ã¿¸öÎïÌå¾ù±£³ÖÍêÕû£¬Ç¡ºÃ·Åµ½Ò»¸öÏä×ÓÖÐÈ¥¡£²»Äܽ«ÎïÌå·Ö¸î³É¼¸¿é¡£µÚ¶þ£¬Ã¿¸öÏä×ÓÖÐËù·ÅµÄÎïÌåµÄÖØÁ¿Ö®ºÍ¾ù²»Ä@@¬¹ýÒ»¸öÏàͬµÄÉÏÏÞ£¬Õâ¸öÉÏÏÞÊÇÒ»¸öÒÑÖªµÄÕýʵÊý¡£
һάװÏäÎÊÌâ¾ßÓкܸߵÄÀíÂÛ¼ÛÖµºÍʵ¼Ê¼ÛÖµ¡£Ò»·½Ã棬ѧÕßÒѾ֤Ã÷һάװÏäÎÊÌâÊÇÒ»¸öNPÄѶÈÎÊÌ⣬Òò´ËһάװÏäÎÊÌâ¾ßÓкܸߵÄÀíÂÛ¼ÛÖµ¡£ÁíÒ»·½Ã棬һάװÏäÎÊÌâ³öÏÖÔÚʵ¼ÊÉú²úµÄһЩÁìÓò£¬Òò´ËÒ²¾ßÓкܸߵÄʵ¼Ê¼ÛÖµ¡£
Æù½ñΪֹ£¬¹úÄÚÍâѧÕßÌá³öÁËÐí¶àÓÃÀ´Çó½âһάװÏäÎÊÌâµÄÑϸñËã·¨ºÍ½üËÆËã·¨¡£Ò»·½Ã棬ÑϸñµÄ×îÓÅËã·¨Ëù»¨Ê±¼äÌ«³¤£¬Êµ¼Ê²¿ÃÅÎÞ·¨ÈÌÊÜ¡£ÁíÒ»·½Ã棬½üËÆËã·¨ÓÉÓÚ¿ÉÄÜ¿ìËÙµØÉú³É×îÓŽâ»òÕß½Ó½ü×îÓŽâ¶øΪʵ¼ÊÉú²ú²¿ÃÅËù¹ã·º²ÉÓá£
ÈËÀà°ÑÎïÌåÍùÈÝÆ÷ÖÐ×°£¬ÒÑÓм¸Ç§ÄêÒÔÉϵľÑé¡£ÕâЩÉú»î¾Ñé¿ÉÒýµ¼³ö¸ßЧÂʵÄËã·¨¡£±¾ÎÄÌá³öÁËÒ»ÖÖÄâÈËËã·¨¡£Ëã·¨ÓÉÈý¸ö²¿·Ö×é³É¡£µÚÒ»²¿·ÖÊǽµÐò×î¼ÑÊʺÏËã·¨£¬ÓÃÓÚÉú³É³õʼ½â¡£µÚ¶þ²¿·ÖÊÇÁÚÓòËÑË÷Ëã·¨¡£¸ø¶¨Ò»¸ö½â£¬ÓÃÁÚÓòËÑË÷Ëã·¨¿ÉÒÔͨ¹ýµü´ú¸Ä½øÕâ¸ö½â¡£±¾ÎĵÄÁÚÓò¶¨ÒåµÄ˼ÏëÀ´Ô´ÓÚ¡°ÌìÖ®µÀËðÓÐÓà¶ø²¹²»×㡱¡£µÚÈý²¿·ÖÊÇÌø¿Ó²ßÂÔ¡£Ìø¿Ó²ßÂÔÓÃÓÚÌø³ö¾Ö²¿×îÓŽ⣬½«ËÑË÷ÒýÏòÓÐÏ£ÍûµÄÇøÓò£¬´Ó¶øÌá¸ßËã·¨µÄЧÂÊ¡£Ìø¿Ó²ßÂÔµÄ˼ÏëÀ´Ô´ÊÇ¡°ÈýÊ®Áù¼Æ×ßΪÉÏ¡±¡£
±¾ÎĵijÌÐò¼ÆËãÁËÒ»×é¹²17¸ö¹ú¼Ê¹«ÈϵÄÎÊÌâʵÀý¡£Õâ×éÎÊÌâʵÀý·ÖΪÁ½Àà¡£µÚÒ»ÀàΪ8¸öÎÊÌâʵÀý£¬Ä¿Ç°ÉÐδȷ¶¨Æä¿Í¹Û×îÓŽ⡣µÚ¶þÀàΪ9¸öÎÊÌâʵÀý£¬Ä¿Ç°ÒѾȷ¶¨ÁËÆä¿Í¹Û×îÓŽ⡣ÄâÈËËã·¨¶ÔµÚÒ»ÀàÎÊÌâʵÀýÖеÄ6¸öÎÊÌâʵÀýÕÒ³öÁËÓ뵱ǰÒÑÖª×îºÃ½âÖÊÁ¿ÏàͬµÄ½â¡£ÄâÈËËã·¨»¹Ö¤Ã÷ÁËTEST0068Õâ¸öÎÊÌâʵÀýµÄÄ¿Ç°ÒÑÖª×îºÃ½âÕýÊǿ͹Û×îÓŽ⡣ÄâÈËËã·¨¿ìËÙµØÕÒ³öÁ˵ڶþÀàÎÊÌâʵÀýÖÐÈ«²¿9¸öÎÊÌâʵÀýµÄ¿Í¹Û×îÓŽ⡣
¼ÆËã½á¹û±íÃ÷£¬ÄâÈËËã·¨ÊÇÒ»ÖÖÓÐЧµÄÇó½âһάװÏäÎÊÌâµÄ½üËÆËã·¨¡£
¹Ø¼ü´Ê£º NPÄѶȣ» ÄâÈË£» ÁÚÓòËÑË÷£» Ìø¿Ó£» ×°Ïä
Abstract
The one dimensional bin packing problem, which is a famous combinatorial optimization problem, comes from long term practice of human being. The definition of the one dimensional bin packing problem discussed in this paper is as following. Given items and enough identical bins, the weight of each item is a known positive real number. The capacities of all bins are equal. The problem is to pack all items into the bins with the objective of minimizing the number of occupied bins, subject to two following constraints. (1) Each item is packed into exact one bin. Each item cannot be divided into several parts and put into different bins. (2) The sum of weight of all items of each bin cannot exceed its capacity.
The one dimensional bin packing problem is of both highly theoretical and practical values. On one hand, the one dimensional bin packing problem has been proved to be NP-hard. On the other hand, the one dimensional bin packing problem appears in some real world factories.
So far, many exact algorithms and approximation algorithms have been proposed to solve the one dimensional bin packing problem. Exact algorithms require too much computing time and cannot be accepted by workers. On the other hand, approximation algorithms are widely used by workers, since they may give optimal or near optimal solutions quickly.
Mankind have more than several thousands of years of experience to pack items into containers. The experience can induce efficient algorithm. A quasi-human algorithm is presented in this paper, which is composed of three parts. The first part is best fit decreasing algorithm to generate initial solution. The second part is local search algorithm. Given a solution, local search algorithm is used to improve this solution by iterative steps. The idea of the definition of the neighborhood comes from a Chinese motto ¡°It is the Way of Heaven to diminish superabundance, and to supplement deficiency¡±. The third part is off-trap strategy, which is used to jump off local optimum and guide the search into promising areas, so as to improve the algorithm. The idea of the off-trap strategy comes from a Chinese motto ¡°decamping being the best¡±.
Computational experiments are carried out on a set of 17 benchmark problems. This set of 17 benchmark instances can be divided into two classes. The first class consists in 8 instances whose optimal solutions are still unknown. The second class consists in 9 instances whose optimal solutions are already known. For 6 out of 8 instances of the first class, our algorithm finds out solutions which are equal to the best known solutions up to now. Our algorithm proves that the best known solution for benchmark instance named as TEST0068 up to now is optimal. For all 9 instances of the second class, our algorithm finds out optimal solutions quickly.
The results show that the quasi-human algorithm is an efficient algorithm for the one dimensional bin packing problem.
Keywords: NP-hard; Quasi-human; Local search; Off-trap; Bin packing
-b..
