Abstract
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.
This work has been supported by COMPETE: POCI-01-0145-FEDER-007043 and FCT – Fundação para a Ciência e a Tecnologia within the Project Scope: UID/CEC/00319/2013, and through the grant SFRH/BD/73584/2010 (funded by QREN-POPH-Typology 4.1- co-funded by the European Social Fund).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
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)
Dantzig, G.B., Wolfe, P.: Decomposition principle for linear programs. Oper. Res. 8(1), 101–111 (1960)
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)
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)
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)
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)
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)
Macedo, R., Alves, C., Valério de Carvalho, J.: Exact algorithms for vehicle routing problems with different service constraints. In: CTW09, France (2009)
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)
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)
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)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer International Publishing Switzerland
About this paper
Cite this paper
Pinto, T., Alves, C., de Carvalho, J.V. (2016). A Branch-and-Price Algorithm for the Vehicle Routing Problem with 2-Dimensional Loading Constraints. In: Paias, A., Ruthmair, M., Voß, S. (eds) Computational Logistics. ICCL 2016. Lecture Notes in Computer Science(), vol 9855. Springer, Cham. https://doi.org/10.1007/978-3-319-44896-1_21
Download citation
DOI: https://doi.org/10.1007/978-3-319-44896-1_21
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-44895-4
Online ISBN: 978-3-319-44896-1
eBook Packages: Computer ScienceComputer Science (R0)