带时间窗的车辆路由问题是交通运输与物流配送等领域中的重要问题, 其应用场景在生产生活中随处可见.
带时间窗的车辆路由问题主要研究如何确定一系列从同一个仓库出发的车辆的行驶路径, 在每辆车均不超载且每个客户都在给定时间窗内被访问的前提下, 最小化所有车辆的行驶时间之和.
比如快递配送过程中, 配送员能携带的物品重量有限, 同时每个客户只在特定的时段内有空收件, 快递公司需要调度配送员用最短的工时完成所有配送任务.
相反地, 在物流公司提供上门取件服务时, 揽件人员也会面临同样的优化问题.
因此, 高效的带时间窗的车辆路由问题的求解算法在理论上与实践上均意义重大.
很欣慰地看到, 国家越来越重视竞赛了, 各个教育阶段的升学和考核等政策都在逐步向有竞赛成果的人倾斜.
相比于论文, 大部分竞赛有相对客观的评价标准, 第一只有一个, 很难出现大量无意义的低质量的重复研究.
因此, 后来者无需花费大量时间甄别前人到底尝试过哪些方法, 其中哪些是有效的, 哪些是无用的.
下面将简单列举一下与运筹优化相关的竞赛.
多年以前曾经有过一段与统一建模语言与通用求解器相关的意识流 (数据库中的搜索, 组合优化问题的搜索, 统一建模语言与通用求解器).
最近机缘巧合, 又遇到了这个话题, 于是又做了进一步的思考.
总的来说, 如果能设计一个能与针对特定问题的专用算法相媲美的通用求解器, 无论是精确还是近似, 其实际应用价值不亚于证明 P = NP.
可惜, 天上不会掉馅饼, 一个高价值的问题, 难度往往也不会低.
矩形装箱问题是物流运输, 芯片制造与游戏开发等领域中的重要问题, 应用场景十分广泛.
矩形装箱问题主要研究如何将一系列矩形块不重叠地摆放至矩形容器中, 使得容器面积最小的问题.
比如玻璃制造过程中, 要在原料 (大矩形) 上进行切割得到一系列成品 (小矩形).
比如在集成电路的物理设计中, 需要用最小的面积排布大量宏单元和标准单元以节约成本.
比如在游戏贴图加载时, 需要将若干矩形图片拼合成大块的矩形图像以充分发挥显存性能.
因此, 高效的矩形装箱问题的求解算法具有极其重要的理论与应用价值.
路由与波长分配问题是通信领域中的重要问题, 具有较高的实际应用价值.
路由与波长分配问题主要研究如何为通信业务规划传输路径并分配波长, 使得所有业务可以在互不干扰的情况下传输.
高效的路由与波长分配问题的求解算法对提高网络的传输效率具有意义重大.
同时, 路由与波长分配问题还与多智能体路径规划以及芯片布线十分相似, 具有重要的理论意义.
柔性作业车间调度问题是智能制造与高性能计算等领域中的重要问题, 具有广泛应用场景.
柔性作业车间调度问题主要研究如何调度有限的资源依次执行多项任务, 使得完成所有任务的完工时间最短的问题.
比如芯片代工厂生产芯片时, 每块晶圆需要在不同机台依次完成光刻与蚀刻等多道工序.
比如在某些大规模并行计算场景中, 计算任务间存在依赖关系, 后继任务的输入为前驱任务的输出.
高效的柔性作业车间调度问题的求解算法具有极其重要的理论与应用价值.
中心选址问题是通信与物流等领域中的重要问题, 其背后的单一成本集合覆盖问题更是用途广泛.
中心选址问题和单一成本集合覆盖问题主要研究如何使用有限的资源提供尽可能高质量的服务的问题.
例如, 移动基站, 消防站, 物流仓库, 数据中心等众多设施的选址都可以建模为中心选址问题.
高效的中心选址或单一成本集合覆盖问题的求解算法具有极其重要的理论与应用价值.
图着色问题在众多领域中有广泛的应用, 可以用来对各种各样的组合优化问题进行建模.
图着色问题主要研究独占资源的分配问题.
比如在编译器给变量分配寄存器分配时, 如果两个变量的生命周期有交集, 则不能分配至同一寄存器.
比如在机场分配停机位时, 如果两架飞机的过站时间有交集, 则不能分配至同一停机位.
比如在光纤网络中进行波长分配时, 如果两条光路经过同一条链路, 则不能使用同一波长传输.
比如移动基站进行通讯频率分配时, 如果两个终端设备位于同一组天线的覆盖范围内, 则不能使用同一通讯频率.
比如在学校排课表时, 如果两个班级要上同一位教师的课, 则其上课时间不能相同.
高效的图着色问题求解算法具有极其重要的理论与应用价值.
虽然目前最顶尖的商业求解器已经非常高效, 直接求解完整的问题模型往往比普通人自己实现算法性能更好, 但是面对特定的问题, 仍然有改进空间.
另一方面, 先贤们告诉我们要站在巨人的肩膀上, 要重用前人的优秀成果.
于是, 我们可以得到一个在完全自行设计算法和完全使用通用求解器之间的折中的方案, 发挥多种方法各自的优势, 更好地解决问题.
算法研发和常规软件开发十分相似, 但也有很多区别.
大多数工程项目往往更注重正确性, 为了提升代码的健壮性与可维护性, 可以适当牺牲性能.
而设计精妙的高效而复杂算法代码往往具有极高的耦合度, 难以进行系统的单元测试.
此外, 算法面临的需求往往不那么简单直接, 不是梳理清楚了业务逻辑就能欢快地敲代码了的.
算法研发真的这么任性吗?