The Capacitated Vehicle Routing Problem with Evidential Demands: A Belief-Constrained Programming Approach

详细信息    查看全文

• 关键词：Vehicle routing problem ; Stochastic programming ; Chance ; constrained programming ; Belief functions
• 刊名：Lecture Notes in Computer Science
• 出版年：2016
• 出版时间：2016
• 年：2016
• 卷：9861
• 期：1
• 页码：212-221
• 全文大小：194 KB
• 参考文献：1.Bodin, L.D., Golden, B.L., Assad, A.A., Ball, M.O.: Routing and scheduling of vehicles and crews: the state of the art. Comput. Oper. Res. 10(2), 63–212 (1983)MathSciNet CrossRef
  2.Charnes, A., Cooper, W.W.: Chance-constrained programming. Manag. Sci. 6(1), 73–79 (1959)MathSciNet CrossRef MATH
  3.Cordeau, J.-F., Laporte, G., Savelsbergh, M.W.P., Vigo, D.: Vehicle routing (Chap. 6). In: Barnhart, C., Laporte, G. (eds.) Transportation, Handbooks in Operations Research and Management Science, vol. 14, pp. 367–428. Elsevier, Amsterdam (2007)
  4.Ferson, S., Tucker, W.T.: Sensitivity in risk analyses with uncertain numbers. Technical report, Sandia National Laboratories (2006)
  5.Harmanani, H., Azar, D., Helal, N., Keirouz, W.: A simulated annealing algorithm for the capacitated vehicle routing problem. In: 26th International Conference on Computers and their Applications, New Orleans, USA (2011)
  6.Kirby, M.J.L.: The current state of chance-constrained programming. In: Kuhn, H.W. (ed.) Proceedings of the Princeton Symposium on Mathematical Programming, pp. 93–111. Princeton University Press (1970)
  7.Kirkpatrick, S., Gelatt, C.D., Vecchi, M.P.: Optimisation by simulated annealing. Science 220(4598), 671–680 (1983)MathSciNet CrossRef MATH
  8.Laporte, G., Louveaux, F.V., van Hamme, L.: An integer l-shaped algorithm for the capacitated vehicle routing problem with stochastic demands. Oper. Res. 50, 415–423 (2002)MathSciNet CrossRef MATH
  9.Masri, H., Abdelaziz, F.B.: Belief linear programming. Int. J. Approx. Reason. 51, 973–983 (2010)CrossRef MATH
  10.Mourelatos, Z.P., Zhou, J.: A design optimization method using evidence theory. J. Mech. Design 128, 901–908 (2006)CrossRef
  11.Nassreddine, G., Abdallah, F., Denoeux, T.: State estimation using interval analysis and belief function theory: application to dynamic vehicle localization. IEEE Trans. Syst. Man Cybern. B 40(5), 1205–1218 (2010)CrossRef
  12.Pichon, F., Dubois, D., Denoeux, T.: Relevance and truthfulness in information correction and fusion. Int. J. Approx. Reason. 53(2), 159–175 (2012)MathSciNet CrossRef MATH
  13.Vehicle Routing Data Sets. http://​www.​coin-or.​org/​SYMPHONY/​branchandcut/​VRP/​data/​index.​htm . Accessed 20 Mar 2016
  14.Shafer, G.: A Mathematical Theory of Evidence. Princeton University Press, Princeton (1976)MATH
  15.Srivastava, R.K., Deb, K., Tulshyan, R.: An evolutionary algorithm based approach to design optimization using evidence theory. J. Mech. Design 135(8), 081003-1–081003-12 (2013)CrossRef
  16.Sungur, I., Ordónez, F., Dessouky, M.: A robust optimization approach for the capacitated vehicle routing problem with demand uncertainty. IIE Trans. 40, 509–523 (2008)CrossRef
  17.Yager, R.R.: Arithmetic and other operations on Dempster-Shafer structures. Int. J. Man Mach. Stud. 25(4), 357–366 (1986)CrossRef MATH
  
• 作者单位：Nathalie Helal (15)
  Frédéric Pichon (15)
  Daniel Porumbel (16)
  David Mercier (15)
  Éric Lefèvre (15)
  
  15. University of Artois, EA 3926, Laboratoire de Génie Informatique et d’Automatique de l’Artois (LGI2A), 62400, Béthune, France
  16. Conservatoire National des Arts et Métiers, EA 4629, Cedric, 75003, Paris, France
  
• 丛书名：Belief Functions: Theory and Applications
• ISBN：978-3-319-45559-4
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349
• 卷排序：9861

文摘

This paper studies a vehicle routing problem, where vehicles have a limited capacity and customer demands are uncertain and represented by belief functions. More specifically, this problem is formalized using a belief function based extension of the chance-constrained programming approach, which is a classical modeling of stochastic mathematical programs. In addition, it is shown how the optimal solution cost is influenced by some important parameters involved in the model. Finally, some instances of this difficult problem are solved using a simulated annealing metaheuristic, demonstrating the feasibility of the approach.