Abstract
The high relevance of location problems in the operations research literature arises from their wide spectrum of real applications, including decision optimization in industrial management, logistics, and territorial planning. Most of these optimization problems fall into the class of NP-hard problems, motivating the search for heuristic and approximated algorithms. Currently, a great interest is being devoted to those optimization approaches yielding a concrete integration with spatial analysis instruments (such as Geographical Information Systems) that provide the user with an easy visualization of input data and optimization results.
Agent-Based computing was recently proposed as an alternative to mathematical programming in order to solve problems whose domains are concurrently distributed, complex, and heterogeneous, also thanks to the availability of many commercial and open source codes including graphical interfaces for the elements of the problem.
In this paper we propose a general Agent-Based framework for modeling various location problems. Together with its description, we present some computational results confirming the suitability and the effectiveness of the proposed approach.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Aras N, Ozkisacik KC, Altinell IK (2006) Solving the uncapacitated multi-facility Weber problem by vector quantization and self-organizing maps. J Oper Res Soc 57(1):82–93
Axelrod R (1997) The complexity of cooperation: agent-based models of competition and collaboration. Princeton University Press, Princeton
Berman O, Huang R (2008) The minimum weighted covering location problem with distance constraints. Comput OR 35(2):356–372
Billari FG, Fent T, Prskawetz A, Scheffran J (eds) (2006) Agent-based computational modelling: applications in demography, social, economic and environmental sciences (contributions to economics). Physica-Verlag, Heidelberg
Bocker J, Lind J, Zirkler B (2001) Using a multi-agent approach to optimise the train coupling and sharing system. Eur J Oper Res 134(1):242–252
Bozkaya B, Zhang J, Erkut E (2002) An efficient genetic algorithm for the p-median problem. In: Drezner Z, Hamacher H (eds) Facility location: applications and theory. Springer, Berlin, pp 179–205
Brimberg J, Hansen P, Mladenovic N, Taillard ED (2000) Improvements and comparison of heuristics for solving the multisource Weber problem. Oper Res 48(3):444–460
Brown D, Riolo R, Robinson DT, North M, Rand W (2005) Spatial process and data models: toward integration of agent-based models and GIS. J Geogr Syst 1(7):25–47
Cappanera P, Gallo G, Maffioli F (2003) Discrete facility location and routing of obnoxious activities. Discrete Appl Math 133(1–3):3–28
Cardon A, Galinho T, Vacher JP (2000) Genetic algorithms using multi-objectives in a multi-agent system. Robot Auton Syst 33(2):179–190
Chen P, Hansen P, Jaumard B, Tuy H (1998) Solution of the multisource Weber and conditional Weber problems by DC programming. Oper Res 46(4):548–562
Church RL, ReVelle CS (1974) The maximal covering location problem. Pap Reg Sci Assoc 32(1):101–118
Conte R, Hegselmann R, Terna P (eds) (1997) Simulating social phenomena. Springer, Berlin
Davidsson P, Johansson S, Persson J, Wernstedt F (2003). Combining agent-based approaches and optimization techniques. In: Proceedings of the EUMAS 2005 conference
Desphande S, Cagan J (2004) An agent based optimization approach to manufacturing process planning. ASME J Mech Des 126(1):46–55
Drezner Z (1987) A heuristic procedure for the layout of a large number of facilities. Manag Sci 33(7):907–915
Drezner T, Drezner Z (2007) Equity models in planar location. Comput Manag Sci 4(1):1–16
Drezner Z, Hamacher HW (2002) Facility location: application and theory. Springer, Berlin
Du Merle O, Villeneuve D, Desrosiers J, Hansen P (1999) Stabilized column generation. Discrete Math 194(1):229–237
Eiselt HA, Laporte G (1995) Objectives in locations problems. In: Drezner Z (ed) Facility location: a survey of applications and methods. Springer, Berlin, pp 151–180
Erkut E, Neuman S (1989) Analytical models for locating undesirable facilities. Eur J Oper Res 40(3):275–291
Ferber J (1999) Multi-agent system: an introduction to distributed artificial intelligence. Addison–Wesley, Redwood City
Fernandez A, Alonso E, Ossowski S (2004) A multi-agent service architectures for bus fleet management. Integr Comput-Aided Eng 11(2):101–115
Fotheringham AS, O’Kelly ME (1989) Spatial interaction models: formulation and applications. Kluwer Academic, Dordrecht
Galvao RD, Espejo LGA, Boffey B (2000) A comparison of Lagrangean and surrogate relaxations for the maximal covering location problem. Eur J Oper Res 124(2):377–389
Guo D, Ren B, Wang C (2008) Integrated agent-based modeling with GIS for large scale emergency simulation. In: Lecture notes in computer science, vol 5370. Springer, Berlin, pp 618–625
Hansen P, Mladenovic N, Taillard E (1998) Heuristic solution of the multisource Weber problem as a p-median problem. Oper Res Lett 22(2–3):55–62
Kathib O (1986) Real time obstacle avoidance for manipulators and mobile robots. Int J Robot Res 5(1):90–99
Klose A, Drexl A (2005) Facility location models for distribution system design. Eur J Oper Res 162(1):4–29
Kuenne R, Soland R (1972) Exact and approximate solutions to the multisource Weber problem. Math Program 3(1):193–209
Megiddo N, Supowit KJ (1984) On the complexity of some common geometric location problems. SIAM J Comput 13(1):182–196
Mehrez A (1983) A note on the linear integer formulation of the maximal covering location problem with facility placement on the entire plane. J Reg Sci 23(4):553–555
Mes M, van der Heijden M, van Harten A (2007) Comparison of agent-based scheduling to look-ahead heuristics for real-time transportation problems. Eur J Oper Res 181(1):59–75
Parker DC (2005) Integration of geographic information systems and agent-based models of land use: challenges and prospects. In: Maguire DJ, Batty M, Goodchild M (eds) GIS, spatial analysis and modelling. ESRI Press, Redlands, pp 403–422
Plastria F (1996) Continuous location of attracting and undesirable facilities: a selective overview. Belg J Oper Res Stat Comput Sci 36(1):109–127
Plastria F (2000) New error bounds in continuous minisum location for aggregation at the gravity centre. Stud Locat Anal 14:101–119
Plastria F (2002) Continuous covering location problems. In: Drezner Z, Hamacher HW (eds) Facility location: application and theory. Springer, Berlin, pp 37–80
Righini G, Zaniboni L (2007) A branch-and-price algorithm for the multi-source Weber problem. Int J Oper Res 2(2):188–207
Rosing KE (1992) An optimal method for solving the (generalized) multi-Weber problem. Eur J Oper Res 58(3):414–426
Sen A, Smith TE (1995) Gravity models of spatial interaction behaviour. Springer, Berlin
Serra D, Colomé R (2001) Consumer choice and optimal location models: formulations and heuristics. Pap Reg Sci 80(4):425–438
Weber A (1929) Alfred Weber’s theory of the locations of industries. University of Chicago Press, Chicago
Wei Q, Sawaragi T, Tian Y (2005) Bounded optimization of resources allocation among multiple agents using an organizational decision model. Adv Eng Inf 19(1):67–78
Weiss G (1999) Multiagent systems, a modern approach to distributed artificial intelligence. MIT Press, Cambridge
Wooldridge M (2002) An introduction to multiagent systems. Wiley, New York
Wooldridge M, Jennings N (1995) Intelligent agents: theory and practice. Knowl Eng Rev 10(2):115–152
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Bruno, G., Genovese, A. & Sgalambro, A. An Agent-Based framework for modeling and solving location problems. TOP 18, 81–96 (2010). https://doi.org/10.1007/s11750-009-0116-1
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11750-009-0116-1