A Variable Neighborhood Search for the Generalized Vehicle Routing Problem with Stochastic Demands

详细信息    查看全文

• 作者：Benjamin Biesinger (15)
  Bin Hu (15)
  G眉nther R. Raidl (15)
  
  15. Institute of Computer Graphics and Algorithms ; Vienna University of Technology ; Favoritenstra脽e 9鈥?1/1861 ; 1040 ; Vienna ; Austria
  
• 关键词：Generalized vehicle routing problem ; Stochastic vehicle routing problem ; Variable neighborhood search ; Stochastic optimization
• 刊名：Lecture Notes in Computer Science
• 出版年：2015
• 出版时间：2015
• 年：2015
• 卷：9026
• 期：1
• 页码：48-60
• 全文大小：248 KB
• 参考文献：1. Afsar, HM, Prins, C, Santos, AC (2014) Exact and heuristic algorithms for solving the generalized vehicle routing problem with flexible fleet size. Int. Trans. Oper. Res. 21: pp. 153-175 CrossRef
  2. Bekta艧, T, Erdo千an, G, R酶pke, S (2011) Formulations and branch-and-cut algorithms for the generalized vehicle routing problem. Trans. Sci. 45: pp. 299-316 CrossRef
  3. Bertsimas, D.J.: Probabilistic combinatorial optimization problems. Ph.D. thesis, Massachusetts Institute of Technology (1988)
  4. Bianchi, L, Birattari, M, Chiarandini, M, Manfrin, M, Mastrolilli, M, Paquete, L, Rossi-Doria, O, Schiavinotto, T (2006) Hybrid metaheuristics for the vehicle routing problem with stochastic demands. J. Math. Model. Algorithms 5: pp. 91-110 CrossRef
  5. Fischetti, M, Salazar Gonz谩lez, JJ, Toth, P (1995) The symmetric generalized traveling salesman polytope. Networks 26: pp. 113-123 CrossRef
  6. Fischetti, M, Salazar Gonz谩lez, JJ, Toth, P (1997) A branch-and-cut algorithm for the symmetric generalized traveling salesman problem. Oper. Res. 45: pp. 378-394 CrossRef
  7. Gendreau, M, Laporte, G, S茅guin, R (1996) A tabu search heuristic for the vehicle routing problem with stochastic demands and customers. Oper. Res. 44: pp. 469-477 CrossRef
  8. H脿, MH, Bostel, N, Langevin, A, Rousseau, LM (2014) An exact algorithm and a metaheuristic for the generalized vehicle routing problem with flexible fleet size. Comput. Oper. Res. 43: pp. 9-19 CrossRef
  9. Hansen, P, Mladenovi膰, N Variable neighborhood search. In: Glover, F, Kochenberger, G eds. (2003) Handbook of Metaheuristics. Springer, US, pp. 145-184
  10. Hansen, P, Mladenovi膰, N, Moreno P茅rez, J (2010) Variable neighbourhood search: methods and applications. Ann. Oper. Res. 175: pp. 367-407 CrossRef
  11. Henry-Labordere: The record balancing problem: a dynamic programming solution of the generalized traveling salesman problem. RAIRO Oper. Res. B2, 43鈥?9 (1969)
  12. Hjorring, C, Holt, J (1999) New optimality cuts for a single vehicle stochastic routing problem. Ann. Oper. Res. 86: pp. 569-584 CrossRef
  13. Jaillet, P.: Probabilistic traveling salesman problems. Ph.D. thesis, Massachusetts Institute of Technology (1985)
  14. Laporte, G, Louveaux, FV, Hamme, L (2002) An integer L-shaped algorithm for the capacitated vehicle routing problem with stochastic demands. Oper. Res. 50: pp. 415-423 CrossRef
  15. Laporte, G, Louveaux, F Solving stochastic routing problems with the integer L-shaped method. In: Crainic, T, Laporte, G eds. (1998) Fleet Management and Logistics. Springer, New York, pp. 159-167 CrossRef
  16. Marinakis, Y, Iordanidou, GR, Marinaki, M (2013) Particle swarm optimization for the vehicle routing problem with stochastic demands. Appl. Soft Comput. 13: pp. 1693-1704 CrossRef
  17. Marinakis, Y, Marinaki, M, Migdalas, A A hybrid clonal selection algorithm for the vehicle routing problem with stochastic demands. In: Pardalos, PM, Resende, MG, Vogiatzis, C, Walteros, JL eds. (2014) Learning and Intelligent Optimization. Springer, Heidelberg, pp. 258-273 CrossRef
  18. Pop, PC, Fuksz, L, Marc, AH A variable neighborhood search approach for solving the generalized vehicle routing problem. In: Polycarpou, M, Carvalho, ACPLF, Pan, J-S, Wo藕niak, M, Quintian, H, Corchado, E eds. (2014) Hybrid Artificial Intelligence Systems. Springer, Heidelberg, pp. 13-24 CrossRef
  19. Pop, PC, Kara, I, Marc, AH (2012) New mathematical models of the generalized vehicle routing problem and extensions. Appl. Math. Model. 36: pp. 97-107 CrossRef
  20. Rei, W, Gendreau, M, Soriano, P (2010) A hybrid monte carlo local branching algorithm for the single vehicle routing problem with stochastic demands. Transp. Sci. 44: pp. 136-146 CrossRef
  21. Saskena, J (1970) Mathematical model of scheduling clients through welfare agencies. J. Can. Oper. Res. Soc. 8: pp. 185-200
  22. Secomandi, N, Margot, F (2009) Reoptimization approaches for the vehicle-routing problem with stochastic demands. Oper. Res. 57: pp. 214-230 CrossRef
  23. Srivastava, SS, Kumar, S, Carg, RC, Sen, P (1969) Generalized traveling salesman problem through n sets of nodes. Can. Oper. Res. Soc. J. 7: pp. 97-101
  24. Yang, WH, Mathur, K, Ballou, RH (2000) Stochastic vehicle routing problem with restocking. Transp. Sci. 34: pp. 99-112 CrossRef
  
• 作者单位：Evolutionary Computation in Combinatorial Optimization
• 丛书名：978-3-319-16467-0
• 刊物类别：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

文摘

In this work we consider the generalized vehicle routing problem with stochastic demands (GVRPSD) being a combination of the generalized vehicle routing problem, in which the nodes are partitioned into clusters, and the vehicle routing problem with stochastic demands, where the exact demands of the nodes are not known beforehand. It is an NP-hard problem for which we propose a variable neighborhood search (VNS) approach to minimize the expected tour length through all clusters. We use a permutation encoding for the cluster sequence and consider the preventive restocking strategy where the vehicle restocks before it potentially runs out of goods. The exact solution evaluation is based on dynamic programming and is very time-consuming. Therefore we propose a multi-level evaluation scheme to significantly reduce the time needed for solution evaluations. Two different algorithms for finding an initial solution and three well-known neighborhood structures for permutations are used within the VNS. Results show that the multi-level evaluation scheme is able to drastically reduce the overall run-time of the algorithm and that it is essential to be able to tackle larger instances. A comparison to an exact approach shows that the VNS is able to find an optimal or near-optimal solution in much shorter time.