American Institute of Mathematical Sciences

Advanced
  • 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

Sarah Ibri 1,

1. 

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

Received  December 2012 Revised  January 2014 Published  May 2014

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-201. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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. Google Scholar

[6]

R. Church and C. R. Velle, The maximal covering location problem, Regional Science, 32 (1974), 101-118. Google Scholar

[7]

M. S. Daskin, Maximum expected covering model: Formulation, properties and heuristic solution, Transportation Science, 17 (1984), 48-70. Google Scholar

[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. Google Scholar

[9]

J. Gaudreault , J. M. Frayret and G. Pesant, Distributed Search for Supply Chain Coordination, Computers in Industry, 60 (2009), 441-451. Google Scholar

[10]

J. Gaudreault, Algorithmes Pour la Prise de Decision Distribuee en Contexte Hierarchique Ph.D thesis, Universite Laval, 2009. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[16]

W. D. Harvey and M. L. Ginsberg, Limited Discrepancy search, the $14^{th}$ International joint conference on Artificial intelligence, (1995), 607-613. Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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. Google Scholar

[20]

P. Kolesar and W. E. Walker, An algorithm for the dynamic relocation of fire companies, Operations Research, 22 (1974), 249-274. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[25]

P. J. Modi, Distributed Constraint Optimization for Multi-agent Systems, Ph.D thesis, University of Southern California, 2003. Google Scholar

[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.  Google Scholar

[27]

A. Petcu and B. Faltings, A Scalable Method for Multiagent Constraint Optimization, The $19^{th}$ International Joint Conference on Artificial Intelligence, 2005. Google Scholar

[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.  Google Scholar

[29]

C. ReVelle and K. Hogan, The maximum availability location problem, Transportation Science, 23 (1989), 192-200. doi: 10.1287/trsc.23.3.192.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

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. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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. Google Scholar

[6]

R. Church and C. R. Velle, The maximal covering location problem, Regional Science, 32 (1974), 101-118. Google Scholar

[7]

M. S. Daskin, Maximum expected covering model: Formulation, properties and heuristic solution, Transportation Science, 17 (1984), 48-70. Google Scholar

[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. Google Scholar

[9]

J. Gaudreault , J. M. Frayret and G. Pesant, Distributed Search for Supply Chain Coordination, Computers in Industry, 60 (2009), 441-451. Google Scholar

[10]

J. Gaudreault, Algorithmes Pour la Prise de Decision Distribuee en Contexte Hierarchique Ph.D thesis, Universite Laval, 2009. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[16]

W. D. Harvey and M. L. Ginsberg, Limited Discrepancy search, the $14^{th}$ International joint conference on Artificial intelligence, (1995), 607-613. Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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. Google Scholar

[20]

P. Kolesar and W. E. Walker, An algorithm for the dynamic relocation of fire companies, Operations Research, 22 (1974), 249-274. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[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. Google Scholar

[25]

P. J. Modi, Distributed Constraint Optimization for Multi-agent Systems, Ph.D thesis, University of Southern California, 2003. Google Scholar

[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.  Google Scholar

[27]

A. Petcu and B. Faltings, A Scalable Method for Multiagent Constraint Optimization, The $19^{th}$ International Joint Conference on Artificial Intelligence, 2005. Google Scholar

[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.  Google Scholar

[29]

C. ReVelle and K. Hogan, The maximum availability location problem, Transportation Science, 23 (1989), 192-200. doi: 10.1287/trsc.23.3.192.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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]

Richard Carney, Monique Chyba, Chris Gray, George Wilkens, Corey Shanbrom. Multi-agent systems for quadcopters. Journal of Geometric Mechanics, 2021  doi: 10.3934/jgm.2021005
[3]

Ke Yang, Wencheng Zou, Zhengrong Xiang, Ronghao Wang. Fully distributed consensus for higher-order nonlinear multi-agent systems with unmatched disturbances. Discrete & Continuous Dynamical Systems - S, 2021, 14 (4) : 1535-1551. doi: 10.3934/dcdss.2020396
[4]

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
[5]

Seung-Yeal Ha, Dohyun Kim, Jaeseung Lee, Se Eun Noh. Emergent dynamics of an orientation flocking model for multi-agent system. Discrete & Continuous Dynamical Systems, 2020, 40 (4) : 2037-2060. doi: 10.3934/dcds.2020105
[6]

Nadia Loy, Andrea Tosin. Boltzmann-type equations for multi-agent systems with label switching. Kinetic & Related Models, 2021, 14 (5) : 867-894. doi: 10.3934/krm.2021027
[7]

Brendan Pass. Multi-marginal optimal transport and multi-agent matching problems: Uniqueness and structure of solutions. Discrete & Continuous Dynamical Systems, 2014, 34 (4) : 1623-1639. doi: 10.3934/dcds.2014.34.1623
[8]

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, 2020, 16 (5) : 2117-2139. doi: 10.3934/jimo.2019046
[9]

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
[10]

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
[11]

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 & Continuous Dynamical Systems - B, 2020, 25 (12) : 4535-4551. doi: 10.3934/dcdsb.2020111
[12]

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
[13]

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
[14]

Hongru Ren, Shubo Li, Changxin Lu. Event-triggered adaptive fault-tolerant control for multi-agent systems with unknown disturbances. Discrete & Continuous Dynamical Systems - S, 2021, 14 (4) : 1395-1414. doi: 10.3934/dcdss.2020379
[15]

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
[16]

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 & Optimization, 2021  doi: 10.3934/naco.2021024
[17]

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
[18]

Rodrigo A. Garrido, Ivan Aguirre. Emergency logistics for disaster management under spatio-temporal demand correlation: The earthquakes case. Journal of Industrial & Management Optimization, 2020, 16 (5) : 2369-2387. doi: 10.3934/jimo.2019058
[19]

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
[20]

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

2020 Impact Factor: 1.801

Tools

Metrics

  • PDF downloads (102)
  • HTML views (0)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences