Formulations and Benders decomposition algorithms for multidepot salesmen problems with load balancing

This paper describes new models and exact solution algorithms for the fixed destination multidepot salesmen problem defined on a graph with n nodes where the number of nodes each salesman is to visit is restricted to be in a predefined range. Such problems arise when the time to visit a node takes considerably longer as compared to the time of travel between nodes, in which case the number of nodes visited in a salesman’s tour is the determinant of their ‘load’. The new models are novel multicommodity flow formulations with O(n²) binary variables, which is contrary to the existing formulations for the same (and similar) problems that typically include O(n³) binary variables. The paper also describes Benders decomposition algorithms based on the new formulations for solving the problem exactly. Results of the computational experiments on instances derived from TSPLIB show that some of the proposed algorithms perform remarkably well in cases where formulations solved by a state-of-the-art optimization code fail to yield optimal solutions within reasonable computation time.     

Discrete Mobile Centers

Abstract. We propose a new randomized algorithm for maintaining a set of clusters among moving nodes in the plane. Given a specified cluster radius, our algorithm selects and maintains a variable subset of the nodes as cluster centers. This subset has the property that (1) balls of the given radius centered at the chosen nodes cover all the others and (2) the number of centers selected is a constant-factor approximation of the minimum possible. As the nodes move, an event-based kinetic data structure updates the clustering as necessary. This kinetic data structure is shown to be responsive, efficient, local, and compact. The produced cover is also smooth, in the sense that wholesale cluster re-arrangements are avoided. This clustering algorithm is distributed in nature and can enable numerous applications in ad hoc wireless networks, where mobile devices must be interconnected to perform various tasks collaboratively.     

Multicriteria tour planning for mobile healthcare facilities in a developing country

A multiobjective combinatorial optimization (MOCO) formulation for the following location-routing problem in healthcare management is given: For a mobile healthcare facility, a closed tour with stops selected from a given set of population nodes has to be found. Tours are evaluated according to three criteria: (i) An economic efficiency criterion related to the tour length, (ii) the criterion of average distances to the nearest tour stops corresponding to p-median location problem formulations, and (iii) a coverage criterion measuring the percentage of the population unable to reach a tour stop within a predefined maximum distance. Three algorithms to compute approximations to the set of Pareto-efficient solutions of the described MOCO problem are developed. The first uses the P-ACO technique, and the second and the third use the VEGA and the MOGA variant of multiobjective genetic algorithms, respectively. Computational experiments for the Thiès region in Senegal were carried out to evaluate the three approaches on real-world problem instances.     

A dynamic programming operator for tour location problems applied to the covering tour problem

This paper presents an evaluation operator for single-trip vehicle routing problems where it is not necessary to visit all the nodes. Such problems are known as Tour Location Problems. The operator, called Selector, is a dynamic programming algorithm that converts a given sequence of nodes into a feasible tour. The operator returns a subsequence of this giant tour which is optimal in terms of length. The procedure is implemented in an adaptive large neighborhood search to solve a specific tour location problem: the Covering Tour Problem. This problem consists in finding a lowest-cost Hamiltonian cycle over a subset of nodes such that nodes outside the tour are within a given distance from a visited node. The metaheuristic proposed is competitive as shown by the quality of results evaluated using the output of a state-of-the-art exact algorithm.     

Discrete Mobile Centers

   Abstract. We propose a new randomized algorithm for maintaining a set of clusters among moving nodes in the plane. Given a specified cluster radius, our algorithm selects and maintains a variable subset of the nodes as cluster centers. This subset has the property that (1) balls of the given radius centered at the chosen nodes cover all the others and (2) the number of centers selected is a constant-factor approximation of the minimum possible. As the nodes move, an event-based kinetic data structure updates the clustering as necessary. This kinetic data structure is shown to be responsive, efficient, local, and compact. The produced cover is also smooth, in the sense that wholesale cluster re-arrangements are avoided. This clustering algorithm is distributed in nature and can enable numerous applications in ad hoc wireless networks, where mobile devices must be interconnected to perform various tasks collaboratively.     

A node-based layered graph approach for the Steiner tree problem with revenues,budget and hop-constraints

The Steiner tree problem with revenues, budget and hop-constraints (STPRBH) is a variant of the classical Steiner tree problem. The goal is to find a tree maximizing the collected revenue, which is associated with nodes, subject to a given budget for the edge cost of the tree and a hop-limit for the distance between the given root node and any other node in that tree. In this work, we introduce a novel generic way to model hop-constrained tree problems as integer linear programs and apply it to the STPRBH. Our approach is based on the concept of layered graphs that gained widespread attention in the recent years, due to their computational advantage when compared to previous formulations for modeling hop-constraints. Contrary to previous MIP formulations based on layered graphs (that are arc-based models), our model is node-based. Thus it contains much less variables and allows to tackle large-scale instances and/or instances with large hop-limits, for which the size of arc-based layered graph models may become prohibitive. The aim of our model is to provide a good compromise between quality of root relaxation bounds and the size of the underlying MIP formulation. We implemented a branch-and-cut algorithm for the STPRBH based on our new model. Most of the instances available for the DIMACS challenge, including 78 (out of 86) previously unsolved ones, can be solved to proven optimality within a time limit of 1000 s, most of them being solved within a few seconds only. These instances contain up to 500 nodes and 12,500 edges, with hop-limit up to 25.     

A Cut and Branch Approach for the Capacitated <Emphasis Type="Italic">p</Emphasis>-Median Problem Based on Fenchel Cutting Planes

The capacitated p-median problem (CPMP) consists of finding p nodes (the median nodes) minimizing the total distance to the other nodes of the graph, with the constraint that the total demand of the nodes assigned to each median does not exceed its given capacity. In this paper we propose a cutting plane algorithm, based on Fenchel cuts, which allows us to considerably reduce the integrality gap of hard CPMP instances. The formulation strengthened with Fenchel cuts is solved by a commercial MIP solver. Computational results show that this approach is effective in solving hard instances or considerably reducing their integrality gap.      

Single-commodity robust network design problem: Complexity,instances and heuristic solutions

We study a single-commodity Robust Network Design problem (RND) in which an undirected graph with edge costs is given together with a discrete set of balance matrices, representing different supply/demand scenarios. In each scenario, a subset of the nodes is exchanging flow. The goal is to determine the minimum cost installation of capacities on the edges such that the flow exchange is feasible for every scenario. Previously conducted computational investigations on the problem motivated the study of the complexity of some special cases and we present complexity results on them, including hypercubes. In turn, these results lead to the definition of new instances (random graphs with {−1, 0, 1} balances) that are computationally hard for the natural flow formulation. These instances are then solved by means of a new heuristic algorithm for RND, which consists of three phases. In the first phase the graph representing the network is reduced by heuristically deleting a subset of the arcs, and a feasible solution is built. The second phase consists of a neighborhood search on the reduced graph based on a Mixed-Integer (Linear) Programming (MIP) flow model. Finally, the third phase applies a proximity search approach to further improve the solution, taking into account the original graph. The heuristic is tested on the new instances, and the comparison with the solutions obtained by Cplex on a natural flow formulation shows the effectiveness of the proposed method.     

Formulations and decomposition methods for the incomplete hub location network design problem with and without hop-constraints

The incomplete hub location problem with and without hop-constraints is modeled using a Leontief substitution system approach. The Leontief formalism provides a set of important theoretical properties and delivers formulations with tight linear bounds that can explicitly incorporate hop constraints for each origin-destination pair of demands. Furthermore, the proposed formulations are amenable to a Benders decomposition technique which can solve large scale test instances. The performance of the devised algorithm is primarily due to a new general scheme for separating Benders feasibility cuts. The novel cuts render a stabilizing effect that is directly responsible for the solution of instances up to 80 nodes.     

POPMUSIC for the travelling salesman problem

POPMUSIC— Partial OPtimization Metaheuristic Under Special Intensification Conditions — is a template for tackling large problem instances. This metaheuristic has been shown to be very efficient for various hard combinatorial problems such as p-median, sum of squares clustering, vehicle routing, map labelling and location routing. A key point for treating large Travelling Salesman Problem (TSP) instances is to consider only a subset of edges connecting the cities. The main goal of this article is to present how to build a list of good candidate edges with a complexity lower than quadratic in the context of TSP instances given by a general function. The candidate edges are found with a technique exploiting tour merging and the POPMUSIC metaheuristic. When these candidate edges are provided to a good local search engine, high quality solutions can be found quite efficiently. The method is tested on TSP instances of up to several million cities with different structures (Euclidean uniform, clustered, 2D to 5D, grids, toroidal distances). Numerical results show that solutions of excellent quality can be obtained with an empirical complexity lower than quadratic without exploiting the geometrical properties of the instances.     

Integer programming models for the q-mode problem

The q-mode problem is a combinatorial optimization problem that requires partitioning of objects into clusters. We discuss theoretical properties of an existing mixed integer programming (MIP) model for this problem and offer alternative models and enhancements. Through a comprehensive experiment we investigate computational properties of these MIP models. This experiment reveals that, in practice, the MIP approach is more effective for instances containing strong natural clusters and it is not as effective for instances containing weak natural clusters. The experiment also reveals that one of the MIP models that we propose is more effective than the other models for solving larger instances of the problem.     

New integer linear programming formulation for the traveling salesman problem with time windows: minimizing tour duration with waiting times

The travelling salesman problem, being one of the most attractive and well-studied combinatorial optimization problems, has many variants, one of which is called ‘travelling salesman problem with Time Windows (TSPTW)’. In this problem, each city (nodes, customers) must be visited within a time window defined by the earliest and the latest time. In TSPTW, the traveller has to wait at a city if he/she arrives early; thus waiting times directly affect the duration of a tour. It would be useful to develop a new model solvable by any optimizer directly. In this paper, we propose a new integer linear programming formulation having O(n²) binary variables and O(n²) constraints, where (n) equals the number of nodes of the underlying graph. The objective function is stated to minimize the total travel time plus the total waiting time. A computational comparison is made on a suite of test problems with 20 and 40 nodes. The performances of the proposed and existing formulations are analysed with respect to linear programming relaxations and the CPU times. The new formulation considerably outperforms the existing one with respect to both the performance criteria. Adaptation of our formulation to the multi-traveller case and some additional restrictions for special situations are illustrated.     

A general variable neighborhood search for the one-commodity pickup-and-delivery travelling salesman problem

We present a variable neighborhood search approach for solving the one-commodity pickup-and-delivery travelling salesman problem. It is characterized by a set of customers such that each of the customers either supplies (pickup customers) or demands (delivery customers) a given amount of a single product, and by a vehicle, whose given capacity must not be exceeded, that starts at the depot and must visit each customer only once. The objective is to minimize the total length of the tour. Thus, the considered problem includes checking the existence of a feasible travelling salesman’s tour and designing the optimal travelling salesman’s tour, which are both NP-hard problems. We adapt a collection of neighborhood structures, k-opt, double-bridge and insertion operators mainly used for solving the classical travelling salesman problem. A binary indexed tree data structure is used, which enables efficient feasibility checking and updating of solutions in these neighborhoods. Our extensive computational analysis shows that the proposed variable neighborhood search based heuristics outperforms the best-known algorithms in terms of both the solution quality and computational efforts. Moreover, we improve the best-known solutions of all benchmark instances from the literature (with 200 to 500 customers). We are also able to solve instances with up to 1000 customers.     

A heuristic procedure for the Capacitated m-Ring-Star problem

In this paper we propose a heuristic method to solve the Capacitated m-Ring-Star Problem which has many practical applications in communication networks. The problem consists of finding m rings (simple cycles) visiting a central depot, a subset of customers and a subset of potential (Steiner) nodes, while customers not belonging to any ring must be “allocated” to a visited (customer or Steiner) node. Moreover, the rings must be node-disjoint and the number of customers allocated or visited in a ring cannot be greater than the capacity Q given as an input parameter. The objective is to minimize the total visiting and allocation costs. The problem is a generalization of the Traveling Salesman Problem, hence it is NP-hard. In the proposed heuristic, after the construction phase, a series of different local search procedures are applied iteratively. This method incorporates some random aspects by perturbing the current solution through a “shaking” procedure which is applied whenever the algorithm remains in a local optimum for a given number of iterations. Computational experiments on the benchmark instances of the literature show that the proposed heuristic is able to obtain, within a short computing time, most of the optimal solutions and can improve some of the best known results.     

A random-key genetic algorithm for the generalized traveling salesman problem

The generalized traveling salesman problem is a variation of the well-known traveling salesman problem in which the set of nodes is divided into clusters; the objective is to find a minimum-cost tour passing through one node from each cluster. We present an effective heuristic for this problem. The method combines a genetic algorithm (GA) with a local tour improvement heuristic. Solutions are encoded using random keys, which circumvent the feasibility problems encountered when using traditional GA encodings. On a set of 41 standard test problems with symmetric distances and up to 442 nodes, the heuristic found solutions that were optimal in most cases and were within 1% of optimality in all but the largest problems, with computation times generally within 10 seconds. The heuristic is competitive with other heuristics published to date in both solution quality and computation time.     

Finding a maximum <Emphasis Type="Italic">k</Emphasis>-club using the <Emphasis Type="Italic">k</Emphasis>-clique formulation and canonical hypercube cuts

Detecting low-diameter clusters is an important graph-based data mining technique used in social network analysis, bioinformatics and text-mining. Low pairwise distances within a cluster can facilitate fast communication or good reachability between vertices in the cluster. Formally, a subset of vertices that induce a subgraph of diameter at most k is called a k-club. For low values of the parameter k, this model offers a graph-theoretic relaxation of the clique model that formalizes the notion of a low-diameter cluster. Using a combination of graph decomposition and model decomposition techniques, we demonstrate how the fundamental optimization problem of finding a maximum size k-club can be solved optimally on large-scale benchmark instances that are available in the public domain. Our approach circumvents the use of complicated formulations of the maximum k-club problem in favor of a simple relaxation based on necessary conditions, combined with canonical hypercube cuts introduced by Balas and Jeroslow.     

An ensemble of discrete differential evolution algorithms for solving the generalized traveling salesman problem

In this paper, an ensemble of discrete differential evolution algorithms with parallel populations is presented. In a single populated discrete differential evolution (DDE) algorithm, the destruction and construction (DC) procedure is employed to generate the mutant population whereas the trial population is obtained through a crossover operator. The performance of the DDE algorithm is substantially affected by the parameters of DC procedure as well as the choice of crossover operator. In order to enable the DDE algorithm to make use of different parameter values and crossover operators simultaneously, we propose an ensemble of DDE (eDDE) algorithms where each parameter set and crossover operator is assigned to one of the parallel populations. Each parallel parent population does not only compete with offspring population generated by its own population but also the offspring populations generated by all other parallel populations which use different parameter settings and crossover operators. As an application area, the well-known generalized traveling salesman problem (GTSP) is chosen, where the set of nodes is divided into clusters so that the objective is to find a tour with minimum cost passing through exactly one node from each cluster. The experimental results show that none of the single populated variants was effective in solving all the GTSP instances whereas the eDDE performed substantially better than the single populated variants on a set of problem instances. Furthermore, through the experimental analysis of results, the performance of the eDDE algorithm is also compared against the best performing algorithms from the literature. Ultimately, all of the best known averaged solutions for larger instances are further improved by the eDDE algorithm.     

A cutting-plane algorithm for solving a weighted influence interdiction problem

We consider a two-stage defender-attacker game that takes place on a network, in which the attacker seeks to take control over (or “influence”) as many nodes as possible. The defender acts first in this game by protecting a subset of nodes that cannot be influenced by the attacker. With full knowledge of the defender’s action, the attacker can then influence an initial subset of unprotected nodes. The influence then spreads over a finite number of time stages, where an uninfluenced node becomes influenced at time t if a threshold number of its neighbors are influenced at time t?1. The attacker’s objective is to maximize the weighted number of nodes that are influenced over the time horizon, where the weights depend both on the node and on the time at which that is influenced. This defender-attacker game is especially difficult to optimize, because the attacker’s problem itself is NP-hard, which precludes a standard inner-dualization approach that is common in many interdiction studies. We provide three models for solving the attacker’s problem, and develop a tailored cutting-plane algorithm for solving the defender’s problem. We then demonstrate the computational efficacy of our proposed algorithms on a set of randomly generated instances.