p-facility Huff location problem on networks

p -facility Huff location problem on networks ∗ Rafael Blanquero 1 , Emilio Carrizosa 1 , Boglárka G.-Tóth 2 , and Amaya Nogales-Gómez 1 1 Departamento de Estadística e Investigación Operativa Facultad de Matemáticas Universidad de Sevilla Spain {rblanquero,ecarrizosa,amayanogales}@us.es 2 Department of Dierential Equations Faculty of Mathematics Budapest University of Technology and Economics Hungary [email protected] Abstract. The p -facility Hu location problem aims at locating facilities on a competitive environment so as to maximize the market share. While it has been deeply studied in the eld of continuous location, in this paper we study the p -facility Hu location problem on networks formulated as a Mixed Integer Nonlinear Programming problem that can be solved by a branch and bound algorithm. We propose two approaches for the initialization and division of subproblems, the rst one based on the straightforward idea of enumerating every possible combination of p edges of the network as possible locations, and the second one dening sophisticated data structures that exploit the structure of the combinatorial and continuous part of the problem. Bounding rules are designed using DC (dierence of convex) and Interval Analysis tools. In our computational study we compare the two approaches on a battery of 21 networks and show that both of them can handle problems for p≤4 in reasonable computing time. Keywords: Hu location problem, location on networks, p -facility, branch and bound, DC, global optimization. ∗ This work has been partially supported by projects MTM2012-36163 of Ministerio de Economía y Competitividad, Spain, P11-FQM-7603 and FQM-329 of Junta de Andalucía, Spain. 1 1 Introduction Competitive location models [12, 23] were originally introduced by Hotelling in [15], considering the location of two competing facilities on a linear market. In the seminal work of Hotelling, users patronize the facility closest to them. In contrast with this all · or · nothing assumption, it was introduced the Hu location model [16], in which the probability that a user patronizes a facility is proportional to its attractiveness and inversely proportional to a power of the distance to it. The Hu location problem has been extensively studied in the eld of continuous location [6, 11, 13, 16, 17] and successfully applied in the marketing eld, in problems such as location of petrol stations, shopping centers or restaurants [14, 20, 22]. Network optimization models [5] are widely used in practice due to their methodological aspects and intuitive formulations. They arise naturally in the context of assignment, ow, transportation or location problems among others [1, 19]. For a comprehensive introduction to location models on networks see [18]. The combination of the Hu location problem and network optimization has been already addressed in the literature [4, 8] and applied to market area analysis [20] and demand estimation [21]. The single-facility case has been solved in [4] by means of Interval Analysis (IA) bounds, and in [8] using IA and dierence of convex (DC) bounds. Dierent metaheuristics have been proposed for the p -facility case in [25]. In this paper we solve the p -facility Hu location problem on networks formulated as a Mixed Integer Nonlinear Programming (MINLP) problem. The remainder of this paper is organized as follows. In Section 2 we set up the notation for networks and introduce the p -facility Hu location problem. In Section 3, a branch and bound method with dierent initialization and branching rules is described. Section 4 is devoted to procedures for calculating lower and upper bounds. Computational results are reported in Section 5, where the p -facility Hu location problem is solved using the dierent branching and bounding rules for 12 real-life and 9 articial networks. Finally, Section 6 contains a brief summary, nal conclusions and some lines for future research. 2 The model Let N= (V, E) be a network, with node set V and edge set E . The length of the edge e∈E is denoted by le . The distance between two nodes ai, aj∈V is calculated as the length of the shortest path [18] from ai to aj . For each e∈E , with end-nodes ai, aj , we identify each x∈[0, le] with the point in the edge e at distance x from ai and le−x from aj . This way, we obtain that, for any vertex ak∈V and x∈e , the distance d(x, ak) from x to ak , as a function of x , is a concave piecewise linear function, given by d(x, ak) = min{x+d(ai, ak),(le−x) + d(aj, ak)} . In the p -facility Hu location model, the nite set V of vertices of the network represents users, asking for a certain service. Each user a∈V has demand ωa≥0 , that is patronized by dierent existing facilities, located at points y1, . . . , yr on the network. The demand captured by facility at yi from user a is assumed to be inversely proportional to 2 a positive nondecreasing function of the distance d(a, yi) , namely, 1/d(a, yi)2 is used as the utility or attraction function of yi . Therefore, the demand captured by the facility at yi from the user at a is given by ωa 1/(d(a, yi))2 Pr j=1 1/(d(a, yj))2. (1) A new rm is entering the market, by locating p new facilities at some points x1, . . . , xp on the network. This perturbs how the market is shared, since the new facilities will capture part of the demand from a∈V , ωaPp j=1 1/(d(a, xj))2 Pp j=1 1/(d(a, xj))2+Pr j=1 1/(d(a, yj))2. (2) Our goal is the maximization of the market share of the entering rm. Thus, the problem we need to solve can be formulated as max x1∈[0,le1],...,xp∈[0,lep] e1,...,ep∈E X a∈V ωaPp j=1 1/(d(a, xj))2 Pp j=1 1/(d(a, xj))2+Pr j=1 1/(d(a, yj))2. (3) Let us denote the total attraction of the existing facilities for each a∈V by the positive constant βa= r X j=1 1 (d(a, yj))2. (4) Problem (3) can be rewritten as the following MINLP: max x1∈[0,le1],...,xp∈[0,lep] e1,...,ep∈E F(x1, . . . , xp) (5) where F is dened as F(x1, . . . , xp) = X a∈V ωa 1 1 + βa Pp j=1 1 (d(a,xj))2 . (6) The MINLP problem (5) is formed by a combinatorial and continuous part. First, we need to solve the combinatorial problem of choosing a set of p edges to locate the facilities, and then solve a continuous location problem on the edges. 3 The methodology The natural way to solve the MINLP formulation of the p -facility Hu location problem is to use a branch and bound method. In our methods we dierenciate two main phases: the initialization phase and the branch and bound phase. In the initialization phase the initial 3 exploration tree is prepared. In the branch and bound phase, an element of the list is selected iteratively (until the termination rule is fullled) according to a selection criterion, and then is divided into new elements that are included into the list if they cannot be eliminated by their bounds. In this phase, division, bounding, selection, elimination and termination rules are required. In this paper we propose dierent approaches for the initialization phase, division and bounding rules. As selection, elimination and termination rules, we always apply the usual ones from the literature [4]: the element to be evaluated is selected as the one with the largest upper bound, elements whose upper bound are lower than the current lower bound are eliminated, and the optimization is terminated when the relative error between the largest upper bound and the current lower bound is less than a xed tolerance. This section is aimed at describing two types of initialization and division rules. Bounding rules will be discussed in Section 4. 3.1 Total enumeration The straightforward way of solving Problem (6) is to separate the combinatorial and the continuous part of the problem: we rst x a set of p edges to locate the facilities, and then solve a continuous location problem on the edges. This means the branch and bound approach starts with a partition of the search space formed by the cartesion product of p -uples. The p -uples are formed by every possible combination of p -edges, taking into account that several facilities can be located at the same edge, i.e., repetitions of the same edge are allowed in the elements of the partition. But obviously, permutations of the p -uples are not taken into account. We denote by s= (s1, . . . , sk) an element of the partition, where each component si is a (sub)edge that has a multiplicity m(si) , i.e., the number of facilities located at si is m(si) . Hence, m(s1) + . . . +m(sk) = p . To avoid symmetric sets, for any element of the partition s= (s1, . . . , sk) , and any si= [l, u]⊆[0, le], e ∈E, si∈s , the cartesian product Πm(si) j=1 si is replaced by {l≤x1≤. . . ≤xm(si)≤u} . The subdivision of each element of the partition is done by splitting each (sub)edge by its midpoint, obtaining two new smaller segments for each (sub)edge, namely lower and upper segments. Then, the new elements of the partition are built by replacing each (sub)edge si by either its lower or upper segment, sL i, sU i respectively. In the case of (sub)edges with multiplicity greater than 1, the above-described method is used to avoid symmetric sets. For instance, Figure 1 depicts the subdivision process, for p= 2 , of the element s= (s1) , with m(s1) = 2 , identied with the blue coloured area of the big square. Then, the subdivision of s leads to three new elements, identied with the blue coloured area of the small squares. 3.2 Superset A more sophisticated data structure for location problems on networks has been proposed in [9], exploiting together the structure of the combinatorial and continuous part of a 4 s 1 sL 1 sU 1 s 1 sL 1 sU 1 Figure 1: Subdivision process of s= (s1) with m(s1) = 2 . covering problem on networks. In order to avoid the enumeration of every possible combination of p edges, [9] proposes to construct clusters of (sub)edges, called hereafter edgesets , and dene a subproblem of (5) over a collection of edgesets called a superset . To be precise, an edgeset is a nite collection of (sub)edges of E ; a superset S is any uple of the form (E1, p1;. . . ;Ek, pk) , where E1, . . . , Ek are disjoint edgesets, pj are strictly positive integer numbers with k X j=1 pj=p, indicating, for each j= 1, . . . , k , that exactly pj facilities are to be located within the (sub)edges in Ej . For this data structure, the subproblem to be solved at this stage on superset S has the form max (x1,...,xp)∈SF(x1, . . . , xp) with F dened as in (6), and (x1, . . . , xp)∈S understood as x1, . . . , xp1∈E1;xp1+1,..., xp1+p2∈E2;. . . ;xp−pk+1, . . . , xp∈Ek . Supersets will be identied with nodes in the branch and bound tree. The root node of the branch and bound tree is the original superset S0= (E, p) . E is rst subdivided into a given partition E(1), . . . , E(p) of E : we add to the branch and bound exploration tree the 2p−1 p supersets of the form (E1, p1;. . . ;Ek, pk) , where {E1, . . . , Ek}⊂{E(1), . . . , E(p)} and p1+. . . +pk=p . First, we need to dene how the edges of the network conforming S0 , are split into the partition of p edgesets E(1), . . . , E(p) . In the rst step, E is divided into 2 edgesets by 5 a distance criterion, namely the diameter of the edgeset, dened as the maximum of the minimal distance between each pair of nodes. Then, the nodes giving the diameter are selected as centres of the two new (sub)edgesets. Each edge of the edgeset is assigned to the closest (sub)edgeset, where the distance from an edge to an (sub)edgeset is measured as the distance from the edge to the (sub)edgeset centre. Then, we will repeat the process until obtaining p edgesets, selecting the largest edgeset to be subdivided at each step, where the size of the edgeset is understood as the sum of the (sub)edgelengths. The subdivision of a superset S= (E1, p1;. . . ;Ek, pk) during the branch and bound is done by partitioning the largest edgeset Ei . If Ei contains only one (sub)edge, the subdivision is done by bisecting the (sub)edge at its midpoint, otherwise Ei is partitioned to edgesets Ei1, Ei2 by its diameter as done in the initial subdivision of S0 . Thus, the following supersets substitute S : Sj= (E1, p1;. . . ;Ei−1, pi−1;Eij, pi;Ei+1, pi+1;. . . ;Ek, pk), j = 1,2 and additionally if 1< pi , for j= 1, . . . , pi−1 S2+j= (E1, p1;. . . ;Ei−1, pi−1;Ei1, j;Ei2, pi−j;Ei+1, pi+1;. . . ;Ek, pk). This means, that in each step pi+ 1 new supersets are created. 4 Lower and Upper bounds A branch and bound algorithm requires the calculation of tight upper and lower bounds. In this section we present dierent bounding approaches for the branch and bound used to solve (5). We propose two upper bounds and two lower bounds: IA bound, DC bound as upper bounds, Hu discrete bound (HuDisc) and midpoint bound (MidPoint) as lower bounds. Note that when a superset contains edgesets with |Ej|= 1 ∀j , it corresponds to a p -uple of (sub)edges. Each p -uple of (sub)edges has its unique superset correspondance. Thus, the following bounds are valid for p -uples of edges as well, i.e., for the enumeration approach in Section 3.1. 4.1 Upper bounds The IA bound considers only endpoints of (sub)edges as possible location of facilities. For a superset S= (E1, p1;. . . ;Ek, pk) we obtain the IA bound by replacing in (6) d(a, xj) by the distance from a to the closest vertex of the edges that belong to Ej , i.e., by d(a, Ej) = min e=[v1,v2],e∈Ej {d(a, v1), d(a, v2)}. For any x∈Ej it holds that d(a, Ej)≤d(a, x)∀j= 1, . . . , p . Hence, the following is a valid upper bound for (6): 6 UBIA(S) := X a∈V ωa 1 1 + βa Pp j=1 pj (d(a,Ej))2 . The second upper bound approach is based on a DC bound of the single facility Hu location problem on networks, max x∈[0,le], e∈EFsingle(x) with Fsingle(x) = Pa∈Vωa1 1+βa(d(a,x))2 , a particular case of (6) for p= 1 . This problem has been already studied in [8]. First, for a given edge e of the network, Fsingle(x) is expressed as a dierence of convex functions, Fsingle(x) = Pa∈V(F+ a(x)−F− a(x)) , namely, its DC decomposition. Then, an upper bound UBDC single(s) for any segment s∈e, e ∈E with v1, v2 being endpoints of s is dened as UBDC single(s) = max{U(v1), U(v2)} with U(x) = X a∈V (F+ a(x)−F− a(x0)−ξa(x−x0)) for ξa∈∂F− a(x0) where ∂F− a(x0) denotes the set of subgradients of F− a at x0 [26]. Therefore, it holds that UBDC single(e)≥Fsingle(x),∀x∈[0, le], e ∈E. (7) A DC bound over an edgeset Ej is dened as the maximum DC bound of the edges from Ej , i.e., UBDC (Ej) := max e∈Ej UBDC single(e)≥Fsingle(x),∀x∈[0, le], e ∈E. Given a superset S= (E1, p1;. . . ;Ek, pk) , a DC bound of (6) is calculated as UBDC (S) := p X j=1 pj·UBDC (Ej) (8) This DC bound is a valid upper bound since it holds that p X j=1 Fsingle(xj) = p X j=1 X a∈V ωa 1 1 + βa(d(a, xj))2 (9) Since 1 (d(a,xj))2≤Pp j=1 1 (d(a,xj))2 , we have: (9) = p X j=1 X a∈V ωa 1/(d(a, xj))2 1/(d(a, xj))2+βa ≥ p X j=1 X a∈V ωa 1/(d(a, xj))2 Pp i=1 1/(d(a, xi))2+βa = 7 =X a∈V ωaPp j=1 1/(d(a, xj))2 Pp i=1 1/(d(a, xi))2+βa =X a∈V ωa 1 1 + βa Pp j=1 1 (d(a,xj))2 =F(x1, . . . , xp). 4.2 Lower bounds Both of our lower bounding approaches are based on the calculation of the objective function at a feasible solution (˜x1,...,˜xp)∈S . Then, a valid lower bound is given by LB(S) := F(˜x1,...,˜xp)≤max (x1,...,xp)∈SF(x1, . . . , xp). Let us now focus on possible feasible solutions. The rst lower bound, namely Hu discrete bound ( LBHuffDisc ), is a greedy procedure based on solving iteratively p times the single facility Hu location problem at the vertices of the edges of the superset. For a given superset S= (E1, p1;. . . ;Ek, pk) , let ˜x1 be the optimal solution of a single facility Hu location problem on the vertices of the (sub)edges of E1 . In the next step, we will consider that a facility is already located at ˜x1 , and will locate ˜x2 solving the single facility Hu location problem at the vertices of the edges of the corresponding edgeset. In the last step, we will choose location ˜xp as the optimal solution of the single facility Hu location problem on the vertices of the edges of Ek , considering that p−1 facilities are already located at ˜x1,...,˜xp−1 . Since only vertices are considered as candidates, each step of the greedy procedure is executed by complete enumeration of the candidate points. The second lower bound, namely the midpoint bound LBMidP oint , is calculated by randomly choosing an edge from an edgeset Ej , and locating pj facilities at its midpoint ∀j≤k . 5 Computational results The approaches described in Sections 3 and 4 were implemented in Fortran and executed on an Intel Core i7 computer with 16.00 Gb of RAM memory. The solutions were found within an accuracy of 10−3 . We tested the approaches on a battery of 21 networks, whose characteristics are shown in Table 1. The rst 9 networks are articial networks generated as described in [2]. The following 5 networks are proposed for p -median problems in [3] and also used in [4]. Finally, the last 7 networks are taken from [10, 24]. The number r of existing facilities, is set as r= 10% of the number of edges of the network, |E| . Each instance is obtained by randomly and independently generating the demands (each vertex of the network is assumed to have a demand uniformly distributed in the interval (0,1) and in (0,20) for the articial networks from [2]) and the location of the existing facilities. To generate the locations of the existing facilities, r edges are randomly chosen with replacement; on each selected edge, the facility location is generated following uniform distribution. 8 Tables 2-9 show a comparison between the two branching rules: total enumeration, Section 3.1, and superset, Section 3.2; and the dierent bounding approaches: IA bound, IA bound with DC bound (IA+DC), midpoint evaluation (MidPoint) and Hu discrete bound (HuDisc). Results for DC bound as the only upper bound are not reported because they were systematically outperformed by the results in Tables 2-9. The results for the combinations of upper and lower bounds are shown in four blocks of columns. The rst column shows the maximum size of the branch and bound tree (MaxList) during execution. The sign  ×  in the MaxList column means that the size limit ( 108 ) was exceeded so the method was stopped. The second column reports the CPU time in seconds. Time limit is set to 6 hours (21600 seconds) and when it is exceeded, it is denoted with  × . In such case, the third column shows the gap in % achieved by the approach, measured as UB−LB LB 100% . We start with the analysis of p= 2 , in Tables 2 and 3. All strategies are able to solve the problem on the 21 networks in less than an average time of 2 seconds. For both approaches, the best upper and lower bound choice is IA+DC and MidPoint respectively, with superset being the fastest approach and enumeration achieving the best MaxList size. For p= 3 , using supersets we achieve the best computing time, while using enumeration we achieve the best Maxlist result. For the superset approach, the choice of lower bound aects the behaviour of computing times, with an average improvement of about 200 seconds of MidPoint bound compared to HuDisc bound. In the case of the enumeration approach, the choice of upper bound aects the MaxList size. Using IA+DC bound halves the MaxList size compared to using only IA bound. For both approaches, the best upper and lower bound choice is IA+DC and MidPoint respectively. Tables 6 and 7 report results for p= 4 . Using enumeration with HuDisc bound solves 15 networks regardless of the upper bound used, while with MidPoint it solves 17 with IA bound and 18 if using IA+DC bound. Supersets with HuDisc bound solves 15 networks regardless of the upper bound used, while with MidPoint we achieve successful results for 20 out of 21 networks. The RAT195G network is not solved by any of the approaches. Using enumeration, its gap reduces from 32.24% to 17.67% if IA+DC bound is used. Using supersets with IA+DC bound its gap reduces from 15.94% to 8.24% when HuDisc bound is used and from 12.57% to 9.93% for MidPoint bound. In terms of time, the best choice is to use MidPoint as lower bound, while the choice of upper bound does not make big dierence for the superset approach, but for the enumeration approach, IA bound is the best choice. If we compare the results only for art1−art9 networks, which are very small, see Table 1, the enumeration approach becomes the best in terms of all criteria. However, when the size of the network increases, the superset approach outperforms the enumeration one. For the enumeration approach, the dierence between the bounding approaches in terms of MaxList size is hardly noticeable, being the best choice IA+DC as upper bound and MidPoint as lower bound. For the superset approach, slightly better MaxList sizes are achieved when using HuDisc bound. Finally, we analyze results for p= 5 , Tables 8 and 9. Using enumeration we are able to solve the problem on 8 networks while with supersets on 7 networks. Using enumeration, 9 Table 6: Maximum branch and bound tree size, running times and achieved gaps for p= 4 for the enumeration approach. enumeration Upper bound IA IA+DC Lower bound HuDisc MidPoint HuDisc MidPoint Network MaxList time gap MaxList time gap MaxList time gap MaxList time gap art1 87598 1.68 − 117441 1.22 − 101277 8.63 − 198557 4.29 − art2 74095 1.23 − 101784 1.58 − 163003 15.16 − 167512 5.40 − art3 177508 8.55 − 293743 4.43 − 307426 29.08 − 490398 12.36 − art4 159413 8.46 − 185915 5.24 − 454552 68.27 − 459312 21.04 − art5 873673 39.11 − 881711 16.61 − 1150102 199.56 − 1177881 59.86 − art6 975158 51.75 − 984445 23.57 − 2080085 327.80 − 2129849 84.52 − art7 1028331 58.73 − 1036206 24.90 − 1347049 268.88 − 1406366 71.64 − art8 1616556 92.37 − 1651432 40.20 − 3423277 659.45 − 3426785 158.54 − art9 1100215 141.68 − 1111150 63.32 − 5890324 1527.42 − 5890324 322.58 − pmed1 3920397 1314.92 − 3927269 851.34 − 6667549 3020.66 − 6667781 1292.31 − pmed2 7644966 959.14 − 7646396 763.20 − 9792019 1369.41 − 9792181 1027.34 − pmed3 2342677 1217.93 − 2344253 832.70 − 4280821 2344.15 − 4280821 1212.02 − pmed4 2652444 1252.69 − 2685214 817.60 − 2767490 1840.00 − 2767490 1100.93 − pmed5 8830603 2538.98 − 8979523 1041.57 − 9393530 3119.91 − 9398491 1350.89 − KROB150G 27979117 × 0.04 29666987 9798.09 − 8609286 20606.66 − 8609286 9043.41 − KROA150G × 5256.88 34.17 × 5348.99 34.17 24167062 × 0.03 24203649 11270.48 − PR152G 2993638 13190.67 − 3099354 6683.47 − 8203867 × 0.01 8203867 9327.78 − RAT195G × 2956.78 32.24 × 3000.29 32.24 × 12331.88 17.67 × 12191.70 17.67 KROB200G × 21119.03 26.10 × 20559.01 26.10 × 20059.76 27.89 24150000 × 0.27 KROA200G 22110803 × 0.18 22149983 × 0.23 8670000 × 0.26 8670000 × 0.26 TS225G 22200741 × 0.02 22243742 12332.64 − 18379844 × 0.04 18379844 15321.28 − Average 19369901 5476.69 4.42 19481264 3990.95 4.42 15040407 7342.70 2.19 11450971 5098.97 0.87 Table 7: Maximum branch and bound tree size, running times and achieved gaps for p= 4 for the superset approach. superset Upper bound IA IA+DC Lower bound HuDisc MidPoint HuDisc MidPoint Network MaxList time gap MaxList time gap MaxList time gap MaxList time gap art1 157141 19.22 − 152898 4.23 − 157141 20.22 − 152898 4.35 − art2 181037 17.05 − 326290 3.81 − 181037 17.89 − 326290 3.87 − art3 1093070 156.98 − 2659877 34.73 − 1093070 165.64 − 2659878 36.05 − art4 101627 13.63 − 248993 2.65 − 101627 14.23 − 248998 2.70 − art5 784382 109.43 − 1730167 21.61 − 784350 114.36 − 1730170 21.96 − art6 1346499 196.92 − 1845530 33.52 − 1346499 202.04 − 1845530 34.68 − art7 1415772 222.43 − 1581166 39.30 − 1415772 225.20 − 1581166 40.17 − art8 3459070 702.52 − 5218221 116.56 − 3459070 708.77 − 5218221 120.68 − art9 4195351 802.08 − 7068510 125.58 − 4195351 809.40 − 7068510 125.33 − pmed1 10765649 7786.70 − 12980089 859.97 − 10765649 7677.53 − 12980089 857.10 − pmed2 11143314 7410.62 − 19962438 834.42 − 10984446 7273.61 − 19944050 819.15 − pmed3 6524060 4148.35 − 9334140 464.82 − 6522592 4116.63 − 9332340 458.92 − pmed4 16174587 9091.02 − 24213155 1031.35 − 16174587 9017.36 − 24213155 1023.01 − pmed5 8687562 5509.46 − 10884353 604.88 − 8687776 5464.92 − 10884353 599.86 − KROB150G 35348181 × 3.26 42047737 3354.30 − 35289997 × 3.24 41974612 3347.03 − KROA150G 31579343 × 2.44 38836554 3146.35 − 31579345 × 2.43 38836554 3172.58 − PR152G 2879248 5482.97 − 3759971 460.70 − 2796219 5290.21 − 3657358 450.09 − RAT195G 39163633 × 15.94 × 3893.07 12.57 40806156 × 8.27 × 3779.84 9.93 KROB200G 27205462 × 4.64 38996783 4209.31 − 25044941 × 3.44 36820724 3896.58 − KROA200G 18774302 × 3.08 24445462 2700.81 − 16949758 × 2.43 22853487 2503.93 − TS225G 22020591 × 2.73 28041441 2878.48 − 22020758 × 2.73 28041441 2869.51 − Average 11571423 8155.68 1.53 17825418 1181.93 0.60 11445531 8129.43 1.07 17636658 1150.83 0.47 16 Table 8: Maximum branch and bound tree size, running times and achieved gaps for p= 5 for the enumeration approach. enumeration Upper bound IA IA+DC Lower bound HuDisc MidPoint HuDisc MidPoint Network MaxList time gap MaxList time gap MaxList time gap MaxList time gap art1 761505 22.62 − 954269 14.45 − 850668 164.28 − 2884315 70.31 − art2 833806 15.69 − 937528 11.62 − 1533922 324.22 − 1655465 102.99 − art3 2218569 200.29 − 5398052 101.84 − 3472626 799.30 − 8899181 296.18 − art4 2072133 210.15 − 2228330 81.31 − 5461464 1934.30 − 5461464 509.90 − art5 13916512 1285.29 − 13942105 433.95 − 17259376 7172.07 − 18616932 1732.50 − art6 17322753 1884.49 − 17534221 681.16 − 39108015 17341.40 − × 763.47 83.84 art7 17115252 1830.39 − 21231438 685.81 − 21110879 11568.02 − 25765937 3450.06 − art8 × 286.62 28.17 × 388.10 34.34 × 416.04 80.16 × 509.84 91.73 art9 17510258 3538.34 − 17525808 1663.44 − × 443.31 99.23 × 590.92 99.23 pmed1 × 5610.09 34.84 × 5318.60 34.84 × 2075.53 73.16 × 2099.87 73.16 pmed2 × 2043.19 40.74 × 1877.88 40.74 × 1071.52 48.64 × 1089.60 48.64 pmed3 × 3195.31 32.60 × 5224.86 33.86 × 2865.89 53.84 × 2843.13 53.84 pmed4 × 1703.33 27.98 × 5537.69 28.46 × 3068.20 53.54 × 3033.74 53.54 pmed5 × 6864.04 35.36 × 1704.56 39.75 × 1733.62 52.25 × 1713.50 52.25 KROB150G × 3326.66 31.34 × 3234.95 31.34 × 8541.38 26.04 × 8453.09 26.04 KROA150G × 4453.25 28.90 × 4371.62 28.90 × 2252.59 31.32 × 2242.95 31.32 PR152G 17820377 × 0.17 17968869 × 0.20 × 13184.08 45.96 × 13009.80 45.96 RAT195G × 2947.69 28.09 × 2885.96 28.09 × 3035.05 23.54 × 3019.45 23.54 KROB200G × 12617.27 26.03 × 12737.00 26.03 × 6584.91 32.84 × 6603.30 32.84 KROA200G × 3645.04 40.16 × 3671.02 40.16 × 8926.33 43.28 × 8845.65 43.28 TS225G × 9715.15 26.58 × 9851.17 26.58 × 8832.73 37.19 × 8742.36 37.19 Average 61408150 4142.61 18.14 61796220 3908.43 18.73 70895092 4873.08 33.38 74442061.62 3320.12 37.92 Table 9: Maximum branch and bound tree size, running times and achieved gaps for p= 5 for the superset approach. superset Upper bound IA IA+DC Lower bound HuDisc MidPoint HuDisc MidPoint Network MaxList time gap MaxList time gap MaxList time gap MaxList time gap art1 1452057 310.71 − 1451329 58.63 − 1452056 307.24 − 1451328 59.09 − art2 1994545 270.01 − 3696608 55.65 − 1994543 270.26 − 3696616 55.88 − art3 36610591 6922.33 − 92922451 1502.35 − 36610591 6910.81 − 92922451 1490.92 − art4 1228104 235.41 − 2984440 43.12 − 1228104 235.27 − 2984440 44.16 − art5 20255341 4142.36 − 45869245 785.61 − 20255346 4144.18 − 45869251 799.97 − art6 22539544 4639.56 − 29757712 727.59 − 22539545 4643.0 − 29757713 733.52 − art7 25822697 5571.06 − 31479371 896.23 − 25822697 5580.98 − 31479371 897.07 − art8 × 9939.57 4.60 × 1094.05 8.10 × 9937.81 4.60 × 1088.79 8.10 art9 × 10181.58 8.96 × 1058.50 24.56 × 10103.78 8.96 × 1049.59 24.56 pmed1 68661960 × 18.38 × 2901.09 19.27 68470552 × 18.40 × 2839.00 19.27 pmed2 70797011 × 19.05 × 2774.52 22.43 70727962 × 18.98 × 2738.64 22.35 pmed3 68662438 × 15.47 × 2865.02 19.57 68029779 × 15.54 × 2893.29 19.57 pmed4 70145377 × 23.65 × 2827.24 26.15 71493389 × 22.38 × 2727.99 27.76 pmed5 69754129 × 18.18 × 2756.32 17.42 69989853 × 18.08 × 2780.73 17.41 KROB150G 31327042 × 26.10 × 4152.59 24.74 36024130 × 21.09 × 3880.06 20.15 KROA150G 32557892 × 24.46 × 4095.34 21.55 35501051 × 20.57 × 3957.60 20.96 PR152G 34521048 × 6.92 × 4522.50 4.34 35281520 × 5.57 × 4524.22 4.13 RAT195G 20016605 × 48.90 × 5492.69 44.99 27657715 × 20.40 × 4631.51 24.53 KROB200G 17064415 × 29.03 × 5865.73 20.12 22428893 × 15.32 × 5085.60 15.25 KROA200G 16281856 × 29.79 × 5778.46 22.11 20716500 × 15.35 × 5165.29 14.37 TS225G 18788148 × 30.97 × 6013.59 23.07 21635793 × 21.94 × 5668.51 20.94 Average 39451467 14352.98 14.50 76579103 2679.37 14.21 40850477 14349.60 10.82 76579103 2529.12 12.35 17