出租车调度问题是交通运输与智能制造等领域中的重要问题, 其应用场景在生产生活中广泛存在. 出租车调度问题主要研究如何确定一系列从同一个车库出发的出租车的行驶路径, 在每辆车均不超载且在指定时间窗内到达接送订单起点和终点的前提下, 确保各乘客的乘车时间和各车辆的行驶时间分别不超过给定上限, 在此基础上最小化所有车辆的行驶时间之和. 比如网约车平台的派单过程中, 出租车同时能服务的订单数或搭载的乘客人数 (拼车) 有限, 且每个订单的对上下车时间有要求, 网约车平台需要调度出租车用最短的工时完成所有接送订单. 比如芯片代工厂中的物料传送系统的运行过程中, 运输车能够装载的晶圆数量有限, 且上层生产排程系统对每道工序的开工时间有要求, 物料传送系统需要调度运输车用最短的时长完成所有运输任务. 因此, 高效的出租车调度问题的求解算法在理论上与实践上均意义重大.

使用 Gitee 挺长一段时间了, 感觉它是一个非常优秀的国内免费代码托管平台. 美中不足的是, 它不支持对常见的数据文件格式进行渲染. 其中就有 CSV 等纯文本表格文件, 在没有按列对齐的情况下可读性相对较低. 作为一个程序员, 当然要自己动手丰衣足食. 下面简单记录一下我的魔改方案 (该方案已发布至 https://greasyfork.org/zh-CN/scripts/446381-gitee-csv-formatter 可以一键安装). 此外, 顺便夹带一点关于表格 CSS 样式设置的小技巧.

与本科数据结构和算法设计与分析课程中学习的 P 问题不同, NP 难组合优化问题的计算复杂度随问题规模增长及其迅速. 因此, 在具有现实意义的问题实例上, NP 难组合优化问题的求解算法不仅有对错之分, 还有优劣之分. 由于 NP 难问题的计算复杂性, 有实际应用价值的算法通常不像 P 问题的求解是一个确定的过程, 得到正确的结果后退出. 相反地, NP 难问题的优化算法需要在计算时间与结果优度之间寻找合适的平衡点, 因此往往使用具有随机性的迭代优化的启发式算法. 为确保结果的可重现性, 启发式算法通常需要支持设置随机种子, 而其停止条件通常为由用户指定计算时间上限, 以避免对庞大的解空间进行永无止尽的探索. 此外, 相比于 P 问题求解算法的简明扼要, NP 难问题的求解算法往往是个庞大的工程, 同时有可能作为子模块接入到更复杂的系统中, 因此还需要满足软件工程的要求. 下面, 我们将以中心选址问题为例, 简单介绍本 NP 难组合优化问题算法测试平台的基本功能与使用方式.

圆形容器内的等圆装配问题在众多领域中有广泛的应用, 可以用来对多种组合优化问题进行建模. 圆形容器内的等圆装配问题主要研究使用大圆装小圆的问题. 例如, 光纤电缆的制造与建筑材料运输等众多应用场景都可以建模为等圆装配问题. 在理论上, 等圆装配问题是经典的非线性连续优化问题, 其求解算法往往还涉及物理系统模拟. 高效的等圆装配问题求解算法具有极其重要的理论与应用价值.

团队的主要构成成份是什么? 显然是人. 所以一个团队要发展壮大, 首先要有人, 其次要有人和, 最好还要有能人. 其中人和决定了团队生命力的下限, 而能人决定了其上限. 实现人和是门大学问, 本人水平有限, 在此不作展开, 先以能人为切入点, 做一些浅显的探讨.

如何聚集能人? 从另一个角度来看, 事在人为, 因此这个问题可以变为建设一个团队需要什么样的人.

最小连通支配集问题在众多领域中有广泛的应用, 可以用来对多种组合优化问题进行建模. 最小连通支配集问题主要研究如何挑选一系列紧密相连的节点为其他节点提供服务的问题. 例如, 通信网络, 能源传输, 物流调拨等众多行业中的选址都可以用最小连通支配集问题进行建模. 高效的最小连通支配集问题求解算法具有极其重要的理论与应用价值.

反馈点集问题在众多领域中有广泛的应用, 可以用来对多种组合优化问题进行建模. 有向反馈点集问题主要研究如何消除有向拓扑图中的环路问题. 比如在操作系统解决死锁时, 需要尽可能少地强行终止用户进程. 比如以层次图模式绘制思维导图或电路原理图时, 需要尽量避免出现逆向边. 高效的反馈点集问题求解算法具有极其重要的理论与应用价值.

斯坦纳树问题是芯片设计, 管道规划与网络设计等领域中的重要问题, 应用场景十分广泛. 而避障直线最小斯坦纳树问题作为一类特殊的斯坦纳树问题, 是数字电路物理设计中全局布线环节的核心问题之一. 避障直线最小斯坦纳树问题主要研究如何用不穿过障碍的正交线段将平面上的一系列节点连接起来, 使得线段总长度最短的问题. 比如在 ASIC 的经典设计流程中, 需要在所有元件布局已经固定的情况下为每个网规划无短路和断路的导线连接方案. 比如在 FPGA 的物理综合过程中, 需要确定逻辑门阵列间的数据通路以实现目标电路的功能. 因此, 高效的避障直线最小斯坦纳树问题的求解算法具有极其重要的理论与应用价值.

羽毛球是一种技巧性很强的运动, 新手想要提高球技, 最大的困难往往在于纠正姿势. 不正确的姿势往往无法快速跑位导致接不到球, 或者接到回球质量很差打不到位, 长此以往还容易导致运动损伤. 相反地, 正确的姿势能够充分发挥全身的力量, 击球质量高打得有来有回不仅观赏性强, 锻炼效果也更好.

带时间窗的车辆路由问题是交通运输与物流配送等领域中的重要问题, 其应用场景在生产生活中随处可见. 带时间窗的车辆路由问题主要研究如何确定一系列从同一个仓库出发的车辆的行驶路径, 在每辆车均不超载且每个客户都在给定时间窗内被访问的前提下, 最小化所有车辆的行驶时间之和. 比如快递配送过程中, 配送员能携带的物品重量有限, 同时每个客户只在特定的时段内有空收件, 快递公司需要调度配送员用最短的工时完成所有配送任务. 相反地, 在物流公司提供上门取件服务时, 揽件人员也会面临同样的优化问题. 因此, 高效的带时间窗的车辆路由问题的求解算法在理论上与实践上均意义重大.