Solving the edge‐disjoint paths problem using a two‐stage method

• Author: Cesar Beltran‐Royo,Bernardo Martín,Abraham Duarte,Ángel Sánchez
• Date: 01 January 2020
• DOI: http://doi.org/10.1111/itor.12544
• Published date: 01 January 2020

Intl. Trans. in Op. Res. 27 (2020) 435–457

DOI: 10.1111/itor.12544

INTERNATIONAL

TRANSACTIONS

IN OPERATIONAL

RESEARCH

Solving the edge-disjoint paths problem using

a two-stage method

Bernardo Mart´

ın, ´

Angel S´

anchez, Cesar Beltran-Royo and Abraham Duarte

Department of Computer Sciences, Universidad ReyJuan Carlos, C/Tulip´

an s/n, M´

ostoles, Madrid, Spain

E-mail: b.martinn@alumnos.urjc.es [Mart´

ın]; angel.sanchez@urjc.es [S´

anchez]; cesar.beltran@urjc.es [Beltran-Royo];

abraham.duarte@urjc.es [Duarte]

Received 11 November2016; received in revised form 16 March 2018; accepted 24 March 2018

Abstract

There exists a wide variety of network problems where several connection requests occur simultaneously. In

general, each request is attended by finding a routein the network, where the origin and destination of such a

route are those hosts that wish to establish a connection for information exchange. As is well documented in

the related literature, the exchange of information through disjoint routes increases the effective bandwidth,

velocity, and the probability of receiving the corresponding information. The definition of disjoint paths may

refer to nodes,edges, or both. One of the most studied variants is the one where disjointness implies not to share

edges. This optimization problem is usually known as the maximum edge-disjoint paths problem. This NP-

hard optimization problem has applications in real-time communications, very large scale integration design,

scheduling, bin packing, or load balancing. The proposed approachhybridizes an integer linear programming

formulation of the problem with an evolutionary algorithm. Empirical results using 174 previously reported

instances show that the proposed procedure compares favorably to previous metaheuristics for this problem.

We confirm the significance of the results by conducting nonparametric statistical tests.

Keywords:matheuristics; edge-disjoint paths; integer linear programming; evolutionary algorithms

1. Introduction

In communication networks, a node may either be a data communication equipment (modem,

hub, bridge, or switch) or a data terminal equipment (telephones, printers, or host computers). A

network is usuallymodeled asan undirected graph G=(V,E), where the set of nodes Vcorresponds

to terminal/communication equipment and the set of edges Ecorresponds to the physical links. For

the sake of clarity, the number of nodes and edges are denoted as |V|=Vand|E|=E, respectively.

Each edge e∈E, with e=(i,j)and i,j∈V, has a weight w(e)∈R+, which usually represents the

physical distance between both endpoints.

C

2018 The Authors.

International Transactionsin Operational Research C

2018 International Federation ofOperational Research Societies

Published by John Wiley & Sons Ltd, 9600 Garsington Road, Oxford OX4 2DQ, UK and 350 Main St, Malden, MA02148,

USA.

436 B. Mart´

ın et al. / Intl. Trans. in Op. Res. 27 (2020) 435–457

Fig. 1. Example of EDP problem.

Let T={[ik,jk]|ik= jk∈V,1≤k≤K}be a set of pairs of nodes, called terminal nodes or

terminals, that request to be connected with a disjoint route, that is, an edge-disjoint path (EDP) Pk

in G. The maximum EDP problem consists in maximizing the number of such EDP (Kolliopoulos,

2007). Figure 1a shows an example of an EDP problem with 16 nodes and 16 edges. Terminal and

transshipment nodes correspond to the white and black ones, respectively. In this example, there

are four pairs of terminals [i1,j1],[i2,j2], [i3,j3], [i4,j4], which request to be connected with disjoint

paths.

In Fig. 1b, we depict a feasible solution (i.e., each edge is used exclusively by one path), where

involved paths have been highlighted with dotted lines. As it is easy to check, this is a feasible

solution composed of two paths {i1,1,2,3,4,j1}and {i4,8,7,6,5,j4}. Therefore, for this feasible

solution, the value of the objective function is equal to 2.

This problem presents a wide range of applications in real-time communications, where several

connection requests occur simultaneously(Kolliopoulos, 2007). Specifically, each request is attended

by finding a route in the network, where the origin and destination of such a route are those hosts

that wish to establish a connection for information exchange. That interchange is performed by

means of disjoint routes, since it increases the effective bandwidth, velocity, and the probability

of receiving the corresponding information. Simultaneously, congestion and possible failures are

reduced (for further details,see Barabasi and Albert, 1999; Baveja and Srinivasan, 2000). Regarding

the practical application areas of the EDP problem, we can mention the two following areas: very

large scale integration (VLSI) design (Chan et al., 2003) and virtual circuit routing (Hsu et al.,

2014; Altarelli et al., 2015). In VLSI design, the EDP problem is similar to the escape problem

(Chan et al., 2003), where it is required to find a maximal number of wiring disjoint paths in

grids (i.e., those that avoid the overlaps) between pairs of terminals. In virtual circuit routing, a

path for each communication request is needed to be reserved in advance, in the sense that once a

communication is establishedno interruptions will occur. Virtual circuit routing presents a practical

application (Altarelli et al., 2015) for database servers and large-scale video servers.

C

2018 The Authors.

International Transactionsin Operational Research C

2018 International Federation ofOperational Research Societies