An efficient distributed optimization and coordination protocol: Application to the emergency vehicle management

Previous Article
Convergence analysis of a nonlinear Lagrangian method for nonconvex semidefinite programming with subproblem inexactly solved
JIMO Home
This Issue
Next Article
Stochastic maximum principle for non-zero sum differential games of FBSDEs with impulse controls and its application to finance

January 2015, 11(1): 41-63. doi: 10.3934/jimo.2015.11.41

An efficient distributed optimization and coordination protocol: Application to the emergency vehicle management

1.	Computer Science Department, Sciences Faculty, Hassiba Benbouali University, BP 151 Chlef 02000, Algeria

Received December 2012 Revised January 2014 Published May 2014

Abstract
Related Papers

In this paper we deal with the distributed optimization of problems where the objective/constraints are related to the whole variables of the system. In this kind of problems we need to bring into play all the distributed agents of the system simultaneously to guarantee that the solution is feasible and of a good quality. We propose an efficient agents coordination protocol which avoids centralizing control and computation to one agent. It overcomes the shortcoming of tree search methods related to the agents order and accelerates the search process. The proposed protocol is applied to the distributed emergency vehicle management problem that consists in taking, in a distributed way, the decisions about the locations of a set of emergency vehicles in order to solve the dispatching and covering issues simultaneously. The protocol is compared to the Synchronous Limited Discrepancy Search method. It is also compared to other distributed and centralized methods. The obtained results showed the efficiency of the proposed protocol in finding good solutions in short times and its capacity to lessen the effect of the agents ordering on the solution quality.

Keywords: emergency vehicles management, multi-agent coordination., Distributed optimization.

Mathematics Subject Classification: Primary: 58F15, 58F17; Secondary: 53C3.

Citation: Sarah Ibri. An efficient distributed optimization and coordination protocol: Application to the emergency vehicle management. Journal of Industrial and Management Optimization, 2015, 11 (1) : 41-63. doi: 10.3934/jimo.2015.11.41

References:

[1]	T. Andersson and P. Varbrand, Decision support tools for ambulance dispatch and relocation, Journal of the Operational Research Society, 58 (2007), 195-201.
[2]	R. Batta, J. M. Dolan and N. N. Krishnamorthy, The maximal expected covering location problem: Revisited, Transportation Science, 23 (1989), 277-287. doi: 10.1287/trsc.23.4.277.
[3]	R. Bejar, C.Domshlakb, C. Fernandeza, C. Gomesb, B. Krishnamacharic, B. Selmanb and M. Vallsd, Sensor networks and distributed CSP: Communication, computation and complexity, Artificial Intelligence, 161 (2005), 117-147. doi: 10.1016/j.artint.2004.09.002.
[4]	A. B. Arabani and R. Z. Farahani, Facility location dynamics: An overview of classifications and applications, Computers and industrial engineering, 62 (2012), 408-420.
[5]	E. Bowring, M. Tambei and M. Yokoo, Multiply-constrained distributed constraint optimization, The $5^{th}$ International Joint Conference on Autonomous Agents and Multiagent Systems, (2006), 1413-1420.
[6]	R. Church and C. R. Velle, The maximal covering location problem, Regional Science, 32 (1974), 101-118.
[7]	M. S. Daskin, Maximum expected covering model: Formulation, properties and heuristic solution, Transportation Science, 17 (1984), 48-70.
[8]	A. Farinelli, A. Rogers, A. Pectu and N. R. Jennings, Decentralized coordination of low power embedded devices using the max sum algorithm, The $7^{th}$ International Conference on Autonomous Agents and Multiagent Systems, (2008), 639-646.
[9]	J. Gaudreault , J. M. Frayret and G. Pesant, Distributed Search for Supply Chain Coordination, Computers in Industry, 60 (2009), 441-451.
[10]	J. Gaudreault, Algorithmes Pour la Prise de Decision Distribuee en Contexte Hierarchique Ph.D thesis, Universite Laval, 2009.
[11]	M. Gendreau, G. Laporte and F. Semet, A dynamic model and parallel tabu search heuristic for real time ambulance relocation, Parallel Computing, 27 (2001), 1641-1653.
[12]	M. Gendreau, G. Laporte and F. Semet, The Maximal expected coverage relocation problem for emergency vehicles, Journal of Operational Research Society, 57 (2006), 22-28.
[13]	A. Grubshtein, R. Zivan, T. Grinshpoun and A. Meisels, Local search for distributed asymmetric optimization, The $9^{th}$ International Conference on Autonomous Agents and Multiagent Systems, (2010), 1015-1022.
[14]	A. Haghani, H. Hu and Q. Tian, An Optimization Model for Real-Time Emergency Vehicle Dispatching and Routing, The $82^{nd}$ annual meeting of the Transportation Research Board, 2003.
[15]	A. Haghani and S.Yang, Real time emergency response fleet deployment concepts, systems, simulation and case studies, Dynamic fleet management, 57 (2007), 133-162.
[16]	W. D. Harvey and M. L. Ginsberg, Limited Discrepancy search, the $14^{th}$ International joint conference on Artificial intelligence, (1995), 607-613.
[17]	K. Hirayama and M. Yokoo, The distributed breakout algorithms, Artificial Intelligence - Special issue: Distributed constraint satisfaction, 161 (2005), 89-115. doi: 10.1016/j.artint.2004.08.004.
[18]	S. Ibri, H. Drias and M. Nourelfath, A parallel hybrid ant-tabu algorithm for integrated emergency vehicle dispatching and covering problem, International Journal of Innovative Computing and Applications, 2 (2010), 226-236.
[19]	S. Ibri, M. Nourelfath and H. Drias, A multi-agent approach for the integrated emergency vehicle allocation and covering problem, Engineering Applications of Artificial Intelligence, 25 (2012), 554-565.
[20]	P. Kolesar and W. E. Walker, An algorithm for the dynamic relocation of fire companies, Operations Research, 22 (1974), 249-274.
[21]	B. Lopez, B. Innocenti, S. Aciar and L. Cuevas, A multi-agent system to support ambulance coordination in time-critical patient treatment, $7^{th}$ Symposio Argentino de Inteligencia Artificial, ASAI, 22 (2005), 43-54.
[22]	B. Lopez, B. Innocenti and D. Busquets, A multiagent system for coordinating ambulances for emergency medical services, Intelligent Systems, IEEE, 23 (2008), 50-57.
[23]	R. T. Maheswaran, J. P. Pearce and M. Tambe, Distributed algorithms for DCOP: A graphical-game-based approach, The $17^{th}$ International Conference on Parallel and Distributed Computing Systems, (2004), 432-439.
[24]	R. Mailler and V. Lesser, Solving distributed constraint optimization problems using cooperative mediation, The $3^{th}$ International Joint Conference on Autonomous Agents and Multiagent Systems, (2004), 438-445.
[25]	P. J. Modi, Distributed Constraint Optimization for Multi-agent Systems, Ph.D thesis, University of Southern California, 2003.
[26]	P. J. Modi, W. M. Shen, M. Tambe and M. Yokoo, ADOPT: Asynchronous distributed constraint optimization with quality guarantees, Artificial Intelligence Journal, 161 (2005), 149-180. doi: 10.1016/j.artint.2004.09.003.
[27]	A. Petcu and B. Faltings, A Scalable Method for Multiagent Constraint Optimization, The $19^{th}$ International Joint Conference on Artificial Intelligence, 2005.
[28]	J. F. Repede and J. J. Bernardo, Developing and validating a decision support system for locating emergency medical vehicles in Louisville, Kentucky, European Journal of Operational Research, 75 (1994), 567-581. doi: 10.1016/0377-2217(94)90297-6.
[29]	C. ReVelle and K. Hogan, The maximum availability location problem, Transportation Science, 23 (1989), 192-200. doi: 10.1287/trsc.23.3.192.
[30]	A. Rogers, A. Farenelli, R. Stranders and N. R. Jennings, Bounded approximate decentralised coordination via the max-sum algorithm, Artificial Intelligence, 175 (2011), 730-759. doi: 10.1016/j.artint.2010.11.001.
[31]	D. A. Schilling, D. J. Elzinga, J. Cohon, R. L. Church and C. S. ReVelle, The TEAM/FLEET models for simultaneous facility and equipment siting, Transportation Science, 13 (1979), 163-175.
[32]	V. Schmid, Solving the dynamic ambulance relocation and dispatching problem using approximate dynamic programming, European journal of operational research, 219 (2012), 611-621. doi: 10.1016/j.ejor.2011.10.043.
[33]	R. Standers, A. Farenelli, A. Rogers and N. R. Jennings, Decentralised coordination of continuously valued control parameters using the max sum algorithm, The $8^{th}$ International Conference on Autonomous Agents and Multiagent Systems, (2009), 601-608.
[34]	C. R. Toregas, R. S. Wain, C. S. ReVelle and L. Bergman, The location of emergency service facilities, Operations Research, 19 (1971), 1363-1373.
[35]	M. Yokoo, E. H. Durfee, T. Ishida and K. Kuwabara, The distributed constraint satisfaction problem: Formalization and algorithms, IEEE Transactions on Knowledge and Data Engineering, 10 (1998), 673-685. doi: 10.1109/69.729707.
[36]	R. Zanjirani Farahani, N. Asgari, N. Heidari, M. Hosseininia and M. Goh, Covering problems in facility location: A review, Computers and industrial engineering, 62 (2012), 368-407. doi: 10.1016/j.cie.2011.08.020.
[37]	W. Zhang, G. Wang, Z. Xing and L. Wittenburg, Distributed stochastic algorithm and distributed breakout algorithm: Properties, comparison and applications to COP sensor networks, Artificial intelligence, 161 (2005), 55-87. doi: 10.1016/j.artint.2004.10.004.
[38]	R. Zivan, Anytime local search for distributed constraint optimization, The $5^{th}$ International Joint Conference on Autonomous Agents and Multiagent Systems, (2008), 1449-1452.

show all references

References:

[1]	T. Andersson and P. Varbrand, Decision support tools for ambulance dispatch and relocation, Journal of the Operational Research Society, 58 (2007), 195-201.
[2]	R. Batta, J. M. Dolan and N. N. Krishnamorthy, The maximal expected covering location problem: Revisited, Transportation Science, 23 (1989), 277-287. doi: 10.1287/trsc.23.4.277.
[3]	R. Bejar, C.Domshlakb, C. Fernandeza, C. Gomesb, B. Krishnamacharic, B. Selmanb and M. Vallsd, Sensor networks and distributed CSP: Communication, computation and complexity, Artificial Intelligence, 161 (2005), 117-147. doi: 10.1016/j.artint.2004.09.002.
[4]	A. B. Arabani and R. Z. Farahani, Facility location dynamics: An overview of classifications and applications, Computers and industrial engineering, 62 (2012), 408-420.
[5]	E. Bowring, M. Tambei and M. Yokoo, Multiply-constrained distributed constraint optimization, The $5^{th}$ International Joint Conference on Autonomous Agents and Multiagent Systems, (2006), 1413-1420.
[6]	R. Church and C. R. Velle, The maximal covering location problem, Regional Science, 32 (1974), 101-118.
[7]	M. S. Daskin, Maximum expected covering model: Formulation, properties and heuristic solution, Transportation Science, 17 (1984), 48-70.
[8]	A. Farinelli, A. Rogers, A. Pectu and N. R. Jennings, Decentralized coordination of low power embedded devices using the max sum algorithm, The $7^{th}$ International Conference on Autonomous Agents and Multiagent Systems, (2008), 639-646.
[9]	J. Gaudreault , J. M. Frayret and G. Pesant, Distributed Search for Supply Chain Coordination, Computers in Industry, 60 (2009), 441-451.
[10]	J. Gaudreault, Algorithmes Pour la Prise de Decision Distribuee en Contexte Hierarchique Ph.D thesis, Universite Laval, 2009.
[11]	M. Gendreau, G. Laporte and F. Semet, A dynamic model and parallel tabu search heuristic for real time ambulance relocation, Parallel Computing, 27 (2001), 1641-1653.
[12]	M. Gendreau, G. Laporte and F. Semet, The Maximal expected coverage relocation problem for emergency vehicles, Journal of Operational Research Society, 57 (2006), 22-28.
[13]	A. Grubshtein, R. Zivan, T. Grinshpoun and A. Meisels, Local search for distributed asymmetric optimization, The $9^{th}$ International Conference on Autonomous Agents and Multiagent Systems, (2010), 1015-1022.
[14]	A. Haghani, H. Hu and Q. Tian, An Optimization Model for Real-Time Emergency Vehicle Dispatching and Routing, The $82^{nd}$ annual meeting of the Transportation Research Board, 2003.
[15]	A. Haghani and S.Yang, Real time emergency response fleet deployment concepts, systems, simulation and case studies, Dynamic fleet management, 57 (2007), 133-162.
[16]	W. D. Harvey and M. L. Ginsberg, Limited Discrepancy search, the $14^{th}$ International joint conference on Artificial intelligence, (1995), 607-613.
[17]	K. Hirayama and M. Yokoo, The distributed breakout algorithms, Artificial Intelligence - Special issue: Distributed constraint satisfaction, 161 (2005), 89-115. doi: 10.1016/j.artint.2004.08.004.
[18]	S. Ibri, H. Drias and M. Nourelfath, A parallel hybrid ant-tabu algorithm for integrated emergency vehicle dispatching and covering problem, International Journal of Innovative Computing and Applications, 2 (2010), 226-236.
[19]	S. Ibri, M. Nourelfath and H. Drias, A multi-agent approach for the integrated emergency vehicle allocation and covering problem, Engineering Applications of Artificial Intelligence, 25 (2012), 554-565.
[20]	P. Kolesar and W. E. Walker, An algorithm for the dynamic relocation of fire companies, Operations Research, 22 (1974), 249-274.
[21]	B. Lopez, B. Innocenti, S. Aciar and L. Cuevas, A multi-agent system to support ambulance coordination in time-critical patient treatment, $7^{th}$ Symposio Argentino de Inteligencia Artificial, ASAI, 22 (2005), 43-54.
[22]	B. Lopez, B. Innocenti and D. Busquets, A multiagent system for coordinating ambulances for emergency medical services, Intelligent Systems, IEEE, 23 (2008), 50-57.
[23]	R. T. Maheswaran, J. P. Pearce and M. Tambe, Distributed algorithms for DCOP: A graphical-game-based approach, The $17^{th}$ International Conference on Parallel and Distributed Computing Systems, (2004), 432-439.
[24]	R. Mailler and V. Lesser, Solving distributed constraint optimization problems using cooperative mediation, The $3^{th}$ International Joint Conference on Autonomous Agents and Multiagent Systems, (2004), 438-445.
[25]	P. J. Modi, Distributed Constraint Optimization for Multi-agent Systems, Ph.D thesis, University of Southern California, 2003.
[26]	P. J. Modi, W. M. Shen, M. Tambe and M. Yokoo, ADOPT: Asynchronous distributed constraint optimization with quality guarantees, Artificial Intelligence Journal, 161 (2005), 149-180. doi: 10.1016/j.artint.2004.09.003.
[27]	A. Petcu and B. Faltings, A Scalable Method for Multiagent Constraint Optimization, The $19^{th}$ International Joint Conference on Artificial Intelligence, 2005.
[28]	J. F. Repede and J. J. Bernardo, Developing and validating a decision support system for locating emergency medical vehicles in Louisville, Kentucky, European Journal of Operational Research, 75 (1994), 567-581. doi: 10.1016/0377-2217(94)90297-6.
[29]	C. ReVelle and K. Hogan, The maximum availability location problem, Transportation Science, 23 (1989), 192-200. doi: 10.1287/trsc.23.3.192.
[30]	A. Rogers, A. Farenelli, R. Stranders and N. R. Jennings, Bounded approximate decentralised coordination via the max-sum algorithm, Artificial Intelligence, 175 (2011), 730-759. doi: 10.1016/j.artint.2010.11.001.
[31]	D. A. Schilling, D. J. Elzinga, J. Cohon, R. L. Church and C. S. ReVelle, The TEAM/FLEET models for simultaneous facility and equipment siting, Transportation Science, 13 (1979), 163-175.
[32]	V. Schmid, Solving the dynamic ambulance relocation and dispatching problem using approximate dynamic programming, European journal of operational research, 219 (2012), 611-621. doi: 10.1016/j.ejor.2011.10.043.
[33]	R. Standers, A. Farenelli, A. Rogers and N. R. Jennings, Decentralised coordination of continuously valued control parameters using the max sum algorithm, The $8^{th}$ International Conference on Autonomous Agents and Multiagent Systems, (2009), 601-608.
[34]	C. R. Toregas, R. S. Wain, C. S. ReVelle and L. Bergman, The location of emergency service facilities, Operations Research, 19 (1971), 1363-1373.
[35]	M. Yokoo, E. H. Durfee, T. Ishida and K. Kuwabara, The distributed constraint satisfaction problem: Formalization and algorithms, IEEE Transactions on Knowledge and Data Engineering, 10 (1998), 673-685. doi: 10.1109/69.729707.
[36]	R. Zanjirani Farahani, N. Asgari, N. Heidari, M. Hosseininia and M. Goh, Covering problems in facility location: A review, Computers and industrial engineering, 62 (2012), 368-407. doi: 10.1016/j.cie.2011.08.020.
[37]	W. Zhang, G. Wang, Z. Xing and L. Wittenburg, Distributed stochastic algorithm and distributed breakout algorithm: Properties, comparison and applications to COP sensor networks, Artificial intelligence, 161 (2005), 55-87. doi: 10.1016/j.artint.2004.10.004.
[38]	R. Zivan, Anytime local search for distributed constraint optimization, The $5^{th}$ International Joint Conference on Autonomous Agents and Multiagent Systems, (2008), 1449-1452.

[1]	Zhiyong Sun, Toshiharu Sugie. Identification of Hessian matrix in distributed gradient-based multi-agent coordination control systems. Numerical Algebra, Control and Optimization, 2019, 9 (3) : 297-318. doi: 10.3934/naco.2019020
[2]	Zhongqiang Wu, Zongkui Xie. A multi-objective lion swarm optimization based on multi-agent. Journal of Industrial and Management Optimization, 2022 doi: 10.3934/jimo.2022001
[3]	Richard Carney, Monique Chyba, Chris Gray, George Wilkens, Corey Shanbrom. Multi-agent systems for quadcopters. Journal of Geometric Mechanics, 2022, 14 (1) : 1-28. doi: 10.3934/jgm.2021005
[4]	Ke Yang, Wencheng Zou, Zhengrong Xiang, Ronghao Wang. Fully distributed consensus for higher-order nonlinear multi-agent systems with unmatched disturbances. Discrete and Continuous Dynamical Systems - S, 2021, 14 (4) : 1535-1551. doi: 10.3934/dcdss.2020396
[5]	Giulia Cavagnari, Antonio Marigonda, Benedetto Piccoli. Optimal synchronization problem for a multi-agent system. Networks and Heterogeneous Media, 2017, 12 (2) : 277-295. doi: 10.3934/nhm.2017012
[6]	Seung-Yeal Ha, Dohyun Kim, Jaeseung Lee, Se Eun Noh. Emergent dynamics of an orientation flocking model for multi-agent system. Discrete and Continuous Dynamical Systems, 2020, 40 (4) : 2037-2060. doi: 10.3934/dcds.2020105
[7]	Nadia Loy, Andrea Tosin. Boltzmann-type equations for multi-agent systems with label switching. Kinetic and Related Models, 2021, 14 (5) : 867-894. doi: 10.3934/krm.2021027
[8]	Mei Luo, Jinrong Wang, Yumei Liao. Bounded consensus of double-integrator stochastic multi-agent systems. Discrete and Continuous Dynamical Systems - S, 2022 doi: 10.3934/dcdss.2022088
[9]	Brendan Pass. Multi-marginal optimal transport and multi-agent matching problems: Uniqueness and structure of solutions. Discrete and Continuous Dynamical Systems, 2014, 34 (4) : 1623-1639. doi: 10.3934/dcds.2014.34.1623
[10]	Zhong Wan, Jingjing Liu, Jing Zhang. Nonlinear optimization to management problems of end-of-life vehicles with environmental protection awareness and damaged/aging degrees. Journal of Industrial and Management Optimization, 2020, 16 (5) : 2117-2139. doi: 10.3934/jimo.2019046
[11]	Rui Li, Yingjing Shi. Finite-time optimal consensus control for second-order multi-agent systems. Journal of Industrial and Management Optimization, 2014, 10 (3) : 929-943. doi: 10.3934/jimo.2014.10.929
[12]	Tyrone E. Duncan. Some partially observed multi-agent linear exponential quadratic stochastic differential games. Evolution Equations and Control Theory, 2018, 7 (4) : 587-597. doi: 10.3934/eect.2018028
[13]	Xi Zhu, Meixia Li, Chunfa Li. Consensus in discrete-time multi-agent systems with uncertain topologies and random delays governed by a Markov chain. Discrete and Continuous Dynamical Systems - B, 2020, 25 (12) : 4535-4551. doi: 10.3934/dcdsb.2020111
[14]	Zhongkui Li, Zhisheng Duan, Guanrong Chen. Consensus of discrete-time linear multi-agent systems with observer-type protocols. Discrete and Continuous Dynamical Systems - B, 2011, 16 (2) : 489-505. doi: 10.3934/dcdsb.2011.16.489
[15]	Yibo Zhang, Jinfeng Gao, Jia Ren, Huijiao Wang. A type of new consensus protocol for two-dimension multi-agent systems. Numerical Algebra, Control and Optimization, 2017, 7 (3) : 345-357. doi: 10.3934/naco.2017022
[16]	Hongru Ren, Shubo Li, Changxin Lu. Event-triggered adaptive fault-tolerant control for multi-agent systems with unknown disturbances. Discrete and Continuous Dynamical Systems - S, 2021, 14 (4) : 1395-1414. doi: 10.3934/dcdss.2020379
[17]	Hong Man, Yibin Yu, Yuebang He, Hui Huang. Design of one type of linear network prediction controller for multi-agent system. Discrete and Continuous Dynamical Systems - S, 2019, 12 (4&5) : 727-734. doi: 10.3934/dcdss.2019047
[18]	Xiaojin Huang, Hongfu Yang, Jianhua Huang. Consensus stability analysis for stochastic multi-agent systems with multiplicative measurement noises and Markovian switching topologies. Numerical Algebra, Control and Optimization, 2021 doi: 10.3934/naco.2021024
[19]	Junyuan Lin, Timothy A. Lucas. A particle swarm optimization model of emergency airplane evacuations with emotion. Networks and Heterogeneous Media, 2015, 10 (3) : 631-646. doi: 10.3934/nhm.2015.10.631
[20]	Rodrigo A. Garrido, Ivan Aguirre. Emergency logistics for disaster management under spatio-temporal demand correlation: The earthquakes case. Journal of Industrial and Management Optimization, 2020, 16 (5) : 2369-2387. doi: 10.3934/jimo.2019058

2020 Impact Factor: 1.801

Tools

Metrics

Other articles
by authors

on AIMS
Sarah Ibri
on Google Scholar
Sarah Ibri

[Back to Top]