摘要：手术计划是优化医疗资源配置的重要组成部分,涉及众多的不确定性,是目前医疗管理领域研究的热点和难点问题.本文聚焦于考虑急诊病人随机手术时长需求的择期病人手术计划问题研究,在各个手术室具有异质性的情况下,优化手术室的超时成本和闲置成本,并为一个计划周期内的择期手术进行手术室和手术日期的分配.建立了一个0-1整数规划模型,针对问题情境和手术计划特有的约束条件提出了满足问题特性的分支定界和列生成相结合的精确型分支定价求解算法.其中在分支定界算法上,通过对比选择适合问题特性的节点选择策略,并且提出了分步分支策略加快搜索过程.为加快列生成算法的求解,通过数值积分和等价转换将带有不确定性的子问题转变为一个0-1背包问题的变形,然后设计动态规划算法进行求解.数值实验表明,根据问题特性设计的分支定价算法可有效求解具有不同实例规模下的手术计划问题,和CPLEX相比,大规模情形下能够在可接受的计算时间内得到问题最优解.

摘要：资源受限项目调度问题是最具代表性的一类项目调度问题,是很多实际调度问题的抽象表示,属于NP-hard问题,对于大规模问题难以求得全局最优解。文中提出了问题的整数规划模型,通过将模型分解为约束主问题和子问题设计了求解线性松弛模型的列生成方法,然后通过分支定价寻找问题的整数解。在求解过程中引入松弛变量解决模型伪不可解的问题,设计了剪支策略和分支策略,并根据不同情况提出了两种缩小解空间的方法。在PSPLIB基准数据集上,对于有30个工序的问题,所提算法在10 m内能够求出480个问题中的301个问题的当前最优解;对于有60个工序的问题,在20 m内能够求出480个问题中的269个问题的当前最优解;对于有90个工序的问题,在30 m内能够求出480个问题中的263个问题的当前最优解。同时,算法使用缩小解空间策略后,超时算例的个数明显减少,优化初始解的性能得到明显提升。以上实验结果表明,所提算法具有较好的求解能力。

摘要：近年来,无人机调度受到了学者们的日益关注.本研究提出了考虑无人机站的车辆路径规划问题,以总成本最低为目标函数,考虑了包裹的最晚送达时间、无人机的数量限制和最长可持续飞行时间等约束条件.针对该问题本研究首先构建了一类基于弧的原问题模型.随后,使用Dantzig-Wolfe分解,将原问题模型分解为基于路径的限制主问题模型和卡车子问题模型以及无人机子问题模型,并设计了分支定价算法进行求解,以获得全局最优解.大量的数值实验结果表明分支定价算法在求解时间和求解质量上均优于主流商业求解器.此外,本研究发现卡车的行驶成本在总成本中占据较高比例.同时,相对于无人机的数量和无人机与卡车的速度比而言,无人机可访问的顾客的比例对总成本有显著影响.因此,扩大无人机的适用范围,可以有效地降低总成本.

摘要：针对物流配送系统优化设计中关键难题之一的团队定向问题,提出了一种部分顾客需求动态到达的动态团队定向问题,并建立了该问题的模型.采用把规划周期分成一系列时间段的策略,将动态问题转化成一系列的静态子问题求解.提出了一种蚁群算法,其特点是利用上一时间段的信息来加速算法寻优能力,并用一种基于分支定价的离线精确性算法来求解动态团队定向问题.实验结果表明,与基于分支定价的离线精确性算法相比,所提出的蚁群算法能在1 ks内求解4个测试算例,并且在2个算例中得到的最好解优于离线精确性算法的解.

摘要：为有效解决当前城市环卫车调度决策过度依赖人工主观经验造成的车辆配置不合理和作业效率低下问题,本文提出一种多约束条件下的城市道路环卫车优化配置与路径规划方法。通过综合考虑环卫车在现实作业中的作业时限、服务次数、行驶速度和车辆退出节点等多种约束条件,将物理道路网络拓展为时空网络,刻画车辆在路网上的时空运行轨迹,进而将环卫车优化配置与路径规划问题从数学上描述为带多类约束条件的弧路径问题(Arc Routing Problem, ARP)。在此基础上,构建以车辆配置与出行总成本最小化为目标函数的环卫车优化配置与路径规划模型,并通过设计分支定价算法精确求解模型。将所提方法应用于苏州工业园区19个区域路网的环卫车辆配置与调度管理,从经济成本、作业效率和环保效益这3方面评估所提方法的可行性和有效性。结果表明:本文所提方法能够显著节约环卫运营成本,提升环卫车辆作业效率;同时,可有效降低环卫车辆碳排放量,形成良好的经济和社会效益,为智慧环卫提供了行之有效的新方案。

摘要：停机位指派问题是机场运营管理的核心问题。现有的停机位指派问题研究集中在提高停机位的利用效率上,而忽略了停机坪的运行安全。针对这一问题,本文以最大化近机位利用率和最小化鲁棒性损失为目标,提出一个考虑港湾安全约束的停机位指派模型;提出一种可精确求解面向港湾机坪的停机位指派问题的分支定价算法;利用机场实际数据验证提出的模型和算法。实验结果表明,在小、中、大规模算例中分支定价的最优解比CPLEX分别改进了0.3%、17.3%、26.7%,在中大规模算例中有明显的优势。在小、中、大规模算例中,本文的设计能分别预先避免27.16%、16.35%、11.01%的航空器发生港湾冲突。在提高近机位利用率和指派计划鲁棒性的同时,提高了机坪的安全性。

摘要：随着节能减碳的需求和人工智能的快速发展,以无人电动车等为配送装置的城市无人物流配送渐成现实。本文考虑电池容量约束和取送货同时装载容量约束,以最小配送成本为目标函数构建数学规划模型(E-VRPSDP);以列生成法和双向动态标签算法为基础,设计了分支定价算法实现模型的精确求解;针对大规模E-VRPSDP,设计改进模拟退火算法,引入构造可行解算子,将原始解进化成符合约束的可行解,提高了算法的搜索能力;最后,利用已有标准测试集生成测试算例以验证所设计的算法。本文可以为城市无人物流配送的发展提供理论指导和算法支持。

摘要：国内很多航空公司多基地间存在机组人员和航班任务数量不匹配的情况,导致各基地生成的任务环在机组派遣阶段难以被很好地执行,因此需在任务环生成阶段生成适量的可满足机组人员跨基地支援的任务半环,而传统的生成完整任务环的方案难以适用于该情况。在该问题中,通过顺序方法找到全局最优解是不可能的,因为在配对问题中做出的决策减少了机组分配问题的决策域。对此,创新性地提出了任务半环生成方案,并且创建基于时空网络的集合划分模型,分析任务半环生成总量约束的子问题目标函数项对列生成求解框架的影响,提出可以有效消除该影响的分治策略,采用实际数据验证算法可行性和有效性。与传统的方法相比,可显著节省成本并更好地满足机组人员分配不平衡问题。