Improving urban deliveries via collaboration

Abstract

Distribution of goods is essential for the economic development of cities but at the same time it entails several problems to the urban systems and different stakeholders. Carriers spend a significant portion of their cost in the last-mile distribution due to traffic congestion and lack of available loading/unloading facilities. In turn, citizens undergo environmental effects like pollution, noise or space competition. Collaborative transportation is currently one of the major trends in transportation research due to its potential benefits with little need for big infrastructure or costly investments. This thesis deals with three different situations that appear repeatedly in the urban context, which can be improved by means of collaboration among private companies and/or public authorities. The first part of the thesis studies a little-disruptive collaboration approach, which is based on sharing loading/unloading urban facilities via an in-advance booking system, managed by local public authorities. In this context, the Parking Slot Assignment Problem is the mathematical problem that finds assignments of carriers to parking places that satisfy their time windows requests. We propose a feasibility model first, and then four other models with various objective functions that penalize in different ways the deviation from the requested time windows. We propose and compare two different formulations: one with time as a continuous variable and a second one with time discretization. Finally, we evaluate and compare the different proposals with extensive computational experiments in a set of test instances. An intermediate level of collaboration among carriers is studied in the second part of this thesis. Urban areas have high customers density and usually there are shared customers (customers with demand from different carriers in the same time horizon). We propose an innovative problem: the Shared Customer Collaboration Vehicle Routing Problem, where several carriers are willing to collaborate transferring part of the demand of their shared customers, if the overall transportation cost is reduced. A vehicle-based and a load-based formulation are studied, and experimented over a specifically generated instance set. The highest level of collaboration in urban deliveries resorts to Urban Consolidation Centers, which are normally led by public authorities but need the collaboration of carriers for a successful implementation. Urban Consolidation Centers are urban terminals where the load from different carriers is consolidated and then, a unique neutral carrier performs last-mile deliveries. In the third part of the thesis we propose continuous models that analyze the improvement in efficiency of urban distribution with the use of Urban Consolidation Centers under different assumptions. Continuous approximation models are known to produce robust solutions, which are useful to provide guidelines for general cases through sensitive analysis. In the three parts of the thesis, innovative models and approaches are proposed and validated on experiments that use data from real scenarios.

La distribució urbana de mercaderies és una activitat essencial pel desenvolupament de les ciutats. Al mateix temps, però, comporta diversos problemes als nuclis urbans i als diferents actors involucrats. Els costos de la distribució urbana resulten una part molt significativa dels costos dels transportistes, especialment a causa de la congestió i la manca de zones de càrrega i descàrrega. Per altre banda, els ciutadans pateixen els efectes de la pol¢lució, el soroll o la competició per l’espai públic. El transport col¢laboratiu és actualment una de les principals tendències de recerca en transport, doncs ofereix beneficis atractius amb poca inversió. Aquesta tesi tracta tres situacions que trobem repetidament en el context urbà, situacions on diverses formes de col¢laboració poden representar una millora, i que consideren tant col¢laboració entre empreses privades com la col·laboració conjunta d’empreses privades amb les administracions. La primera part de la tesi estudia un nivell de col·laboració baix, basat en compartir les zones de càrrega i descàrrega gràcies a un sistema de reserves gestionat per l’administració. En aquest context, sorgeix el Parking Slot Assignment Problem (Problema d’assignació de places de parking), com el problemamatemàtic que assigna transportistes a places de parking satisfent els seus requeriments a través de finestres temporals. En primer lloc proposem un model de factibilitat, i després proposem quatremodelsamb funcions objectius desiguals que penalitzen la desviació de les finestres temporals de formes diferents. Es proposen i comparen dues formulacions: una amb el temps com una variable contínua, i la segona amb discretització temporal. Finalment, s’avaluen i es comparen les diferents propostes a través d’uns extensos experiments computacionals en un conjunt de test basat en dades reals. Un nivell intermedi de col¢laboració entre transportistes s’analitza en la segona part d’aquesta tesi. Les àrees urbanes presenten una alta densitat de clients i és comú trobar clients compartits (és a dir, clients que reben mercaderies a través de diferents transportistes en el mateix interval temporal). Proposem un problema innovador: el Shared Customer Collaboration Vehicle Routing Problem (Problema de rutes de vehicles amb col·laboració de clients compartits), on diferents transportistes estan disposats a col¢laborar transferint part de la demanda dels seus clients compartits, si el cost total de transport es redueix. S’estudien dues formulacions: una basada en els vehicles i una altra basada en la càrrega, i s’experimenta en un conjunt d’instàncies generades. El màxim nivell de col¢laboració en distribució urbana de mercaderies és l’ús de centres de consolidació urbana. Aquests centres estan normalment liderats per l’administració pública però necessiten l’activa col·laboració dels transportistes per aconseguir una implantació amb èxit. Els centres de consolidació urbana són terminals urbanes on es consolida la càrrega dels diferents transportistes i després, un únic transportista neutral realitza la distribució d’última milla. En aquesta tercera part de la tesi proposem models continus que analitzen la millora de l’eficiència en la distribució urbana a través de l’ús de centres de consolidació urbana amb diferents hipòtesis. Els models continus produeixen solucions robustes, que són útils per proporcionar guies en casos genèrics a través de l’anàlisi de sensibilitat. En les tres parts de la tesi es proposen nous enfocs i models que es validen a través d’experiments utilitzant dades obtingudes d’escenaris reals

La distribución urbana de mercancías es una actividad esencial para el desarrollo de las ciudades, aunque al mismo tiempo conlleva diversos problemas en los núcleos urbanos y los distintos actores involucrados. Los costes de la distribución urbana resultan una parte muy significativa de los costes de los transportistas, especialmente a causa de la congestión y la falta de zonas de carga y descarga. Por otro lado, los ciudadanos sufren los efectos de la contaminación, el ruido y la competición por el espacio público. El transporte colaborativo es actualmente una de las principales tendencias en la investigación en transporte, pues ofrece beneficios atractivos con poca inversión. Esta tesis trata tres situaciones que se reproducen repetidamente en el contexto urbano, donde distintas formas de colaboración (tanto entre compañías privadas como con administraciones) pueden representar una mejora. La primera parte de la tesis estudia un nivel de colaboración bajo, basado en compartir las zonas de carga y descarga a través de un sistema de reservas gestionado por la administración. En este contexto surge el Parking Slot Assignment Problem (Problema de asignación de plazas de parking), como el problema matemático que asigna transportistas a plazas de parking satisfaciendo sus requerimientos a través de ventanas temporales. En primer lugar proponemos un modelo de factibilidad, y después cuatro modelos con funciones objetivo que penalizan la desviación de las ventanas temporales de formas distintas. Se proponen y comparan dos formulaciones: una con el tiempo como una variable continua, y la segunda con discretización temporal. Finalmente, se evalúa y compara las distintas propuestas a través de unos extensos experimentos computacionales en un conjunto de test basado en datos reales. Un nivel intermedio de colaboración entre transportistas se analiza en la segunda parte de esta tesis. Las áreas urbanas presentan una alta densidad de clientes, y es común encontrar clientes compartidos (es decir, clientes que reciben mercancías a través de distintos transportistas en el mismo intervalo temporal). Proponemos un problema innovador: el Shared Customer Collaboration Vehicle Routing Problem (Problema de rutas de vehículos con colaboración de clientes compartidos), donde los distintos transportistas están dispuestos a colaborar transfiriendo parte de la demanda de sus clientes compartidos, si el coste total del transporte se reduce. Estudiamos dos formulaciones: una basada en los vehículos y otra basada en la carga, y se experimenta en un conjunto de instancias generadas. El máximo nivel de colaboración en distribución urbana de mercancías es el uso de centros de consolidación urbana. Estos centros, normalmente liderados por la administración pública, necesitan la activa colaboración de los transportistas para conseguir una exitosa implantación. Se trata de terminales urbanas donde se consolida la carga de distintos transportistas y, después, un único transportista neutral realiza la distribución de última milla. En esta tercera parte de la tesis proponemos modelos continuos que analizan la mejora de la eficiencia en la distribución urbana a través del uso de centros de consolidación urbana con distintas hipótesis. Los modelos continuos producen soluciones robustas, que son útiles para proporcionar guías en casos genéricos a través del análisis de sensibilidad. En las tres partes de la tesis se proponen nuevos enfoques y modelos que se validan con experimentos utilizando datos obtenidos en escenarios reales