Riassunto analitico
Negli ultimi decenni abbiamo assistito ad un persistente processo di riscaldamento globale causato da diversi fattori, come il settore industriale, il traffico veicolare, la deforestazione e gli allevamenti intensivi. Il continuo sviluppo tecnologico e il conseguente cambio di mentalità dei consumatori ha portato alla creazione di servizi come gli e-commerce, che hanno contribuito all’accentuazione dei problemi legati alla salvaguardia dell’ambiente, incrementando drasticamente il traffico veicolare e creando la necessità di trovare soluzioni per fornire un adeguato servizio ai clienti, abbattendone i costi. In questo contesto la sharing economy, riguardante il campo dei trasporti, può svolgere un ruolo fondamentale.
Considerando la letteratura, abbiamo studiato un problema di delivery dal punto di vista di un’azienda di consegne che ha a disposizione un numero limitato di corrieri. A questa si unisce la disponibilità, da parte di persone comuni, di trasportare anche solo per una parte di tragitto queste merci, sfruttano percorsi che farebbero in ogni caso e accettando una possibile deviazione da quello che sarebbe il loro tragitto ottimo. Dopo un’attenta analisi dei vari approcci a questa tematica, abbiamo formalizzato il problema come un Multi-Hop Crowdshipping Problem con Time Windows e Locker points. Abbiamo sviluppato in Java un modello matematico di tipo MILP (mixed integer linear programming) con lo scopo di ottimizzare i processi di consegna, minimizzando la funzione di costo, con l’obbiettivo di ridurre drasticamente le emissioni e i costi di gestione. Le consegne sono effettuate rispettando limiti di capacità e di tempo imposti da persone e pacchi. Abbiamo inoltre considerato la possibilità che i pacchi possano essere trasferiti tra diverse persone, prima di arrivare a destinazione (multi-hop).
Successivamente, per ridurre la complessità dei dati di input abbiamo implementato un algoritmo di speed-up. Esso viene processato prima dell’esecuzione del modello e ha lo scopo di ridurre il numero di variabili totali, diminuendo di conseguenza i tempi computazionali. Infine, abbiamo proposto un algoritmo euristico di tipo MILP-based che esegue iterativamente il modello con istanze di dimensione ridotta. In questo modo abbiamo ottenuto tempi computazionali molto minori, a scapito di soluzioni leggermente lontane dall’ottimo.
Per effettuare test adeguati, abbiamo sviluppato un processo in grado di generare istanze random, in modo tale da simulare diverse situazioni e casi particolari.
|
Abstract
In the last decades we have witnessed a persistent process of global warming caused by various factors, such as industrial sector, road traffic, deforestation, and intensive farming. The incessant technological development and the consequent change of mentality of customers have led to the creation, and massively utilization, of services like e-commerce. These new platforms have contributed to the accentuation of problems related to environmental protection. They have created the need for optimization solutions about logistic and economic topics. The delivery process has to be completed minimizing road traffic and cost, but at the same time it must be able to provide a high level of customer service. In this context, the sharing economy in the transportation field can play a significant role.
Considering the literature, we have studied a delivery problem with the point of view of a shipping company that has a limited number of couriers available. In addition to this, we take into account a set of common people that make themselves available to carry the parcels. This delivery process takes place along routes that common people would take anyway, accepting small detours.
After a careful analysis of the various approaches to this issue, we formalized the problem as a Multi-Hop Crowdshipping Problem with Time Windows and Locker points.
We have developed a MILP (mixed integer linear programming) mathematical model in Java with the aim of optimizing delivery processes, minimizing the cost function. Deliveries are made respecting capacity and time limits imposed by people and packages. We also considered the possibility that packages can be transferred between different people, before arriving at their destination (multi-hop).
Subsequently, to reduce the complexity of the input data, we have implemented a speed-up algorithm. It is processed before the execution of the model and has the purpose of reducing the number of total variables, consequently decreasing the computational times. Finally, we have proposed a MILP-based heuristic algorithm that iteratively executes the model with reduced-size instances.
In this way we have obtained much shorter computational times, at the expense of solutions slightly far from optimal. To carry out adequate tests, we have developed a process capable of generating random instances, in order to simulate different situations and particular cases.
|
