基于分组策略的多目标三维装箱算法

目的 针对现有三维装箱算法优化目标单一、优化效率低的问题,提出适用于求解大规模货物装载问题的多目标装箱算法,以提高装箱规划效率,确保货物运输安全。方法 考虑5种现实约束条件,以体积利用率和装载垛型重心偏移量为优化目标,建立多目标货物装载优化模型。采用拟人式装箱对货物进行预分组,减小决策空间,然后结合分组信息与装箱算法生成初始解;引入数据驱动的装箱交叉算子提高算法收敛性;设计多策略变异算子提高算法结果的多样性。结果 以公共数据集和真实航空货物数据作为实验数据进行实验。实验结果表明,在满足多种约束条件下,集装箱装载强异构货物平均体积利用率达到92.0%,重心位置空间偏移从20 cm减少到7.5 cm,并且算法运行时间减少了73.5%。结论 本文所提算法应用于求解大规模多目标三维装箱问题,提高了装箱质量和效率,可为三维装箱算法的工程应用提供参考。     

Quasi-physical global optimization method for solving the equal circle packing problem

The equal circle packing problem is a well-known challenge in geometry.It is also a natural,clear and fair test system for global optimization.This paper presents a quasi-physical global optimization algorithm for solving the equal circle packing problem.The algorithm simulates two kinds of movements of N elastic disks: smooth movement driven by elastic pressures and violent movement driven by strong repulsive forces and attractive forces.The smooth movement makes the disks reach a locally optimal configura...     

Adaptive beam search lookahead algorithms for the circular packing problem

This paper addresses the circular packing problem (CPP), which consists in packing n circles C_i, each of known radius r_i, i∈N={1, …, n}, into the smallest containing circle C. The objective is to determine the radius r of C as well as the coordinates (x_i, y_i) of the center of C_i, i∈N. CPP is solved using two adaptive algorithms that adopt a binary search to determine r, and a beam search to check the feasibility of packing n circles into C when the radius is fixed at r. A node of level ?, ?=1, …, n, of the beam search tree corresponds to a partial packing of ? circles of N into C. The potential of each node of the tree is assessed using a lookahead strategy that, starting with the partial packing of the current node, assigns each unpacked circle to its maximum hole degree position. The beam search stops either when the lookahead strategy identifies a feasible packing or when it has fathomed all nodes. The computational tests on a set of benchmark instances show the effectiveness of the proposed adaptive algorithms.     

MF-TDMA信道分配研究

MF-TDMA因其灵活的分配策略和信道利用率在通信系统中广泛使用。由于信道资源有限性以及用户需求的多变性,使得如何将有限的信道最大的利用以便为更多的用户服务成为MF-TDMA的关键问题。针对这一问题,文章首先对MF-TDMA信道结构进行处理,将MF-TDMA的信道分配问题转为二维装箱问题。然后,针对该问题的常规算法FFA进行改进,提出了基于最小资源浪费率的FFA贪心算法（IFFA）。最后,对给出的结果进行了简单的验证。     

An efficient placement heuristic for three-dimensional rectangular packing

By embodying the spirit of “gold corner, silver side and strawy void” directly on the candidate packing place such that the searching space is reduced considerably, and by utilizing the characteristic of weakly heterogeneous problems that many items are in the same size, a fit degree algorithm (FDA) is proposed for solving a classical 3D rectangular packing problem, container loading problem. Experiments show that FDA works well on the complete set of 1500 instances proposed by Bischoff, Ratcliff and Davies. Especially for the 800 difficult strongly heterogeneous instances among them, FDA outperforms other algorithms with an average volume utilization of 91.91%, which to our knowledge is 0.45% higher than current best result just reported in 2010.     

Solving the irregular strip packing problem via guided local search for overlap minimization

The irregular strip-packing problem (ISP) requires a given set of non-convex polygons to be placed without overlap within a rectangular container having a fixed width and a variable length, which is to be minimized. As a core sub-problem to solve ISP, we consider an overlap minimization problem (OMP) whose objective is to place all polygons into a container with given width and length so that the total amount of overlap between polygons is made as small as possible. We propose to use directional penetration depths to measure the amount of overlap between a pair of polygons, and present an efficient algorithm to find a position with the minimum overlap for each polygon when it is translated in a specified direction. Based on this, we develop a local search algorithm for OMP that translates a polygon in horizontal and vertical directions alternately. Then we incorporate it in our algorithm for OMP, which is a variant of the guided local search algorithm. Computational results show that our algorithm improves the best-known values of some well-known benchmark instances.     

AVS视频的分层重传优化策略与实现

针对网络抖动等因素会影响图像质量的问题,采用差错控制与拥塞控制相结合的恢复技术,改进AVS视频数据在传输层的RTP打包,提出提高重传效率的AVS视频分层重传策略,通过令牌发放的方式控制数据包重传的次数解决重传导致网络拥塞问题。实验结果表明,在低带宽的网络下,该策略对AVS视频传输相对于无令牌发放的重传方式图像质量有一定的提高。