装箱问题的算法及最新进展

装箱问题在经济社会发展中扮演着重要的角色,该问题研究的是寻找较好的布局方式,尽可能实现利益的最大化.装箱问题具有NP-难性质,其理论和应用研究存在一定的挑战,但因其有广泛的应用背景而受到研究者高度的关注.本文主要总结近几十年来装箱问题的研究成果,特别针对一维、二维和三维单目标装箱问题和算法,以及多目标装箱问题的算法进行概括和总结,并提出装箱问题算法上有待进一步的研究工作.     

考虑货架存放期的经济批量排产问题的改良算法

经济批量排产问题是关于在单一设备上协调地、周期性地生产多种产品的问题.其解要求在生产准备与库存总成本最小的条件下,决定 I 种产品的生产序列.本文研究的经济批量排产问题考虑了产品货架存放期因素.指出了Dobson算法的不足,并提出了求解该问题的新算法(改进的装箱算法),新算法不仅以生产次数最大的产品为基础进行装箱,而且进一步以生产次数略低的产品为基础进行装箱.排产时,先按生产次数降序进行装箱,再按单次生产时间与生产准备时间之和降序装箱.计算结果显示,本算法结果更优.     

基于对角转轮样式的托盘装箱优化模型

针对托盘装箱问题(PLP),建立了对角转轮样式下具有托盘柔性的整数规划模型,设计了求解模型的启发式算法,并利用VB程序对模型的最优解及装箱图谱进行了讨论分析,结果表明:对角转轮样式就提高具有较大长、宽比箱子的装载效率以及解决装箱压缝问题方面具有明显的优势;而柔性也是影响托盘装载效率的重要因素之一,具有较大的回报率.     

约束装箱问题的混合遗传算法求解

本将最佳适应法和遗传算法相结合，提出了一种新的启发式混合遗传算法对具有时间约束的装箱问题进行求解，给出了具体的算法步骤，试算结果表明基于启发式算法的混合遗传算法适合于求解各种约束条件下的大规模装箱问题。     

带冲突关系装箱问题的启发式求解算法

现实物流活动中大量存在的食品、药品和危险品等货物的分组包装问题属于带冲突关系的装箱问题(BPPC),其优化目标是在满足货物间冲突限制的前提下完成装箱操作,并最小化使用货箱的数量。本文从实际需求出发,基于货物之间的冲突关系、装箱顺序和货箱容量等约束建立相应的数学规划模型;随后设计了求解BPPC问题的启发式算法,算法通过迭代求解最大团结构实现货物间冲突关系的消去,根据当前货物最大团采用改进降序首次适应算法(FFD)完成货物装箱操作,并通过“洗牌”策略对已有装箱方案进行局部优化;最后,针对Iori算例数据,将以上算法与基于图着色的启发式算法进行比较分析,结果表明,本文算法是求解BPPC问题更为有效的方法。     

LPT算法在广义装箱问题中的应用

本文利用排序问题中的LPT算法提出了广义装箱问题的MFLPT算法，并分析了这个算法的最坏情况。     

基于图着色模型的冲突装箱问题启发式算法

带有冲突关系装箱问题的优化目标是在满足货物冲突关系的前提下,使用数量最少的货箱完成货物装箱的目的。本文分析了冲突装箱问题的数学模型,提出了基于图着色模型的启发式算法进行求解。首先,使用冲突图来描述货物之间的冲突关系;其次,基于冲突图,采取图着色的方式将货物进行分组,并且组内的货物之间不存在冲突关系;最后,采取改进FFD算法对每组的货物进行装箱操作。实验表明,本文提出的启发式算法能够快速有效地找到问题的可行解,为此类装箱问题的求解提供了新思路。     

物品大小不超过1/2的一维在线装箱模型研究

研究主要针对所有装入物品大小上限为1/2时的一维装箱问题模型展开,根据物品尺寸大小划分的思想,提出一种新的一维在线装箱算法.本模型中,物品在线到来,对即将到来的物品信息及物品数量未知,算法执行过程中,首先根据物品尺寸大小将物品划分成7大类,再根据欲先设定的packing规则,将对应类物品放入对应类型箱子中,任何时刻,算法最多打开7个箱子.算法设计过程中,不再需要额外的空间存储物品,物品一旦装入箱子不允许取出重装,箱子关闭后不允许再打开装其他物品.最后,通过详细的分析计算,验证出本算法能获得1.4236的渐近竞争比.同时通过实例构建得出问题新的下界为1.4231,将上下界之间的缝隙缩小至0.0005.     

在线约束单机排序问题的启发式算法

由于约束单机排序问题是经典装箱问题的一种推广并且同经典装箱问题有一些相同的特征。本文主要讨论了经典装箱问题的一些启发式算法在在线约束单机排序问题上的推广和最坏界估计。     

经典一维装箱问题近似算法的研究进展

自20世纪70年代开始,随着计算复杂性理论的建立,近似算法逐渐成为组合优化的重要研究方向。作为第一批研究对象,装箱问题引起了组合优化领域学者的极大关注。装箱问题模型简单、拓展性强,广泛出现在各种带容量约束的资源分配问题中。除了在物流装载和材料切割等方面愈来愈重要的应用外,装箱算法的任何理论突破都关乎到整个组合优化领域的发展。直到今天,对装箱问题近似算法的研究仍如火如荼。本文主要针对一维模型,简述若干经典Fit算法的发展历程,分析基于线性规划松弛的近似方案的主要思路,总结当前的研究现状并对未来的研究提供一些参考建议。     

On an open problem in spherical facility location

In this paper we partially resolve an open problem in spherical facility location. The spherical facility location problem is a generalization of the planar Euclidean facility location problem. This problem was first studied by Katz and Cooper and by Drezner and Wesolowsky where a Weszfeld-like algorithm was proposed. This algorithm is very simple and does not require a line search. However, its convergence has been an open problem for more than ten years. In this paper, we prove that the sequence generated by the algorithm converges to the unique optimal solution under the condition that the oscillation of the sequence converges to zero. We conjecture that the algorithm is a descent algorithm and prove that the sequence generated by the algorithm converges to the optimal solution under this conjecture.     

关于求解变分不等式问题的2-次梯度外梯度算法收敛性的一个补注

Yair Censor,Aviv Gibali和Simeon Reich为求解变分不等式问题提出了2-次梯度外梯度算法。关于此算法的收敛性,作者给出了部分证明,有一个问题：由算法产生的迭代点列能否收敛到变分不等式问题的一个解上,没有得到解决。此问题作为一个公开问题在文章“Extensions of Korpelevich's extragradient method for the variational inequalityproblem in Euclidean space”(Optimization,61(9)：1119-1132,2012)中被提出。在这篇简短的补注性文章中,对所提出的问题给出了答案：由算法产生的迭代点列能收敛到变分不等式问题的一个解上。给出2-次梯度外梯度算法的全局收敛性的一个完整证明,证明了从任意起始点开始,由算法产生的迭代点列都能收敛到变分不等式问题的一个解上。     

求解摩擦接触问题的一个非内点光滑化算法

给出了一个求解三维弹性有摩擦接触问题的新算法,即基于NCP函数的非内点光滑化算法．首先通过参变量变分原理和参数二次规划法,将三维弹性有摩擦接触问题的分析归结为线性互补问题的求解;然后利用NCP函数,将互补问题的求解转换为非光滑方程组的求解;再用凝聚函数对其进行光滑化,最后用NEWTON法解所得到的光滑非线性方程组．方法具有易于理解及实现方便等特点．通过线性互补问题的数值算例及接触问题实例证实了该算法的可靠性与有效性．     

H∞强镇定问题的新解法

H∞强镇定问题可解的原始算法是依赖于一个解存在的充分条件．自然的此算法应用起来有一定的局限性．针对此问题，首先给出H∞强镇定问题可解的一个充要条件．并说明该条件在计算上很容易实现的．并由此充要条件出发设计了一个简单且实际可行的算法．该算法实际上没有局限性，而且比较利于计算机编程．最后举例说明新算法与H∞强镇定问题可解的原有算法相比，具有更大的优点．     

一类新的车辆路径问题及其两阶段算法

本文结合汽车零部件第三方物流业的实际背景,提出了一类新的车辆路径问题,它是一种带时间窗约束的分车运输同时收发车辆路径问题(简称SVRPSPDTW).接着给出了问题的模型,并提出求解问题的启发式算法：两阶段算法. 最后在改进的Solomn的算例的基础上,进行了数值试验.     

A new algorithm for the quasi-assignment problem

The quasi-assignment problem can be used to solve the bus scheduling problem, the tourist guide problem, and the minimum number of chains in a partially ordered set. A successive shortest path algorithm for the assignment problem is extended to the quasiassignment problem. The algorithm is a variation of the primal-dual algorithm, and its computational complexity isO(n ³).The research for this paper was partly supported by the Chinese National Science Foundation.     

Global minimization of a generalized linear multiplicative programming

This article presents a simplicial branch and bound algorithm for globally solving generalized linear multiplicative programming problem (GLMP). Since this problem does not seem to have been studied previously, the algorithm is apparently the first algorithm to be proposed for solving such problem. In this algorithm, a well known simplicial subdivision is used in the branching procedure and the bound estimation is performed by solving certain linear programs. Convergence of this algorithm is established, and some experiments are reported to show the feasibility of the proposed algorithm.     

Increasing the total net revenue for single machine order acceptance and scheduling problems using an artificial bee colony algorithm

The order acceptance and scheduling (OAS) problem is an important topic for make-to-order production systems with limited production capacity and tight delivery requirements. This paper proposes a new algorithm based on Artificial Bee Colony (ABC) for solving the single machine OAS problem with release dates and sequence-dependent setup times. The performance of the proposed ABC-based algorithm was validated by a benchmark problem set of test instances with up to 100 orders. Experimental results showed that the proposed ABC-based algorithm outperformed three state-of-art metaheuristic-based algorithms from the literature. It is believed that this study successfully demonstrates a high-performance algorithm that can serve as a new benchmark approach for future research on the OAS problem addressed in this study.

     

Enhanced Direct and Indirect Genetic Algorithm Approaches for a Mall Layout and Tenant Selection Problem

During our earlier research, it was recognised that in order to be successful with an indirect genetic algorithm approach using a decoder, the decoder has to strike a balance between being an optimiser in its own right and finding feasible solutions. Previously this balance was achieved manually. Here we extend this by presenting an automated approach where the genetic algorithm itself, simultaneously to solving the problem, sets weights to balance the components out. Subsequently we were able to solve a complex and non-linear scheduling problem better than with a standard direct genetic algorithm implementation.     

带投资约束且p不确定的推广p-中位问题

p-中位问题是设施选址中的一个经典模型,在交通、物流等领域有着广泛应用．在经典p-中位问题的基础上提出一种p不确定的推广p-中位问题,并且加上总投资约束,使得此推广模型更加实用．针对此推广模型,提出三种启发式算法：简单启发式算法、变邻域搜索算法和改进的遗传算法．数值实验结果表明变邻域搜索算法和改进的遗传算法在求解此推广模型时是有效的．