This article is concerned with a recently introduced variant of the generalized traveling salesman problem (GTSP) called the family traveling salesman problem (FTSP). Given a set of nodes partitioned into multiple clusters termed as families, the FTSP consists in finding a tour visiting a pre-specified number of nodes from each of these families in such a manner that the total distance traveled is minimized. FTSP finds application in order picking in modern warehouses, where similar items can be stored at different places as the latest technologies like radio frequency identification (RFID) facilitate item localization. To solve this problem in a manner that is both effective and efficient, a hyper-heuristic approach is presented. This approach makes use of three large neighborhood search methods as low level heuristics. The solution obtained through the hyper-heuristic approach is improved further by using a local search phase. To assess the performance of the proposed approach, computational experiments are performed on the 86 standard benchmark instances of the problem. The proposed approach obtained good-quality solutions in comparison to the state-of-the-art approaches on these instances. Moreover, our approach is several times faster on most of the large instances. We have also reported the performance of our approach on a set of 60 new benchmark instances.

In this paper, a novel hybrid discrete differential evolution based approach is proposed to address a single machine scheduling problem where each job has a release date and the tardiness cost of the job increases stepwise with respect to various due dates. In the literature, this problem is termed as the single machine total stepwise tardiness problem with release dates (SMTSTP-R). The objective of the problem is to find a schedule of jobs which minimizes the total tardiness cost. The stepwise increase in tardiness cost is more prevalent in several real life scenario, especially in transportation. We have used two constructive heuristics and concept of opposition based solutions to generate initial population. Our proposed approach uses a series of local searches to further enhance the quality of solutions obtained by the proposed discrete differential evolution approach. In order to justify the superiority of proposed approach, various comparisons are done with the existing approaches available in the literature. The results of these comparisons validate the superiority of our approach in comparison to the existing state-of-the-art approaches.

The maximum scatter traveling salesman problem (MSTSP) is a variant of the well-known traveling salesman problem (TSP) where the objective is to find a Hamiltonian cycle on a graph that maximizes the minimum length among its constituent edges. The MSTSP finds important application in manufacturing and medical imaging. In this study, we propose a multi-start iterated local search algorithm for the MSTSP. Two local search algorithms based on insertion and modified 2-opt moves have been developed as part of our approach. To investigate the performance of the proposed approach, benchmark instances from the standard TSPLIB are used. Computational results and their analysis show the effectiveness of the proposed approach.

The minimum weight dominating set (MWDS) problem is a classic NP-Hard optimisation problem with a wide range of practical applications. As a result, many algorithms have been proposed for this problem. Several greedy and approximation algorithms exist which provide good results for unit disk graphs with smooth weights. However, these algorithms do not perform well when applied to general graphs. There are a few metaheuristics in the literature such as genetic algorithms and ant colony optimisation algorithm, which also work for general graphs. In this paper, a swarm intelligence algorithm called artificial bee colony (ABC) algorithm is presented for the MWDS problem. The proposed ABC algorithm is compared with other metaheuristics in the literature and shown to perform better than any of these metaheuristics, both in terms of solution quality and time taken.

Abstract This article addresses three problems that arise in coverage scheduling for wireless sensor networks subject to bandwidth constraints. The first problem focuses on minimizing the total breach under a lifetime constraint, where a breach occurs when some targets are not covered by active sensors. The second problem aims at maximizing the network lifetime under a breach constraint. Finally, the problem of computing the possible trade‐offs between breach and lifetime offered by the sensor network is also addressed. An exact approach based on a column generation algorithm is proposed for solving these problems, and a heuristic is also derived from it and briefly presented. The use of a genetic algorithm within the column generation scheme appears to significantly decrease computation time. © 2011 Wiley Periodicals, Inc. NETWORKS, 2012