共查询到14条相似文献,搜索用时 62 毫秒
1.
研究了一类有实际背景的新的装箱问题—— A形装箱问题 (ASBP)的在线情形 .在 ASBP中物品均为圆柱形 ,并且在每个箱子中物品均摆放成 A字形 ,即后到达的物品放在先到达的物品之上且上层物品的截面半径不超过下层物品的截面半径 ,优化目标是最小化装下所有物品所用的箱子数 .当所有物品半径都相同时 ASBP退化成经典一维装箱问题 (BP) ,故 BP为 ASBP的特殊情形 .BP的大多数启发式算法可以推广到 ASBP中 ,我们从最坏情形分析的角度讨论了两类 ASBP启发式算法 .证明了直接推广的启发式算法性能较差 ,其中一些算法的渐近最坏比甚至可以任意大 ;如果半径的种类有限 ,按半径分类的启发式算法的性能较好 ,并且一些算法的渐近最坏比和它们所基于的 BP启发式算法的渐近最坏比相等. 相似文献
2.
关于“放映员问题”(FDP)的启发式算法 总被引:1,自引:0,他引:1
本文研究了新近出现的“放映员问题”(FDP)模型及其启发式算法;不仅证明寻找一个FDP近似(有界)解也是NP难题,而且给出一般情况下FDP最优解的下确界估计;还提出一种启发式新算法MT;它具一定总体寻优特性,且在最好情形下能给出FDP最优解,因而优于文献[1]中FDP算法。算例证实MT的可行性和有效性。 相似文献
3.
4.
带二维装箱约束的绿色开放式车辆路径问题(green open vehicle routing problem with twodimensional loading constraints, 2L-GOVRP)是绿色开放式车辆路径问题和二维装箱问题的集成。以最小化燃油消耗量为优化目标建立了2L-GOVRP模型,并提出一种两阶段优化算法(two stage optimization algorithm, TSOA)进行求解。TSOA的第一阶段,针对车辆路径问题,设计自适应鲸鱼优化算法(adaptive whale optimization algorithm, AWOA)进行求解,从而确定车辆初步配送路径(即2L-GOVRP的初始解),并采用4种变邻域局部操作进行局部搜索。TSOA的第二阶段,针对二维装箱问题,设计融入扰动机制的天际线填充算法(skyline filling algorithm combined with disturbance mechanism, SFA-DM)优化装箱过程,从而确保所有货物能够合理装箱。通过对不同客户规模测试数例的仿真实验和算法比较,验证了TSOA可... 相似文献
5.
一个求解带有时间窗口约束的车辆路径问题的启发式算法 总被引:11,自引:0,他引:11
对适用于旅行商问题的最近距离搜索启发式算法进行修正,构造出评价函数,并依此提出一个求解有时间窗约束的车辆路径问题的启发式算法。求解具体算例表明,此算法是有效的。 相似文献
6.
车辆路径问题是一类典型的组合优化问题,大部分研究都只考虑车辆能力固定的情形,实际中受货物形状特性及客户需求变化,车辆的能力是受限变化的,针对能力受限变化的车辆路径问题(varied capacitated vehicle routing problem,VCVRP),基于动态规划理论,提出一种求解大规模VCVRP问题的快速动态规划算法.该算法以传统的最佳适应降序算法(best fit decreasing,BFD)和最小生成树(minimum spanning tree,MST)算法为基础,引入K步回溯,短途优先原则,实现了VCVRP中的货物装箱问题和路由选择问题的近似解耦.同时给出了该算法的优化目标车辆旅程的理论上界,短途优先原则的局部最小的理论分析与证明.最后以乘用车物流运输案例为背景,给出了计算实例,并从算法参数与算例规模多个角度进行求解质量与算法性能的分析. 相似文献
7.
N-车探险问题是一类NP-hard离散优化问题,针对该问题,首次提出一种融合局部搜索的离散水波优化算法。结合该问题等价于置换排序的特性,设计基于置换序列的编码方式;利用反转、移动、交换等操作重新定义传播、折射和碎浪算子;开发基于插入邻域的局部搜索策略,以增强水波优化算法的局部搜索能力。最后,利用实验设计探讨关键参数对算法性能的影响。基于14个标准问题的测试结果表明:所提方法的寻优精度、稳定性等整体优于标准水波优化算法、粒子群算法、烟花算法和启发式算法H1~H4;与离散水波优化算法相比,基于禁忌搜索的变邻域搜索算法用至少66.6倍的计算时间得到了最大相对偏差比为0.017的寻优精度。结果表明,离散水波优化算法能在较短时间内获得较满意的解。 相似文献
8.
解二维分配问题的行列启发式算法 总被引:4,自引:0,他引:4
二维 (2 D)分配算法在实际中具有广泛的应用 ,本文提出求解该问题的一种新的算法———行列启发式算法。该算法采用交替消去代价矩阵行与列中多余元素的方法得到分配问题的最优解。算法简单易懂 ,避免了其它 2 D分配算法中存在的算法实现难、处理速度慢的不足。给出相关原理的理论证明及算法的具体步骤 ,并通过实例验证了该算法的有效性 相似文献
9.
10.
采用混合单亲遗传算法求解一类资源-时间优化问题 总被引:5,自引:0,他引:5
针对资源有限最短时间的一类资源 -时间优化问题 ,提出了混合单亲遗传算法进行求解 .作为一类 NP完全问题 ,该问题求解难度相当大 ,尤其问题规模大时寻找最短时间优化解就更困难 .针对问题的特点本文引入的算法结合了启发式规则 ,给出了算法全局收敛的理论分析 ,并给出实际应用表明该算法的有效性. 相似文献
11.
针对大型产品在双边拆卸线进行作业时,零部件间存在拆卸干扰的情形,构建双边顺序相依拆卸线平衡问题优化模型,并提出一种动态协同进化算法。所提算法设计了一维正负整数排列编码方法,可将任务间先后关系及任务所在操作方位同时有效表示,编码简单易于实现;采用动态邻域深度搜索策略,提高局部搜索质量;引入后天学习算子,加快个体进化速度;通过种群间相互交流,提升下一代种群质量。最后,通过算例验证所提算法具有良好的寻优性能。 相似文献
12.
13.
求解复杂TSP问题的随机扰动蚁群算法 总被引:10,自引:0,他引:10
针对基本蚁群算法 ,设计出一种新颖的随机扰动蚁群算法 ,并将其应用于求解复杂 TSP问题 .该算法包含了两个重要方面 :一是提出了采用倒指数曲线来描述的扰动因子 ;二是设计出了相应的随机选择策略和扰动策略 .数值模拟表明 :该算法可以有效地克服基本蚁群算法的计算时间较长和容易出现停滞现象的缺陷 ,具有更好的全局搜索能力 .此外 ,还对该算法中参数的取值范围及选取方法进行了研究和探讨. 相似文献
14.
基于解均匀度的车辆路径问题的自适应蚁群算法 总被引:9,自引:5,他引:9
蚁群算法是一种新型的模拟进化算法,具有许多优良的性质,可以很好地解决旅行商问题(Traveling Salesman Problem,TSP),但同时也存在计算时间长、易出现停滞等缺陷。在分析车辆路径问题(Vehicle Roulting Problem,VRP)与TSP区别的基础上,将蚁群算法应用于VRP的求解,通过引入解均匀度、选择窗口以及吸引力等概念对算法的转移策略和更新策略进行改进,构造了具有自适应功能的蚁群算法。实验仿真结果表明所设计的算法具有很强的搜索能力,计算效率较高,能够有效地解决加速收敛与停滞现象之间的矛盾。 相似文献