Flights require a range of ground support services during airport stopovers, of which baggage transportation is an important component. At present, most airports in China still use the manual dispatching method of single vehicle and single flight, which is costly and inefficient. To address the problem, this paper analyzes the baggage trolley scheduling process, determines the scheduling constraints, and establishes the model of airport baggage trolley scheduling. In this paper, based on NSGAII combined with the contribution hypervolume metric, an interactive multi-objective optimization algorithm is proposed, which allows the decision-maker to adjust the weights of the objective function during the process of the algorithm in order to guide the algorithm to find solutions that fit real-world. Experiments on the airport dataset show that the algorithm proposed in this paper can significantly improve efficiency and solution quality.

City express delivery services (a.k.a.~last-mile delivery) have become more prominent in recent years. Many logistics giants, such as Amazon, JD, and Cainiao, have deployed intelligent express delivery systems to deal with the growing demand for parcel delivery. Existing works adopt queuing or batch processing approaches to assign parcels to couriers. However, these approaches do not fully consider the distribution of parcels and couriers, leading to poor quality of task assignment. In this paper, we investigate a problem of delivery matching based on revenue maximization in real-time city express delivery services. Given a set of couriers and a stream of parcel collection tasks, our problem aims to assign each collection task to a suitable courier to maximize the overall revenue of the platform. The problem is shown to be NP-hard. To tackle the problem efficiently, we present a time-aware batch matching algorithm to offer high-quality courier-task matching in each sliding window. We further theoretically analyze the matching approximation bound. In addition, we propose an efficient deep reinforcement learning-based approach to adaptively determine the sliding window size for better matching results. Finally, extensive experiments demonstrate that our proposed algorithms can achieve desirable effectiveness and efficiency under a wide range of parameter settings.

Understanding the behaviour of heuristic search methods is a challenge. This even holds for simple local search methods such as 2-OPT for the Travelling Salesperson Problem (TSP). In this article, we present a general framework that is able to construct a diverse set of instances which are hard or easy for a given search heuristic. Such a diverse set is obtained by using an evolutionary algorithm for constructing hard or easy instances which are diverse with respect to different features of the underlying problem. Examining the constructed instance sets, we show that many combinations of two or three features give a good classification of the TSP instances in terms of whether they are hard to be solved by 2-OPT.

Evolutionary diversity optimization aims to compute a set of solutions that are diverse in the search space or instance feature space, and where all solutions meet a given quality criterion. With this paper, we bridge the areas of evolutionary diversity optimization and evolutionary multi-objective optimization. We show how popular indicators frequently used in the area of multi-objective optimization can be used for evolutionary diversity optimization. Our experimental investigations for evolving diverse sets of TSP instances and images according to various features show that two of the most prominent multi-objective indicators, namely the hypervolume indicator and the inverted generational distance, provide excellent results in terms of visualization and various diversity indicators.

Greedy algorithms provide a fast and often also effective solution to many combinatorial optimization problems. However, it is well known that they sometimes lead to low quality solutions on certain instances. In this paper, we explore the use of randomness in greedy algorithms for the minimum vertex cover and dominating set problem and compare the resulting performance against their deterministic counterpart. Our algorithms are based on a parameter y which allows to explore the spectrum between uniform and deterministic greedy selection in the steps of the algorithm and our theoretical and experimental investigations point out the benefits of incorporating randomness into greedy algorithms for the two considered combinatorial optimization problems.

Diversity plays a crucial role in evolutionary computation. While diversity has been mainly used to prevent the population of an evolutionary algorithm from premature convergence, the use of evolutionary algorithms to obtain a diverse set of solutions has gained increasing attention in recent years. Diversity optimization in terms of features on the underlying problem allows to obtain a better understanding of possible solutions to the problem at hand and can be used for algorithm selection when dealing with combinatorial optimization problems such as the Traveling Salesperson Problem.

Parent selection in evolutionary algorithms for multi-objective optimization is usually performed by dominance mechanisms or indicator functions that prefer non-dominated points, while the reproduction phase involves the application of diversity mechanisms or other methods to achieve a good spread of the population along the Pareto front. We propose to refine the parent selection on evolutionary multi-objective optimization with diversity-based metrics. The aim is to focus on individuals with a high diversity contribution located in poorly explored areas of the search space, so the chances of creating new non-dominated individuals are better than in highly populated areas. We show by means of rigorous runtime analysis that the use of diversity-based parent selection mechanisms in the Simple Evolutionary Multi-objective Optimiser (SEMO) and Global SEMO for the well known bi-objective functions OneMinMax and Lotz can significantly improve their performance. Our theoretical results are accompanied by additional experiments that show a correspondence between theory and empirical results.

Diversity mechanisms are key to the working behaviour of evolutionary multi-objective algorithms. With this paper, we contribute to the theoretical understanding of such mechanisms by means of rigorous runtime analysis. We consider the OneMinMax problem for which it has been shown in [11] that a standard benchmark algorithm called SIBEA is not able to obtain a population with optimal hypervolume distribution in expected polynomial time if the population size is relatively small. We investigate the same setting as in [11] and show that SIBEA is able to achieve a good approximation of the optimal hypervolume distribution very efficiently. Furthermore, we study OneMinMax in the context of search-based diversity optimization and examine the time until SIBEA with a search-based diversity mechanism has obtained a population of maximal diversity covering the whole Pareto front.

Evolutionary algorithms have been frequently used to deal with dynamic optimization problems, but their success is hard to understand from a theoretical perspective. With this paper, we contribute to the theoretical understanding of evolutionary algorithms for dynamic combinatorial optimization problems. We examine a dynamic version of the classical vertex cover problem and analyse evolutionary algorithms with respect to their ability to maintain a 2-approximation. Analysing the different evolutionary algorithms studied by Jansen et al. (2013), we point out where two previously studied approaches are not able to maintain a 2-approximation even if they start with a solution of that quality. Furthermore, we point out that the third approach is very effective in maintaining 2-approximations for the dynamic vertex cover problem.

Recently Ulrich and Thiele [14] have introduced evolutionary algorithms for the mixed multi-objective problem of maximizing fitness as well as diversity in the decision space. Such an approach allows to generate a diverse set of solutions which are all of good quality. With this paper, we contribute to the theoretical understanding of evolutionary algorithms for maximizing the diversity in a population that contains several solutions of high quality. We study how evolutionary algorithms maximize the diversity of a population where each individual has to have fitness beyond a given threshold value. We present a first runtime analysis in this area and study the classical problems called \emph{\OM} and \emph{\LO}. Our results give first rigorous insights on how evolutionary algorithms can be used to produce a maximal diverse set of solutions in which all solutions have quality above a certain threshold value.