物流公司在流通过程中，需要将打包完毕的箱子装入到一个货车的车厢中，为了提高物流效率，需要将车厢尽量填满，显然，车厢如果能被100%填满是最优的，但通常认为，车厢能够填满85%，可认为装箱是比较优化的。

设车厢为长方形，其长宽高分别为L，W，H；共有n个箱子，箱子也为长方形，第i个箱子的长宽高为li，wi，hi**（n个箱子的体积总和是要远远大于车厢的体积）**，做以下假设和要求：

1. 长方形的车厢共有8个角，并设靠近驾驶室并位于下端的一个角的坐标为（0,0,0），车厢共6个面，其中长的4个面，以及靠近驾驶室的面是封闭的，只有一个面是开着的，用于工人搬运箱子；

2. 需要计算出每个箱子在车厢中的坐标，即每个箱子摆放后，其和车厢坐标为（0,0,0）的角相对应的角在车厢中的坐标，并计算车厢的填充率。

问题分解为基础和高级部分。

基础部分：

1. 所有的参数为整数；
2. 静态装箱，即从n个箱子中选取m个箱子，并实现m个箱子在车厢中的摆放（无需考虑装箱的顺序，即不需要考虑箱子从内向外，从下向上这种在车厢中的装箱顺序）；
3. 所有的箱子全部平放，即箱子的最大面朝下摆放；
4. 算法时间不做严格要求，只要1天内得出结果都可。

高级部分：

1. 参数考虑小数点后两位；
2. 实现在线算法，也就是箱子是按照随机顺序到达，先到达先摆放；
3. 需要考虑箱子的摆放顺序，即箱子是从内到外，从下向上的摆放顺序；
4. 因箱子共有3个不同的面，所有每个箱子有6种不同的摆放状态；
5. 算法需要实时得出结果，即算法时间小于等于2秒。

C：(L, W, H) 分别表示车厢的长宽高

B：[(l1, w1, h1, n1), (l2, w2, h2, n2)....] 分别表示各个种类箱子的长宽高和个数

对于每次实验
	利用染色体双倍体编码方案初始化种群
	对于每次迭代
		利用锦标赛选择算法选择父母个体，交叉产生子个体，再对子个体进行变异
		计算原始种群和新种群的适应值，保留适应值较大的个体

对于B中的每个箱子bi
    对于每种摆放方式
        对于R中的每个剩余空间rj
            if 剩余空间rj能容纳箱子bi
                计算f(bi,rj)
    对所有的f(bi,rj)进行排序并选f(bi,rj)最大的放置方式
    放置箱子
    更新剩余空间集合

python==3.9
numpy==1.21.5
matplotlib==3.5.1

遗传算法

# 运行
# 切换至项目文件目录下
python problem1.py
# 关闭所有画图窗口则程序执行结束，或Ctrl+C

# 参数
ITERATIONS = 1  # 实验次数
INDIVIDUALS = 36  # 种群个体数量
GENERATIONS = 400  # 一次实验种群要迭代几次，若要快速执行可以使用较小的数
PC = 0.8  # 交叉概率
PM1 = 0.2  # 变异概率，序列
PM2 = 0.02  # 变异概率，面
ROTATIONS = 2  # 2种摆放方式
# 保存结果路径，“当前项目文件夹/results/p1_时间”文件夹下
loca = time.strftime("%Y-%m-%d-%H-%M-%S")
new_dir_path = r'./results/p1_' + loca

# 若不想显示画图窗口注释掉problem1.py最后一行的plt.show()

最优剩余空间算法

# 运行
# 切换至项目文件目录下
python problem2.py
# 关闭所有画图窗口则程序执行结束，或Ctrl+C

# 参数
a = 0.1  # 评价函数中的权重大小
# 保存结果路径，“当前项目文件夹/results/p2_时间”文件夹下
loca = time.strftime("%Y-%m-%d-%H-%M-%S")
new_dir_path = r'./results/p2_' + loca

# 若不想显示画图窗口注释掉problem2.py最后一行的plt.show()

[1] 李威,王士乾.三维装箱问题研究现状与展望[J].电脑知识与技术,2021,17(08):204-205+222.DOI:10.14004/j.cnki.ckt.2021.0694.

[2] 李孙寸,施心陵,张松海,董易,高莲.基于多元优化算法的三维装箱问题的研究[J].自动化学报,2018,44(01):106-115.DOI:10.16383/j.aas.2018.c160381.

[3] 朱向,雷定猷.带平衡约束三维装箱问题的双层混合遗传算法[J].交通运输系统工程与信息,2015,15(02):203-209.DOI:10.16097/j.cnki.1009-6744.2015.02.031.

[4] Andreas Bortfeldt, Hermann Gehring. A hybrid genetic algorithm for the container loading problem. European Journal of Operational Research. Vol. 131, Issue 1, pp. 143-161, 2001.

[5] 李昱蓉,侯波.集装箱单箱三维装载问题研究[J].物流科技,2013,36(12):71-74+77.

[6]尚正阳,顾寄南,唐仕喜,孙晓红.高效求解三维装箱问题的剩余空间最优化算法[J].计算机工程与应用,2019,55(05):44-50.