Locating switches

• Published in: Expert systems with applications 2019-12, Vol.136, p.338-352
• Main Authors: Landete, Mercedes, Marín, Alfredo, Sainz-Pardo, José Luis
• Format: Article
• Language: English
• Subjects: Algorithms; Apexes; Articulation vertex; Block-Cutpoint graph; Decision making; Decomposition; Discrete location; Embedded systems; Equipment costs; Expert systems; Graph theory; Graphical representations; Math-heuristic; Nodes; Site selection; Switches; Switching theory
• ISSN: 0957-4174; 1873-6793
• DOI: 10.1016/j.eswa.2019.06.054

•The Switch Location Problem is defined, modelled and solved.•The exact method is a decomposition approach based on articulation vertices.•The math-heuristic algorithm is based on articulation vertices. In this paper, a novel problem in transshipment networks has been proposed. The main aims of this paper 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 Problem 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 articulation 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 external 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.