Applied Science and Innovative Research ISSN 2474-4972 (Print) ISSN 2474-4980 (Online) Vol. 7, No. 2, 2023 www.scholink.org/ojs/index.php/asir 158 Original Paper Modeling and Solving a Linear Integer Problem (PLNE) for the Optimal Localization of a Hub Air Transport in the WAEMU Zone Abdoulaye Ali Ibrahima1*, Saley Bisso2 & Salimata Gueye Diagne2 1 Andre Salifou University, Zinder, Niger 2 Abdou Moumouni University, Niamey, Niger * Cheikh Anta Diop University, Dakar, Senegal Received: May 2, 2023 Accepted: May 20, 2023 Online Published: May 27, 2023 doi:10.22158/asir.v7n2p158 URL: http://doi.org/10.22158/asir.v7n2p158 Abstract In this article, we propose a linear integer model for the optimal location of a hub for air traffic in the WAEMU zone. A hub represents for an airline a base where an essential part of its activities is concentrated. Its location must therefore be judiciously determined. The hub location problem is one of the new and promising areas of research in the field of location theory. In order to satisfy a demand, the location of the hub involves the movement of people, goods between origin destination pairs required. Hubs are applied to reduce the number of transport links between the origin and destination airports The proposed model minimizes the distances and takes into account the flow of passengers registered in the different airports and minimizes the total cost of the transfer via the hub airport. The simulations were made with the programming language Python. Keywords optimization, optimal localization, algorithm, hub, PLNE, WAEMU 1. Introduction The hub location problem is one of the new and promising areas of research in the field of location theory. In order to satisfy a demand, the location of the hub involves the movement of people, goods between origin-destination pairs required. Hubs are applied to reduce the number of transport links between the origin and destination airports. The choice of its location consists in determining the ideal location of the airport in order to optimize an economic function. This can depend on distances between the airports, the cost of extending the airport, the transport cost per unit distance, it integrates Kerozene www.scholink.org/ojs/index.php/asir Applied Science and Innovative Research Vol. 7, No. 2, 2023 159 Published by SCHOLINK INC. operating costs, the number of passengers registered at the airport, etc. Several researchers have worked on the problem of air transport in general and in particular on the location of hubs. Regarding the most important preliminary studies in the hub location sector, O’Kelly had a key position to develop the first quadratic mathematical formula (O’Kelly, 1987, 1992). Later, Campbell proposed multiple mathematical formulas to consider similar objective functions as several classic locational problems (Campbell, 1994, 1996). Moreover, Aykin and Klincewicz have also had important roles in advancing the field (Aykin, 1994, 1995; Klincewicz, 1991, 1992). Recently, Campbell and O’Kelly (2012) recently discussed the origins and motivations of the hub localization problem as well as some of the shortcomings in this in this field. The first investigations of the hub localization problem were offered by Campbell (1994a), O’Kelly and Miller (1994). In addition, Klincewicz (1998) and Bryan and O’Kelly (1999) reviewed hub localization applications for telecommunications and the airline industry respectively. Alumur and Kara (2008) reviewed and classified published material until 2007. In addition to these journals, we can refer to Campbell, Ernst, and Krishnamoorthy (2002) and Farahani and Hekmatfar (2009) for the basic definitions, classification, mathematical models and solution methods of hubs. Ivan Contreras et al used the Branch and price and Lagrangian relaxation (Lapgue, 2013) for the problem of locating and uniquely assigning a hub with a large capacity. C. Diallo et al worked on the scheduling of landings at Leopold airport Sedar SENGOR from Dakar. Tanguy et al developed a mathematical model for the scheduling of staff with assignment of tasks and in using the localization to present an industrial problem. O’Kelly gives a quadratic formulation of the entire program of locating a hub with no-capacity assignment. Rodguez and all solved the problem of locating and assigning a single hub with a large capacity by Branch and Price. N’DOGOTAR NELIO presented the first model of location of an air hub in WAEMU zone, which minimizes the distances traveled taking into account the flow of passengers registered at the airports of the WAEMU zone that we will present. Although these studies have dealt with localization problems from various points of view, all of these authors, whose list is not exhaustive, have made a contribution to the air transport system. But so far no specific contribution for the WAEMU zone. In this article, we make our contribution in the management of the air transport system in the UEMOA zone by proposing and solving an air hub location model, which minimizes the total cost of transport per unit of distance, taking into account of the flow of passengers registered at the airports of the UEMOA zone and we use the Cplex software for the simulation. 1.1 State Art of the Problem The hub location problem is a relatively new extension of the location problems of conventional installations. Hubs are facilities that function as consolidation, connection, and switch points for flows between stipulated origins and destinaf tions. Although there are few review papers on the problems of localization of the air hub in the UEMOA zone, the most recent (N’DOGOTAR Nelio Modeling and Resolution of a linear integer problem (PLNE) for the optimal localization anair hub in the WAEMU 3 www.scholink.org/ojs/index.php/asir Applied Science and Innovative Research Vol. 7, No. 2, 2023 160 Published by SCHOLINK INC. zone). Indeed several factors must be taken into account when choosing an airline. The structure of the network has to say the number of hubs and their location. Among the main ones, we can mention: The potential of traffic in the city centers, central geographical position compared to the markets served in order to minimize the costs taking into account the demand for good airport facilities allowing an optimal coordination of the schedules with time of correspondence minimum, good meteorological conditions allowing the airlines to operate the network satisfactorily, as well as the location of the hubs and the strategic behavior of the competitors. It is necessary to avoid the passengers detours too important. The hub must be located in a region that itself generates significant demand for air transport, in order to contribute to the filling of aircraft and the geographical diversity of the proposed routes. As a result, most hubs are located close to major urban centers, especially if they concentrate international economic functions. The hub airport must have sufficient capacity, both to develop the offer and to organize schedules as freely as possible and thus effectively coordinate flights. We consider here the eight countries of the UEMOA zone: Benin, Burkina Faso, Ivory Coast, Guinea Bissau, Mali, Niger, Senegal and Togo, represented by the international airport of their capital. 2. Method 2.1 Mathematical Modeling Let us consider the graph G = (N, A) where N is the set of numbers corresponding to the origins / destinations and representing the airports of the capitals of the WAEMU countries. All nodes are airports that can be a potential hub. A is the set of edges connecting the different airports. 2.2 Mathematical Model Minimizing Distances for Locating a Hub Nelio N’DOGOTAR presented the first problem of locating a hub in WAEMU zone in which, the number of hubs to locate is defined exogenously and is equal to one of which the second will be presented by us in the next section. And the problem is a single assignment because only one hub needs to be located. Parameters: • N: the number of international airports in the WAEMU zone; • d i j: the distance between two nodes i and j; • δ ik j: the distance between the nodes i and j via the node k; • P i: The number of passengers registered in one year in at an airport i; • X: the arithmetic average of the number of passengers registered in the WAEMU zone; • mi: the number of commercial movements recorded in one year at the airport i; • M:the arithmetic average of movements recorded in the WAEMU zone. The decision variable is: www.scholink.org/ojs/index.php/asir Applied Science and Innovative Research Vol. 7, No. 2, 2023 161 Published by SCHOLINK INC. The function to minimize is: where x = (x1, x2,…, xN); δikk = dik; δkkj = dkj and δkkk = 0. Our mathematical model in Linear Integer Programming (PLNE for its acronym in french), called the Problem P, is (1) S/C (2) (3) (4) (5) Objective (1) minimizes the sum of the distances between the different airports and the hub airport. The constraint (2) means that exactly a hub must be localized. The constraint (3) shows that if the hub is located at the airport k then the number of passengers registered in this The airport must be higher than the average of the passengers registered in the WAEMU zone. The constraint (4) shows that if the hub is located at the airport k then the number of movements recorded in this The airport must be greater than the average of the movements recorded in the WAEMU zone. Constraints (5) mean that the decision variables xk are binary 2.3 Mathematical Model Minimizing the Total Cost of Transportation via Hub Airport We propose a model in which the solution domain is the WAEMU airport network, the non-hub airports are connected to the hub airport, the number of hubs to be located is defined exogenously and is equal to one. There is no cost for setting up the hub’s capacity, and the problem is a single assignment as only one hub needs to be located. The entries of the problem are as follows: www.scholink.org/ojs/index.php/asir Applied Science and Innovative Research Vol. 7, No. 2, 2023 162 Published by SCHOLINK INC. The parameters: • N: the number of international airports in the WAEMU zone; • hi j: the passenger flow between two nodes i and j; • ci j: unit cost of transfer from the non-hub airport to the hub airport; • Pi: The number of passengers registered in one year at the airport i; • X: the arithmetic average of the number of passengers registered in the WAEMU zone; • mi: the number of commercial transactions recorded in one year at the airport i; • M: the arithmetic average of movements registered in the WAEMU zone. The decision variable is: If yij= 1, the airport j is assigned to himself because of this it is a hub. The function to minimize is: Our Mathematical Model in Linear Integer Programming (PLNE), called problem P, is: (6) S/C (7) (8) (9) (10) (11) Eq (6) minimizes the total cost of transfer via hub airport. Eq (7) states that there is only one hub. Eq (8) www.scholink.org/ojs/index.php/asir Applied Science and Innovative Research Vol. 7, No. 2, 2023 163 Published by SCHOLINK INC. states that if the hub is located at the airport j the number of passengers registered at this airport must be greater than the average of the passengers in the uemoa zone. Eq (9) states that if the hub is located at the airborne j then the number of movements recorded at that airport must be greater than the average of the movements recorded in the uemoa zone. Eq (10) states that airport i can only be linked to a hub airport in j. Eq (11) defines the binary type decision variable. To linearise the objective function, if the non hub airport is assigned to a hub airport, we will only have one hub and the other non hub airports must be assigned to this hub. 3. Resolution For the resolution of this model, we have developed a resolution algorithm that we present with three steps: Step 1 1. Enter the value of N 2. Enter Pi for all i in {1,...,N} 3. Calculates X Step 2 1. Enter the di; j 2. Calculate the ”distancer” matrix 3. Compute sums Li(i in {1,...,N}) Step 3 1. Initialize the sum (take a value � maxLi) 2. For all i in {1,...,N} if Pi ≥ X give line i and sum Li sum Li < sum for all i in {1,.. .,N} then solution = Li 3. Give the minimum value Li and the index i 4. The optimal location of the hub is in i 4. Result 4.1 Simulations and Results For the simulation, we used Python software version 3.8, on an HP computer whose characteristics are as follows: System: Windows 7 Enterprise Rating: 5.9 Windows Performance Index Processor: Intel(R) core(TM)i5-53OOU CPU @230GHz 230GHz Installed memory (RAM): 8.00GB (7.88GB usable) System type: 64bit operating system, processor64. The data concerning the distances between the different airports are calculated by a software for determining the distances as the crow flies between the airports which can be found on the site: www.scholink.org/ojs/index.php/asir Applied Science and Innovative Research Vol. 7, No. 2, 2023 164 Published by SCHOLINK INC. www.ephemeride.com For the number of passengers registered at airports in a year, we use annual data from the seven countries of the West African Monetary and Economic Union (UEMOA), the eighth that is Guinea Bissau was removed due to lack of observations on some indicators over the period. Data cover the period from 2002 to 2017 and come from the database of the World Bank (World Development Indicators (http://data.worldbank.org/indicator)). The selection of this period is constrained by the lack of observations of certain variables to be from previous years and for most countries we have taken the average. Table 1. Number of Air Passengers Transported Pays BFA CIV BEN MLI NER SEN TGO 99302,02 324999,8 65468,45 187224,2 106919,14 349666,3 578545,6 After simulation by Python software, the average number of passengers registered in the WAEMU zone is of X = 244589.358 or 244590 passengers and the sum of the distances from each airport to all the other airports is shown in the table below: Table of simulation results. Table 2. Table of Distance Matrix Results Pays BFA CIV BEN MLI NER SEN TGO Somme V.V.C BFA 0 828,943 789,734 699,712 418,901 1749,6 748,308 5235,198 CIV 828,943 0 710,061 918,532 1130,158 1818,472 583,025 5989,191 5989,191 BEN 789,734 710,061 0 1324,38 789,308 2363,256 127,041 6103,78 MLI 699,712 840,934 1324,38 0 1102,383 1061,459 1231,227 6337,693 NER 418,901 1942,843 789,308 1102,383 0 2127,439 815,437 6383,626 SEN 1749,6 373,591 2363,256 1061,459 2127,439 0 2258,757 11378,983 11378,983 TGO 748,308 1961,805 127,041 1231,227 815,437 2258,757 0 5763,795 5763,795 In this Table 2: - From the first column to the eighth column, we have the distancing matrix. - The ninth column gives the sum of the distances from each airport to all the others. - The last column gives the V.V.C (Values Verifying the Constraints). They are three in number. Among the three values, the minimum values are 5989.198 and 5763.795 km and correspond to the airport ABJ and TGO. The TGO airport without taking transport costs into account. Now let’s take a look at the transport cost matrix www.scholink.org/ojs/index.php/asir Applied Science and Innovative Research Vol. 7, No. 2, 2023 165 Published by SCHOLINK INC. Table 3. Transport Cost Matrix Table BEN BFA CIV GIN MLI NER SEN TGO Somme V.V.C BEN 0 287 167 468 250 392 321 302 2187 BFA 249 0 230 538 267 511 272 249 2316 CIV 142 292 0 420 306 308 152 164 1784 1784 GNB 3140 440 671 0 437 2852 665 780 8985 MLI 252 254 202 371 0 487 230 338 2134 NER 446 215 356 1439 557 0 454 356 3823 SEN 340 360 202 261 273 398 0 446 2280 2280 TGO 476 483 298 511 499 641 378 0 3286 3286 In this Table 3: - From the first column to the eighth column, we have the cost matrix. - The ninth column gives the sum of the costs from each airport to all the others. - The last column gives the V.V.C (Values Verifying the Constraints). They are three in number. Among the three values, the minimum value is 1784 euro and corresponds to ABJ airport against that of TGO which is 3286 euro. Abidjan airport is therefore the optimal location. NB: Ouagadougou airport does not respect constraint (3). In the absence of this constraint instead of Abidjan airport Ouagadougou airport would have been chosen as the hub. 5. Discussion 5.1 Conclusion and Outlook In this paper, we have proposed a model for the air hub location problem for the area UEMOA and a model that minimizes the total cost of transfer via the hub airport. In the constraints, we have introduces a constraint on the average number of passengers registered in a year at the airport. Stress who to our knowledge does not appear in the models proposed so far on the location of hubs. For the resolution, we developed an algorithm and we used Python software to do the simulation. After simulation three airports out of the eight, namely the airports of Abidjan, Dakar and Lom, have fulfilled all the constraints imposed. But as we seek to minimize the distances traveled and the transfer costs, the airport having the smallest distance and the minimum cost among the three will be the best. It turned out that the optimal hub location is Abidjan airport for a company in the UEMOA zone. As a hub can be moved for one reason or another, as a perspective we intend to make a model a location of a hub which will take into account: -The political stability of countries - the cost of expanding airports -the capacity of the planes of the fleet www.scholink.org/ojs/index.php/asir Applied Science and Innovative Research Vol. 7, No. 2, 2023 166 Published by SCHOLINK INC. - then we also plan to make a model of location of two hubs. References Alumur, S., & Kara, B. Y. (2008). Network hub location problems: The state of the art. European Journal of Operational Research, 190(1), 1-21. https://doi.org/10.1016/j.ejor.2007.06.008 Aykin, T. (1994). Lagrangian relaxation based approaches to capacitated hub-and spoke network design problem. European Journal of Operational Research, 79, 501-523. https://doi.org/10.1016/0377-2217(94)90062-0 Aykin, T. (1995a). Networking policies for hub-and-spoke systems with application to the air transportation system. Transportation Science, 29(3), 201-221. https://doi.org/10.1287/trsc.29.3.201 Aykin, T. (1995b). The hub location and routing problem. European Journal of Operational Research, 83, 200-219. https://doi.org/10.1016/0377-2217(93)E0173-U Bryan, D. L., & O’Kelly, M. E. (1999). Hub and spoke networks in air transportation: An analytical review. Journal of Regional Sciences, 39(2), 275-295. https://doi.org/10.1111/1467-9787.00134 Campbell, J. F. (1994b). Integer programming formulations of discrete hub location problems. European Journal of Operational Research, 72, 387-405. https://doi.org/10.1016/0377-2217(94)90318-2 Campbell, J. F. (1996). Hub location and p-hub median problem. Operations Research, 44(6), 923-935. https://doi.org/10.1287/opre.44.6.923 Campbell, J. F., & O’Kelly, M. E. (2012). Twenty-five years of hub location research. Transportation Science, 46(2), 153-169. https://doi.org/10.1287/trsc.1120.0410 Contreras Ivan, A. Das Juan, & Elena Fernndez. (2009). Lagrangian relaxation for the capacited hub location problem with single assignment. Regular Article, 31, 483-505. https://doi.org/10.1007/s00291-008-0159-y Contreras Ivan, A. Dias Juan, & Elena Fernandez. (2011). Branch and price for large-scale capacitated hub location problems with single assignment. INFORMS Journal on Computing, 23, 41-55. https://doi.org/10.1287/ijoc.1100.0391 Diallo Coumba, Mbaye Ndiaye Babacar, & Seck Diaraf. (2012). Scheduling aircraft landings at lss airport. American Journal of Operations Research, 2, 235-241. https://doi.org/10.4236/ajor.2012.22027 Ernst, A. T., Hamacher, H., Jiang, H., Krishnamoorthy, M., & Woeginger, G. (2002). Uncapacitated single and multiple allocation p-hub center problems. Technical report, CSIRO, Australia. Farahani, R. Z., & Hekmatfar, M. (2009). Facilities location: Concepts, models, algorithms and case studies. Heidelberg: Springer-Verlag. https://doi.org/10.1007/978-3-7908-2151-2 Klincewicz, J. G. (1991). Heuristics for the p-hub location problem. European Journal of Operational Research, 53, 25-37. https://doi.org/10.1016/0377-2217(91)90090-I www.scholink.org/ojs/index.php/asir Applied Science and Innovative Research Vol. 7, No. 2, 2023 167 Published by SCHOLINK INC. Klincewicz, J. G. (1992). Avoiding local optima in the p-hub location problem using Tabu search and grasp. Annals of Operational Research, 40, 283-302. https://doi.org/10.1007/BF02060483 Klincewicz, J. G. (1998). Hub location in backbone tributary network design: A review. Location Science, 6, 307-335. https://doi.org/10.1016/S0966-8349(98)00042-4 Lapgue Tanguy, Bellenguez-Morineau Odile, & Prot Damien. (2013). A constraint-based approach for the shift design personnel task scheduling problem with equity. Computers and Operations Research, 40, 2450-2465. https://doi.org/10.1016/j.cor.2013.04.005 Lapgue Tanguy, Prot Damien, & Bellenguez-Morineau Odile. (2013). Ordonnancement de personnel avec affectation detches: un modle mathmatique. In ROADEF. N’Dogotar Nelio, Salimata Gueye Diagne, Pr Youssou Gningue, et al. (2015). Modlisation et Rsolution d’un problme linaire en nombres entiers(PLNE) pour la localisation optimale d’un hub arien dans la zone UEMOA. 16 Avril 2015. O’Kelly, M. (1987). A quadratic integer program for the location of interacting hub facilities. European Journal of Operational Research, 32, 393-404. https://doi.org/10.1016/S0377-2217(87)80007-3 O’Kelly, M. E. (1986a). The location of interacting hub facilities. Transportation Science, 20, 92-106. https://doi.org/10.1287/trsc.20.2.92 O’Kelly, M. E. (1986b). Activity levels at hub facilities in interacting networks. Geographical Analysis, 18(4), 343-356. https://doi.org/10.1111/j.1538-4632.1986.tb00106.x O’Kelly, M. E. (1987). A quadratic integer program for the location of interacting hub facilities. European Journal of Operational Research, 32, 393-404. https://doi.org/10.1016/S0377-2217(87)80007-3 O’Kelly, M. E. (1992). Hub facility location with fixed costs. Papers in Regional Science, 71, 292-306. https://doi.org/10.1007/BF01434269 O’Kelly, M. E. (2009). Rectilinear minimax hub location problems. Journal of Geographical Systems, 11, 227-241. https://doi.org/10.1007/s10109-009-0091-y O’Kelly, M. E., & Bryan, D. (1998). Hub location with flow economies of scale. Transportation Research Part B, 32(8), 605-616. https://doi.org/10.1016/S0191-2615(98)00021-6 O’Kelly, M. E., & Miller, H. (1994). The hub network design problem: A review and synthesis. Journal of Transport Geography, 2(1), 31-40. https://doi.org/10.1016/0966-6923(94)90032-9 O’Kelly, M. E., Skorin-Kapov, D., & Skorin-Kapov, J. (1995). Lower bounds for the hub location problem. Management Science, 41, 713-721. https://doi.org/10.1287/mnsc.41.4.713 Ostresh, L. M. Jr. (1975). An efficient algorithm for solving the two center location-allocation problem. Journal of Regional Science, 15, 209-216. https://doi.org/10.1111/j.1467-9787.1975.tb00921.x