# CPIPC2021-F

**Repository Path**: JasonXiao999/CPIPC2021-F

## Basic Information

- **Project Name**: CPIPC2021-F
- **Description**: No description available
- **Primary Language**: Python
- **License**: MIT
- **Default Branch**: main
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2024-07-30
- **Last Updated**: 2024-07-30

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# CPIPC2021-F
“华为杯”第十八届中国研究生数学建模竞赛F题求解参考。最终结果是二等奖，在所有F题队伍中排名第三十，还不错啦。

## 我们来自东南大学

![东南大学计算机科学与工程学院](http://ehall.seu.edu.cn/new/portal/custom/img/logo/logo-mini.png)

## 方法

建立了基于0-1整数规划的数学模型，求解上对数据规模较小的A数据集使用Gurobi线性规划求解器进行。对多目标优化问题，我们采用了分阶段求解的策略，模型首先优化第一优先目标，再将计算得到的这一目标作为约束加入模型，优化次要目标。

对于问题二三，为了简化模型的求解，将数据集按照天数均分为了两个部分分别求解。

对数据规模较大的B数据集使用基于贪心策略的优化算法进行。

## 程序运行相关

### 运行程序所需要的软件环境

- Python 3.x
- Gurobi 9.x

如果需要运行贪心程序，还需要有G++编译器来对CPP程序进行编译再进行执行。

### 运行程序所需要的硬件环境

若想完整运行全部程序，建议在一台32G及以上内存电脑上执行。

### 如何运行？

关于数据集A，三个问题分别对应三个`jupyter notebook`：q1 q2 q3，分别打开运行即可，但由于是分阶段优化，其中可能有一些需要手动调整的内容，详细可以看diamagnetic注释。

对于数据集B，已经提前准备好了`Makefile`文件，`make`编译即可，随后运行对应的三个exe文件：1b 2b 3b。

## 结果

在论文中，我们的利用率计算方式和题目的说明有所不同，我们的计算方法是

`机组总体利用率=使用到的机组人员/总机组人员数`，这里有些不妥，是一个比较大的失误，按理说应该用题目所要求的方式进行计算。

**A数据集的结果展示**

| 结果指标                       | 子问题1 | 子问题2       | 子问题3        |
| ------------------------------ | ------- | ------------- | -------------- |
| 不满足机组配置航班数           | 0       | 0             | 0              |
| 满足机组配置航班数             | 206     | 206           | 206            |
| 机组人员总体乘机次数           | 8       | 21            | 56             |
| 替补资格使用次数               | 0       | 0             | 74             |
| 最大/平均/最大一次执勤飞行时长 |         | 65/147.02/520 | 65/298.51/775  |
| 最小/平均/最大一次执勤执勤时长 |         | 65/162.29/680 | 65/374.35/855  |
| 最小/平均/最大机组人员执勤天数 |         | 15/15/15      | 4/8/12         |
| 一/二/三/四天任务环数量分布    |         |               | 190/105/70/135 |
| 总体执勤成本（万元）           |         | 53.3473       | 53.1256        |

**B数据集的结果展示**

| 结果指标                       | 子问题1 | 子问题2       | 子问题3        |
| ------------------------------ | ------- | ------------- | -------------- |
| 不满足机组配置航班数           | 543     | 2272          | 9185           |
| 满足机组配置航班数             | 13411   | 11682         | 4769           |
| 机组人员总体乘机次数           | 0       | 0             | 0              |
| 替补资格使用次数               | 12      | 12            | 2              |
| 最大/平均/最大一次执勤飞行时长 |         | 45/220.81/545 | 50/235.06/545  |
| 最小/平均/最大一次执勤执勤时长 |         | 45/316.00/720 | 50/327.10/720  |
| 最小/平均/最大机组人员执勤天数 |         | 0/21.72/31    | 0/8.37/16      |
| 一/二/三/四天任务环数量分布    |         |               | 1566/120/24/17 |
| 总体执勤成本（万元）           |         | 3341.53       | 1335.75        |

## 联系我们

关于模型问题请联系队长 :mailbox: seiraa@126.com

关于贪心策略的讨论可以联系[lwzjb6](https://github.com/lwzjb6)

关于程序及其他问题欢迎写在issues中~