Solving Last-Mile Deliveries for Dairy Products Using a Biased Randomization-Based Spreadsheet. A Case Study

Abstract

During recent years, Last-mile deliveries (LMD) have become relevant due to its application in e-commerce, urban logistics, and food delivery among others. This work addresses an LMD denoted as a Vehicle Routing Problem with time windows (VRPTW) and aims to minimize total time of the distribution process (i.e., makespan). The LMD is an NP-Hard problem that refers to the delivery of goods from a consolidation center to a destination. For solving the problem, a spreadsheet-based solution that employs a multi-start algorithm based on the biased-randomized version of the nearest neighbor heuristic is introduced. Real historical data of last-mile deliveries for dairy products in Bogotá (Colombia) was considered for evaluating our proposed method. Computational experiments are carried out to show the competitiveness of our method in terms of makespan, number of vehicles, average vehicle occupancy, average load and costs. Some insights for future works are also provided.

Durante los últimos años, las entregas de última milla (LMD) han cobrado relevancia debido a su aplicación en el comercio electrónico, la logística urbana y la entrega de alimentos, entre otros. Este trabajo aborda un LMD denominado Problema de enrutamiento de vehículos con ventanas de tiempo (VRPTW) y tiene como objetivo minimizar el tiempo total del proceso de distribución (es decir, los tiempos de entrega). El LMD es un problema NP-Hard que se refiere a la entrega de mercancías desde un centro de consolidación a un destino. Para resolver el problema, se presenta una solución basada en una hoja de cálculo que emplea un algoritmo de inicio múltiple basado en la versión aleatoria sesgada de la heurística del vecino más cercano. Para evaluar nuestro método propuesto se consideraron datos históricos reales de entregas de última milla de productos lácteos en Bogotá (Colombia). Se llevan a cabo experimentos computacionales para mostrar la competitividad de nuestro método en términos de marcas, número de vehículos, ocupación promedio de vehículos, carga promedio y costos. También se proporcionan algunas ideas para trabajos futuros.