Skip to main content

2019 | OriginalPaper | Buchkapitel

Location Assignment of Capacitated Services in Smart Cities

verfasst von : Gerbrich Hoekstra, Frank Phillipson

Erschienen in: Mobile, Secure, and Programmable Networking

Verlag: Springer International Publishing

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

This paper introduces the Multi-Service Capacitated Facility Location Problem for assigning equipment to access points. Here multiple services should be offered to customers in a Smart City context. Purpose is to offer the total of services to fulfil the customer demand, given the coverage of the service and their capacity constraints. The problem is formulated and some practical results are presented solving the problem as an Integer Linear Programming Problem.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Literatur
1.
Zurück zum Zitat Akinc, U., Khumawala, B.: An efficient branch and bound heuristic for the capacitated warehoues location problem. Manage. Sci. 23(6), 585–594 (1977)MATHCrossRef Akinc, U., Khumawala, B.: An efficient branch and bound heuristic for the capacitated warehoues location problem. Manage. Sci. 23(6), 585–594 (1977)MATHCrossRef
2.
Zurück zum Zitat Albino, V., Berardi, U., Dangelico, R.M.: Smart cities: definitions, dimensions, performance, and initiatives. J. Urban Technol. 22(1), 3–21 (2015)CrossRef Albino, V., Berardi, U., Dangelico, R.M.: Smart cities: definitions, dimensions, performance, and initiatives. J. Urban Technol. 22(1), 3–21 (2015)CrossRef
3.
Zurück zum Zitat Balinski, M., Quandt, R.: On an integer program for a delivery problem. Oper. Res. 12, 300–304 (1964)CrossRef Balinski, M., Quandt, R.: On an integer program for a delivery problem. Oper. Res. 12, 300–304 (1964)CrossRef
4.
Zurück zum Zitat Bao, S., Xiao, N., Lai, Z., Zhang, H., Kim, C.: Optimizing watchtower locations for forest fire monitoring using location models. Fire Saf. J. 72, 100–109 (2015)CrossRef Bao, S., Xiao, N., Lai, Z., Zhang, H., Kim, C.: Optimizing watchtower locations for forest fire monitoring using location models. Fire Saf. J. 72, 100–109 (2015)CrossRef
5.
Zurück zum Zitat Barcelo, J., Casanovas, J.: A heuristic lagrangian algorithm for the capacitated plant location problem. Eur. J. Oper. Res. 15, 212–226 (1984)MATHCrossRef Barcelo, J., Casanovas, J.: A heuristic lagrangian algorithm for the capacitated plant location problem. Eur. J. Oper. Res. 15, 212–226 (1984)MATHCrossRef
6.
Zurück zum Zitat Brown, G., Graves, G., Ronen, D.: Scheduling ocean transportation of crude oil. Manage. Sci. 33, 335–346 (1987)CrossRef Brown, G., Graves, G., Ronen, D.: Scheduling ocean transportation of crude oil. Manage. Sci. 33, 335–346 (1987)CrossRef
7.
Zurück zum Zitat Calvillo, C., Sànchez-Miralles, A., Villar, J.: Energy management and planning in smart cities. Renew. Sustain. Energy Rev. 55, 273–287 (2016)CrossRef Calvillo, C., Sànchez-Miralles, A., Villar, J.: Energy management and planning in smart cities. Renew. Sustain. Energy Rev. 55, 273–287 (2016)CrossRef
8.
Zurück zum Zitat Canel, C., Khumawala, B., Law, J., Loh, A.: An algorithm for the capacitated, multi-commodity, multi-period facility location problem. Comput. Oper. Res. 28, 411–427 (2001)MathSciNetMATHCrossRef Canel, C., Khumawala, B., Law, J., Loh, A.: An algorithm for the capacitated, multi-commodity, multi-period facility location problem. Comput. Oper. Res. 28, 411–427 (2001)MathSciNetMATHCrossRef
9.
10.
Zurück zum Zitat Cornuéjols, G., Nemhauser, G., Wolsey, L.: The uncapacitated facility location problem. In: Mirchandani, P., Francis, R. (eds.) Discrete location Theory, pp. 119–171. Wiley, New York (1990) Cornuéjols, G., Nemhauser, G., Wolsey, L.: The uncapacitated facility location problem. In: Mirchandani, P., Francis, R. (eds.) Discrete location Theory, pp. 119–171. Wiley, New York (1990)
11.
Zurück zum Zitat Desrochers, M., Soumis, F.: A column generation approach to the urban transit crew scheduling problem. Transp. Sci. 23, 1–13 (1989)MATHCrossRef Desrochers, M., Soumis, F.: A column generation approach to the urban transit crew scheduling problem. Transp. Sci. 23, 1–13 (1989)MATHCrossRef
12.
Zurück zum Zitat Farahani, R., Asgari, N., Heidari, N.: Covering problems in facility location: a review. Comput. Ind. Eng. 62(1), 368–407 (2012)CrossRef Farahani, R., Asgari, N., Heidari, N.: Covering problems in facility location: a review. Comput. Ind. Eng. 62(1), 368–407 (2012)CrossRef
13.
Zurück zum Zitat Feldman, E., Lehrer, F., Ray, T.: Warehouse location under continuous economies of scale. Manage. Sci. 12, 670–684 (1966)CrossRef Feldman, E., Lehrer, F., Ray, T.: Warehouse location under continuous economies of scale. Manage. Sci. 12, 670–684 (1966)CrossRef
14.
Zurück zum Zitat Filippini, I., Cesana, M.: Topology optimization for hybrid optical/wireless access networks. Ad Hoc Netw. 8, 614–625 (2010)CrossRef Filippini, I., Cesana, M.: Topology optimization for hybrid optical/wireless access networks. Ad Hoc Netw. 8, 614–625 (2010)CrossRef
15.
Zurück zum Zitat Fisher, M., Rosenwein, M.: An interactive optimisation system for bulk-cargo ship scheduling. Nav. Res. Logist. 36, 27–42 (1989)CrossRef Fisher, M., Rosenwein, M.: An interactive optimisation system for bulk-cargo ship scheduling. Nav. Res. Logist. 36, 27–42 (1989)CrossRef
16.
Zurück zum Zitat Fisk, J.: A solution procedure for a special type of capacitated warehouse location problem. Logist. Transp. Rev. 13, 305–320 (1978) Fisk, J.: A solution procedure for a special type of capacitated warehouse location problem. Logist. Transp. Rev. 13, 305–320 (1978)
17.
18.
Zurück zum Zitat Gandhi, R., Khuller, S., Srinivasan, A.: Approximation algorithms for partial covering problems. J. Algorithms 53(1), 55–84 (2004)MathSciNetMATHCrossRef Gandhi, R., Khuller, S., Srinivasan, A.: Approximation algorithms for partial covering problems. J. Algorithms 53(1), 55–84 (2004)MathSciNetMATHCrossRef
19.
Zurück zum Zitat Garey, M.R., Johnson, D.S.: Computers and intractability: a guide to the theory of NP completeness. Comput. Intractability (1979) Garey, M.R., Johnson, D.S.: Computers and intractability: a guide to the theory of NP completeness. Comput. Intractability (1979)
20.
Zurück zum Zitat Geoffrion, A., Graves, G.: Mutlicommodity distribution system design by benders decomposition. Manage. Sci. 20(5), 822–844 (1974)MATHCrossRef Geoffrion, A., Graves, G.: Mutlicommodity distribution system design by benders decomposition. Manage. Sci. 20(5), 822–844 (1974)MATHCrossRef
21.
Zurück zum Zitat Georgakopoulos, D., Jayaraman, P.P.: Internet of things: from internet scale sensing to smart services. Computing 98(10), 1041–1058 (2016)MathSciNetCrossRef Georgakopoulos, D., Jayaraman, P.P.: Internet of things: from internet scale sensing to smart services. Computing 98(10), 1041–1058 (2016)MathSciNetCrossRef
22.
Zurück zum Zitat Guastaroba, G., Speranza, M.: A heuristic for BILP problems: the single source capacitated facility location problem. Eur. J. Oper. Res. 238, 438–450 (2014)MathSciNetMATHCrossRef Guastaroba, G., Speranza, M.: A heuristic for BILP problems: the single source capacitated facility location problem. Eur. J. Oper. Res. 238, 438–450 (2014)MathSciNetMATHCrossRef
23.
Zurück zum Zitat Hinojosa, Y., Puerto, J., Fernández, F.: A multiperiod two-echelon multicommodity capacitated plant location problem. Eur. J. Oper. Res. 123, 271–291 (2000)MathSciNetMATHCrossRef Hinojosa, Y., Puerto, J., Fernández, F.: A multiperiod two-echelon multicommodity capacitated plant location problem. Eur. J. Oper. Res. 123, 271–291 (2000)MathSciNetMATHCrossRef
24.
Zurück zum Zitat Jacobsen, S.: Heuristics for the capacitated plant location model. Eur. J. Oper. Res. 12, 253–261 (1983)MATHCrossRef Jacobsen, S.: Heuristics for the capacitated plant location model. Eur. J. Oper. Res. 12, 253–261 (1983)MATHCrossRef
25.
Zurück zum Zitat Klincewicz, J., Luss, H.: A lagrangian relaxation heuristic for capacitated facility location with single source constraints. J. Oper. Res. Soc. 37, 495–500 (1986)MATHCrossRef Klincewicz, J., Luss, H.: A lagrangian relaxation heuristic for capacitated facility location with single source constraints. J. Oper. Res. Soc. 37, 495–500 (1986)MATHCrossRef
26.
Zurück zum Zitat Klose, A., Görtz, S.: A branch-and-price algorithm for the capacitated facility location problem. Eur. J. Oper. Res. 179(3), 1109–1125 (2007)MATHCrossRef Klose, A., Görtz, S.: A branch-and-price algorithm for the capacitated facility location problem. Eur. J. Oper. Res. 179(3), 1109–1125 (2007)MATHCrossRef
27.
28.
Zurück zum Zitat Kuehn, A., Hambuger, B.: A heuristic program for locating warehouses. Manage. Sci. 9, 643–666 (1963)CrossRef Kuehn, A., Hambuger, B.: A heuristic program for locating warehouses. Manage. Sci. 9, 643–666 (1963)CrossRef
29.
Zurück zum Zitat Li, J., Chu, F., Prins, C.: Lower and upper bounds for a capacitated plant location problem with multicommodity flow. Comput. Oper. Res. 36, 3019–3030 (2009)MathSciNetMATHCrossRef Li, J., Chu, F., Prins, C.: Lower and upper bounds for a capacitated plant location problem with multicommodity flow. Comput. Oper. Res. 36, 3019–3030 (2009)MathSciNetMATHCrossRef
30.
Zurück zum Zitat Li, J., Chu, F., Prins, C., Zhu, Z.: Lower and upper bounds for a two-stage capacitated facility location problem with handling costs. Eur. J. Oper. Res. 236, 957–967 (2014)MathSciNetMATHCrossRef Li, J., Chu, F., Prins, C., Zhu, Z.: Lower and upper bounds for a two-stage capacitated facility location problem with handling costs. Eur. J. Oper. Res. 236, 957–967 (2014)MathSciNetMATHCrossRef
31.
Zurück zum Zitat Magnanti, T., Wong, R.: Decomposition methods for facility location problems. In: Mirchandani, P., Francis, R. (eds.) Discrete Location Theory, pp. 209–262. Wiley, New York (1990) Magnanti, T., Wong, R.: Decomposition methods for facility location problems. In: Mirchandani, P., Francis, R. (eds.) Discrete Location Theory, pp. 209–262. Wiley, New York (1990)
32.
Zurück zum Zitat Mahdian, M., Ye, Y., Zhang, J.: Approximation algorithms for metric facility location problems. SIAM J. Comput. 36(2), 411–432 (2003)MathSciNetMATHCrossRef Mahdian, M., Ye, Y., Zhang, J.: Approximation algorithms for metric facility location problems. SIAM J. Comput. 36(2), 411–432 (2003)MathSciNetMATHCrossRef
33.
Zurück zum Zitat Melo, M., Nickel, S., Saldanha da Gama, F.: Dynamic multi-commodity capacitated facility location: a mathematical modeling framework for strategic supply chain planning. Comput. Oper. Res. 33, 181–208 (2005)MATHCrossRef Melo, M., Nickel, S., Saldanha da Gama, F.: Dynamic multi-commodity capacitated facility location: a mathematical modeling framework for strategic supply chain planning. Comput. Oper. Res. 33, 181–208 (2005)MATHCrossRef
34.
Zurück zum Zitat Murray, A., Feng, X.: Public street lighting service standard assessment and achievement. Socio-Econ. Plan. Sci. 53, 14–22 (2016)CrossRef Murray, A., Feng, X.: Public street lighting service standard assessment and achievement. Socio-Econ. Plan. Sci. 53, 14–22 (2016)CrossRef
35.
36.
Zurück zum Zitat Peralta, A., Inga, E.: Hincapié: optimal scalability of fiwi networks based on multistage stochastic programming and policies. Opt. Soc. Am. 9(12), 1172–1183 (2017) Peralta, A., Inga, E.: Hincapié: optimal scalability of fiwi networks based on multistage stochastic programming and policies. Opt. Soc. Am. 9(12), 1172–1183 (2017)
37.
Zurück zum Zitat Pirkul, H.: Efficient algorithm for the capacitated concentrator location problem. Comput. Oper. Res. 14, 197–208 (1987)MATHCrossRef Pirkul, H.: Efficient algorithm for the capacitated concentrator location problem. Comput. Oper. Res. 14, 197–208 (1987)MATHCrossRef
38.
Zurück zum Zitat Pirkul, H., Jayaraman, V.: A multi-commodity, multi-plant, capacitated facility location problem: formulation and efficient heuristic solution. Manage. Sci. 25, 869–878 (1998)MathSciNetMATH Pirkul, H., Jayaraman, V.: A multi-commodity, multi-plant, capacitated facility location problem: formulation and efficient heuristic solution. Manage. Sci. 25, 869–878 (1998)MathSciNetMATH
39.
Zurück zum Zitat Rathore, M.M., Ahmad, A., Paul, A., Rho, S.: Urban planning and buidling smart cities based on the internet of things using big data analytics. Comput. Netw. 101, 63–80 (2016)CrossRef Rathore, M.M., Ahmad, A., Paul, A., Rho, S.: Urban planning and buidling smart cities based on the internet of things using big data analytics. Comput. Netw. 101, 63–80 (2016)CrossRef
40.
Zurück zum Zitat Rathore, M.M., Paul, A., Ahmad, A., Chilamkurthi, N., Hong, W.-W., Seo, H.: Real-time secure communication for smart city in high-speed big data environment. Futur. Gener. Comput. Syst. 83, 638–652 (2017)CrossRef Rathore, M.M., Paul, A., Ahmad, A., Chilamkurthi, N., Hong, W.-W., Seo, H.: Real-time secure communication for smart city in high-speed big data environment. Futur. Gener. Comput. Syst. 83, 638–652 (2017)CrossRef
41.
Zurück zum Zitat Rönnqvist, M., Tragantalerngsak, S., Holt, J.: A repeated matching heuristic for the single-source capacitated facility location problem. Eur. J. Oper. Res. 116, 51–68 (1999)MATHCrossRef Rönnqvist, M., Tragantalerngsak, S., Holt, J.: A repeated matching heuristic for the single-source capacitated facility location problem. Eur. J. Oper. Res. 116, 51–68 (1999)MATHCrossRef
42.
43.
Zurück zum Zitat Sarkar, S., Yen, H.H., Dixit, S., Mukherjee, B.: Hybrid wireless-optical broadband access network (WOBAN): network planning and setup. IEEE J. Sel. Areas Commun. 26(6), 12–21 (2008)CrossRef Sarkar, S., Yen, H.H., Dixit, S., Mukherjee, B.: Hybrid wireless-optical broadband access network (WOBAN): network planning and setup. IEEE J. Sel. Areas Commun. 26(6), 12–21 (2008)CrossRef
44.
Zurück zum Zitat Schilling, D., Jayaraman, V., Barkhi, R.: A review of covering problems in facility location. Locat. Sci. 1(1), 25–55 (1993)MATH Schilling, D., Jayaraman, V., Barkhi, R.: A review of covering problems in facility location. Locat. Sci. 1(1), 25–55 (1993)MATH
45.
Zurück zum Zitat Schreuder, J.: Application of a location model to fire stations in Rotterdam. Eur. J. Oper. Res. 6, 212–219 (1981)CrossRef Schreuder, J.: Application of a location model to fire stations in Rotterdam. Eur. J. Oper. Res. 6, 212–219 (1981)CrossRef
46.
Zurück zum Zitat Sridharan, R.: The capacitated plant location problem. Eur. J. Oper. Res. 87(2), 203–213 (1995)MATHCrossRef Sridharan, R.: The capacitated plant location problem. Eur. J. Oper. Res. 87(2), 203–213 (1995)MATHCrossRef
47.
Zurück zum Zitat Toregas, C., Swain, R., Revelle, C., Bergman, L.: The location of emergency service facilities. Oper. Res. 19, 1363–1373 (1971)MATHCrossRef Toregas, C., Swain, R., Revelle, C., Bergman, L.: The location of emergency service facilities. Oper. Res. 19, 1363–1373 (1971)MATHCrossRef
48.
Zurück zum Zitat Verhoek, M.: Optimising the placement of access points for smart city services with stochastic demand. Master’s thesis (2017) Verhoek, M.: Optimising the placement of access points for smart city services with stochastic demand. Master’s thesis (2017)
49.
Zurück zum Zitat Vos, T., Phillipson, F.: Dense multi-service planning in smart cities. In: International Conference on Information Society and Smart Cities (2018) Vos, T., Phillipson, F.: Dense multi-service planning in smart cities. In: International Conference on Information Society and Smart Cities (2018)
50.
Zurück zum Zitat Vos, T.: Using lamppost to provide urban areas with multiple services. Master’s thesis (2016) Vos, T.: Using lamppost to provide urban areas with multiple services. Master’s thesis (2016)
51.
Zurück zum Zitat Warszawski, A.: Multi-dimensional location problems. Oper. Res. Q. 24, 165–179 (1973)MATHCrossRef Warszawski, A.: Multi-dimensional location problems. Oper. Res. Q. 24, 165–179 (1973)MATHCrossRef
52.
Zurück zum Zitat Warszawski, A., Peer, S.: Optimizing the location of facilities on a building site. Oper. Res. Q. 24, 35–44 (1973)CrossRef Warszawski, A., Peer, S.: Optimizing the location of facilities on a building site. Oper. Res. Q. 24, 35–44 (1973)CrossRef
53.
Zurück zum Zitat Wentges, P.: Accelerating Benders’ decomposition for the capacitated facility location problem. Math. Methods Oper. Res. 44(2), 267–290 (1996)MathSciNetMATHCrossRef Wentges, P.: Accelerating Benders’ decomposition for the capacitated facility location problem. Math. Methods Oper. Res. 44(2), 267–290 (1996)MathSciNetMATHCrossRef
Metadaten
Titel
Location Assignment of Capacitated Services in Smart Cities
verfasst von
Gerbrich Hoekstra
Frank Phillipson
Copyright-Jahr
2019
DOI
https://doi.org/10.1007/978-3-030-03101-5_17