Skip to main content
SpringerLink
Log in

An ILS-biased randomization algorithm for the two-dimensional loading HFVRP with sequential loading and items rotation

  • General Paper
  • Published:
Journal of the Operational Research Society

Abstract

This paper discusses the Two-dimensional Loading Vehicle Routing Problem with Heterogeneous Fleet, Sequential Loading, and Item Rotation (2L-HFVRP-SR). Despite the fact that the 2L-HFVRP-SR can be found in many real-life situations related to the transportation of voluminous items, where heterogeneity of fleets, two-dimensional packing restrictions, sequential loading, and items rotation have to be considered, this rich version of vehicle routing-and-packing problem has been rarely analysed in the literature. Accordingly, this paper contributes to filling the gap by presenting a relatively simple-to-implement algorithm which is able to provide state-of-the-art solutions for such a complex problem in relatively short computational times. The proposed algorithm integrates inside an Iterated Local Search framework, biased-randomized versions of both vehicle routing and packing heuristics. The efficiency of the proposed algorithm is validated throughout an extensive set of computational tests.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Figure 1
Figure 2
Figure 3
Figure 4
Figure 5
Figure 6
Figure 7
Figure 8

Similar content being viewed by others

References

  • Bruce G, Raghavan S and Edward W (2008). Routing a heterogeneous fleet of vehicles. In: Golden B, Raghavan S and Wasil E (eds). The Vehicle Routing Problem: Latest Advances and New Challenges. Springer: USA, pp 3–27.

    Google Scholar 

  • Baldacci R and Mingozzi A (2009). A unified exact method for solving different classes of vehicle routing problems. Mathematical Programming 120 (2): 347–380.

    Article  Google Scholar 

  • Burke EK, Kendall G and Whitwell G (2004). A new placement heuristic for the orthogonal stock-cutting problem. Operations Research 52 (4): 655–671.

    Article  Google Scholar 

  • Burke E et al (2010). Iterated local search vs. hyper-heuristics: Towards general-purpose search algorithms. In: IEEE Congress on Evolutionary Computation (CEC), pp 1–8 ISBN: 978-1-4244-6909-3. DOI: 10.1109/CEC.2010.5586064. Barcelona, Spain. July 18–23.

  • Caceres-Cruz J, Arias P, Guimarans D, Riera D and Juan AA (2014). Rich vehicle routing problem: Survey. ACM Computing Surveys. (CSUR) 47(2): 32: 1–32: 28.

  • Clarke GU and Wright JW (1964). Scheduling of vehicles from a central depot to a number of delivery points. Operations Research 12 (4): 568–581.

    Article  Google Scholar 

  • Dominguez O, Juan AA, Barrios B, Faulin J and Agustin A (2014a). Using biased randomization for solving the two-dimensional loading vehicle routing problem with heterogeneous fleet. Annals of Operations Research, 1–22.

  • Dominguez O, Juan AA and Faulin J (2014b). A biased‐randomized algorithm for the two‐dimensional vehicle routing problem with and without item rotations. International Transactions in Operational Research 21 (3): 375–398.

    Article  Google Scholar 

  • Duhamel C, Lacomme P, Quilliot A and Toussaint H (2009). 2L-CVRP: A GRASP resolution scheme based on RCPSP. In: IEEE International Conference on Computers & Industrial Engineering, 6–9 July 2009, Troyes, France, Conference Publications, pp 1094-1099. doi:10.1109/ICCIE.2009.5223772.

  • Duhamel C, Lacomme P, Quilliot A and Toussaint H (2011). A multi-start evolutionary local search for the two-dimensional loading capacitated vehicle routing problem. Computers & Operations Research 38 (3): 617–640.

    Article  Google Scholar 

  • Fuellerer G, Doerner K, Hartl R and Iori M (2009). Ant colony optimization for the two-dimensional loading vehicle routing problem. Computers and Operations Research 36 (3): 655–673.

    Article  Google Scholar 

  • Gendreau M, Iori M, Laporte G and Martello S (2008). A tabu search heuristic for the vehicle routing problem with two-dimensional loading constraints. Networks 51 (1): 4–18.

    Article  Google Scholar 

  • Gendreau M, Laporte G, Musaraganyi C and Taillard ÉD (1999). A tabu search heuristic for the heterogeneous fleet vehicle routing problem. Computers & Operations Research 26 (12): 1153–1173.

    Article  Google Scholar 

  • Golden B, Assad A, Levy L and Gheysens F (1984). The fleet size and mix vehicle routing. Computers & Operations Research 11 (1): 49–66.

    Article  Google Scholar 

  • Golden B, Raghavan S and Wasil E (eds.) (2008). The Vehicle Routing Problem: Latest Advances and New Challenges. Springer: New York.

    Book  Google Scholar 

  • Herrero R, Rodríguez A, Cáceres–Cruz J and Juan AA (2014). Solving vehicle routing problems with asymmetric costs and heterogeneous fleets. International Journal of Advanced Operations Management 6 (1): 58–80.

    Article  Google Scholar 

  • Iori M and Martello S (2010). Routing problems with loading constraints. TOP 18 (1): 4–27.

    Article  Google Scholar 

  • Iori M, Salazar JJ and Vigo D (2007). An exact approach for the vehicle routing problem with two-dimensional loading constraints. Transportation Science 41 (2): 253–264.

    Article  Google Scholar 

  • Juan A, Faulin J, Ferrer A, Lourenço H and Barrios B (2013a). MIRHA: Multi-start biased randomization of heuristics with adaptive local search for solving non-smooth routing problems. TOP 21 (1): 109–132.

    Article  Google Scholar 

  • Juan AA, Faulin J, Jorba J, Caceres J and Marques J (2013b). Using parallel & distributed computing for solving real-time vehicle routing problems with stochastic demands. Annals of Operations Research 207 (1): 43–65.

    Article  Google Scholar 

  • Juan A, Faulin J, Jorba J, Riera D, Masip D and Barrios B (2011). On the use of Monte Carlo simulation, cache and splitting techniques to improve the Clarke and Wright saving heuristics. Journal of the Operational Research Society 62 (6): 1085–1097.

    Article  Google Scholar 

  • Juan AA, Faulin J, Ruiz R, Barrios B and Caballè S (2010). The SR-GCWS hybrid algorithm for solving the capacitated vehicle routing. Applied Soft Computing 10 (1): 215–224.

    Article  Google Scholar 

  • Khebbache-Hadji S, Prins C, Yalaoui A and Reghioui M (2013). Heuristics and memetic algorithm for the two-dimensional loading capacitated vehicle routing problem with time windows. Central European Journal of Operations Research 21 (2): 307–336.

    Article  Google Scholar 

  • Leung SC, Zheng J, Zhang D and Zhou X (2010). Simulated annealing for the vehicle routing problem with two-dimensional loading constraints. Flexible Services and Manufacturing Journal 22 (1–2): 61–82.

    Article  Google Scholar 

  • Leung SC, Zhou X, Zhang D and Zheng J (2011). Extended guided tabu search and a new packing algorithm for the two-dimensional loading vehicle routing problem. Computers & Operations Research 38 (1): 205–215.

    Article  Google Scholar 

  • Leung SC, Zhang Z, Zhang D, Hua X and Lim MK (2013). A meta-heuristic algorithm for heterogeneous fleet vehicle routing problems with two-dimensional loading constraints. European Journal of Operational Research 225 (2): 199–210.

    Article  Google Scholar 

  • Lima CDR, Goldbarg MC and Goldbarg EFG (2004). A memetic algorithm for the heterogeneous fleet vehicle routing problem. Electronic Notes in Discrete Mathematics 18: 171–176.

    Article  Google Scholar 

  • Liu S, Huang W and Ma H (2009). An effective genetic algorithm for the fleet size and mix vehicle routing problems. Transportation Research Part E: Logistics and Transportation Review 45 (3): 434–445.

    Article  Google Scholar 

  • Lodi A, Martello S and Vigo D (1999). Heuristic and metaheuristic approaches for a class of two-dimensional bin packing problems. INFORMS Journal on Computing 11 (4): 345–357.

    Article  Google Scholar 

  • Lourenço HR, Martin OC and Stützle T (2003). Iterated local search. In: Glover F and Kochenberger G (eds). Handbook of Metaheuristics. Kluwer Academic Publishers: Norwell, MA, pp 321–353.

    Google Scholar 

  • Malapert A, Guéret C, Jussien N, Langevin A and Rousseau L-M (2008). Two-dimensional pickup and delivery routing problem with loading constraints. In: 1st Workshop on Bin Packing and Placement Constraints (BPPC’08), Paris.

  • Ochi LS, Vianna DS, Drummond LM and Victor AO (1998a). An Evolutionary Hybrid Metaheuristic for Solving the Vehicle Routing Problem with Heterogeneous fleet. In Genetic Programming. Springer: Berlin Heidelberg, pp 187–195.

    Google Scholar 

  • Ochi LS, Vianna DS, Drummond LM and Victor AO (1998b). A Parallel Evolutionary Algorithm for the Vehicle Routing Problem with Heterogeneous Fleet. In Parallel and Distributed Processing. Springer: Berlin Heidelberg, pp 216–224.

    Google Scholar 

  • Osman IH and Salhi S (1996). Local search strategies for the vehicle fleet mix problem. In: Rayward- Smith VJ, Osman IH, Reeves CR and Smith GD (eds). Modern Heuristic Search Methods. Wiley: Chichester, pp 131–153.

    Chapter  Google Scholar 

  • Pessoa A, Uchoa E and Poggi de Aragão M (2009). A robust branch‐cut‐and‐price algorithm for the heterogeneous fleet vehicle routing problem. Networks 54 (4): 167–177.

    Article  Google Scholar 

  • Prins C (2009). A GRASP × Evolutionary local search hybrid for the vehicle routing problem. In: Pereira FB and Tavares J (eds). Bio-inspired Algorithms for the Vehicle Routing Problem. Studies in Computational Intelligence, Vol. 161 (Springer): Berlin, pp 35–53.

    Chapter  Google Scholar 

  • Riff MC, Bonnaire X and Neveu B (2009). A revision of recent approaches for two-dimensional strip-packing problems. Engineering Applications of Artificial Intelligence 22 (4): 823–827.

    Article  Google Scholar 

  • Taillard ÉD (1999). A heuristic column generation method for the heterogeneous fleet VRP. RAIRO-Operations Research 33 (01): 1–14.

    Article  Google Scholar 

  • Tarantilis CD, Kiranoudis CT and Vassiliadis VS (2003). A list based threshold accepting metaheuristic for the heterogeneous fixed fleet vehicle routing problem. Journal of the Operational Research Society 54 (1): 65–71.

    Article  Google Scholar 

  • Tarantilis CD, Kiranoudis CT and Vassiliadis VS (2004). A threshold accepting metaheuristic for the heterogeneous fixed fleet vehicle routing problem. European Journal of Operational Research 152 (1): 148–158.

    Article  Google Scholar 

  • Tarantilis CD, Zachariadis EE and Kiranoudis CT (2008). A guided tabu search for the heterogeneous vehicle routeing problem. Journal of the Operational Research Society 59 (12): 1659–1673.

    Article  Google Scholar 

  • Toth P and Vigo D (2002). The Vehicle Routing Problem. SIAM Publishers: Philadelphia, PA.

    Book  Google Scholar 

  • Wang F, Tao Y and Shi N (2009). A survey on vehicle routing problem with loading constraints. In Computational Sciences and Optimization, 2009. CSO 2009. International Joint Conference on (Vol. 2, pp. 602–606). IEEE.

  • Zachariadis EE, Tarantilis CD and Kiranoudis CT (2009). A guided tabu search for the vehicle routing problem with two-dimensional loading constraints. European Journal of Operational Research 195 (3): 729–743.

    Article  Google Scholar 

  • Zachariadis EE, Tarantilis CD and Kiranoudis CT (2013). Integrated distribution and loading planning via a compact metaheuristic algorithm. European Journal of Operational Research 228 (1): 56–71.

    Article  Google Scholar 

Download references

Acknowledgements

This work has been partially supported by the Spanish Ministry of Economy and Competitiveness (grant TRA2013-48180-C3-P), FEDER, and the Department of Universities, Research & Information Society of the Catalan Government (Grant 2014-CTP-00001).

Author information

Authors and Affiliations

  1. University of Las Palmas de Gran Canaria, Las Palmas de Gran Canaria, Spain

    Oscar L Domínguez Rivero & Ignacio A de la Nuez Pestana

  2. IN3—Open University of Catalonia, Barcelona, Spain

    Angel A Juan Pérez

  3. University of Portsmouth, Portsmouth, UK

    Djamila Ouelhadj

Authors
  1. Oscar L Domínguez Rivero
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Angel A Juan Pérez
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Ignacio A de la Nuez Pestana
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Djamila Ouelhadj
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Domínguez Rivero, O., Juan Pérez, A., de la Nuez Pestana, I. et al. An ILS-biased randomization algorithm for the two-dimensional loading HFVRP with sequential loading and items rotation. J Oper Res Soc 67, 37–53 (2016). https://doi.org/10.1057/jors.2015.48

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1057/jors.2015.48

Keywords

Search

Navigation