两阶段法求解1.5维切割问题

切割问题亦称为下料问题.多维切割问题是机加工、木材加工和造纸等行业在生产中经常遇见的实际问题.1.5维切割问题是介于一维和二维切割问题之间的一类问题.针对1.5维切割问题的特殊性,采用两阶段方法进行求解.第一阶段是将1.5维切割问题转化为一维切割问题,第二阶段首先利用一种启发式算法得到一组初始解,然后使用粒子群算法对初始解进行优化,得最终解.     

考虑动态度和时间窗的两级车辆路径问题

为应对由客户的动态需求、大型货车的限行政策及配送时间窗的限制给供应商制定科学配送计划带来的严峻挑战,设计考虑动态度和时间窗的两级车辆路径优化方法。该方法基于客户动态增量概率阈值及动态度构建响应增量需求的车辆路径更新策略;将连续两级车辆路径优化问题映射为由配送中心到中转站和由中转站到客户的两个子网络的带时间窗的车辆路径问题(VRPTW),并在并行模拟退火算法框架下融合Or-opt, 2-opt, 2-opt^*,Swap/shift 4种邻域搜索策略求解VRPTW。用数据案例对模型及算法进行验证,表明所提策略及方法能较好地满足供应商对客户动态需求的响应,且具有良好的鲁棒性。     

基于两阶段狼群算法的自动化立体仓库作业集成优化

为提高单载具自动化立体仓库动态工况下的进出库效率,针对自动化立体仓库作业集成优化问题建立了仿真优化模型。模型根据货物重质、出入库频率划分货架区域,以指令内最小化单载具堆垛机运行时间为研究目标,设计了一种两阶段狼群算法对其进行优化。该算法使用狼群算法对货位分配和作业调度进行集成优化,求解过程体现出两优化问题之间的关联和反馈。实验结果表明,在不同的订单规模下,相比其他优化方式,两阶段狼群算法能得到满意解,并有效缩短自动化立体仓库的作业时间。     

两级定位—路径问题的路径重连变邻域搜索人工蜂群算法

为适应物流需求从少品种大批量到多品种少批量的转变,建立了两级定位—路径问题的数学模型,提出求解该问题的路径重连变邻域搜索人工蜂群算法,即在基本人工蜂群算法中嵌入近年来广泛应用于组合优化问题求解的两种启发式搜索策略——变邻域搜索和路径重连。采用Lingo求解小规模两级定位—路径问题;选取三组较大规模的两级定位—路径问题,分别采用基本人工蜂群算法、路径重连人工蜂群算法、变邻域搜索人工蜂群算法和路径重连变邻域搜索人工蜂群算法进行求解。结果表明,所建数学模型是正确的,所提算法不但能够取得更好的优化结果,而且具有更好的收敛性。     

生成最优同质条带两阶段布局方式的精确算法

传统最优解算法在解决大规模二维件布局问题时,计算时间较长。提出一种基于同质条带两阶段布局算法,此算法生成的同质两阶段布局方式,满足生产中的剪冲下料工艺,且计算时间合理。首先,竖直剪切线将板材分割成同质段;然后,水平剪切线将同质段分割成同质条带。通过求解动态规划算法生成最优同质条带布局方式,求解背包问题得到同质条带在同质段上和同质段在板材上的最优布局方式。利用经典文献中的基准测题,将此算法与普通两阶段算法、TABU500算法和最优解精确算法进行比较,结果表明此算法在布局价值优于普通两阶段和TABU500型算法,计算时间远远短于最优解精确算法,优化结果等于或极接近于最优解精确算法。     

模糊需求下多中心开放式车辆路径优化

针对模糊需求下多中心及开放式三重约束的车辆路径问题,运用三角模糊数表征模糊需求,根据可信性理论设置决策保守程度值刻画决策者的风险偏好,对多中心约束采用"先路径后分组"的策略,在此基础上建立了相应的数学模型;设计了两阶段禁忌搜索算法进行求解,算法第1阶段求解包含全部客户的旅行商问题,以此作为算法第2阶段的初始解,并采用合适的编码方式来保证算法两个阶段解兼容。通过算例实验表明,所使用的三角模糊数能够有效地对模糊需求进行定量刻画,随机模拟算法则能在计算机中对模糊需求进行模拟。所设计的两阶段禁忌搜索算法的第1阶段能够显著提升算法整体的求解质量。决策者的决策保守程度对配送总成本影响很大,过于保守或过于冒险均不能获得较好的路径安排方案,决策保守程度值为0.6时的模型求解效果最好,所提算法能够在可接受时间内对该类问题进行有效求解。     

多车型动态需求车辆路径问题建模及优化

针对现代物流配送系统中客户需求动态变化、配送中心车型多样化以及车辆行驶路线开放式的特点,建立了多车型开放式动态需求车辆路径问题的两阶段数学规划模型。制定了相应的预优化路线调度和实时动态调度的两阶段求解策略,提出了混合2-OPT量子进化算法的求解方法,设计了一种将常用的整数编码转换为量子比特的编码方法,每一个染色体都代表一种行车路线方案,对于量子进化算法求得的行车路线方案,引入2-OPT优化方法,对线路内的子路径进行局部调整,进一步提高了算法的收敛速度。最后通过实例测试及与其他算法的比较,验证了该方法的有效性。     

基于两阶段蚁群算法的带非等效并行机的作业车间调度

针对带非等效并行机的作业车间生产调度问题,以制造系统的生产成本、准时交货率等为目标,构建生产调度多目标模型。利用蚁群算法在求解复杂优化问题方面的优越性,建立调度问题与蚁群并行搜索的映射关系,将调度过程分成任务分派和任务排序两个阶段,每个阶段分别设计蚁群优化算法,并将两阶段寻优蚂蚁有机结合,构建一种具有继承关系的两阶段蚁群并行搜索算法,可以大大提高获得较优解的概率,并且压缩求解空间,快速获得较优解。通过均匀试验和统计分析确定算法的关键参数组合,将两阶段蚁群算法应用不同规模的8组算例。结果表明,无论是优化结果还是计算效率,两阶蚁群算法均优于改进的遗传算法。将所提出两阶段蚁群算法应用于实际车间的生产调度,减少了生产过程中工序间等待时间和缩短了产品交付周期。     

基于NSGA-Ⅱ的两级行星齿轮减速机的多目标优化设计

为了设计体积更小、效率更高的两级行星齿轮减速机,首先建立两级行星齿轮减速机多目标优化的数学模型;采用多目标进化算法NSGA-II对数学模型进行优化,选择五种不同行星齿轮个数,优化得到两级行星齿轮减速机体积和传动效率的pareto最优解。同时与MATLAB工具箱优化获得的结果进行比较,结果显示NSGA-II算法优化的结果均优于MATLAB工具箱优化的结果,特别是所设计的二级行星轮减速机的体积更小。所提出的多目标优化方法和步骤还可以为多级行星齿轮减速机的优化设计提供有效地指导。     

求解柔性作业车间调度问题的两级邻域搜索混合算法

针对柔性作业车间调度问题(Flexible job shop scheduling problem,FJSP),以优化最大完工时间为目标,提出一种融合两级邻域搜索和遗传算法的混合算法。基于通过利用机器空闲时间来减小最大完工时间的想法,构造邻域结构,对关键路径上的关键工序进行移动,实现邻域搜索,以改进当前解;设计针对FJSP问题特点的两级邻域搜索方式,第一级邻域搜索为跨机器移动工序,将工序移动到除当前加工机器之外的其他可选机器上,第二级邻域搜索为同机器移动工序,将工序在当前加工机器上进行移动;给出两级邻域搜索相应的保证可行解工序移动条件;兼顾FJSP问题求解算法的全局搜索能力和局部搜索能力,利用遗传算法实现全局搜索,两级邻域搜索实现局部搜索;采用国际通用的FJSP问题基准算例进行测试,验证了所提方法的有效性。     

考虑准备时间的分布式两阶段混合流水车间调度

针对准备时间依赖于顺序的分布式两阶段混合流水车间调度问题(DTHFSP),提出一种双变邻域搜索(DVNS)算法以同时最小化总延迟时间和最大完成时间。由于该问题子问题较多,将工厂分配和第一阶段的机器分配合并以减少子问题的数量。DVNS包含两个相互协作的变邻域结构,每个变邻域结构都加入全局搜索算子,并应用了邻域搜索和全局搜索协调、邻域结构的合理配置以及当前解的周期性更新等策略。通过大量实例的对比实验表明,DVNS在求解DTHFSP方面具有较强的优势。     

基于两阶段启发式算法的低碳物流选址-多车型路径问题研究

为解决低碳排放量物流背景下配送中心选址与多车型车辆路径优化组合的决策问题，构建了以考虑碳排放量的物流综合成本最小为目标的规划模型，并针对该模型的特点，设计了两阶段启发式算法进行求解。第一阶段设计改进K-means聚类方法对客户节点进行分区聚类，然后使用空间单旅程分区算法以货车满载条件为限制确定各配送中心所服务客户；第二阶段以物流综合成本最低为优化目标，建立量子遗传算法进行求解。结合算例结果表明能够在低碳排放量情况下有效降低物流综合成本。     

蚁群算法及其在有硬时间窗的车辆路径问题中的应用

为求解有硬时间窗的车辆路径问题,提出了一种基于可行解两阶段构造策略的自适应混合蚁群算法.在第一阶段,用蚂蚁的局部遍历代替传统的全局遍历,每个蚂蚁采用蚁群算法进行局部遍历,构造一个回路,蚂蚁转移采用回路两阶段构路策略;在第二阶段,由前一阶段所构造的回路通过采用近似解可行化策略来组合形成可行解.此外,为提高算法的寻优能力,在转移规则中引入了基于时间窗的紧迫性因子和匹配度因子,并与节约算法和爬山法有机结合.实验结果表明,自适应混和蚁群算法性能优良,能够有效地求解有硬时间窗的车辆路径问题.     

大批量定制服装裁剪分床计划的两阶段优化方法

为解决大批量定制服装生产中裁剪分床计划尺码较多且各尺码数量不规则的问题，建立了裁剪分床计划的数学模型；提出基于概率搜索和遗传算法的两阶段优化方法进行求解，第一阶段随机生成若干满足生产约束的初始裁床铺料层数方案，利用搜索算法结合概率，按投入裁床数量最少的原则得到最优尺码组合方案和相应初始裁床铺料层数方案，第二阶段基于前一阶段得到的最优尺码组合方案，按照满足订单情况下生产多余服装的比例不超过企业允许的最大值原则，利用遗传算法再次优化得到最优裁床铺料层数方案。针对实际生产案例，分别利用本算法和人工经验算法求解并进行比较，结果表明在相同的生产条件下，两阶段优化方法能快速求解出服装裁剪分床方案，减少铺床数、节省面料并降低成本。     

基于并行模拟退火算法求解时间依赖型车辆路径问题

为提高传统串行模拟退火算法求解时间依赖型车辆路径问题的效率,提出一种并行模拟退火算法。该算法首先使用前向插入启发式算法生成初始解,在主从式并行模拟退火算法框架下使用4种邻域搜索法对初始解进行优化。采用Figliozzi测试数据库(包含56个测试问题,顾客数均设定为100)对算法性能进行测试,结果表明在不同时间依赖型行驶函数情形下,当使用6个线程时,并行模拟退火算法相对于传统串行模拟退火算法可以得到近似于5倍的加速比,且均能在较快时间内得到比Figliozzi算法更优的解。因此,并行模拟退火算法能有效地求解时间依赖型车辆路径问题,并且可以灵活地扩展解决其他车辆路径问题和组合优化问题。     

含批量加工设备的木门流水车间排产方案

针对包含批量加工工序的两阶段实木复合流水车间排产问题，建立了该问题的混合整数规划模型。根据拉式生产方式和木门加工工艺特点，将原问题拆分为独立的两阶段子问题；针对第2阶段子问题基于Dantzig-Wolfe分解转化为集合划分模型，采用分支定价算法获得其最优整数解；根据第2阶段整数解求解第1阶段子问题，得到该车间这两阶段的排产方案。通过算例分析验证了所提算法可求解大规模木制家具批量生产问题，并能在牺牲少量最优值的情况下，高效快速地得到排产方案。     

高鲁棒性两阶段激光雷达-惯性测量单元外参在线标定算法

针对车辆在近似平面上运动时,退化的传感器数据难以标定外参的问题,提出了一种高鲁棒性两阶段激光雷达-惯性测量单元(LiDAR-IMU)外参在线标定算法。标定算法包括剔除外点的解析解初值计算和非线性滑窗在线迭代优化两个阶段。第一阶段剔除预数据集中的外点,以滑动窗口的形式多次求解只包含旋转分量的手眼标定模型,并改进解析解筛选的条件,求解出多解加权旋转外参的SVD解析解。第二阶段最小化包含外参的残差函数,以旋转解析解为初值滑动窗口迭代优化六自由度外参,使外参快速收敛,并在退化运动和错误历史约束过大时固定外参,避免外参退化。与原始算法对比,该算法对退化的传感器数据具有鲁棒性,可在无外参初值的情况下实现精准鲁棒地在线标定外参。     

求解物流Web服务组合问题的两阶段多目标蚁群算法

针对基于QoS的物流Web服务组合优化问题,提出了两阶段多目标蚁群优化(TMACO)算法。首先,针对原始数据集中存在被支配候选服务而增加算法求解时间的问题,提出了基于Pareto支配的预优化策略;其次,针对属性权重难以确定的问题,提出了不依赖权重的信息素更新策略和启发信息策略;最后,针对基础蚁群算法容易陷入局部最优的问题,提出了懒蚂蚁策略。实验结果表明,TMACO算法具有良好性能,相对于基础蚁群算法、利用解与理想解距离来更新信息素的改进蚁群算法、遗传算法以及用支配程度作为解的个体评价的改进遗传算法,TMACO算法有更高的寻优能力,能够找到更多更优的非劣解。     

考虑变动成本的车辆路径问题建模及求解

为满足实际配送中变化的客户订货量,同时控制方案实时调整对配送效率及成本产生的影响,提出变动成本的概念,引入预优化策略,建立了带变动限制的随订货量变化实时调整的车辆路径问题的两阶段数学模型,并设计了一种两阶段求解算法。采用粒子群算法求解预优化阶段模型,采用改进的装箱问题降序最佳适应插入算法求解实时调整阶段模型。通过对标准算例库和济南卷烟配送的实例测试及与其他优化方法的比较,验证了两阶段模型和算法的有效性。     

基于沿途补货的多配送中心动态需求VRP建模及优化

为了研究沿途补货策略在客户需求动态变化环境下的实用性,提出基于沿途补货的多配送中心动态需求车辆路径问题.将动态问题按照时间轴依次分解为一系列的静态调度子问题,并建立其两阶段数学模型;设计了一种最邻近法结合贪婪法则来控制车辆沿途补货的解码方法;提出了自适应免疫量子进化算法的求解方法,引入免疫算子进行线路内和线路间的再优化,从关于问题的先验知识中提取疫苗,有效地加快了算法的收敛速度,提高了解的质量,同时在疫苗接种的过程中设计了一种随个体适应度大小而变化的自适应选择概率,减少了算法的运行时间.对实例进行仿真测试并与其他算法进行了比较,结果表明所提算法能获得较好的解,能有效求解动态调度问题,同时分析了沿途补货策略影响,实验表明沿途补货策略适用于动态需求车辆路径问题.