Proceedings

Coordinating Logistics Operations with Privacy Guarantees

Download BibTeX Cite

Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence. Pages 2482-2486.

https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-413

© 2011 International Joint Conferences on Artificial Intelligence

Abstract

Several logistics service providers serve a certain number of customers, geographically spread over an area of operations. They would like to coordinate their operations so as to minimize overall cost. At the same time, they would like to keep information about their costs, constraints and preferences private, thus precluding conventional negotiation. We show how AI techniques, in particular Distributed Constraint Optimization (DCOP), can be integrated with cryptographic techniques to allow such coordination without revealing agents' private information. The problem of assigning customers to companies is formulated as a DCOP, for which we propose two novel, privacy-preserving algorithms. We compare their performances and privacy properties on a set of Vehicle Routing Problem benchmarks.

  1. [Agarwal et al., 1989] Y. Agarwal, K. Mathur, and H. M. Salkin. A set-partitioning-based exact algorithm for the vehicle routing problem. Networks, 19:731-749, 1989.
  2. [Christofides and Eilon, 1969] N. Christofides and S. Eilon. An algorithm for the vehicle dispatching problem. Opera- tional Research Quarterly, 20:309-318, 1969.
  3. [Christofides et al., 1981] N. Christofides, A. Mingozzi, and Paolo Toth. Space state relaxation procedures for the computation of bounds to routing problems. Networks, 11:145-164, 1981.
  4. [Clarke and Wright, 1964] G. Clarke and J. W. Wright. Scheduling of vehicles from a central depot to a number of delivery points. Operations Research, 12(4):568-581, July-August 1964.
  5. [Croes, 1958] G. A. Croes. A method for solving traveling- salesman problems. Operations Research, 6(6):791-812, November-December 1958.
  6. [Elgamal, 1985] Taher Elgamal. A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE Trans. on Information Theory, 31(4):469-472, July 1985.
  7. [Faltings et al., 2008] Boi Faltings, Thomas Léauté, and Adrian Petcu. Privacy Guarantees through Distributed Constraint Satisfaction. In IAT'08, pages 350-358, 2008.
  8. [Gendreau et al., 2007] Michel Gendreau, Jean-Yves Potvin, Olli Bräysy, Geir Hasle, and Arne Løkketangen. Meta- heuristics for the vehicle routing problem and its exten- sions : A categorized bibliography. Technical Report 2007-27, CIRRELT, August 2007.
  9. [Gentry, 2009] Craig Gentry. Fully homomorphic encryption using ideal lattices. In Proc. 41st Annual ACM Symp. on Theory of Computing (STOC'09), pages 169-178, 2009.
  10. [Gillett and Miller, 1974] Billy E. Gillett and Leland R. Miller. A heuristic algorithm for the vehicle-dispatch prob- lem. Ops Research, 22(2):340-349, March-April 1974.
  11. [Hjorring, 1995] C. Hjorring. The Vehicle Routing Problem and Local Search Metaheuristics. PhD thesis, Dept of En- gineering Science, The University of Auckland, 1995.
  12. [Laporte and Nobert, 1987] Gilbert Laporte and Y. Nobert. Exact algorithms for the vehicle routing problem. Annals of Discrete Mathematics, 31:147-184, 1987.
  13. [Léauté and Faltings, 2009] Thomas Léauté and Boi Falt- ings. Privacy-Preserving Multi-agent Constraint Satisfac- tion. In Proc. IEEE International Conference on PrivAcy, Security, riSk And Trust (PASSAT'09), pages 17-25, 2009.
  14. [Léauté et al., 2009] Thomas Léauté, Brammert Ottens, and Radoslaw Szymanek. FRODO 2.0: An Open-Source Framework for Distributed Constraint Optimization. In Proceedings of the DCR'09 Workshop, pages 160-164, 2009. http://liawww.epfl.ch/frodo. Link
  15. [Léauté et al., 2010] Thomas Léauté, Brammert Ottens, and Boi Faltings. Ensuring Privacy through Distributed Com- putation in Multiple-Depot Vehicle Routing Problems. In Proceedings of the ECAI'10 Workshop on Artificial Intel- ligence and Logistics (AILog'10), pages 25-30, 2010.
  16. [OpsResearch, 2010] Operations Research -Java Objects. http://or-objects.org/, 2010. Link
  17. [Petcu and Faltings, 2005] Adrian Petcu and Boi Faltings. DPOP: A Scalable Method for Multiagent Constraint Op- timization. In Proc. IJCAI'05, pages 266-271, 2005.
  18. [Shamir, 1979] Adi Shamir. How to share a secret. Commu- nications of the ACM, 22(11):612-613, November 1979.
  19. [Silaghi and Mitra, 2004] Marius-Cȃlin Silaghi and Debasis Mitra. Distributed constraint satisfaction and optimization with privacy enforcement. In Proc. Intl Conf. on Intelligent Agent Technology (IAT'04), pages 531-535, 2004.
  20. [Silaghi, 2005] Marius-Cȃlin Silaghi. Hiding absence of solution for a distributed constraint satisfaction problem (poster). In Proc. of the 18th Intl Florida A.I. Research Society Conference (FLAIRS'05), pages 854-855, 2005.
  21. [Sultanik et al., 2007] Evan A. Sultanik, Robert N. Lass, and William C. Regli. DCOPolis: A framework for simulat- ing and deploying distributed constraint optimization al- gorithms. In Proceedings of the DCR'07 Workshop, 2007.
  22. [Toth and Vigo, 2001] Paolo Toth and Daniele Vigo, editors. The Vehicle Routing Problem. SIAM, 2001.
  23. [VRP Web, 2007] The VRP Web. http://neo.lcc. uma.es/radi-aeb/WebVRP/, March 2007. Link

References were extracted automatically from the PDF and may contain errors.

Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards