[en] We consider two covering variants of the network design problem. We are given a set of origin/destination pairs, called O/D pairs, and each such O/D pair is covered if there exists a path in the network from the origin to the destination whose length is not larger than a given threshold. In the first problem, called the Maximal Covering Network Design problem, one must determine a network that maximizes the total fulfilled demand of the covered O/D pairs subject to a budget constraint on the design costs of the network. In the second problem, called the Partial Covering Network Design problem, the design cost is minimized while a lower bound is set on the total demand covered. After presenting formulations, we develop a Benders decomposition approach to solve the problems. Further, we consider several stabilization methods to determine Benders cuts as well as the addition of cut-set inequalities to the master problem. We also consider the impact of adding an initial solution to our methods. Computational experiments show the efficiency of these different aspects.
Disciplines :
Quantitative methods in economics & management
Author, co-author :
Bucarey, V.
Fortz, Bernard ; Université de Liège - ULiège > HEC Liège Research > HEC Liège Research: Business Analytics & Supply Chain Mgmt
González-Blanco, N.
Labbé, M.
Mesa, J.A.
Language :
English
Title :
Benders decomposition for network design covering problems
scite shows how a scientific paper has been cited by providing the context of the citation, a classification describing whether it supports, mentions, or contrasts the cited claim, and a label indicating in which section the citation was made.
Bibliography
Balakrishnan, A., Magnanti, T.L., Wong, R.T., A dual-ascent procedure for large-scale uncapacitated network design. Oper. Res. 37:5 (1989), 716–740.
Balas, E., Perregaard, M., Lift-and-project for mixed 0–1 programming: recent progress. Discrete Appl. Math. 123:1–3 (2002), 129–154.
Balas, E., Perregaard, M., A precise correspondence between lift-and-project cuts, simple disjunctive cuts, and mixed integer Gomory cuts for 0-1 programming. Math. Program. 94:2–3 (2003), 221–245.
Barahona, F., Network design using cut inequalities. SIAM J. Optim. 6:3 (1996), 823–837.
Ben-Ameur, W., Neto, J., Acceleration of cutting-plane and column generation algorithms: Applications to network design. Networks: Int. J. 49:1 (2007), 3–17.
Berge, C., Two theorems in graph theory. Proc. Natl. Acad. Sci. USA 43:9 (1957), 842–844.
Botton, Q., Fortz, B., Gouveia, L., Poss, M., Benders decomposition for the hop-constrained survivable network design problem. INFORMS J. Comput. 25:1 (2013), 13–26.
Canca, D., De-Los-Santos, A., Laporte, G., Mesa, J.A., An adaptive neighborhood search metaheuristic for the integrated railway rapid transit network design and line planning problem. Comput. Oper. Res. 78 (2017), 1–14.
Canca, D., De-Los-Santos, A., Laporte, G., Mesa, J.A., Integrated railway rapid transit network design and line planning problem with maximum profit. Transp. Res. E 127 (2019), 1–30.
Cascetta, E., Transportation Systems Analysis: Models and Applications, Vol. 29. 2009, Springer Science & Business Media.
Church, R., ReVelle, C., The maximal covering location problem. Pap. Reg. Sci. Assoc. 32 (1974), 101–118.
Church, R., ReVelle, C., The maximal covering location problem. Papers of the Regional Science Association, Vol. 32, No. 1, 1974, Springer-Verlag, 101–118.
Conforti, M., Wolsey, L.A., “Facet” separation with one linear program. Math. Program. 178:1–2 (2019), 361–380.
Cordeau, J.-F., Furini, F., Ljubić, I., Benders decomposition for very large scale partial set covering and maximal covering location problems. European J. Oper. Res. 275:3 (2019), 882–896.
Desrochers, M., An Algorithm for the Shortest Path Problem with Resource Constraints, Vol. 421. 1986, Université de Montréal, Centre de recherche sur les transports.
Fischetti, M., Salvagnin, D., Zanette, A., A note on the selection of Benders’ cuts. Math. Program. 124:1–2 (2010), 175–182.
Fortz, B., Gouveia, L., Moura, P., A Comparison of Node-Based and Arc-Based Hop-Indexed Formulations for the Steiner Tree Problem with Hop Constraints: Technical Report., 2021, Université libre de Bruxelles.
Fortz, B., Poss, M., An improved Benders decomposition applied to a multi-layer network design problem. Oper. Res. Lett. 37:5 (2009), 359–364.
García, S., Marín, A., Covering location problems. Laporte, G., Stefan, N., da Gama, F.S., (eds.) Location Science, 2020, Springer, 99–119.
García-Archilla, B., Lozano, A.J., Mesa, J.A., Perea, F., GRASP algorithms for the robust railway network design problem. J. Heuristics 19:2 (2013), 399–422.
Guihaire, V., Hao, J.-K., Transit network design and scheduling: A global review. Transp. Res. A 42:10 (2008), 1251–1273.
Hakimi, S.L., Optimum distribution of switching centers in a communication network and some related graph theoretic problems. Oper. Res. 13:3 (1965), 462–475.
Hellman, F., Sioux falls variants for network design. 2013 URL: http://www.bgu.ac.il/bargera/tntp/SiouxFalls_CNDP/SiouxFallsVariantsForNetworkDesign.html. (Accessed 24 April 2021).
Koster, A., Phan, T.K., Tieves, M., Extended cutset inequalities for the network power consumption problem. Electron. Notes Discrete Math. 41 (2013), 69–76.
Król, A., Król, M., The design of a metro network using a genetic algorithm. Appl. Sci., 9(3), 2019, 433.
Ljubić, I., Mouaci, A., Perrot, N., Gourdin, E., Benders decomposition for a node-capacitated virtual network functions placement and routing problem. 2019.
Ljubić, I., Putz, P., Salazar-González, J.-J., Exact approaches to the single-source network loading problem. Networks 59:1 (2012), 89–106.
Magnanti, T.L., Mireault, P., Wong, R.T., Tailoring benders decomposition for uncapacitated network design. Netflow at Pisa, 1986, Springer, 112–154.
Magnanti, T.L., Wong, R.T., Accelerating Benders decomposition: Algorithmic enhancement and model selection criteria. Oper. Res. 29:3 (1981), 464–484.
Magnanti, T.L., Wong, R.T., Network design and transportation planning: Models and algorithms. Transp. Sci.(18), 1984, 1–55.
Norman, R.Z., Rabin, M.O., An algorithm for a minimum cover of a graph. Proc. Amer. Math. Soc. 10:2 (1959), 315–319.
Perea, F., Menezes, M.B., Mesa, J.A., Rubio-Del-Rey, F., Transportation infrastructure network design in the presence of modal competition: computational complexity classification and a genetic algorithm. TOP 28 (2020), 442–474.
Rahmaniani, R., Crainic, T.G., Gendreau, M., Rei, W., The Benders decomposition algorithm: A literature review. European J. Oper. Res. 259:3 (2017), 801–817.
Schmidt, M., Schöbel, A., Location of speed-up subnetworks. Ann. Oper. Res. 223:1 (2014), 379–401.
Sinnl, M., Ljubić, I., A node-based layered graph approach for the Steiner tree problem with revenues, budget and hop-constraints. Math. Program. Comput. 8:4 (2016), 461–490.
Toregas, C., Swain, R., ReVelle, C., Bergman, L., The location of emergency service facilities. Oper. Res. 19:6 (1971), 1363–1373.
This website uses cookies to improve user experience. Read more
Save & Close
Accept all
Decline all
Show detailsHide details
Cookie declaration
About cookies
Strictly necessary
Performance
Strictly necessary cookies allow core website functionality such as user login and account management. The website cannot be used properly without strictly necessary cookies.
This cookie is used by Cookie-Script.com service to remember visitor cookie consent preferences. It is necessary for Cookie-Script.com cookie banner to work properly.
Performance cookies are used to see how visitors use the website, eg. analytics cookies. Those cookies cannot be used to directly identify a certain visitor.
Used to store the attribution information, the referrer initially used to visit the website
Cookies are small text files that are placed on your computer by websites that you visit. Websites use cookies to help users navigate efficiently and perform certain functions. Cookies that are required for the website to operate properly are allowed to be set without your permission. All other cookies need to be approved before they can be set in the browser.
You can change your consent to cookie usage at any time on our Privacy Policy page.