Heuristics for the multi-period orienteering problem with multiple time windows

We present the multi-period orienteering problem with multiple time windows (MuPOPTW), a new routing problem combining objective and constraints of the orienteering problem (OP) and team orienteering problem (TOP), constraints from standard vehicle routing problems, and original constraints from a real-world application. The problem itself comes from a real industrial case. Specific route duration constraints result in a route feasibility subproblem. We propose an exact algorithm for this subproblem, and we embed it in a variable neighborhood search method to solve the whole routing problem. We then provide experimental results for this method. We compare them to a commercial solver. We also adapt our method to standard benchmark OP and TOP instances, and provide comparative tables with state-of-the-art algorithms.     

Multiscale production routing in multicommodity supply chains with complex production facilities

In this work, we introduce the multiscale production routing problem (MPRP), which considers the coordination of production, inventory, distribution, and routing decisions in multicommodity supply chains with complex continuous production facilities. We propose an MILP model involving two different time grids. While a detailed mode-based production scheduling model captures all critical operational constraints on the fine time grid, vehicle routing is considered in each time period of the coarse time grid. In order to solve large instances of the MPRP, we propose an iterative MILP-based heuristic approach that solves the MILP model with a restricted set of candidate routes at each iteration and dynamically updates the set of candidate routes for the next iteration. The results of an extensive computational study show that the proposed algorithm finds high-quality solutions in reasonable computation times, and in large instances, it significantly outperforms a standard two-phase heuristic approach and a solution strategy involving a one-time heuristic pre-generation of candidate routes. Similar results are achieved in an industrial case study, which considers a real-world industrial gas supply chain.     

Decentralized multi-objective bilevel decision making with fuzzy demands

Decisions in a decentralized organization often involve two levels. The leader at the upper level attempts to optimize his/her objective but is affected by the follower; the follower at the lower level tries to find an optimized strategy according to each of possible decisions made by the leader. When model a real-world bilevel decision problem, it also may involve fuzzy demands which appear either in the parameters of objective functions or constraints of the leader or the follower or both. Furthermore, the leader and the follower may have multiple conflict objectives that should be optimized simultaneously in achieving a solution. This study addresses both fuzzy demands and multi-objective issues and propose a fuzzy multi-objective bilevel programming model. It then develops an approximation branch-and-bound algorithm to solve multi-objective bilevel decision problems with fuzzy demands. Finally, two case-based examples further illustrate the proposed model and algorithm.     

基于Pareto多目标优化的工业传感网路由协议研究

工业传感网通常包含实时性和可靠性在内的多个性能指标,因此需要应用多目标优化方法设计路由算法,以满足性能需求。在收集树协议CTP的基础上进行改进,提出了基于Pareto多目标优化的路由协议TCTP。该协议首先在单跳链路质量评估中,增加单跳节点传输时延性能指标。然后运用Parcto原理通过路由拓扑建立了多路径路由,并基于数据传输的实时性和可靠性指标,选择多路径路由。最后使用有色Petri网对TCTP进行了形式化建模并利用CPN Tools工具进行了实现和验证。与CTP协议相比,TCTP协议不仅在选择传输路径上具有更强的适用性和灵活性,而且满足了工业上实时、可靠等多目标传输性能的需求。     

基于深度强化学习的电力物资配送多目标路径优化

针对现有电力物资车辆路径问题（EVRP）优化时考虑目标函数较为单一、约束不够全面,并且传统求解算法效率不高的问题,提出一种基于深度强化学习（DRL）的电力物资配送多目标路径优化模型和求解算法。首先,充分考虑了电力物资配送区域的加油站分布情况、物资运输车辆的油耗等约束,建立了以电力物资配送路径总长度最短、成本最低、物资需求点满意度最高为目标的多目标电力物资配送模型;其次,设计了一种基于DRL的电力物资配送路径优化算法DRL-EVRP求解所提模型。DRL-EVRP使用改进的指针网络（Ptr-Net）和Q-学习（Q-learning）算法结合的深度Q-网络（DQN）来将累积增量路径长度的负值与满意度之和作为奖励函数。所提算法在进行训练学习后,可直接用于电力物资配送路径规划。仿真实验结果表明,DRL-EVRP求解得到的电力物资配送路径总长度相较于扩展C-W（ECW）节约算法、模拟退火（SA）算法更短,且运算时间在可接受范围内,因此所提算法能更加高效、快速地进行电力物资配送路径优化。     

基于时空聚类求解带容积约束的选址-路径问题

选址-路径问题是供应链管理和物流系统规划中的一个重要问题,对总成本具有十分重要的影响.对考虑配送中心容积约束的带时间窗的选址-路径问题进行研究,建立以总成本最小和客户满意度最大为目标的多目标规划模型,提出两阶段算法对其进行求解.首先,利用k-means聚类算法确定配送中心选址;然后,提出一种基于时间-空间双因素的客户划分方法以确定配送中心所服务客户;最后,利用粒子群算法对各配送中心的配送路径进行规划.数值算例表明,所提出的算法较其他已有算法,均能有效地降低物流运作总成本及总配送路径长度,为解决带容积约束及时间窗的选址-路径问题提供了一种新的解决思路.     

Harmony search-based multi-objective optimization model for multi-site order planning with multiple uncertainties and learning effects

This paper addresses a multi-objective multi-site order planning problem in make-to-order manufacturing with the consideration of various real-world features such as production uncertainties and learning effects. A novel harmony search-based multi-objective optimization model, mainly integrating a harmony search based Pareto optimization (HSPO) process and a Monte Carlo simulation process, is developed to tackle this problem. A series of experiments are conducted to evaluate the effectiveness of the proposed model based on real industrial data. Results demonstrate that (1) the proposed model can effectively solve the problem investigated; and (2) the HSPO process can generate the optimization performance superior to those generated by a multi-objective genetic algorithm (NSGA-II)-based process and an industrial method.     

Local search techniques for a routing-packing problem

We propose a complex real-world problem in logistics that integrates routing and packing aspects. It can be seen as an extension of the Three-Dimensional Loading Capacitated Vehicle Routing Problem (3L-CVRP) introduced by Gendreau, Iori, Laporte, and Martello (2006). The 3L-CVRP consists in finding a set of routes that satisfies the demand of all customers, minimizes the total routing cost, and guarantees a packing of items that is feasible according to loading constraints. Our problem formulation includes additional constraints in relation to the stability of the cargo, to the fragility of items, and to the loading and unloading policy. In addition, it considers the possibility of split deliveries, so that each customer can be visited more than once. We propose a local search approach that considers the overall problem in a single stage. It is based on a composite strategy that interleaves simulated annealing with large-neighborhood search. We test our solver on 13 real-world instances provided by our industrial partner, which are very diverse in size and features. In addition, we compare our solver on benchmarks from the literature of the 3L-CVRP showing that our solver performs well compared to other approaches proposed in the literature.     

Multi-objective vehicle routing problem with time windows using goal programming and genetic algorithm

This paper presents a new model and solution for multi-objective vehicle routing problem with time windows (VRPTW) using goal programming and genetic algorithm that in which decision maker specifies optimistic aspiration levels to the objectives and deviations from those aspirations are minimized. VRPTW involves the routing of a set of vehicles with limited capacity from a central depot to a set of geographically dispersed customers with known demands and predefined time windows. This paper uses a direct interpretation of the VRPTW as a multi-objective problem where both the total required fleet size and total traveling distance are minimized while capacity and time windows constraints are secured. The present work aims at using a goal programming approach for the formulation of the problem and an adapted efficient genetic algorithm to solve it. In the genetic algorithm various heuristics incorporate local exploitation in the evolutionary search and the concept of Pareto optimality for the multi-objective optimization. Moreover part of initial population is initialized randomly and part is initialized using Push Forward Insertion Heuristic and λ-interchange mechanism. The algorithm is applied to solve the benchmark Solomon's 56 VRPTW 100-customer instances. Results show that the suggested approach is quiet effective, as it provides solutions that are competitive with the best known in the literature.     

A surrogate-assisted evolution strategy for constrained multi-objective optimization

In many real-world optimization problems, several conflicting objectives must be achieved and optimized simultaneously and the solutions are often required to satisfy certain restrictions or constraints. Moreover, in some applications, the numerical values of the objectives and constraints are obtained from computationally expensive simulations. Many multi-objective optimization algorithms for continuous optimization have been proposed in the literature and some have been incorporated or used in conjunction with expert and intelligent systems. However, relatively few of these multi-objective algorithms handle constraints, and even fewer, use surrogates to approximate the objective or constraint functions when these functions are computationally expensive. This paper proposes a surrogate-assisted evolution strategy (ES) that can be used for constrained multi-objective optimization of expensive black-box objective functions subject to expensive black-box inequality constraints. Such an algorithm can be incorporated into an intelligent system that finds approximate Pareto optimal solutions to simulation-based constrained multi-objective optimization problems in various applications including engineering design optimization, production management and manufacturing. The main idea in the proposed algorithm is to generate a large number of trial offspring in each generation and use the surrogates to predict the objective and constraint function values of these trial offspring. Then the algorithm performs an approximate non-dominated sort of the trial offspring based on the predicted objective and constraint function values, and then it selects the most promising offspring (those with the smallest predicted ranks from the non-dominated sort) to become the actual offspring for the current generation that will be evaluated using the expensive objective and constraint functions. The proposed method is implemented using cubic radial basis function (RBF) surrogate models to assist the ES. The resulting RBF-assisted ES is compared with the original ES and to NSGA-II on 20 test problems involving 2–15 decision variables, 2–5 objectives and up to 13 inequality constraints. These problems include well-known benchmark problems and application problems in manufacturing and robotics. The numerical results showed that the RBF-assisted ES generally outperformed the original ES and NSGA-II on the problems used when the computational budget is relatively limited. These results suggest that the proposed surrogate-assisted ES is promising for computationally expensive constrained multi-objective optimization.     

基于进化算法的无线传感器网络任播路由算法

在无线传感器网络WSN(Wireless Sensor Networks)中存在无线链路容易失效的现象,但大多数学者在设计路由算法时较多地关注网络生存期问题,而忽略路由健壮性问题.提出一种基于进化算法的WSN任播路由算法.该算法以网络生存期和路由健壮性为优化目标,并通过多目标进化算法寻找到两者的最佳适应值.实验验证了该算法的有效性,实验数据表明:相比较基于单目标优化(网络生存期)的任播路由算法,所提算法的网络生存期及路由健壮性两个性能的综合优化值优于前者;相比较传统单路径任播路由算法,所提算法的网络生存期、路由健壮性和可扩展性优于前者.     

Applying multi-objective ant colony optimization algorithm for solving the unequal area facility layout problems

The unequal area facility layout problem (UA-FLP) which deals with the layout of departments in a facility comprises of a class of extremely difficult and widely applicable multi-objective optimization problems with constraints arising in diverse areas and meeting the requirements for real-world applications. Based on the heuristic strategy, the problem is first converted into an unconstrained optimization problem. Then, we use a modified version of the multi-objective ant colony optimization (MOACO) algorithm which is a heuristic global optimization algorithm and has shown promising performances in solving many optimization problems to solve the multi-objective UA-FLP. In the modified MOACO algorithm, the ACO with heuristic layout updating strategy which is proposed to update the layouts and add the diversity of solutions is a discrete ACO algorithm, with a difference from general ACO algorithms for discrete domains which perform an incremental construction of solutions but the ACO in this paper does not. We propose a novel pheromone update method and combine the Pareto optimization based on the local pheromone communication and the global search based on the niche technology to obtain Pareto-optimal solutions of the problem. In addition, the combination of the local search based on the adaptive gradient method and the heuristic department deformation strategy is applied to deal with the non-overlapping constraint between departments so as to obtain feasible solutions. Ten benchmark instances from the literature are tested. The experimental results show that the proposed MOACO algorithm is an effective method for solving the UA-FLP.     

Development and correlation analysis of non-dominated sorting buffalo optimization NSBUF II using Taguchi’s design coupled gray relational analysis and ANN

African Buffalo Optimization (ABO) is a latest bio-inspired optimization technique in the domain of evolutionary optimization, which mimics the migratory behaviour of the buffalo foraging for food across the African plains and forests. The ABO is, by now, recognized as a single-objective optimization algorithm, comprising the ability to solve both, the continuous and discrete optimization problems. However, a multi-objective version of ABO could be more useful for industrial problems. An aim is made in this article to develop the multi-objective variant of ABO, namely NSBUF II, which incorporates Pareto search for non-dominated solutions in the state space and a local search module for faster convergence. Selection of parameters for the NSBUF II is extremely sensitive to the obtained Pareto fronts. Thus, a Grey Relational Analysis (GRA) coupled with Taguchi’s L₁₆ orthogonal array is adopted, which efficiently obtains the best set of parameters for the NSBUF II. Initially the proposed NSBUF II is tested using utilization based bi-objective production cell design problem and compared with published Multi-Objective Particle Swarm Optimization (MOPSO), and Non-dominated Sorting Genetic Algorithm (NSGA II) successfully. To analyse the performance of the NSBUF II, Self-Organizing Map (SOM) is applied, which is a powerful tool for visualizing the high-dimensional data in low dimensional maps. Applied SOM visually reveals the hidden correlational structure among the design parameters and the objective space. The performance of the NSBUF II is validated statistically NSBUF II is further verified with a real-world case obtained based on the Abrasive Water Jet Machining (AWJM) process. Validation test proves the competence of the proposed NSBUF II for real-world problem solving. The contribution of this paper is threefold. First, a novel multi-objective NSBUF II algorithm is developed. Second, a SOM based visual analysis is proposed to visualize the correlation among design parameters and Pareto fronts. Third, the NSBUF II is employed to solve a combinatorial production cell design problem followed by a real-world industrial problem.     

A multi-objective differential evolutionary algorithm for constrained multi-objective optimization problems with low feasible ratio

Most current evolutionary multi-objective optimization (EMO) algorithms perform well on multi-objective optimization problems without constraints, but they encounter difficulties in their ability for constrained multi-objective optimization problems (CMOPs) with low feasible ratio. To tackle this problem, this paper proposes a multi-objective differential evolutionary algorithm named MODE-SaE based on an improved epsilon constraint-handling method. Firstly, MODE-SaE self-adaptively adjusts the epsilon level in line with the maximum and minimum constraint violation values of infeasible individuals. It can prevent epsilon level setting from being unreasonable. Then, the feasible solutions are saved to the external archive and take part in the population evolution by a co-evolution strategy. Finally, MODE-SaE switches the global search and local search by self-switching parameters of search engine to balance the convergence and distribution. With the aim of evaluating the performance of MODE-SaE, a real-world problem with low feasible ratio in decision space and fourteen bench-mark test problems, are used to test MODE-SaE and five other state-of-the-art constrained multi-objective evolution algorithms. The experimental results fully demonstrate the superiority of MODE-SaE on all mentioned test problems, which indicates the effectiveness of the proposed algorithm for CMOPs which have low feasible ratio in search space.     

基于微粒群算法的生料浆调配多目标满意优化

氧化铝生料浆优化调配是一个多目标、多约束且非线性的0-1组合优化问题。首先给出了该问题的数学描述,然后根据调配过程判断生料浆质量是否达标的不同满意标准,基于满意度原理,将带约束的多目标优化问题转换为求多目标和多约束综合满意度最大的满意优化问题,最后提出一种改进的离散微粒群算法对该问题进行求解。实例仿真和工业应用证明了模型与算法的有效性     

Decomposition-based multi-objective evolutionary algorithm for vehicle routing problem with stochastic demands

Vehicle routing problem with stochastic demands (VRPSD) is a famous and challenging optimization problem which is similar to many real world problems. To resemble the real world scenario, total traveling distance, total driver remuneration, the number of vehicles used and the difference between driver remuneration are considered and formulated in the multi-objective optimization perspective. This paper aims to solve multi-objective VRPSD under the constraints of available time window and vehicle capacity using decomposition-based multi-objective evolutionary algorithm (MOEA/D) with diversity-loss-based selection method incorporates with local search and multi-mode mutation heuristics. We have also compared the optimization performance of the decomposition-based approach with the domination-based approach to study the difference between these two well-known evolutionary multi-objective algorithm frameworks. The simulation results have showed that the decomposition-based approach with diversity-loss-based selection method is able to maintain diverse output solutions.     

Developing a context-aware ubiquitous learning system based on a hyper-heuristic approach by taking real-world constraints into account

In a context-aware ubiquitous learning environment, learning systems are aware of students’ locations and learning status in the real world via the use of sensing technologies which provide personalized guidance or support. In such a learning environment that guides students to observe and learn from real-world targets, various physical world constraints need to be taken into account when planning learning paths for individuals. In this study, an optimization problem is formulated by taking the relevance of real-world learning targets and the environmental constraints into account when determining personalized learning paths in the real world to maximize students’ learning efficacy. Moreover, a hyper-heuristic approach is proposed to efficiently find quality learning paths for individual students. To evaluate the performance of the proposed approach, the teachers’ feedback was collected and analyzed based on the learning activities conducted in an elementary school natural science course; in addition, the performances of the proposed algorithm and other approaches were compared based on a set of test data.     

Robust load-balanced backbone-based multicast routing in mobile opportunistic networks

Mobile opportunistic network (MON) is an efficient way of communication when there is no persistent connection between nodes. Multicast in MONs can be used to efficiently deliver messages to multiple destination nodes. However, because multiple destination nodes are involved, multicast routing is more complex than unicast and brings a higher communication cost. Backbone-based routing can effectively reduce the network overhead and the complexity of routing scheme. However, the load of backbone nodes is larger than that of regular nodes. If the backbone node’s buffer is exhausted, it will have a significant impact on the performance of the routing scheme. Load balancing can improve the ability of backbone to deal with the change of network load, and backbone maintenance algorithm can provide backbone robustness. In this paper, we propose a robust load-balanced backbone-based multicast routing scheme in MONs. In the backbone construction algorithm, we transform the problem of backbone construction into a multi-objective optimization problem, and propose a multi-objective evolutionary algorithm-based backbone construction algorithm, namely LBMBC-MOEA algorithm. In addition, in order to increase the robustness of the backbone-based routing scheme, we propose a localized multicast backbone maintenance algorithm (MBMA) to deal with the buffer exhaustion of backbone nodes. When a backbone node’s residual buffer is insufficient, MBMA algorithm selects other nodes to replace the backbone node. The results on extensive simulations show that when considering the node buffer size constraints, compared with previous backbone-based multicast routing schemes, our proposed algorithm has better performance, and when the node’s residual buffer is insufficient, MBMA algorithm can significantly improve the performance of the backbone-based multicast routing scheme.     

面向产品线交互配置不一致性修复的差分IBEA算法

在大规模复杂系统产品线工程中,人工配置难免会导致配置的不一致,即,配置数据会违背预定义的约束(也可以称为一致性约束).对于大规模复杂系统产品线体系结构,比如信息物理系统产品线,往往存在成百上千的可变点以及约束,而且约束与可变点之间存在复杂的依赖关系,为不一致配置的修复带来很大的挑战.为了解决这个问题,针对前期提出的基于多目标搜索以及约束求解技术的自动不一致配置修复推荐框架(Zen-Fix),提出一种改进的IBEA算法(De IBEA).De IBEA通过将差分引入IBEA算法,搜索过程中,基于可行解和不可行解的差分变异产生后代,最终为用户推荐符合预定义约束并且对于配置效率来说最优的配置修复方案.基于一个工业案例海底油田采控系统产品线为例,通过模拟一个产品的配置过程,产生了10 189个优化问题,结果表明:Zen-Fix框架结合De IBEA算法,可以实时地为用户提供较优的不一致配置修复方案.此外,通过对这10 189个问题的推荐方案进行对比,证明了De IBEA算法无论从时间效率还是搜索性能上都优于原始的IBEA算法.     

基于遗传算法的应用层多播路由方案

通过分析应用层多播树的路由约束，定义了3个适值函数，分别考察应用层多播树在开销、平衡和网络层业务量均衡3方面的性能。并根据生成的总适值函数进行遗传算法操作．仿真结果表明，与基于几何规则的应用层路由算法比较，本文提出的算法对多播树的3方面性能都有所优化，树的平衡和网络层业务量均衡性能的优化程度尤为明显．