定位-运输路线安排问题的两阶段启发式算法

重点研究了集成化物流中一类特殊的定位-运输路线安排问题(LRP)的解决方法.LRP问题包括设施定位和运输路线优化两方面决策,属于NP-hard难题.由于问题的复杂性,提出基于假设前提的LRP模型及其两阶段启发式求解算法.该方法分两步实现:首先,采用基于最小包络聚类分析的启发式方法确定被选择的潜在设施及由每一个选中的设施所要提供服务的客户群;其次,运用带有控制开关的遗传算法求解每一确定客户类中的优化运输路线.提出利用两阶段启发式算法求解LRP问题,此方法实现容易、运算简单,一定程度上避免了遗传算法中的"局部最优现象".仿真实验证明了该算法求解单目标LRP的有效性和准确性.

多车辆合乘问题的两阶段聚类启发式优化算法

车辆合乘问题研究在物流领域和交通领域意义重大.良好的合成策略不仅可以节省物流成本,降低交通拥塞,在减少噪声及提高环境等方面也是很有利的.针对确定性多车辆合乘匹配问题,提出了两阶段聚类的启发式匹配策略:第1阶段聚类过程提出匹配度的概念,用于指导将服务需求分配到某一具体车辆,从而将多车辆问题转化为单车辆问题;第2阶段聚类过程基于"先验聚类"插入思想,可降低单车辆匹配过程的插入试探次数,从而提高算法效率.为提高搭乘成功率并降低运营总成本,通过迁移对第1阶段聚类过程进行调整.实际算例结果表明,算法在可接受时间范围内不仅可提高搭乘成功率,还明显降低车辆的运行成本,表现出较强的实用性.

求解2D条带矩形Packing问题的迭代启发式算法

为求解二维矩形条带装箱问题,提出了一种新颖而有效的启发式算法.算法主要包括矩形装载适应度的计算规则和树型迭代搜索规则,通过选择最高适应度的矩形来装载空间.对大量国际上公认的Benchmark问题实例的计算结果表明,相对于当前的很多著名算法,提出的算法更加有效.

一种基于元启发式策略的迭代自学习K-Means算法

类内误差平方和最小化的聚类准则求解是NP难问题,K-Means采用的迭代重定位方法本质上是一种局部搜索的爬山算法,因此聚类结果对初始代表点的选择非常敏感,只能保证局部最优。为此,引入元启发式策略,通过建立评估函数对K-Means初始代表点和目标函数之间的依赖关系进行近似,然后利用近似评估函数指导新的初始代表点的选择,构成一种迭代自学习框架下的K-Means算法。实验表明算法可以很好地克服K-Means对初始代表点的依赖性,获得较高质量的聚类结果。

两阶段启发式算法在矩形件排样中的应用

针对定制式木门家具生产过程中板材资源利用率低和常规启发式排样算法得到的排样结果切割工艺复杂的问题,采用启发式排样和优化排序相结合的方式,提出了两阶段排样方式和遗传算法相结合的组合式矩形板材排样算法。以两阶段排样方式为基础,通过对排样过程中物块摆放时会遇到的5种情况分别给出对应处理方案,提出了两阶段启发式排样算法,同时利用改进的遗传算法进行板材组号的排序优化。测试结果表明,该文算法取得了98.11%的最高资源利用率,算法输出排样方案的板材切割工艺得到了优化,提高了实际生产中板材切割的生产效率并降低了生产与时间成本。

无等待流水调度问题迭代启发式算法

针对以总完工时间最小化为目标的无等待流水调度问题(缩写为NWFSP),提出了两个迭代启发式算法(缩写为IHA1、IHA2).一个是以FL(described by Framinan and Leisten,OMEGA,2003)启发式算法产生的解作为初始解,另一个是以WY(described by Hoon-shik Woo and Dong-soon Yim,Computers&Ops Res,1998)启发式算法产生的解作为初始解,然后两者均应用RZ(developed by Rajendran and Ziegler,European Journal of Operational Research,1997)和FL插入以及成对交换技术进行多次迭代来改善解的质量.为了评估,我们使用了Taillard’s基准程序随机产生了大量实例,实验结果显示,IHA1和IHA2在解的性能上优于经典的RC1、RC2、PH1(p)算法,随着问题规模的增大,对解的质量改善得更好.

基于两阶段启发式算法的多目标外卖配送优化分析

如何在保证顾客时间满意度的同时选择合适的送餐线路是外卖行业急需解决的问题.本文建立了基于客户时间满意度和配送总成本的多目标外卖配送线路优化模型,对SWEEP算法和蚁群算法进行改进,采用两阶段启发式算法进行外卖配送线路优化,以最大化客户满意度为主要目标为商家提供了最佳配送方案,实例分析结果表明该模型提高了算法效率,增强了算法实用性.

基于一种启发式迭代算法的产品组合优化

本文研究了一个单个时期的产品组合优化问题。文章假定商品的需求符合MNL model。笔者通过设计一种迭代算法从零售商所有能够经营的产品种类集合中挑选出在零售商库存约束范围内单位期望收益最大的产品集合作为其最优产品组合。数据实验表明该算法可有效提高零售商的期望收益,并为如何改进零售商经营的产品组合提供科学指导。

一种求解两级累计式车辆路径问题的两阶段启发式算法

现代物流的发展中,运输网络的多级化以及对快速服务的更高要求是两大重要趋势。在这样的背景下,提出两级累计式车辆路径问题(2E-CCVRP),其中两级是指物资须由中心仓库配送至中转站(1级)再转送给客户(2级),累计式是指优化目标为所有客户的累计等待时间最小。2E-CCVRP是NP-hard问题,抽象并建模后使用一种两阶段启发式算法进行求解,第一阶段使用改进的CCVRP-split算法找到初始可行解,第二阶段通过扰乱结合局部搜索进行优化。实验结果显示,该算法能够取得高质量的解,且求解速度快,稳定性好。

基于两阶段启发式算法的公路网布局研究

为形成科学、合理的公路网布局方案,为公路网布局实践提供理论支撑,以节点重要度为基础,在一定的约束条件下,以满足节点间的运输需求为目的,以路网总旅行时间最小为目标构建混合整数规划模型。在此基础上,以路段重要度和运输需求为启发式条件,设计基于随机游走算法和模拟退火算法的两阶段启发式算法,对MATLAB生成的随机算例进行求解。计算结果表明,在算法迭代初期,节点重要度较大的节点优先被连通,伴随迭代次数的增加和一定的随机扰动,节点在实现全部连通的基础上以路网总旅行时间最小为目标进行优化,最终获得目标函数值最优的公路网布局方案。算例求解过程符合公路网规划实践规律,表明了该模型和算法的有效性,同时表明模拟退火算法对随机游走算法求得的初始解具有一定的优化效果。可以看出,两阶段启发式算法能在较短时间内求解NP-hard问题并获得相对满意的解,可为求解大规模网络优化问题提供一定的方法借鉴。

集送货可拆分车辆路径问题的两阶段构造启发式方法

为了节能减排,提高物流效率效益,集送货需求可拆分的车辆路径问题是一个重要的研究课题,目标是在使用最少车辆的前提下最小化行驶距离。提出一种两阶段构造启发式方法来解决这个问题。第一阶段,采用扩展的多重启动迭代扫描算法和微调系数、在车辆容量限制下,根据集送货需求将客户域划分为子域,并确定每个子域的分裂点和分裂值。第二阶段,采用改进的Clarke-Wright节约算法来优化每个子域中的路线。基于Solomon基准数据集、按照需求重构数据集,验证算法的可行性和有效性。实验结果表明,可拆分集送货车辆路径优化对物流企业的运输非常有利,它可以减少使用的车辆数并提高平均装载率,降低总运输成本。

基于多顶点替换策略的迭代局部搜索算法解决覆盖推销员问题

覆盖推销员问题(Covering Salesman Problem,CSP)是著名的旅行商问题的一个变体,是NP难问题。给定一组顶点和每个顶点相关联的预定覆盖半径,CSP的目标是在顶点子集上找到一个最短长度的哈密顿回路,使每个顶点被访问或者在被访问顶点的覆盖范围内。为提升搜索候选顶点集的质量,提出一种基于多顶点替换的搜索策略,并将该策略引入到迭代局部搜索算法解决CSP。所提CSP算法通过扰动过程和改进过程的迭代探索邻域最优解,其中扰动过程将搜索发散到未探索的区域,改进过程提升解的质量。实验结果表明,多顶点替换方法相比“移出-重新插入”过程可以获得更高质量的候选顶点集。所提CSP算法在寻优的正确率上取得了不错的成效,尽管运行速度与其他启发式算法相比有差距,但可以在合理的运行时间内解决CSP。

基于两阶段混合算法的卷烟车间排产优化

针对卷烟车间生产流程复杂、多目标和多约束等特点,综合考虑卷烟生产的交货及时率、换牌次数、工作日数量及生产均衡性等方面,建立了卷烟生产排产的多目标模型。为求解该问题,设计了一种结合线性规划和启发式算法的两阶段混合算法,混合算法中第一阶段将部分约束纳入到线性规划中求解,获得初始排产结果,第二阶段通过自研的启发式算法对初始排产结果进行产量上下限、烟丝批次、机台换牌等约束性修复后,得到最终排产结果。该方法已在某卷烟厂进行排产验证,取得了良好的效果。

基于遗传算法的二阶段迭代模型任务分布方案寻优

针对利用启发式方法求解二阶段迭代模型的最优任务分布方案容易陷入局部最优解的问题,根据二阶段迭代模型中各任务的分布特点,引入具有自适应全局优化特性的遗传算法求解出二阶段迭代模型的最优任务分布方案,从而减少任务执行的时间成本。以某汽车发动机的开发为例,分别应用基于启发式方法和基于遗传算法方法进行求解寻优,通过比较说明了后者的有效性。

公交网络多路径选择启发式算法研究

公交乘客出行路径选择算法是公交乘客信息系统的核心技术。建立了公交网络出行路径选择的数学模型,在Dijkstra算法和迭代惩罚法的基础上,设计了公交网络多路径选择的启发式算法,并结合实际公交网络进行了算法的验证。算法合理考虑了换乘因素和距离因素对公交出行者路径选择行为的共同影响,能够生成多条备选路径供出行者选择。对于公交乘客信息系统相关技术的研究开发具有参考价值。

基于启发式算法的成品油配送计划研究

通过对成品油配送计划特点的研究与分析,建立了成品油配送计划编制的数学模型;并设计了模型求解方案;通过对实验结果的分析,证明本文设计的算法快速、有效、稳定。

海岛无人机多模式应急配送模型与算法研究

灾害情况下物资海岛配送是应急物流的一种特殊应用场景.无人机配送作为解决应急物流问题的一种新型配送方式受到广泛关注,并涌现出了一系列配送模式.通过考虑无人机成本、无人机飞行距离、无人机起降平台和地面配送成本,构建无人机直接配送、点对点双阶段配送、回路双阶段配送和双层物流配送网络4种配送模式.针对回路双阶段配送的多指标耦合特征,提出一种迭代启发式算法进行优化.围绕普陀山海岛场景,构建20~100个需求点和2~4个无人机起降平台的算例进行数值实验,分析并验证模型正确性和算法性能.实验结果表明,4种配送模式模型具有有效性;算法一般经过2~5次迭代,能够有效减少回路双阶段配送约19.08%的无人机飞行距离,减少双层物流配送网络约28.63%的地面配送距离.

基于两阶段调度的制造单元协同调度算法研究

针对单元制造问题,提出了一种基于两阶段的调度算法,通过过程分解和算法优化两方面实现问题求解。调度过程分为"预调度"和"整体调度"两个阶段,对大规模调度进行调度,不仅有效地降低了问题规模,同时制造单元调度结果对实际生产具有现实意义;调度算法采用了"精确"计算和"近似"求解相结合的方式,既提高计算效率又兼顾了全局优化目标。数值实验结果表明了的这一设计思路的有效性。

基于两阶段遗传算法的传感器网络布点

随着传感器网络在世界范围内得到越来越广泛的应用,具有感知、计算和通信能力的传感器节点以及由大量此类节点互联构成的传感器网络需要不断地优化并进行自动设计。文中致力于设计1种新型交通信息监测传感器网络,并采用两阶段启发式算法完成网络的自动布点,分析不同启发式算法运行结果性能指标的差异,从而证明了两阶段启发式算法在交通监测网络中的优越性。

求解两阶段线性规划的原始-对偶分解算法

本文介绍一种求解两阶段线性规划的原始-对偶分解算法,该方法在两方面上明显优于传统分解方法,即具有平衡的分解结构和良好的收敛特性。新分解结构将原问题分解为一对受限制的原始和对偶子问题,每一个子问题都保存有对方以前迭代的所有信息,而在传统的主-子分解结构中,子问题只保留主问题传递来的当前信息。新的迭代机制使两个子问题在迭代过程中始终保持单调改善的收敛特性。在相当一般的条件下,新算法可以在有限次迭代中收敛于预先指定的收敛误差之内。