Incremental assignment problem

In this paper we introduce the incremental assignment problem. In this problem, a new pair of vertices and their incident edges are added to a weighted bipartite graph whose maximum-weighted matching is already known, and the maximum-weighted matching of the extended graph is sought. We propose an O(|V|²) algorithm for the problem.     

一种多目标不等面积设施布局问题的启发式算法

多目标不等面积设施布局问题（UA-FLP）是将一些不等面积设施放置在车间内进行布局,要求优化多个目标并满足一定的限制条件。以物料搬运成本最小和非物流关系强度最大来建立生产车间的多目标优化模型,并提出一种启发式算法进行求解。算法采用启发式布局更新策略更新构型,通过结合基于自适应步长梯度法的局部搜索机制和启发式设施变形策略来处理设施之间的干涉性约束。为了得到问题的Pareto最优解集,提出了基于Pareto优化的局部搜索和基于小生境技术的全局优化方法。通过两个典型算例对算法性能进行测试,实验结果表明,所提出的启发式算法是求解多目标UA-FLP的有效方法。     

A genetic algorithm for a bi-objective capacitated arc routing problem

The capacitated arc routing problem (CARP) is a very hard vehicle routing problem for which the objective—in its classical form—is the minimization of the total cost of the routes. In addition, one can seek to minimize also the cost of the longest trip.In this paper, a multi-objective genetic algorithm is presented for this more realistic CARP. Inspired by the second version of the Non-dominated sorted genetic algorithm framework, the procedure is improved by using good constructive heuristics to seed the initial population and by including a local search procedure. The new framework and its different flavour is appraised on three sets of classical CARP instances comprising 81 files.Yet designed for a bi-objective problem, the best versions are competitive with state-of-the-art metaheuristics for the single objective CARP, both in terms of solution quality and computational efficiency: indeed, they retrieve a majority of proven optima and improve two best-known solutions.     

Exact and heuristic algorithms for the interval data robust assignment problem

We consider the Assignment Problem with interval data, where it is assumed that only upper and lower bounds are known for each cost coefficient. It is required to find a minmax regret assignment. The problem is known to be strongly NP-hard. We present and compare computationally several exact and heuristic methods, including Benders decomposition, using CPLEX, a variable depth neighborhood local search, and two hybrid population-based heuristics. We report results of extensive computational experiments.     

A dynamic programming algorithm for tree-like weighted set packing problem

In hierarchical organizations, hierarchical structures naturally correspond to nested sets. That is, we have a collection of sets such that for any two sets, either one of them is a subset of the other, or they are disjoint. In other words, a nested set system forms a hierarchy in the form of a tree structure. The task assignment problem on such hierarchical organizations is a real life problem. In this paper, we introduce the tree-like weighted set packing problem, which is a weighted set packing problem restricted to sets forming tree-like hierarchical structure. We propose a dynamic programming algorithm with cubic time complexity.     

On the variable-depth-search heuristic for the linear-cost generalized assignment problem

The classical assignment problem seeks to determine a mapping between a set of assignees and a set of assignments. The linear cost assignment problem (LCGAP), as a generalized model, incorporates the relative workloads between assignees and assignments. Although LCGAP is computationally intractable, it has been extensively studied because of its practical implications in many real world situations. Variable-depth-search heuristic (VDSH) method is one of the solution methods that have been developed to produce quality near-optimal solutions to LCGAP. The main structure of VDSH consists of two basic operations: reassign and swap. In this paper, we make further observations on this effective heuristic method through a series of computational experiments. The numerical results statistically evince that different combina-tions of these two operations will result in solutions of different quality levels. These findings are expected to have similar implications to search heuristics for other optimization problems.     

An intelligent moving object optimization algorithm for design problems with mixed variables, mixed constraints and multiple objectives

This paper presents an optimization algorithm for engineering design problems having a mix of continuous, discrete and integer variables; a mix of linear, non-linear, differentiable, non-differential, equality, inequality and even discontinuous design constraints; and conflicting multiple design objectives. The intelligent movement of objects (vertices and compounds) is simulated in the algorithm based on a Nelder–Mead simplex with added features to handle variable types, bound and design constraints, local optima, search initiation from an infeasible region and numerical instability, which are the common requirements for large-scale, complex optimization problems in various engineering and business disciplines. The algorithm is called an INTElligent Moving Object algorithm and tested for a wide range of benchmark problems. Validation results for several examples, which are manageable within the scope of this paper, are presented herein. Satisfactory results have been obtained for all the test problems, hence, highlighting the benefits of the proposed method.     

基于偏好矩阵遗传算法求解长期车辆合乘问题

针对长期车辆合乘问题（LTCPP）,提出带有偏好矩阵的遗传算法（PMGA）,将拥有私家车且目的地相同的用户群体分配到产生总花费最少的合乘小组。首先,建立计算基于全体用户费用成本的目标函数,构建以用户时间窗和车容量为约束的长期车辆合乘模型;然后,结合模型特点,在传统遗传算法（GA）的基础上,通过在交叉算子与变异算子中添加偏好矩阵记录并更新用户间的偏好信息来提高可行解的数量和质量。实验结果表明,在相同计算环境下,当用户数量小于200时,通过PMGA所获得的20个解中的最优解的值与最优化算法相同;而处理大规模的实例时,PMGA可以获得更高质量的解。所提算法可以明显提高长期车辆合乘问题的求解质量,在降低汽车尾气污染和减少交通拥挤等方面具有重要作用。     

A hybrid multi-objective shuffled frog-leaping algorithm for a mixed-model assembly line sequencing problem

In this paper, a mixed-model assembly line (MMAL) sequencing problem is studied. This type of production system is used to manufacture multiple products along a single assembly line while maintaining the least possible inventories. With the growth in customers’ demand diversification, mixed-model assembly lines have gained increasing importance in the field of management. Among the available criteria used to judge a sequence in MMAL, the following three are taken into account: the minimization of total utility work, total production rate variation, and total setup cost. Due to the complexity of the problem, it is very difficult to obtain optimum solution for this kind of problems by means of traditional approaches. Therefore, a hybrid multi-objective algorithm based on shuffled frog-leaping algorithm (SFLA) and bacteria optimization (BO) are deployed. The performance of the proposed hybrid algorithm is then compared with three well-known genetic algorithms, i.e. PS-NC GA, NSGA-II, and SPEA-II. The computational results show that the proposed hybrid algorithm outperforms the existing genetic algorithms, significantly in large-sized problems.     

Unit commitment problem with ramp rate constraint using a binary-real-coded genetic algorithm

The unit commitment problem (UCP) is a nonlinear mixed-integer optimization problem, encountered as one of the toughest problems in power systems. The problem becomes even more complicated when dynamic power limit based ramp rate constraint is taken into account. Due to the inadequacy of deterministic methods in handling large-size instances of the UCP, various metaheuristics are being considered as alternative algorithms to realistic power systems, among which genetic algorithm (GA) has been investigated widely since long back. Such proposals have been made for solving only the integer part of the UCP, along with some other approaches for the real part of the problem. Moreover, the ramp rate constraint is usually discussed only in the formulation part, without addressing how it could be implemented in an algorithm. In this paper, the GA is revisited with an attempt to solve both the integer and real parts of the UCP using a single algorithm, as well as to incorporate the ramp rate constraint in the proposed algorithm also. In the computational experiment carried out with power systems up to 100 units over 24-h time horizon, available in the literature, the performance of the proposed GA is found quite satisfactory in comparison with the previously reported results.     

A population-based algorithm for solving linear assignment problems with two objectives

The paper presents a population-based algorithm for computing approximations of the efficient solution set for the linear assignment problem with two objectives. This is a multiobjective metaheuristic based on the intensive use of three operators – a local search, a crossover and a path-relinking – performed on a population composed only of elite solutions. The initial population is a set of feasible solutions, where each solution is one optimal assignment for an appropriate weighted sum of two objectives. Genetic information is derived from the elite solutions, providing a useful genetic heritage to be exploited by crossover operators. An upper bound set, defined in the objective space, provides one acceptable limit for performing a local search. Results reported using referenced data sets have shown that the heuristic is able to quickly find a very good approximation of the efficient frontier, even in situation of heterogeneity of objective functions. In addition, this heuristic has two main advantages. It is based on simple easy-to-implement principles, and it does not need a parameter tuning phase.     

求解指派问题的一次性分配算法

匈牙利算法是求解指派问题的全局最优求解算法,但是经典的匈牙利算法存在着实现难、处理速度慢等不足。提出了一种改进匈牙利算法,对匈牙利算法寻找独立零的次序进行了改进,从而避免了匈牙利算法通常需要进行多次试分配的不足。针对改进前后两种算法的复杂度、运算时间、精确度等进行了对比分析,结果表明,改进的算法是一种高精度的近似最优求解算法;与匈牙利算法相比,改进的算法易于编程实现,且时间花费较低,是一种适用于工程实时应用的有效求解算法。     

求解护士分配问题的矩阵编码进化算法

护士分配问题是护理人力资源配置中的一个优化问题,也是计算机科学中的很有挑战性的NP难问题。根据中国实际医院需求日益增加的情况,研究改良了随机规划（SPA）模型,建立了优化的多场景护士分配模型。基于护士与病人的对应关系,设计了0/1矩阵作为算法编码;采用矩阵编码进化算法（EAs with Matrix Coding）框架对矩阵编码进行迭代。基于求同存异的思想,运用随机编码部分介入技术实现了矩阵型染色体的变异算子。实验结果表明,与目前的随机贪心算法、基于Bender's分解的启发式算法和随机扰动遗传算法相比,提出的矩阵编码进化算法在求解护士分配问题时能得到更高质量、更稳定的解;在多场景和多约束前提下,其平均性能优势更加明显。     

The hybrid genetic algorithm with two local optimization strategies for traveling salesman problem

Traveling salesman problem (TSP) is proven to be NP-complete in most cases. The genetic algorithm (GA) is improved with two local optimization strategies for it. The first local optimization strategy is the four vertices and three lines inequality, which is applied to the local Hamiltonian paths to generate the shorter Hamiltonian circuits (HC). After the HCs are adjusted with the inequality, the second local optimization strategy is executed to reverse the local Hamiltonian paths with more than 2 vertices, which also generates the shorter HCs. It is necessary that the two optimization strategies coordinate with each other in the optimization process. The two optimization strategies are operated in two structural programs. The time complexity of the first and second local optimization strategies are O(n) and O(n³), respectively. The two optimization strategies are merged into the traditional GA. The computation results show that the hybrid genetic algorithm (HGA) can find the better approximate solutions than the GA does within an acceptable computation time.     

A decomposition based memetic algorithm for multi-objective vehicle routing problem with time windows

Multi-objective evolutionary algorithm based on decomposition (MOEA/D) provides an excellent algorithmic framework for solving multi-objective optimization problems. It decomposes a target problem into a set of scalar sub-problems and optimizes them simultaneously. Due to its simplicity and outstanding performance, MOEA/D has been widely studied and applied. However, for solving the multi-objective vehicle routing problem with time windows (MO-VRPTW), MOEA/D faces a difficulty that many sub-problems have duplicated best solutions. It is well-known that MO-VRPTW is a challenging problem and has very few Pareto optimal solutions. To address this problem, a novel selection operator is designed in this work to enhance the original MOEA/D for dealing with MO-VRPTW. Moreover, three local search methods are introduced into the enhanced algorithm. Experimental results indicate that the proposed algorithm can obtain highly competitive results on Solomon׳s benchmark problems. Especially for instances with long time windows, the proposed algorithm can obtain more diverse set of non-dominated solutions than the other algorithms. The effectiveness of the proposed selection operator is also demonstrated by further analysis.     

A negative dual rectangle cancellation algorithm for the linear assignment problem

In this paper, we consider three alternative primal models and their corresponding alternative dual models for the linear assignment problem. We then define the concept of Negative Dual Rectangle (NDR) and suggest an algorithm that solves two of these dual problems by repeatedly finding and cancelling NDRs until it yields an optimal solution to the assignment problem. The algorithm is simple, flexible, efficient, and unified. We also introduce the notion of partial zero cover as an interpretation of an NDR. We then introduce some heuristic methods for finding NDRs. We also state and prove a lemma to establish the optimal use of an NDR. Furthermore, we show that on a new class of benchmark instances that is introduced in this paper the running time of our algorithm is highly superior to a well-known pure shortest path algorithm.     

Genetic algorithm to solve the p-centre and p-radius problem on a network

The p-centre problem is to locate p facilities on a network so as to minimize the largest distance from a demand point to its nearest facility. The problem is NP-complete for an arbitrary network. In this paper, genetic algorithms (GAs) to solve this problem are developed via two different representations. The nodes are taken as weighted, and the demand points are assumed to coincide with the nodes. Computational results obtained from the proposed GAs for different network sizes and different values of p are presented and compared for two different representations.     

An improved multi-objective evolutionary algorithm for the vehicle routing problem with time windows

The vehicle routing problem with time windows is a complex combinatorial problem with many real-world applications in transportation and distribution logistics. Its main objective is to find the lowest distance set of routes to deliver goods, using a fleet of identical vehicles with restricted capacity, to customers with service time windows. However, there are other objectives, and having a range of solutions representing the trade-offs between objectives is crucial for many applications. Although previous research has used evolutionary methods for solving this problem, it has rarely concentrated on the optimization of more than one objective, and hardly ever explicitly considered the diversity of solutions. This paper proposes and analyzes a novel multi-objective evolutionary algorithm, which incorporates methods for measuring the similarity of solutions, to solve the multi-objective problem. The algorithm is applied to a standard benchmark problem set, showing that when the similarity measure is used appropriately, the diversity and quality of solutions is higher than when it is not used, and the algorithm achieves highly competitive results compared with previously published studies and those from a popular evolutionary multi-objective optimizer.     

An improved genetic algorithm with conditional genetic operators and its application to set-covering problem

The genetic algorithm (GA) is a popular, biologically inspired optimization method. However, in the GA there is no rule of thumb to design the GA operators and select GA parameters. Instead, trial-and-error has to be applied. In this paper we present an improved genetic algorithm in which crossover and mutation are performed conditionally instead of probability. Because there are no crossover rate and mutation rate to be selected, the proposed improved GA can be more easily applied to a problem than the conventional genetic algorithms. The proposed improved genetic algorithm is applied to solve the set-covering problem. Experimental studies show that the improved GA produces better results over the conventional one and other methods.