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

Sarah Ibri

doi:10.3934/jimo.2015.11.41

Article Contents

2015, Volume 11, Issue 1: 41-63. Doi: 10.3934/jimo.2015.11.41

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

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

Sarah Ibri^1,

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

Received: November 30, 2012

Revised: December 31, 2013

Published: December 2014

Abstract Related Papers Cited by

Abstract

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:

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

Citation:

Related Papers

Cited by

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.