A Branch-and-Price Algorithm for the Vehicle Routing Problem with 2-Dimensional Loading Constraints

详细信息    查看全文

• 关键词：Vehicle routing ; Loading constraints ; Branch ; and ; price ; Computational study
• 刊名：Lecture Notes in Computer Science
• 出版年：2016
• 出版时间：2016
• 年：2016
• 卷：9855
• 期：1
• 页码：321-336
• 全文大小：380 KB
• 参考文献：1.Cordeau, J., Iori, M., Ropke, S., Vigo, D.: Branch-and-cut-and-price for the capacitated vehicle routing problem with two-dimensional loading constraints. In: ROUTE 2007, Jekyll Island (2007)
  2.Dantzig, G.B., Wolfe, P.: Decomposition principle for linear programs. Oper. Res. 8(1), 101–111 (1960)CrossRef MATH
  3.Feillet, D., Dejax, P., Gendreau, M., Gueguen, C.: An exact algorithm for the elementary shortest path problem with resource constraints: application to some vehicle routing problems. Networks 44(3), 216–229 (2004)CrossRef MATH MathSciNet
  4.Gendreau, M., Iori, M., Laporte, G., Martello, S.: A Tabu search heuristic for the vehicle routing problem with two-dimensional loading constraints. Networks 51(1), 4–18 (2008)CrossRef MATH MathSciNet
  5.Hokama, P., Miyazawa, F., Xavier, E.: A branch-and-cut approach for the vehicle routing problem with loading constraints. Expert Syst. Appl. 47, 1–13 (2016)CrossRef
  6.Iori, M., Salazar-Gonzalez, J.-J., Vigo, D.: An exact approach for the vehicle routing problem with two-dimensional loading constraints. Transp. Sci. 41(2), 253–264 (2007)CrossRef
  7.Junqueira, L., Oliveira, J., Carravilla, M.A., Morabito, R.: An optimization model for the vehicle routing problem with practical three-dimensional loading constraints. Int. Trans. Oper. Res. 20(5), 645–666 (2013)CrossRef MATH MathSciNet
  8.Macedo, R., Alves, C., Valério de Carvalho, J.: Exact algorithms for vehicle routing problems with different service constraints. In: CTW09, France (2009)
  9.Mahvash, B., Awasthi, A., Chauhan, S.: A column generation based heuristic for the capacitated vehicle routing problem with three-dimensional loading constraints. In: 15th IFAC Symposium on Information Control Problems in Manufacturing, vol. 48(3), pp. 448–453 (2015)
  10.Pinto, T., Alves, C., de Carvalho, J.V.: Variable neighborhood search for the elementary shortest path problem with loading constraints. In: Gervasi, O., Murgante, B., Misra, S., Gavrilova, M.L., Rocha, A.M.A.C., Torre, C., Taniar, D., Apduhan, B.O. (eds.) ICCSA 2015. LNCS, vol. 9156, pp. 474–489. Springer, Heidelberg (2015)CrossRef
  11.Souza, V.: Algoritmos para o problema de roteamento de veículos capacitado com restrições de carregamento bidimensional. Master’s thesis, Universidade Federal de Minas Gerais, Belo Horizonte, Brasil (2013)
  
• 作者单位：Telmo Pinto (16)
  Cláudio Alves (16)
  José Valério de Carvalho (16)
  
  16. Departamento de Produção e Sistemas, Escola de Engenharia, Universidade do Minho, 4710-057, Braga, Portugal
  
• 丛书名：Computational Logistics
• ISBN：978-3-319-44896-1
• 刊物类别：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
• 卷排序：9855

文摘

In this paper, we describe a branch-and-price algorithm for the capacitated vehicle routing problem with 2-dimensional loading constraints and a virtually unlimited number of vehicles. The column generation subproblem is solved heuristically through variable neighborhood search. Branch-and-price is used when it is not possible to add more attractive columns to the current restricted master problem, and the solution remains fractional. In order to accelerate the convergence of the algorithm, a family of valid dual inequalities is presented. Computational results are provided to evaluate the performance of the algorithm and to compare the different branching strategies proposed.