面向多起点均衡多旅行商问题的进化算法

为解决多起点均衡多旅行商问题，分析问题的特点，从优化旅行商的起点、最小化所有旅行商总路程和维持各旅行商路径均衡的角度出发，提出一种基于改进交叉、变异操作的遗传算法。根据均衡多旅行商问题的优化目标，构建新型评价函数，设计双染色体编码方式。在此基础上，引入改进的三交换启发式交叉操作并设计双变异策略。在经典旅行商问题的测试集TSPLIB上，与其它求解多旅行商问题的进化算法进行对比，验证算法的有效性。     

基于混合算法的均衡路程MTSP研究

给出了MTSP的整数线性规划模型、分类,提出了均衡各旅行商访问路程和均衡各旅行商访问人数的多目标MTSP问题.针对均衡各旅行商访问路程的MTSP设计了相应的求解算法,求解算法为遗传算法和2-0pt的混合算法.给出了相应的示例和实验结果,并对实验结果的有效性进行了研究.     

基于遗传算法的多旅行商问题研究

针对所有旅行商路径总和最小为优化标准的多旅行商一类问题,用遗传算法优化,并提出了矩阵解码方法。对距离非对称的多旅行商问题的实例进行了仿真,并对不同交叉算子性能进行了比较。结果表明,该算法是有效的,适用于距离对称和非对称的多旅行商问题求解。     

考虑工作量平衡的多旅行商问题及其求解

根据多旅行商问题（MTSP）特点,针对最小化各旅行商最长路线这一优化目标,提出改进蚁群算法（IACO）。最小化各旅行商最长路线考虑各旅行商的工作量平衡,更具实际应用意义。算法中信息素更新与限制遵循最大最小蚁群算法（MMAS）框架,为提高算法性能设计混合局域搜索算法。利用文献中标准算例进行检验,结果表明,所设计蚁群算法与三种遗传算法相比表现出较强竞争性。     

带冲突图的着色旅行商问题模型与算法

着色旅行商问题是多旅行商问题的一个重要变种，它被广泛地应用于带有重叠区域的多机工程系统。现有的着色旅行商问题难以有效应对带冲突的场景，这种冲突通常表现为两个城市不允许被同一旅行商访问。受带冲突图的组合优化问题的启发，提出了带冲突图的着色旅行商问题，且给出了其形式化的表达。带冲突图的着色旅行商问题是一个NP难问题，精确算法求解器CPLEX仅能在小规模问题实例上获得问题的最优解。为了求解更大规模的实例，提出了一个有效的模因算法。该模因算法采用了自适应大规模邻域搜索算子。对比模因算法和精确算法，模因算法在20个小规模实例中的9个结果更好，在18个实例上展现了其远超精确算法的求解速度。而比较模因算法和其他启发式算法，模因算法在全部14个中等规模实例上均取得了更好结果。此外，消融实验结果验证了模因算法中自适应大规模领域搜索算子的有效性。     

基于递阶遗传算法的多旅行商问题优化*

旅行商问题是一个经典的NP问题,对多人旅行商问题的求解则更具有意义。为了解决所有旅行商路径总和最小为优化标准的多旅行商一类问题,提出了一种递阶遗传算法和矩阵解码方法。该算法根据问题的特点,采用一种递阶编码方案,此编码与多旅行商问题一一对应。用递阶遗传算法优化多旅行商问题无须设计专门的遗传算子,操作简单,并且解码方法适于求解距离对称和距离非对称的多旅行商问题。计算结果表明,递阶遗传算法是有效的,能适用于优化多旅行商问题。     

一种求解双目标旅行商问题的进化算法

双目标旅行商问题是经典TSP问题的扩展和延伸,具有很强的实际研究意义。本文在多目标进化算法NS-GA-Ⅱ的基础上设计了一种双目标进化算法以求解该问题。其中,提出了按需分层的非支配前沿集分层方法,混合了爬山法以提高局部寻优能力．采用了类OX的杂交算子和逆转变异等遗传算子。实验结果表明,提出的方法比NSGA—Ⅱ具有更好的运行效率及更好的求解结果。     

最小比率旅行商问题的引力搜索算法求解

经典旅行商问题的目标函数是总路程最小,而在实际情况中往往会考虑旅行商的收益问题,研究了以总路程和总收益之比为目标函数的最小比率旅行商问题.由于该问题的目标函数是非线性的,比求解目标函数是线性的旅行商问题更为困难,为有效求解该问题,提出一种引力搜索算法.算法基于万有引力定律和牛顿第二定律进行寻优,并采用速度和位置的计算模型.同时结合随机键的编码方法,将搜索个体的连续位置转换为离散的城市访问顺序.给出了算法的具体实现方案,并通过仿真和比较实验验证算法的优化性能.实验结果表明该算法可以有效求解最小比率旅行商问题.     

子旅行商问题及其蚁群求解算法

扩展旅行商问题是根据实际需要对传统旅行商问题的一种延伸和拓展,在实际问题中有许多有趣的应用。提出一种新的扩展旅行商问题(子旅行商问题),传统旅行商问题仅仅是子旅行商问题的一种特例。然后根据子旅行商问题的定义对蚁群系统算法进行改造,设计了一种有效的求解子旅行商问题的蚁群算法,并根据子旅行商问题的特点设计了一种高效的邻域局部搜索技术来提高解的质量。最后在10个TSPLIB范例上进行比较实验。结果表明:改进的蚁群算法能够有效求解提出的子旅行商问题,设计的邻域局部搜索技术是有效的。     

求解旅行商问题的混合蚂蚁算法

旅行商问题是一个经典的NP问题，文中给出了一个有效的求解旅行商问题的混合蚂蚁算法。算法设计了初始信息素量设置方案和信息素的更新方法，限制了蚂蚁转移的目标城市数，并使用2-Opt方法对路径进行优化。数据实验表明，该算法是有效的。     

Choquet optimal set in biobjective combinatorial optimization

We study in this paper the generation of the Choquet optimal solutions of biobjective combinatorial optimization problems. Choquet optimal solutions are solutions that optimize a Choquet integral. The Choquet integral is used as an aggregation function, presenting different parameters, and allowing to take into account the interactions between the objectives. We develop a new property that characterizes the Choquet optimal solutions. From this property, a general method to easily generate these solutions in the case of two objectives is defined. We apply the method to two classical biobjective optimization combinatorial optimization problems: the biobjective knapsack problem and the biobjective minimum spanning tree problem. We show that Choquet optimal solutions that are not weighted sum optimal solutions represent only a small proportion of the Choquet optimal solutions and are located in a specific area of the objective space, but are much harder to compute than weighted sum optimal solutions.     

A Market-based Solution to the Multiple Traveling Salesmen Problem

This paper describes a market-based solution to the problem of assigning mobile agents to tasks. The problem is formulated as the multiple depots, multiple traveling salesmen problem (MTSP), where agents and tasks operate in a market to achieve near-optimal solutions. We consider both the classical MTSP, in which the sum of all tour lengths is minimized, and the Min-Max MTSP, in which the longest tour is minimized. We compare the market-based solution with direct enumeration in small scenarios, and show that the results are nearly optimal. For the classical MTSP, we compare our results to linear programming, and show that the results are within 1 % of the best cost found by linear programming in more than 90 % of the runs, with a significant reduction in runtime. For the Min-Max case, we compare our method with Carlsson’s algorithm and show an improvement of 5 % to 40 % in cost, albeit at an increase in runtime. Finally, we demonstrate the ability of the market-based solution to deal with changes in the scenario, e.g., agents leaving and entering the market. We show that the market paradigm is ideal for dealing with these changes during runtime, without the need to restart the algorithm, and that the solution reacts to the new scenarios in a quick and near-optimal way.     

An algorithm for the biobjective integer minimum cost flow problem

In this paper, we study the single commodity flow problems, optimizing two objectives simultaneously, where the flow values must be integer values. We propose a method that finds all the efficient integer points in the objective space. Our algorithm performs two phases. In the first phase, all integer points on the efficient boundary are found and in the second phase, the efficient integer points that do not lie on the efficient boundary are calculated. In addition, we carry out a computational experiment showing that the number of efficient integer solutions that do not lie on the efficient boundary is greater than the number of integer solutions on the efficient boundary.Scope and purposeIn many combinatorial optimization problems, the selection of the optimum solution takes into account more than one criterion. For example, in transportation problems or in network flows problems, the criteria that can be considered are the minimization of the cost for selected routes, the minimization of arrival times at the destinations, the minimization of the deterioration of goods, the minimization of the load capacity that would not be used in the selected vehicles, the maximization of safety, reliability, etc. Often, these criteria are in conflict and for this reason, a multiobjective network flow formulation of the problem is necessary. The solution to this problem is searched for among the set of efficient points. Although multiobjective network flow problems can be solved using the techniques available for the multiobjective linear programming problem, network-based methods are computationally better. The multicriteria minimum cost flow problem has already merited the attention of several authors and the case which has been considered in literature is that which has two objectives, where the continuous flow values are permissible. However, the integer case of the biobjective minimum cost flow problem has scarcely been studied. Whereas, in many real network flow problems, integer values on flow values are required. In this paper, we propose an approach to solve the biobjective integer minimum cost flow problem. An algorithm to obtain all efficient integer solutions of this problem is introduced. This method is characterized by the use of the classic resolution tools of network flow problems, such as the network simplex method. It does not utilize the biobjective integer linear programming methodology. Furthermore, the method does not calculate dominated solutions, so it is not necessary to incorporate tools to eliminate dominated solutions.     

Computing all efficient solutions of the biobjective minimum spanning tree problem

A common way of computing all efficient (Pareto optimal) solutions for a biobjective combinatorial optimisation problem is to compute first the extreme efficient solutions and then the remaining, non-extreme solutions. The second phase, the computation of non-extreme solutions, can be based on a “k-best” algorithm for the single-objective version of the problem or on the branch-and-bound method. A k-best algorithm computes the k-best solutions in order of their objective values. We compare the performance of these two approaches applied to the biobjective minimum spanning tree problem. Our extensive computational experiments indicate the overwhelming superiority of the k-best approach. We propose heuristic enhancements to this approach which further improve its performance.     

Stochastic facility and transfer point covering problem with a soft capacity constraint

Existing models for transfer point location problems (TPLPs) do not guarantee the desired service time to customers. In this paper, a facility and TPLP is formulated based on a given service time that is targeted by a decision maker. Similar to real‐world situations, transportation times and costs are assumed to be random. In general, facilities are capacitated. However, in emergency services, they are not allowed to reject the customers for out of capacity reasons. Therefore, a soft capacity constraint for the facilities and a second objective to minimize the overtime in the facility with highest assigned demand are proposed. To solve the biobjective model with random variables, a variance minimization technique and chance‐constraint programming are applied. Thereafter, using fuzzy multiple objective linear programming, the proposed biobjective model is converted to a single objective. Computational results on 30 randomly designed experimental problems confirm satisfactory performance of the proposed model in reducing the variance of solutions as well as the overtime in the busiest facility.     

Three new metrics to measure the convergence of metaheuristics towards the Pareto frontier and the aesthetic of a set of solutions in biobjective optimization

In this paper, some new quality metrics concerning the evaluation of performances of biobjective optimization methods relating to the generation of the Pareto frontier are presented. A new metric for the calculation of the running speed of a multiobjective optimization method is also presented.These metrics are tested on two biobjective scalarization functions (Weighted sum and Tchebychev aggregation of objective functions) handled by a metaheuristic (Simulated Annealing).     

A Dijkstra-like method computing all extreme supported non-dominated solutions of the biobjective shortest path problem

We address the problem of determining all extreme supported solutions of the biobjective shortest path problem. A novel Dijkstra-like method generalizing Dijkstra׳s algorithm to this biobjective case is proposed. The algorithm runs in O(N(m+n log n)) time to solve one-to-one and one-to-all biobjective shortest path problems determining all extreme supported non-dominated points in the outcome space and one supported efficient path associated with each one of them. Here n is the number of nodes, m is the number of arcs and N is the number of extreme supported points in outcome space for the one-to-all biobjective shortest path problem. The memory space required by the algorithm is O(n+m) for the one-to-one problem and O(N+m) for the one-to-all problem. A computational experiment comparing the performance of the proposed methods and state-of-the-art methods is included.     

New reduction strategy in the biobjective knapsack problem

In this paper, the admissible region of a biobjective knapsack problem is our main interest. Although the reduction of feasible region has been studied by some authors, yet more investigation has to be done in order to deeply explore the domain before solving the problem. We propose, however, a new technique based on extreme supported efficient solutions combined with the dominance relationship between items' efficiency. An illustration of the algorithm by a didactic example is given and some experiments are presented, showing the efficiency of the procedure compared to the previous techniques found in the literature.     

The multiobjective multidimensional knapsack problem: a survey and a new approach

The knapsack problem (KP) and its multidimensional version (MKP) are basic problems in combinatorial optimization. In this paper, we consider their multiobjective extension (MOKP and MOMKP), for which the aim is to obtain or approximate the set of efficient solutions. In the first step, we classify and briefly describe the existing works that are essentially based on the use of metaheuristics. In the second step, we propose the adaptation of the two‐phase Pareto local search (2PPLS) to the resolution of the MOMKP. With this aim, we use a very large scale neighborhood in the second phase of the method, that is the PLS. We compare our results with state‐of‐the‐art results and show that the results we obtained were never reached before by heuristics for biobjective instances. Finally, we consider the extension to three‐objective instances.