Parameter Tuning of a Local Search Heuristic for a Vehicle Routing Problem with Loading Constraints

Hanne Pollaris, Gerrit Karel Janssens, Kris Braekers, An Caris

Abstract


A vehicle routing problem (VRP) with sequence-based pallet loading and axle weight constraints is introduced in the study. An Iterated Local Search (ILS) metaheuristic algorithm is used to solve the problem. Like any metaheuristic, a number of parameters need to be set before running the experiments. Parameter tuning is important because the value of the parameters may have a substantial impact on the efficacy of a heuristic algorithm. While traditionally, parameter values have been set manually using expertise and experimentation, recently several automated tuning methods have been proposed. The performance of the routing algorithm is mostly improved by using parameter tuning, but no single best tuning method for routing algorithms exists. The tuning method, Iterated F-race, is chosen because it seems to be a very robust method and it has been shown to perform well on the ILS metaheuristic and other metaheuristics. The research aims at developing an algorithm, which performs well over a wide range of network sizes.


Keywords:
Decision making; evolutionary computation; operations research; supply chain management

Full Text:

 PDF

References


J. Caceres-Cruz, et al. “Rich Vehicle Routing Problem: Survey”, ACM Computing Surveys, vol. 47, no. 2, Article 32, 2014. https://doi.org/10.1145/2666003

R. F. Hartl, G. Hasle, and G. K. Janssens, “Special issue on rich vehicle routing problems”, Central European Journal of Operations Research, vol. 14, no. 2, pp. 103–104, 2006. https://doi.org/10.1007/s10100-006-0162-9

G. Hasle, and O. Kloster, “Industrial vehicle routing”. In Geometric Modelling, Numerical Simulation, and Optimization, G. Hasle, K. A. Lie, and E. Quak (Eds). Springer, Berlin, pp. 397–435, 2007. https://doi.org/10.1007/978-3-540-68783-2_12

H. Pollaris, et al. “Vehicle routing problems with loading constraints: State-of-the-art and future directions”, OR Spectrum, vol. 37, pp. 297–330, 2015. https://doi.org/10.1007/s00291-014-0386-3

B. Jacob, and V. F.-de La Beaumelle, “Improving truck safety: potential of weigh-in-motion technology”, IATSS (International Association of Traffic and Safety Science) Research, vol. 34, no. 1, pp. 9–15, 2010. https://doi.org/10.1016/j.iatssr.2010.06.003

T. Vidal, G. Laporte, and P. Matl, “A concise guide to existing and emerging vehicle routing problem variants”, European Journal of Operational Research, vol. 286, no. 2, pp. 401–416, 2020. https://doi.org/10.1016/j.ejor.2019.10.010

A. Lim, et al. “The single container loading problem with axle weight constraints”, International Journal of Production Economics, vol. 144, no. 1, pp. 358–369, 2013. https://doi.org/10.1016/j.ijpe.2013.03.001

M. T. Alonso, et al. “Mathematical models for multicontainer loading problems”, Omega, vol. 66, Part A, pp. 106–117, 2013. https://doi.org/10.1016/j.omega.2016.02.002

H. Pollaris, et al. “Capacitated vehicle routing problem with sequence-based pallet loading and axle weight constraints”, EURO Journal of Transportation and Logistics, vol. 5, no. 2, pp. 231–255, 2016. https://doi.org/10.1007/s13676-014-0064-2

H. Pollaris, et al. “Iterated local search for the capacitated vehicle routing problem with sequence-based pallet loading and axle weight constraints”, Networks, vol. 69, no. 3, pp. 304–316, 2017. https://doi.org/10.1002/net.21738

M. Iori, and S. Martello, “Routing problems with loading constraints”, TOP, vol. 18, pp. 4–27, 2010. https://doi.org/10.1007/s11750-010-0144-x

H. R. Lourenço, O. C. Martin, and T. Stützle, “Iterated local search: framework and applications”. In Gendreau, M. and Potvin, J. Y. (eds), Handbook of Metaheuristics. International Series in Operations Research & Management Science, vol. 146, pp. 363–397, 2010. Springer, Boston. https://doi.org/10.1007/978-1-4419-1665-5_12

A. A Juan, et al. “Combining biased randomization with iterated local search for solving the multidepot vehicle routing problem”, International Transactions in Operational Research, vol. 22, no. 4, pp. 647–667, 2015. https://doi.org/10.1111/itor.12101

J. Brandao, “Iterated local search algorithm with ejection chains for the open vehicle routing problem with time windows”, Computers & Industrial Engineering, vol. 120, pp. 146–159, 2018. https://doi.org/10.1016/j.cie.2018.04.032

P. Chen, H. Huang, and X.-Y. Dong, “Iterated variable neighbourhood descent algorithm for the capacitated vehicle routing problem”, Expert Systems with Applications, vol. 37, no. 2, pp. 1620–1627, 2010. https://doi.org/10.1016/j.eswa.2009.06.047

C. Waters, “A solution procedure for the vehicle scheduling problem based on iterative route improvement”, Journal of the Operational Research Society, vol. 38, no. 9, pp. 833–839, 1987. https://doi.org/10.1057/jors.1987.137

G. A. Croes, “A method for solving traveling salesman problems”, Operations Research, vol. 6, no. 6, pp. 791–812, 1958. https://doi.org/10.1287/opre.6.6.791

E. Taillard, et al. “A tabu search heuristic for the vehicle routing problem with soft time windows”, Transportation Science, vol. 31, no. 2, pp. 170–186, 1997. https://doi.org/10.1287/trsc.31.2.170

S. Ropke, and D. Pisinger, “An adaptive neighbourhood search heuristic for the pickup and delivery problem with time windows”, Transportation Science, vol. 40, no. 4, pp. 455–472, 2006. https://doi.org/10.1287/trsc.1050.0135

H. H. Hoos, “Automated algorithm configuration and parameter tuning”. In Hamadi, Y., Monfroy, E., Saubion, F. (Eds), Autonomous Search. Springer, Berlin, Heidelberg, pp. 37–71, 2012. https://doi.org/10.1007/978-3-642-21434-9_3

P. Pellegrini, and M. Birattari, “Out-of-the-box and custom implementation of metaheuristics. A case study: The vehicle routing problem with stochastic demand.” In Köppen, M., Schaefer, G., Abraham, A. (Eds), Intelligent Computational Optimization in Engineering Techniques and Applications. Springer, Berlin, Heidelberg, pp. 273–295, 2011. https://doi.org/10.1007/978-3-642-21705-0_10

M. Birattari, et al. “A racing algorithm for configuring metaheuristics.” In Proceedings of the Genetic and Evolutionary Computation Conference GECCO ’02. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, pp. 11–18, 2002.

J. Rasku, N. Musliu, and T. Kärkkäinen, T. “Automating the parameter selection in VRP: an off-line parameter tuning tool comparison.” In Fitzgibbon, W., Kuznetsov, A. Y., Neittaanmäki, P., Pironneau, O. (Eds), Modeling, Simulation and Optimization for Science and Technology, vol. 34, pp. 191–209, 2014. Springer, Netherlands. https://doi.org/10.1007/978-94-017-9054-3_11

M. Lopez-Ibanez, et al. “The irace package Iterated racing for automatic algorithm configuration”, Operations Research Perspectives, vol. 3, pp. 43–58, 2016.

M. Birattari, Tuning Metaheuristics: A Machine Learning Perspective, 1st Edition. Springer Publishing Company, 2009. https://doi.org/10.1007/978-3-642-00483-4

S. Ceschia, A. Schaerf, and T. Stützle, “Local search techniques for a routing packing problem”, Computers & Industrial Engineering, vol. 66, no. 4, pp. 1138–1149, 2013. https://doi.org/10.1016/j.cie.2013.07.025

V. François, et al. “Large neighborhood search for multi-trip vehicle routing”, European Journal of Operational Research, vol. 255, no. 2, pp. 422–441, 2016. https://doi.org/10.1016/j.ejor.2016.04.065




DOI: 10.7250/itms-2020-0008

Refbacks

  • There are currently no refbacks.


Copyright (c) 2020 Gerrit Karel Janssens, Hanne Pollaris, Kris Braekers, An Caris

Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.