Locating switches (2019). Expert Systems With Applications, 136, 338–352.

[:es]Mercedes Landete (University Miguel Hernández of Elche), Alfredo Marín (University of Murcia) and José Luis Sainz-Pardo (University Miguel Hernández of Elche).
Abstract. In this paper, a novel problem in transshipment networks has been proposed. The main aims of this pa- per are to introduce the problem and to give useful tools for solving it both in exact and approximate ways. In a transshipment network it is important to decide which are the best paths between each pair of nodes. Representing the network by a graph, the union of thesepaths is a delivery subgraph of the original graph which has all the nodes and some edges. Nodes in this subgraph which are adjacent to more than two nodes are called switches because when sending the flow between any pair of nodes, switches on the path must adequately direct it. Switches are facilities which direct flows among users. The installation of a switch involves the installation of adequate equipment and thus an allocation cost. Furthermore, traversing a switch also implies a service cost or allocation cost. The Switch Location Prob- lem is defined as the problem of determining which is the delivery subgraph with the total lowest cost. Two of the three solutions approaches that we propose are decomposition algorithms based on articula- tion vertices, the exact and the math-heuristic ones. These two approaches could be embedded in expert systems for locating switches in transshipment networks. The results should help a decision maker to select the adequate approach depending on the shape and size of the network and also on the exter- nal time-limit. Our results show that the exact approach is a valuable tool if the network has less than 1000 nodes. Two upsides of our heuristics are that they do not require special networks and give good solutions, gap-wise. The impact of this paper is twofold: it highlights the difficulty of adequately locating switches and it emphasizes the benefit of decomposing algorithms.
Keywords. Discrete location; Math-heuristic; Articulation vertex; Block-Cutpoint graph[:]