Suppose that mobile service units are located at a base station (depot) in a transportation network with nodes. On any day, the nodes of the network may generate calls for service independently with known probabilities. The calls are centrally allocated to the service units who then visit the allocated customers on shortest open tours, that is, for each service unit, the way back to the depot from the last served customer is not counted towards the length of the tour. It is required to find an optimal location for the depot to minimize the expected travel distance. We obtain bounds on the approximation ratios for two simple and fast heuristics for the problem on a general network. For the problem on a tree, we present an exact algorithm.

A network is given whose edges need to be constructed (or restored after a disaster). The lengths of edges represent the required construction/restoration times given available resources, and one unit of length of the network can be constructed per unit of time. All points of the network are accessible for construction at any time. For each pair of vertices, a due date is given. It is required to find a construction schedule that minimizes the maximum lateness of all pairs of vertices, where the lateness of a pair is the difference between the time when the pair becomes connected by an already constructed path and the pair’s due date. We introduce the problem and analyze its structural properties, present a mixed-integer linear programming formulation, develop a number of lower bounds that are integrated in a branch-and-bound algorithm, and discuss results of computational experiments both for instances based on randomly generated networks and for instances based on 2010 Chilean earthquake data. The online appendix is available at https://doi.org/10.1287/ijoc.2017.0796 .

Suppose that a destroyed network needs to be restored by a number of servers (construction crews) that are initially located at some nodes of the network (depots). Each server can restore one unit of length of the network per unit of time. When several servers are simultaneously working at the same point, their restoration speeds combine additively. The servers can travel within the already restored part of the network with infinite speed, which means that travel times are negligible with respect to construction times. It is required to minimize the time when each node becomes connected to at least one of the depots. We show that the problem is strongly NP‐hard on general networks, and present fast polynomial algorithms for trees and cactus networks which are connected networks where each node and each edge belong to at most one cycle. © 2017 Wiley Periodicals, Inc. NETWORKS, Vol. 70(1), 60–68 2017

If |$d(x,y)$| denotes the distance between vertices |$x$| and |$y$| in a graph |$G$|⁠, then an |$L(2,1)$|-labeling of a graph |$G$| is a function |$f$| from vertices of |$G$| to nonnegative integers such that |$\boldsymbol {\vert f(x) - f(y)\vert \ge 2}$| if |$\boldsymbol {d(x,y) = 1}$|⁠, and |$\boldsymbol {\vert f(x) - f(y)\vert \ge 1}$| if |$\boldsymbol {d(x,y) = 2}$|⁠. Griggs and Yeh conjectured that for any graph with maximum degree |$\boldsymbol {\Delta \ge 2}$|⁠, there is an |$\boldsymbol {L(2,1)}$|-labeling with all labels not greater than |$\boldsymbol {\Delta ^2}$|⁠. We prove that the conjecture holds for dot-Cartesian products and dot-lexicographic products of two graphs with possible minor exceptions in some special cases. The bounds obtained are in general much better than the |$\boldsymbol {\Delta ^2}$|-bound.

We consider a generalization of the classical quadratic assignment problem, where material flows between facilities are uncertain, and only upper and lower bounds are known for each flow. The objective is to find a minmax regret solution. We present an exact Benders decomposition algorithm based on two developed mathematical programming formulations and on the developed linearizations of master problems, and a heuristic based on using tabu search in the context of a Benders decomposition framework. Then, we develop a hybrid Benders decomposition approach that allows us to combine the speed of heuristics with the rigor and precision of the exact Benders method. We discuss the results of extensive computational experiments.

Abstract We consider the problem of locating facilities of two types at nodesof a tree network. Customers may need just one type of service, or bothtypes; in the latter case, to minimize transportation costs, the customers visit facilities of both types in a single trip. Each facility incurs a fixed cost that depends on the type of the facility and the node where it is located. It is required to minimize the sum of the total transportation and fixed costs. For the problem with a single facility of each type, we present an O( n) exact algorithm, which improves on the algorithm presented in [2]. For the problem with multiple facilities of each type, we present an algorithm. © 2013 Wiley Periodicals, Inc. NETWORKS, Vol. 63(2), 154–159 2014

In this article, we consider the cooperative maximum covering location problem on a network. In this model, it is assumed that each facility emits a certain “signal” whose strength decays over distance according to some “signal strength function.” A demand point is covered if the total signal transmitted from all the facilities exceeds a predefined threshold. The problem is to locate facilities so as to maximize the total demand covered. For the 2‐facility problem, we present efficient polynomial algorithms for the cases of linear and piecewise linear signal strength functions. For the p‐facility problem, we develop a finite dominant set, a mixed‐integer programming formulation that can be used for small instances, and two heuristics that can be used for large instances. The heuristics use the exact algorithm for the 2‐facility case. We report results of computational experiments. © 2014 Wiley Periodicals, Inc. NETWORKS, Vol. 63(4), 334–349 2014

We consider a version of the 1-median problem on a network with uncertain weights of nodes. For each node, only an interval estimate of its weight is known. It is required to find the minmax relative regret location, i.e., to minimize the worst-case ratio of the loss in the objective-function value (opportunity loss) that may occur because a decision is made without knowing which state of nature (scenario) will take place, to the best possible value of the objective function under the realized scenario. We present a polynomial O(mn3 log n) algorithm for this problem on a general network. We also present fast algorithms for networks with special structure (trees and paths).

Abstract We consider the 1‐median problem with uncertain weights for nodes. Specifically, for each node, only an interval estimate of its weight is known. It is required to find a “minmax regret” location, that is, to minimize the worst‐case loss in the objective function that may occur because the decision is made without knowing which state of nature will take place. For this problem on a tree, the best published algorithm has complexity O(n2). We present an algorithm with complexity O(n log2 n). © 2003 Wiley Periodicals, Inc.

Abstract The generic problem studied is to locate p distinguishable facilities on a tree to satisfy upper‐bound constraints on distances between pairs of facilities, given that each facility must be located within its own feasible region, which is defined as a subtree of the tree. We present a parallel location scheme (PLS) for solving the problem that can be implemented as an NC‐algorithm. We also introduce parallel NC‐algorithms based on the PLS for the minimax versions of the problem, including the distance‐constrained p‐center problem with mutual communication. Combining the PLS and the improved Megiddo's parametric technique, we develop strongly polynomial serial algorithms for the minimax problems; the algorithms have the best complexities currently available in the literature. Efficient parallel algorithms are given for obtaining optimal regions of the facilities. © 2002 Wiley Periodicals, Inc.

We consider the 1-median problem on a network with uncertain weights of nodes. Specifically, for each node, only an interval estimate of its weight is known. It is required to find the “minimax regret” location, i.e., to minimize the worst-case loss in the objective function that may occur because a decision is made without knowing which state of nature will take place. We present the first polynomial algorithm for this problem on a general network. For the p roblem on a tree network, we discuss an algorithm with an order of complexity improved over the algorithms known in the literature.

Parallel NC-algorithms for a general class of multifacility location problems on a tree with identical facilities and the minisum objective function are presented. The class includes the p-median problem, the p-coverage problem, and the uncapacitated plant location problem.

We study generalizations of classical multifacility location problems, where customers' demand has a hierarchial structure, i.e., the set of local customers is partitioned into categories (global customers), each having its own requirements for quality of service. For the case of identical facilities, we prove that the categorized coverage, covering, p-center, and p-median problems are strongly NP-hard on trees, in contrast with their classical noncategorized versions (which are polynomially solvable on trees). Some of the problems are shown to be NP-hard even on paths. For the case of distinguishable facilities, we provide polynomial and strongly polynomial algorithms for the categorized covering, multicenter, and multimedian problems with mutual communication on a tree. © 1998 John Wiley & Sons, Inc. Networks 31:81–92, 1998

The objective is to connect a given set of terminal nodes of a network by a subnetwork of maximum bottleneck capacity. The bottleneck capacity of a subnetwork is the minimum of the capacities of its edges. For the problem with the additional requirement that the connecting subnetwork must be k-edge-connected or k-node-connected, k = 2,3, algorithms with complexities O(m + n log n) are given, where m and n are the numbers of edges and nodes of the network respectively. For the problem where the connecting subnetwork is required to be k-edge-connected or k-node-connected, k ≥ 4, the complexities of the proposed algorithms are O(m + fk(n) · log n) and O(m + gk(n) · log n) respectively, where fk(m)(gk(m)) is the complexity of finding nontrivial k-edge-connected components (k-node-connected components) of a network. The results of the paper improve known complexities for k ≥ 2 in the case of k-edge-connectivity requirement and for k ≥ 3 in the case of k-node-connectivity requirement.

Abstract Suppose that customers who require some service are situated at nodes of a network. Service is provided by a server who performs a service tour through all the nodes. The server has two objectives: (1) minimize the total waiting time of the customers and (2) minimize the length of the tour. It is assumed that the latter objective is of primary importance. For routing and location‐routing variants of the problem on trees and cactus networks, polynomial algorithms are presented, most of them with complexity O(n log n) or O(n). Multiserver variants of the problem on a tree are proved to be NP‐complete. Some modifications of the problem are also investigated.