最小费用多集装箱装箱问题的研究

摘要

在集装箱装箱问题的研究中，最小费用多集装箱装箱问题是这样的一个分支：给定n种货物的集合和m种集装箱，每种集装箱都具有不同的价格并且可用的数量是没有限制的。问题的目标是使用最小的费用将所有的货物都装到集装箱中。相对于其他的装箱问题的分支，最小费用多集装箱装箱问题更具有现实意义。本文正是针对该问题进行的研究。
　　 最小费用多集装箱装箱问题是单集装箱装箱问题的扩展，比单集装箱装箱问题更加复杂难解。不但包括了单集装箱的摆放问题，还包含了集装箱与货物的对应分配问题，集装箱的选择问题等。显然不能通过简单的修改将一个单集装箱装箱算法改造为解决多集装箱问题的算法。并且由于多集装箱装箱问题需要解决大量的单集装箱装箱问题，因此需要一个快速有效的单集装箱装箱算法。本文通过对该问题的深入研究，找出了该问题的关键点并一个个地进行了有效的解决，提出了2个用于求解单集装箱装箱问题的快速算法作为求解多集装箱问题的子过程。并提出了一个基于模式生成的用于求解最小费用多集装箱装箱问题的算法框架。最后针对现有的测试数据的不足，提出了一种产生已知最优解的测试数据的方法。这些数据能帮助更好地评价单集装箱，多集装箱算法的性能。通过对标准数据和产生数据的测试，说明了本文所提出的算法是有效的。