摘要：电动汽车的充电站选址问题是当前社会的热点问题,其实质是组合优化中经典的NP-hard问题。基于最小开设费用对充电站选址问题进行研究,首先对该问题进行了数学建模,进而研究了该问题的数学性质并给予相应的证明,利用这些性质减小问题的规模,从而降低问题的求解难度;然后设计了上下界子算法以及降阶子算法,基于这些子算法提出了一种可以快速缩小问题规模同时得到最优解的分支定界算法,降低了时间复杂度,同时可以对解空间进行大量剪枝加快求解速度;最后通过分析和求解一个示例来进一步阐述所提算法的原理和执行过程。

摘要：资源的多技能和时间窗属性是软件开发、工程设计、设备维修等领域在人力资源调度时常考虑的关键因素,而且在很多实际项目中,任务的执行允许中断.研究一类资源具有多技能和时间窗约束的任务可中断项目调度问题,建立了相应的整数规划模型,设计了一种分支定界算法构造搜索树进行求解,搜索树的每个节点代表一个任务组合,同时为减少分支节点数,提出了两个有效的剪枝规则,并设计了节点优先规则,对各节点任务组合则采用贪婪算法来进行资源约束判断.利用改进的PSPLIB案例库设计多组计算实验,实验结果检验了优选策略的有效性,经与CPLEX模型求解和基本启发式方法的对比揭示了算法在解决这类问题上的效率和有效性,求解结果可为实际项目调度提供决策依据.

摘要：研究带装载组合约束的出厂物流装箱问题的精确算法和启发式算法,问题的优化目标是最大化装载商品车数量的同时最小化使用承运车数量,其中装载组合约束是指每辆承运车所能装载商品车的类型和数量是给定的。数值实验和案例分析表明,设计的分支定界算法都能够有效提高求解效率并应用于实际情况。

摘要：针对阻塞混流生产机器人制造单元调度问题,为了同时优化机器人运行顺序和工件加工顺序,提出了分支定界算法。首先,定义机器人活动,将双排序转化为单排序;其次,构建顺序插入规则生成可行解;最后,依据顺序插入规则,设计了分支过程。通过计算随机生成算例,计算结果表明:工作站个数为3时,分支定界算法得到的目标函数值与CPLEX相同,但平均运行时间比CPLEX降低38.58%,证实了分支定界算法的有效性;工作站个数大于3时,与CPLEX相比,在同等时间内,有85.19%的算例搜索到更好解,因此,对于大规模情形,分支定界算法更有价值。

摘要：给出了一类加工需要额外资源的平行机调度问题的精确算法。针对在平行机上加工的工件,除需要机器资源外,还需要一个单位额外资源的问题,考虑额外资源的种类和数量有限,以给出问题的最优调度使工件的完工时间最小为目标。该问题源于地球观测卫星的数据下载,在智能制造和信息处理等领域亦有广泛应用。给出了该问题的整数规划模型、最优解下界和分支定界算法;给出了一种有效的分支策略以避免重复分支,设计了相应的定界方法以提高算法的收敛速度。通过小规模实例和大量的数值仿真实验,验证了算法的正确性和在不同参数配置下的有效性。

摘要：研究具有入树约束的两台同类机排序问题,工件具有不同的到达时间且具有单位的加工时间,目标为极小化最大完工时间.对于该NP-难问题,首先设计了一个分支定界算法并证明了算法的最优性.然后通过一个具体算例,详细验证了算法的执行过程.

摘要：旅行商问题是一个经典的组合优化问题。为快速求解旅行商问题,设计了由图嵌入网络、图卷积神经网络、注意力神经网络和多层感知机组合而成的深度学习模型的学习分支规则,通过改进传统的分支定界算法提高算法性能。对15个城市的旅行商问题实例进行监督训练,并在SCIP求解器上分别测试10,15,20,25和30个城市的旅行商问题实例。发现:基于学习分支规则的分支定界算法的求解时间比基于传统分支规则的分支定界算法的求解时间分别快-0.0022 s,0.0178 s,1.7643 s,2.3074 s和2.0538 s。因此,基于图神经网络的分支变量选择对传统分支规则的改进是有效的,可以较好地泛化到训练规模更大的旅行商问题实例中。

摘要：智能手机装配品种多、批量小及交期紧迫的特点,导致其生产组织常面临高频换产情境,给其订单调度提出了很高的要求。为此,提出一种考虑生产线重构约束的订单调度优化方法。描述了手机装配线订单调度问题,并以最小化换产与库存成本为目标建立了数学模型;设计了一种基于可行域的多叉树分支定界算法对模型进行求解,并与遗传算法进行了性能对比;通过智能手机装配生产线的应用案例及影响因素敏感度分析,验证了所提优化方法的有效性、优越性及应用价值。

摘要：针对编制开行方案涉及因素多、建模及求解困难的特点,结合有容量限制的多商品流网络设计问题,建立确定列车开行对数、开行区段、停站方案及编组形式的多目标整数规划模型,运用权重法将多目标规划转化为单目标规划。鉴于标准的列生成算法难以协同处理网络设计与网络配流问题,设计综合使用列生成与行生成策略的启发式算法确定列车的运行路径及停站方案,采用改进分支策略的分支定界算法求解最终模型。最后,以京沪高铁为例进行验证,在有效时间内获得较高质量解,该解与最优解的误差率为2.13%,且优于京沪高铁实际采用的开行方案。

摘要：结合单相智能电能表计量电能准确度要求高的特点,建立描述批次单相智能电能表基本误差一致性的模型,提出相应的容差设计优化目标及约束条件。利用整数规划思想,提出一种面向离散型设计变量的容差设计方法。在此基础上,以加工成本作为优化目标、计量误差的变化范围作为约束条件,对某型号单相智能电能表的计量电路进行容差设计优化。通过设置不同的误差变化范围界限值,获得相应的元器件公差等级和成本值。优化结果表明,所提方法在控制误差变化范围的同时,有效地将成本最小化,适用于单相智能电能表计量电路的容差设计。