A biased-randomized iterated local search for the vehicle routing problem with optional backhauls

Abstract

The vehicle routing problem with backhauls integrates decisions on product delivery with decisions on the collection of returnable items. In this paper, we analyze a scenario in which collection of items is optional—but subject to a penalty cost. Both transportation costs and penalties associated with non-collecting decisions are considered. A mixed-integer linear model is proposed and solved for small instances. Also, a metaheuristic algorithm combining biased randomization techniques with iterated local search is introduced for larger instances. Our approach yields cost savings and is competitive when compared to other state-of-the-art approaches. © 2020, Sociedad de Estadística e Investigación Operativa.

El problema de las rutas de vehículos con los retornos integra decisiones sobre la entrega de productos con decisiones sobre la recolección de artículos retornables. En este artículo, analizamos un escenario en el que la recolección de artículos es opcional, pero está sujeta a un costo de penalización. Se consideran tanto los costos de transporte como las sanciones asociadas a decisiones de no cobro. Se propone y resuelve un modelo lineal entero mixto para instancias pequeñas. Además, para instancias más grandes se introduce un algoritmo metaheurístico que combina técnicas de aleatorización sesgada con búsqueda local iterada. Nuestro enfoque genera ahorros de costos y es competitivo en comparación con otros enfoques de última generación. © 2020, Sociedad de Estadística e Investigación Operativa.