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

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

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 & 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.
[2]	R. Batta, J. M. Dolan and N. N. Krishnamorthy, The maximal expected covering location problem: Revisited,, Transportation Science, 23 (1989), 277. 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. 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.
[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.
[6]	R. Church and C. R. Velle, The maximal covering location problem,, Regional Science, 32 (1974), 101.
[7]	M. S. Daskin, Maximum expected covering model: Formulation, properties and heuristic solution,, Transportation Science, 17 (1984), 48.
[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.
[9]	J. Gaudreault , J. M. Frayret and G. Pesant, Distributed Search for Supply Chain Coordination,, Computers in Industry, 60 (2009), 441.
[10]	J. Gaudreault, Algorithmes Pour la Prise de Decision Distribuee en Contexte Hierarchique, Ph.D thesis, (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.
[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.
[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.
[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.
[16]	W. D. Harvey and M. L. Ginsberg, Limited Discrepancy search,, the $14^{th}$ International joint conference on Artificial intelligence, (1995), 607.
[17]	K. Hirayama and M. Yokoo, The distributed breakout algorithms,, Artificial Intelligence - Special issue: Distributed constraint satisfaction, 161* (2005), 89. 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.
[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.
[20]	P. Kolesar and W. E. Walker, An algorithm for the dynamic relocation of fire companies,, Operations Research, 22 (1974), 249.
[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, 22 (2005), 43.
[22]	B. Lopez, B. Innocenti and D. Busquets, A multiagent system for coordinating ambulances for emergency medical services,, Intelligent Systems, 23 (2008), 50.
[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.
[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.
[25]	P. J. Modi, Distributed Constraint Optimization for Multi-agent Systems,, Ph.D thesis, (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. 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. doi: 10.1016/0377-2217(94)90297-6.
[29]	C. ReVelle and K. Hogan, The maximum availability location problem,, Transportation Science, 23 (1989), 192. 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. 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.
[32]	V. Schmid, Solving the dynamic ambulance relocation and dispatching problem using approximate dynamic programming,, European journal of operational research, 219* (2012), 611. 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.
[34]	C. R. Toregas, R. S. Wain, C. S. ReVelle and L. Bergman, The location of emergency service facilities,, Operations Research, 19 (1971), 1363.
[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. 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. 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. 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.

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.
[2]	R. Batta, J. M. Dolan and N. N. Krishnamorthy, The maximal expected covering location problem: Revisited,, Transportation Science, 23 (1989), 277. 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. 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.
[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.
[6]	R. Church and C. R. Velle, The maximal covering location problem,, Regional Science, 32 (1974), 101.
[7]	M. S. Daskin, Maximum expected covering model: Formulation, properties and heuristic solution,, Transportation Science, 17 (1984), 48.
[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.
[9]	J. Gaudreault , J. M. Frayret and G. Pesant, Distributed Search for Supply Chain Coordination,, Computers in Industry, 60 (2009), 441.
[10]	J. Gaudreault, Algorithmes Pour la Prise de Decision Distribuee en Contexte Hierarchique, Ph.D thesis, (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.
[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.
[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.
[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.
[16]	W. D. Harvey and M. L. Ginsberg, Limited Discrepancy search,, the $14^{th}$ International joint conference on Artificial intelligence, (1995), 607.
[17]	K. Hirayama and M. Yokoo, The distributed breakout algorithms,, Artificial Intelligence - Special issue: Distributed constraint satisfaction, 161* (2005), 89. 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.
[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.
[20]	P. Kolesar and W. E. Walker, An algorithm for the dynamic relocation of fire companies,, Operations Research, 22 (1974), 249.
[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, 22 (2005), 43.
[22]	B. Lopez, B. Innocenti and D. Busquets, A multiagent system for coordinating ambulances for emergency medical services,, Intelligent Systems, 23 (2008), 50.
[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.
[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.
[25]	P. J. Modi, Distributed Constraint Optimization for Multi-agent Systems,, Ph.D thesis, (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. 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. doi: 10.1016/0377-2217(94)90297-6.
[29]	C. ReVelle and K. Hogan, The maximum availability location problem,, Transportation Science, 23 (1989), 192. 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. 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.
[32]	V. Schmid, Solving the dynamic ambulance relocation and dispatching problem using approximate dynamic programming,, European journal of operational research, 219* (2012), 611. 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.
[34]	C. R. Toregas, R. S. Wain, C. S. ReVelle and L. Bergman, The location of emergency service facilities,, Operations Research, 19 (1971), 1363.
[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. 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. 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. 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.

[1]	Zhiyong Sun, Toshiharu Sugie. Identification of Hessian matrix in distributed gradient-based multi-agent coordination control systems. Numerical Algebra, Control & Optimization, 2019, 9 (3) : 297-318. doi: 10.3934/naco.2019020
[2]	Giulia Cavagnari, Antonio Marigonda, Benedetto Piccoli. Optimal synchronization problem for a multi-agent system. Networks & Heterogeneous Media, 2017, 12 (2) : 277-295. doi: 10.3934/nhm.2017012
[3]	Brendan Pass. Multi-marginal optimal transport and multi-agent matching problems: Uniqueness and structure of solutions. Discrete & Continuous Dynamical Systems - A, 2014, 34 (4) : 1623-1639. doi: 10.3934/dcds.2014.34.1623
[4]	Rui Li, Yingjing Shi. Finite-time optimal consensus control for second-order multi-agent systems. Journal of Industrial & Management Optimization, 2014, 10 (3) : 929-943. doi: 10.3934/jimo.2014.10.929
[5]	Zhongkui Li, Zhisheng Duan, Guanrong Chen. Consensus of discrete-time linear multi-agent systems with observer-type protocols. Discrete & Continuous Dynamical Systems - B, 2011, 16 (2) : 489-505. doi: 10.3934/dcdsb.2011.16.489
[6]	Yibo Zhang, Jinfeng Gao, Jia Ren, Huijiao Wang. A type of new consensus protocol for two-dimension multi-agent systems. Numerical Algebra, Control & Optimization, 2017, 7 (3) : 345-357. doi: 10.3934/naco.2017022
[7]	Tyrone E. Duncan. Some partially observed multi-agent linear exponential quadratic stochastic differential games. Evolution Equations & Control Theory, 2018, 7 (4) : 587-597. doi: 10.3934/eect.2018028
[8]	Hong Man, Yibin Yu, Yuebang He, Hui Huang. Design of one type of linear network prediction controller for multi-agent system. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 727-734. doi: 10.3934/dcdss.2019047
[9]	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 & Management Optimization, 2017, 13 (5) : 1-23. doi: 10.3934/jimo.2019046
[10]	Junyuan Lin, Timothy A. Lucas. A particle swarm optimization model of emergency airplane evacuations with emotion. Networks & Heterogeneous Media, 2015, 10 (3) : 631-646. doi: 10.3934/nhm.2015.10.631
[11]	Rodrigo A. Garrido, Ivan Aguirre. Emergency logistics for disaster management under spatio-temporal demand correlation: The earthquakes case. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-19. doi: 10.3934/jimo.2019058
[12]	Fan Zhang, Guifa Teng, Mengmeng Gao, Shuai Zhang, Jingjing Zhang. Multi-machine and multi-task emergency allocation algorithm based on precedence rules. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1501-1513. doi: 10.3934/dcdss.2019103
[13]	Sandeep Dulluri, N. R. Srinivasa Raghavan. Revenue management via multi-product available to promise. Journal of Industrial & Management Optimization, 2007, 3 (3) : 457-479. doi: 10.3934/jimo.2007.3.457
[14]	Zhongbao Zhou, Ximei Zeng, Helu Xiao, Tiantian Ren, Wenbin Liu. Multiperiod portfolio optimization for asset-liability management with quadratic transaction costs. Journal of Industrial & Management Optimization, 2019, 15 (3) : 1493-1515. doi: 10.3934/jimo.2018106
[15]	Nina Yan, Tingting Tong, Hongyan Dai. Capital-constrained supply chain with multiple decision attributes: Decision optimization and coordination analysis. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-26. doi: 10.3934/jimo.2018125
[16]	João Borges de Sousa, Bernardo Maciel, Fernando Lobo Pereira. Sensor systems on networked vehicles. Networks & Heterogeneous Media, 2009, 4 (2) : 223-247. doi: 10.3934/nhm.2009.4.223
[17]	Jueyou Li, Guoquan Li, Zhiyou Wu, Changzhi Wu, Xiangyu Wang, Jae-Myung Lee, Kwang-Hyo Jung. Incremental gradient-free method for nonsmooth distributed optimization. Journal of Industrial & Management Optimization, 2017, 13 (4) : 1841-1857. doi: 10.3934/jimo.2017021
[18]	Tsuguhito Hirai, Hiroyuki Masuyama, Shoji Kasahara, Yutaka Takahashi. Performance optimization of parallel-distributed processing with checkpointing for cloud environment. Journal of Industrial & Management Optimization, 2018, 14 (4) : 1423-1442. doi: 10.3934/jimo.2018014
[19]	Chuong Van Nguyen, Phuong Huu Hoang, Hyo-Sung Ahn. Distributed optimization algorithms for game of power generation in smart grid. Numerical Algebra, Control & Optimization, 2019, 9 (3) : 327-348. doi: 10.3934/naco.2019022
[20]	Lan Yi, Zhongfei Li, Duan Li. Multi-period portfolio selection for asset-liability management with uncertain investment horizon. Journal of Industrial & Management Optimization, 2008, 4 (3) : 535-552. doi: 10.3934/jimo.2008.4.535

2017 Impact Factor: 0.994

American Institute of Mathematical Sciences