非确定型指派问题的求解算法

考虑了一类非确定型指派问题,每人所承担的工作数不确定,按每人至少承担一项工作,每项工作只允许一人承担的指派原则,针对人员无工作数限制和有工作数限制两种情况加以讨论和分析,借鉴Floyd算法的负回路思想,提出了一种迭代算法,并给出了应用此算法求解的具体实例。实验表明：与其他求解算法相比,该算法求解规模小,效率高,应用简便,易于编程实现。     

A novel global harmony search algorithm for task assignment problem

The objective of task assignment problem (TAP) is to minimize the sum of interprocessor communication and task processing costs for a distributed system which subjects to several resource constraints. We use a novel global harmony search algorithm (NGHS) to solve this problem, and the NGHS algorithm has demonstrated higher efficiency than the improved harmony search algorithm (IHS) on finding the near optimal task assignment. We also devise a new method called normalized penalty function method to tradeo^® the costs and the constraints. A large number of experiments show that our algorithm performs well on finding the near optimal task assignment, and it is a viable approach for the task assignment problem.     

A hybrid approach based on stochastic competitive Hopfield neural network and efficient genetic algorithm for frequency assignment problem

This paper presents a hybrid efficient genetic algorithm (EGA) for the stochastic competitive Hopfield (SCH) neural network, which is named SCH–EGA. This approach aims to tackle the frequency assignment problem (FAP). The objective of the FAP in satellite communication system is to minimize the co-channel interference between satellite communication systems by rearranging the frequency assignment so that they can accommodate increasing demands. Our hybrid algorithm involves a stochastic competitive Hopfield neural network (SCHNN) which manages the problem constraints, when a genetic algorithm searches for high quality solutions with the minimum possible cost. Our hybrid algorithm, reflecting a special type of algorithm hybrid thought, owns good adaptability which cannot only deal with the FAP, but also cope with other problems including the clustering, classification, and the maximum clique problem, etc. In this paper, we first propose five optimal strategies to build an efficient genetic algorithm. Then we explore three hybridizations between SCHNN and EGA to discover the best hybrid algorithm. We believe that the comparison can also be helpful for hybridizations between neural networks and other evolutionary algorithms such as the particle swarm optimization algorithm, the artificial bee colony algorithm, etc. In the experiments, our hybrid algorithm obtains better or comparable performance than other algorithms on 5 benchmark problems and 12 large problems randomly generated. Finally, we show that our hybrid algorithm can obtain good results with a small size population.     

A great deluge and tabu search hybrid with two-stage memory support for quadratic assignment problem

A two-stage memory architecture is maintained within the framework of great deluge algorithm for the solution of single-objective quadratic assignment problem. Search operators exploiting the accumulated experience in memory are also implemented to direct the search towards more promising regions of the solution space. The level-based acceptance criterion of the great deluge algorithm is applied for each best solution extracted in a particular iteration. The use of short- and long-term memory-based search supported by effective move operators resulted in a powerful combinatorial optimization algorithm. A successful variant of tabu search is employed as the local search method that is only applied over a few randomly selected memory elements when the second stage memory is updated. The success of the presented approach is illustrated using sets of well-known benchmark problems and evaluated in comparison to well-known combinatorial optimization algorithms. Experimental evaluations clearly demonstrate that the presented approach is a competitive and powerful alternative for solving quadratic assignment problems.     

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

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

A fuzzy approach for the reviewer assignment problem

Assignment of experts to project proposals is a significant task for funding agencies which have to assess the potential value of the research and development (R&D) projects through peer review. The problem is known as reviewer assignment problem and has real-world applications in funding agencies, conferences and research journals. Given a set of experts and a set of proposals; the problem can be defined as assigning the most suitable experts to the proposals under some constraints, which are generally encountered by funding agencies. In this study, a fuzzy model is offered to solve the reviewer assignment problem. The objective of the model is to maximize the total matching degree of assigned experts under some constraints such as cost of forming a panel and the size of a panel. The matching degrees are defined using linguistic variables to denote the expertise of each expert with respect to each proposal. The fuzzy mathematical model, which also takes into account different constraints related to the problem, is solved via the selected fuzzy ranking methods namely; the signed distance method and the method of ranking fuzzy numbers with integral value. The solution of an example problem – inspired from a real-life situation – with both of the mentioned methods revealed the effectiveness of the solution approach. It is believed that the use of the offered fuzzy approach could improve the accuracy of the decisions made by funding agencies.     

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

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

Variable neighborhood search for the linear ordering problem

Given a matrix of weights, the linear ordering problem (LOP) consists of finding a permutation of the columns and rows in order to maximize the sum of the weights in the upper triangle. This NP-complete problem can also be formulated in terms of graphs, as finding an acyclic tournament with a maximal sum of arc weights in a complete weighted graph. In this paper, we first review the previous methods for the LOP and then propose a heuristic algorithm based on the variable neighborhood search (VNS) methodology. The method combines different neighborhoods for an efficient exploration of the search space. We explore different search strategies and propose a hybrid method in which the VNS is coupled with a short-term tabu search for improved outcomes. Our extensive experimentation with both real and random instances shows that the proposed procedure competes with the best-known algorithms in terms of solution quality, and has reasonable computing-time requirements.Variable neighborhood search (VNS) is a metaheuristic method that has recently been shown to yield promising outcomes for solving combinatorial optimization problems. Based on a systematic change of neighborhood in a local search procedure, VNS uses both deterministic and random strategies in search for the global optimum.In this paper, we present a VNS implementation designed to find high quality solutions for the NP-hard LOP, which has a significant number of applications in practice. The LOP, for example, is equivalent to the so-called triangulation problem for input–output tables in economics. Our implementation incorporates innovative mechanisms to include memory structures within the VNS methodology. Moreover we study the hybridization with other methodologies such as tabu search.     

随机需求车辆路径问题及混合变邻域分散搜索算法求解

随机需求车辆路径问题(capacitated vehicle routing problem with stochastic demand,CVRPSD)是对带容量约束车辆路径问题(capacitated vehicle routing problem,CVRP)的扩展,需求不确定的特点使其较CVRP更复杂,对求解方法要求更高.基于先预优化后重调度思想,提出两阶段的混合变邻域分散搜索算法(variable neighborhood scatter search,VNSS)对该问题进行求解:预优化阶段构建随机机会约束规划模型,对客户点随机需求作机会约束确定型等价处理,生成最优预优化方案;重调度阶段采用新的点重优化策略进行线路调整,降低因失败点而产生的额外成本,减少对人工和车辆的占用.算例验证表明,随机机会约束模型和两阶段变邻域分散搜索算法在求解CVRPSD时较为有效,点重优化策略调整效果较佳.     

An adaptive large neighborhood search heuristic for solving a robust gate assignment problem

With the rapid growth of air traffic demand, airport capacity becomes a major bottleneck within the air traffic control systems. Minor disturbances may have a large impact on the airport surface operations due to the overly tight schedules, which results in frequent gate conflict occurrences during airport’s daily operations. A robust gate schedule that is resilient to disturbances is essential for an airport to maintain a good performance. Unfortunately, there is no efficient expert system available for the airport managers to simultaneously consider the traditional cost (the aircraft tow cost, transfer passenger cost) and the robustness. To fill this gap, in this paper, we extend the traditional gate assignment problem and consider a wider scope, in which the traditional costs and the robustness are simultaneously considered. A mathematical model is first built, which leads to a complex non-linear model. To efficiently solve this model, an adaptive large neighborhood search (ALNS) algorithm is then designed. We novelly propose multiple local search operators by exploring the characteristics of the gate assignment problem. The comparison with the benchmark algorithm shows the competitiveness of proposed algorithm in solving the considered problem. Moreover, the proposed methodology also has great potential from the practical perspective since it can be easily integrated into current expert systems to help airport managers make satisfactory decisions.     

MaxMinMin p-dispersion problem: A variable neighborhood search approach

In this work we have developed a Variable Neighborhood Search (VNS) method in order to solve the MaxMinMin p-dispersion problem, which adds a new type of plateau search mechanism to the classical VNS metaheuristic framework. Besides, several other contributions have been made to the basic VNS heuristic in terms of the ascent and perturbation functions. To the best of our knowledge this is the first application of the VNS to the MaxMinMin problem and our approach, compared to previous methods, finds or improves the results for all of the large-sized benchmarks with low computational efforts. Finding most of the proven optimal solutions in a fraction of a second, the robustness and quality of the solutions and the low complexity of the methods demonstrate the strength of the proposed heuristic solution procedures.     

Study on an improved adaptive PSO algorithm for solving multi-objective gate assignment

Gate is a key resource in the airport, which can realize rapid and safe docking, ensure the effective connection between flights and improve the capacity and service efficiency of airport. The minimum walking distances of passengers, the minimum idle time variance of each gate, the minimum number of flights at parking apron and the most reasonable utilization of large gates are selected as the optimization objectives, then an efficient multi-objective optimization model of gate assignment problem is proposed in this paper. Then an improved adaptive particle swarm optimization(DOADAPO) algorithm based on making full use of the advantages of Alpha-stable distribution and dynamic fractional calculus is deeply studied. The dynamic fractional calculus with memory characteristic is used to reflect the trajectory information of particle updating in order to improve the convergence speed. The Alpha-stable distribution theory is used to replace the uniform distribution in order to escape from the local minima in a certain probability and improve the global search ability. Next, the DOADAPO algorithm is used to solve the constructed multi-objective optimization model of gate assignment in order to fast and effectively assign the gates to different flights in different time. Finally, the actual flight data in one domestic airport is used to verify the effectiveness of the proposed method. The experiment results show that the DOADAPO algorithm can improve the convergence speed and enhance the local search ability and global search ability, and the multi-objective optimization model of gate assignment can improve the comprehensive service of gate assignment. It can effectively provide a valuable reference for assigning the gates in hub airport.     

An ANTS heuristic for the frequency assignment problem

The problem considered in this paper consists in assigning frequencies to radio links between base stations and mobile transmitters in order to minimize the global interference over a given region. This problem is NP-hard and few results have been reported on techniques for solving it to optimality. We have applied to this problem an ANTS metaheuristic, that is, an approach following the ant colony optimization paradigm. Computational results, obtained on a number of standard problem instances, testify the effectiveness of the proposed approach.     

A variable neighborhood search simheuristic for the multiperiod inventory routing problem with stochastic demands

The inventory routing problem (IRP) combines inventory management and delivery route‐planning decisions. This work presents a simheuristic approach that integrates Monte Carlo simulation within a variable neighborhood search (VNS) framework to solve the multiperiod IRP with stochastic customer demands. In this realistic variant of the problem, our goal is to establish the optimal refill policies for each customer–period combination, that is, those individual refill policies that minimize the total expected cost over the periods. This cost is the aggregation of both expected inventory and routing costs. Our simheuristic algorithm allows to consider the inventory changes between periods generated by the realization of the random demands in each period, which have an impact on the quantities to be delivered in the next period and, therefore, on the associated routing plans. A range of computational experiments are carried out in order to illustrate the potential of our simulation–optimization approach.     

求解护士排班问题的变邻域搜索算法

变邻域搜索算法是求解护士排班问题的一个有效算法,其扰动方法对算法性能有显著影响。为提高护士排班问题中护士的满意度,提出一个改进的变邻域搜索(IVNS)算法。该算法使用了三种邻域结构,而且当使用任意的邻域都不能进一步改进当前解时,设计了一个对当前最优解进行扰动的方法,即在排班期间内随机地选择两天,在不违反硬性约束的条件下选出一组值班护士并交换他们在这两天中的班次。在2010年举行的第一次全球护士排班大赛提供的一组公共测试集上与一个混合变邻域搜索(HVNS)算法进行了比较,在Sprint-early、Medium-early和Long-early组算例上的结果表明,IVNS算法的最优值至少不劣于HVNS,而平均值均优于HVNS;IVNS算法的最大方差为0.72,波动范围小,求解性能稳定。IVNS的扰动方案对现有方案的扰动较小,能有效跳出当前局部最优,增强变邻域搜索算法的优化能力,与HVNS算法相比,其求解性能更优。     

On the initialization methods of an exterior point algorithm for the assignment problem

In this paper, we present a theoretical investigation and an extensive computational study of exterior point simplex algorithm (EPSA) initialization methods for the assignment problem (AP). We describe the exterior point algorithm using three different initialization methods. Effective implementations are explored for each initialization method. Then we perform an experimental evaluation on a large set of benchmark problems from the TSPLib 95 and OR Library collections. The results obtained demonstrate the advantages of the three initialization methods. Finally, we give a theoretical justification of the initialization methods efficiency. We explain theoretically the computational ranking for these methods.     

平面选址问题的引力搜索算法求解

为求解平面选址问题,给出了一种基于引力搜索算法的求解方法。算法利用万有引力定律进行全局搜索,采用一种邻域搜索方法进行局部搜索,实现算法全局优化和局部优化的平衡。通过大量实验和与现有求解方法的比较,结果验证了算法的可行性和有效性。     

An addendum on the incremental assignment problem

In Toroslu and Üçoluk [I.H. Toroslu, G. Üçoluk, Incremental assignment problem, Information Sciences 177 (2007) 1523-1529] the incremental assignment problem is defined as follows. 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. An O(n²) algorithm for the problem has been derived, with n the size of a partition in the bipartite graph. We point out that such a result can be found in literature.     

火力优化分配问题的小生境遗传蚂蚁算法

火力分配问题是NP难题,经典的求解算法存在指数级的时间复杂度。文中提出一种小生境遗传算法与蚁群优化算法相结合的小生境遗传蚂蚁算法,并针对具体问题提出蚂蚁搜索的禁忌规则。对该算法进行了实验,并将实验结果与其他算法进行比较分析,分析结果表明：新算法无论是在优化性能还是在时间性能都取得了非常好的效果。文中算法对其他的NP问题同样适用。     

一种新的离散粒子群算法在指派问题中的应用

指派问题在组合优化中属NP-Complete问题。提出了一种基于离散粒子群算法的求解方法。算法中每个粒子的位置代表了一种可行的指派方案,在迭代中通过交叉策略和局部搜索策略来更新粒子的位置,这既保证了粒子位置的可行性,又增加了粒子的多样性,避免陷入早熟收敛。通过实例仿真可以看出DPSO算法简洁,较以往算法具有更好的收敛性,能得到更优的解,能够求解匈牙利法不能求解的指派问题。对不同的问题,通过影响参数的调整,可以取得好的收敛效果。