Narrow Results

A center subtree is a subtree with a specified length that minimizes the maximum weighted distance between the vertices in a network and the subtree. This paper addresses the inverse center subtree problem on tree graphs, where vertex weights are adjusted to either augment or reduce them, aiming to transform a predetermined subtree into a center subtree. Initially, we explore the optimality criterion for a subtree that is a center subtree within a tree network. Using this criterion, we frame the corresponding problem as a piecewise linear optimization problem. Lastly, we propose a combinatorial algorithm that effectively solves the problem in $O(nlogn)$ time, where $n$ represents the number of vertices in the tree.

Bus network design is an important problem in public transportation. In practice, some parameters of this problem are uncertain. We propose two models for the bus terminal location problem with fuzzy parameters. In the first formulation, the number of passengers corresponding to each node is a fuzzy number. In the second formulation, an additional assumption of fuzzy neighborhood is considered. These problems being NP-hard, we use a genetic algorithm (GA) and a simulated annealing (SA) algorithm for solving them. We also propose an idea to hybridize these algorithms. In our hybrid algorithm, SA is applied as a neighborhood search procedure of GA on the best individual of the population, which is the best available approximation of the optimal solution, with a varying probability that is gradually increased with the increase in the number of iterations in GA. We then implement GA, SA, our hybrid algorithm, and a recently proposed hybrid algorithm making use of a constant probability for application of SA on all the individuals of the population of GA, and use a nonparametric statistical test to compare their performances on a collection of randomly generated medium to large-scale test problems. Results of computational experiments demonstrating the efficiency and practicability of our proposed algorithm are reported.

The classical reverse 1-median problem on trees is to adjust the edge lengths within a budget so as to reduce the 1-median function at a predetermined vertex as much as possible. This paper concerns the corresponding problem with uncertain vertex weights presented by linear functions. Moreover, we use the minmax regret criterion to measure the maximum loss of a feasible solution with respect to the worst-case scenario. The regarding problem is called the minmax regret reverse 1-median problem on trees. We first partition the set of scenarios into parts such that the optimal solution of the corresponding reverse 1-median problem does not change in each part. Then the problem can be reformulated as the minimization of a quadratic number of affine linear functions. We finally develop a greedy algorithm that solves the problem in $O(n^3)$ time where n is the number of vertices in the underlying tree.

We address in this paper a variant of the scheduling-location (ScheLoc) problem on tree networks with interval edge lengths where the total deviation of the uncertain data cannot exceed a threshold. We further use the minmax regret concept to deal with the corresponding uncertainty. In order to solve the problem, we investigate the structure of the schedule which leads to the maximum regret value at a fixed point. Then we consider the machine location belonging to a specific edge of the tree and partition the underlying edge into regions with linear maximum regret function. Finally, we develop a combinatorial algorithm that solves the minmax regret ScheLoc problem in polynomial time based on a finite dominating set approach.

Location problems describe those situations in which one or more facilities have to be placed in a region trying to optimize a suitable objective function. Game theory has been used as a tool to solve location problems and this paper is devoted to describe the state-of-the-art of the research on location problems through the tools of game theory. Particular attention is given to the problems that are still open in the field of cooperative location game theory.

This paper considers the $2$-maxian location problem on a cactus graph $G=(V,E)$ in which the aim is to find two points on $G$ for establishing obnoxious facilities such that the sum of weighted distances from all vertices (existing clients) to the farthest facility is maximized. We develop a modified algorithm for obtaining an optimal solution of the problem under investigation. The proposed algorithm is based on the generic solution idea by Kang et al., while it is straightforward and takes lower computational operations.

We address in this paper the connected $p$-median problem on complete multi-layered graphs. We first solve the corresponding 1-median problem on the underlying graph in linear time based on the structure of the induced path. For $p\ge 2$, we prove that the connected $p$-median contains at least one vertex in the layered set corresponding to the 1-median or its adjacent vertices in the induced path. Then, we develop an $O(nlogn)$ algorithm that solves the problem on a complete multi-layered graph with $n$ vertices.