The last mile two-level delivery problem : identifying key elements and developing a functional heuristic

The importance of freight movement in large urban centers feature last mile logistics as a contemporary challenge. Matters regarding current public policies and private state-of-practice need to contemplate short and long term planning, market dynamics and economic concerns. A way of contributing to this subject is through modelling techniques. The proposed study concerns the hereby called ‘Last mile two-level delivery problem’, encompassing a highly constrained urban delivery problem in which a set of routes for a fleet of vehicles must be programed. Issues arising from volume and weight capacity, vehicle type compatibility, metropolitan districts knowledge, business relationships between long-haul transporters and last mile carriers, optional deliveries, vehicle exclusivity, and time window respect must be considered. The objective lays in finding scenarios performing most favorable values for a compound objective function, which considers both reducing the longest route and maximizing the number of optional products served. Based on the examination of the literature, the author offers a bi-level program method to cope with this problem. In the first level, a primary decision in assigning products to vehicles is provided, pondering the aforementioned restrictions. In the second one, vehicle routes are heuristically established using a nearest neighborhood algorithm. Further efforts run reallocating already assigned products and inserting optional ones at a higher level. Iteratively, interfaces between both levels and a reevaluation on each step support guidance to the succeeding operations. Tests are performed using manufactured instances from different sources, from benchmark ones to real-world data. A discussion on the obtained results is provided, following a sensitivity analysis on the algorithm and a rationalization on potential techniques to assess the generated vehicle routes more in-depth.

Nell’ambito del trasporto merci in grandi centri urbani, la logistica di ultimo miglio rappresenta una sfida contemporanea. Le politiche pubbliche e la pratica privata dovrebbero tenere conto della pianificazione a breve e lungo termine, delle dinamiche di mercato e degli interessi economici di questo tipo di logistica. Ciò può avvenire in modo razionale attraverso tecniche di modellazione. Lo studio proposto riguarda il cosiddetto ‘Last mile two-level delivery problem’, che consiste nella pianificazione del percorso di una flotta di veicoli per consegne multiple in presenza di un ambiente urbano altamente vincolato. In tale problema devono essere presi in considerazione aspetti quali le capacità del veicolo in termini di volume e peso, la compatibilità tra tipologie di veicolo e prodotti, la conoscenza pregressa di aree metropolitane da parte degli autisti, le relazioni commerciali tra i trasportatori a lungo raggio e i vettori dell'ultimo miglio, l’esistenza di consegne opzionali, l’esclusività dei veicoli, e il rispetto delle time windows. Il problema ha due obiettivi: sia la minimizzazione del percorso più lungo che la massimizzazione del numero di prodotti opzionali serviti. Attraverso il primo obiettivo si vuole garantire che il carico di lavoro sia equamente distribuito tra i veicoli e che il percorso totale sia minimizzato. Sulla base dell’analisi della letteratura scientifica, si individua un metodo di programmazione bi-livello per far fronte a questo problema. Nel primo livello, viene fornita la decisione di come assegnare i prodotti ai veicoli, tenendo conto delle suddette limitazioni. Nel secondo livello, i percorsi dei veicoli sono euristicamente determinati utilizzando l'algoritmo nearest neighborhood. Ulteriori sforzi si concentrano sulla riallocazione di prodotti già assegnati e sull'inserimento di quelli opzionali ad un livello superiore. Iterativamente, l'interazione tra i due livelli e una rivalutazione ad ogni passo supportano le operazioni successive. L’algoritmo è stato sviluppato in linguaggio C e testato su istanze del problema di vehicle routing ottenute da fonti diverse: sia da modelli di benchmark che dati reali. È fornita una discussione sui risultati ottenuti, a seguito di un'analisi di sensitività dell’algoritmo e una esposizione su possibili tecniche per valutare l’insieme dei percorsi generati in modo più approfondito.