Abstract
We study a variant of the vehicle routing problem with multiple compartments in which compartment sizes are flexibly adjustable in discrete steps. Additionally, a last-in-first-out unloading policy has to be considered since rearranging of cargo on the load bed is prohibited. This problem occurs as a special case at a German food retailer that has to supply a large number of hypermarkets on a daily basis. Transported products are divided into several categories based on the transport temperature. Due to these different temperatures, it is expedient to use trucks with multiple compartments. Moreover, the retailer engages various forwarders for transportation. Forwarders are paid according to previously negotiated tariffs based on the different product categories. This leads to a cost function that differs a lot from the common distance minimization. We propose an iterated tabu search with two different perturbation mechanisms to solve this challenging vehicle routing problem. Various computational experiments with real data from the retailer are performed to assess the performance of our algorithm. Comparisons with results obtained by employing a mixed integer program and solving this with a commercial solver show that the iterated tabu search consistently produces high quality solutions.
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.-F., Maischberger, M.: A parallel iterated tabu search heuristic for vehicle routing problems. Comput. Oper. Res. 39(9), 2033–2050 (2012)
Henke, T., Speranza, M.G., Wäscher, G.: The multi-compartment vehicle routing problem with flexible compartment sizes. Eur. J. Oper. Res. 246(3), 730–743 (2015)
Hübner, A., Ostermeier, M.: A multi-compartment vehicle routing problem with loading and unloading costs. Transp. Sci. 53(1), 282–300 (2018)
Lourenço, H.R., Martin, O.C., Stützle, T.: Iterated local search. In: Glover, F., Kochenberger, G.A. (eds.) Handbook of Metaheuristics, chapter 11, pp. 320–353. Springer, Boston (2003)
Misevičius, A.: Using iterated tabu search for the traveling salesman problem. Inf. Technol. Control 32(3), 29–40 (2004)
Silvestrin, P.V., Ritt, M.: An iterated tabu search for the multi-compartment vehicle routing problem. Comput. Oper. Res. 81, 192–202 (2017)
Tamke, F.: A mixed-integer programming model for a vehicle routing problem in the food retailing industry. Dresdner Beiträge zur Betriebswirtschaftslehre 181, 18 (2018)
Vidović, M., Popović, D., Ratković, B.: Mixed integer and heuristics model for the inventory routing problem in fuel delivery. Int. J. Prod. Econ. 147, 593–604 (2014)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer Nature Switzerland AG
About this paper
Cite this paper
Tamke, F. (2019). An Iterated Tabu Search for the Vehicle Routing Problem with Multiple Compartments and Last-in-First-Out Unloading. In: Fortz, B., Labbé, M. (eds) Operations Research Proceedings 2018. Operations Research Proceedings. Springer, Cham. https://doi.org/10.1007/978-3-030-18500-8_37
Download citation
DOI: https://doi.org/10.1007/978-3-030-18500-8_37
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-18499-5
Online ISBN: 978-3-030-18500-8
eBook Packages: Mathematics and StatisticsMathematics and Statistics (R0)