Multiple-Depot Vehicle Routing Problems as a Distributed Constraint Optimization Problem

Abstract:

The Distributed Constraint Optimization Problem (DCOP) is able to model a variety of distributed reasoning tasks that arise in multi-agent systems, and widely applying to distribute programming, scheduling and resource allocation etc. In order to solve the multi-depot vehicle routing problem (MDVRP) in distributed manner, this article show how DCOP can be used to model the MDVRP, and using existing various DCOP algorithm solve it base on Frodo simulation platform. We have evaluated the performances of various DCOP algorithms on an existing MDVRP.

• Periodical: Applied Mechanics and Materials (Volumes 66-68)
• Pages: 1033-1038
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.66-68.1033
• Online since: July 2011
• Authors: Xing Ming Lei, Chang Feng Xing, Ling Wu, Yun Feng Wen
• Keywords: ADOPT, DCOP, DPOP, MDVRP

References

[1] G. Laporte, Y. Nobert, and D. Arpin, Optimal solutions to capacitated Multi-depot vehicler outing problems, Congressus Numerantium, 44(1984), p.283–292.

[2] Jean-Franc¸ois Cordeau, Michel Gendreau, A tabu search heuristic for periodic and multi-depot vehicle routing problems, Networks, 30 (1998), p.105–119.

DOI: 10.1002/(sici)1097-0037(199709)30:2<105::aid-net5>3.0.co;2-g

[3] Sam R. Thangiah , Said Salhi, Genetic clustering: An adaptive heuristic for the multidepot vehicle routing problem, Applied Artificial Intelligence, 15(2001), p.361–383.

DOI: 10.1080/08839510151087293

[4] David Pisinger, Stefan Ropkea, A general heuristic for vehicle routing problems, Computers and OR, 34(2007), p.2403–2435.

DOI: 10.1016/j.cor.2005.09.012

[5] William P. C. Ho, George T. S. Ho, Ping Ji, A hybrid genetic algorithm for the multi-depot vehicle routing problem, Engineering Applications of AI, 21(2008), p.548–557.

DOI: 10.1016/j.engappai.2007.06.001

[6] Dariusz Barbucha , Piotr Je¸drzejowicz, An agent-based approach to vehicle routing problem, WASET, 26(2007), p.36–41.

[7] A.E. Rizzoli, R. Montemanni, E. Lucibello, Ant colony optimization for real-world vehicle routing problems: From theory to applications, Swarm Intelligence, (2007), p.135–151.

DOI: 10.1007/s11721-007-0005-x

[8] Thomas Leaute , Brammert Ottens , Boi Faltings, Ensuring Privacy through Distributed Computation in Multiple-Depot Vehicle Routing Problems", Proceedings of the ECAI'10 Workshop on Artificial Intelligence and Logistics (AILog, 10), Lisbon, Portugal, (2010).

[9] P. Modi, W. Shen, M. Tambe, M. Yokoo, ADOPT: asynchronous distributed constraint optimization with quality guarantees, Artificial Intelligence, 161(2005), pp.149-180.

DOI: 10.1016/j.artint.2004.09.003

[10] A. Petcu, B. Faltings, A Scalable Method for Multiagent Constraint Optimization. In proceedings of IJCAI 05, (2005), pp.266-271.

[11] Matsui T, Matsuo H, Improvement of efficiency in pseudo-tree based distributed best first search, IAENG International Journal of Computer Science, 34(2007), pp.73-77.

[12] Yeoh W, Koenig S, Felner A, IDB-ADOPT: A Depth-First Search DCOP Algorithm, Computer Science( 2009), pp.132-146.

DOI: 10.1007/978-3-642-03251-6_9

[13] W. Yeoh, A. Felner, S. Koenig, Bnb-ADOPT: An asynchronous branch-and-bound DCOP algorithm, Proc. of AAMAS, (2008), p.591–598.

DOI: 10.1613/jair.2849

[14] M. Silaghi ,M. Yokoo, Nogood-based asynchronous distributed optimization (ADOPT-ng), Proc. of AAMAS, (2006), p.1389–1396.

DOI: 10.1145/1160633.1160894

[15] Thomas Leaute, Brammert Ottens, Radoslaw Szymanek, FRODO 2. 0: An open-source framework for distributed constraint optimization, In Hirayama et al , (2010), p.160–164. http: /liawww. epfl. ch/frodo.

[16] Adrian Petcu, Boi Faltings, O-DPOP: An algorithm for open/distributed constraint optimization", in Proc. of the 21st National Conf. on Artificial Intelligence (AAAI, 06), (2006), p.703–708.

[17] Brammert Ottens, Boi Faltings, Coordinating agent plans through distributed constraint optimization", in Proceedings of the ICAPS'08 Multiagent Planning Workshop (MASPLAN, 08), (2008).

[18] Boi Faltings, Thomas Leaute, and Adrian Petcu, Privacy guarantees through distributed constraint satisfaction", in Proceedings of the 2008 IEEE/WIC/ACM International Conference on Intelligent Agent Technology(IAT, 08), (2008), p.350–358.

DOI: 10.1109/wiiat.2008.177

[19] Adrian Petcu , Boi Faltings, S-DPOP: Superstabilizing, faultcontaining multiagent combinatorial optimization", in Proc. of the 20th National Conference on A.I. (AAAI, 05), (2005), p.449–454.