• 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

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

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

[6]

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

[7]

M. S. Daskin, Maximum expected covering model: Formulation, properties and heuristic solution,, Transportation Science, 17 (1984), 48.   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.   Google Scholar

[9]

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

[10]

J. Gaudreault, Algorithmes Pour la Prise de Decision Distribuee en Contexte Hierarchique, Ph.D thesis, (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.   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.   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.   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.   Google Scholar

[16]

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

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

[20]

P. Kolesar and W. E. Walker, An algorithm for the dynamic relocation of fire companies,, Operations Research, 22 (1974), 249.   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, 22 (2005), 43.   Google Scholar

[22]

B. Lopez, B. Innocenti and D. Busquets, A multiagent system for coordinating ambulances for emergency medical services,, Intelligent Systems, 23 (2008), 50.   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.   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.   Google Scholar

[25]

P. J. Modi, Distributed Constraint Optimization for Multi-agent Systems,, Ph.D thesis, (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.  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.  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.  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.  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.   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.  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.   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.   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.  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.  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.  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.   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.   Google Scholar

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

[6]

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

[7]

M. S. Daskin, Maximum expected covering model: Formulation, properties and heuristic solution,, Transportation Science, 17 (1984), 48.   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.   Google Scholar

[9]

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

[10]

J. Gaudreault, Algorithmes Pour la Prise de Decision Distribuee en Contexte Hierarchique, Ph.D thesis, (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.   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.   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.   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.   Google Scholar

[16]

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

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

[20]

P. Kolesar and W. E. Walker, An algorithm for the dynamic relocation of fire companies,, Operations Research, 22 (1974), 249.   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, 22 (2005), 43.   Google Scholar

[22]

B. Lopez, B. Innocenti and D. Busquets, A multiagent system for coordinating ambulances for emergency medical services,, Intelligent Systems, 23 (2008), 50.   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.   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.   Google Scholar

[25]

P. J. Modi, Distributed Constraint Optimization for Multi-agent Systems,, Ph.D thesis, (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.  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.  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.  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.  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.   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.  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.   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.   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.  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.  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.  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.   Google Scholar

[1]

Hong Seng Sim, Wah June Leong, Chuei Yee Chen, Siti Nur Iqmal Ibrahim. Multi-step spectral gradient methods with modified weak secant relation for large scale unconstrained optimization. Numerical Algebra, Control & Optimization, 2018, 8 (3) : 377-387. doi: 10.3934/naco.2018024

[2]

Karl-Peter Hadeler, Frithjof Lutscher. Quiescent phases with distributed exit times. Discrete & Continuous Dynamical Systems - B, 2012, 17 (3) : 849-869. doi: 10.3934/dcdsb.2012.17.849

[3]

Raz Kupferman, Cy Maor. The emergence of torsion in the continuum limit of distributed edge-dislocations. Journal of Geometric Mechanics, 2015, 7 (3) : 361-387. doi: 10.3934/jgm.2015.7.361

[4]

Dmitry Treschev. A locally integrable multi-dimensional billiard system. Discrete & Continuous Dynamical Systems - A, 2017, 37 (10) : 5271-5284. doi: 10.3934/dcds.2017228

[5]

Benrong Zheng, Xianpei Hong. Effects of take-back legislation on pricing and coordination in a closed-loop supply chain. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021035

[6]

Eduardo Casas, Christian Clason, Arnd Rösch. Preface special issue on system modeling and optimization. Mathematical Control & Related Fields, 2021  doi: 10.3934/mcrf.2021008

[7]

Ardeshir Ahmadi, Hamed Davari-Ardakani. A multistage stochastic programming framework for cardinality constrained portfolio optimization. Numerical Algebra, Control & Optimization, 2017, 7 (3) : 359-377. doi: 10.3934/naco.2017023

[8]

Luke Finlay, Vladimir Gaitsgory, Ivan Lebedev. Linear programming solutions of periodic optimization problems: approximation of the optimal control. Journal of Industrial & Management Optimization, 2007, 3 (2) : 399-413. doi: 10.3934/jimo.2007.3.399

[9]

Namsu Ahn, Soochan Kim. Optimal and heuristic algorithms for the multi-objective vehicle routing problem with drones for military surveillance operations. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021037

[10]

Dayalal Suthar, Sunil Dutt Purohit, Haile Habenom, Jagdev Singh. Class of integrals and applications of fractional kinetic equation with the generalized multi-index Bessel function. Discrete & Continuous Dynamical Systems - S, 2021  doi: 10.3934/dcdss.2021019

[11]

Abdulrazzaq T. Abed, Azzam S. Y. Aladool. Applying particle swarm optimization based on Padé approximant to solve ordinary differential equation. Numerical Algebra, Control & Optimization, 2021  doi: 10.3934/naco.2021008

[12]

Mohsen Abdolhosseinzadeh, Mir Mohammad Alipour. Design of experiment for tuning parameters of an ant colony optimization method for the constrained shortest Hamiltonian path problem in the grid networks. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 321-332. doi: 10.3934/naco.2020028

[13]

Reza Lotfi, Yahia Zare Mehrjerdi, Mir Saman Pishvaee, Ahmad Sadeghieh, Gerhard-Wilhelm Weber. A robust optimization model for sustainable and resilient closed-loop supply chain network design considering conditional value at risk. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 221-253. doi: 10.3934/naco.2020023

2019 Impact Factor: 1.366

Metrics

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

Other articles
by authors

[Back to Top]