Consolidation and coordination of routes in urban distribution

In this thesis, two relevant aspects of routing in the urban environment are studied. In the first part of the thesis, the implications of considering release dates when planning for delivery from distribution centers are discussed. The routing problems with release dates are contextualized in the class of routing problems, and in particular, in the class of routing problems in which timing decisions must be considered. The Traveling Salesman Problem with release dates and completion time minimization is studied. Properties are introduced for the problem and a formulation is proposed. Two variants of a heuristic algorithm are tested against the optimal solution and shown to provide high quality results. The benefits of considering release dates are assessed by comparing the results with those obtained disregarding the release dates and delivering the parcels as soon as they arrive to the distribution center. The study on routing problems with release dates is then expanded to consider the stochastic and dynamic nature of the release dates. A reoptimization technique is proposed to tackle the dynamic aspect of the problem. Three reoptimization policies are proposed, with increasing reoptimization frequency, together with two models for the solution of the problem. The first is a stochastic model, considering the entire probabilistic information available for the release dates, and the second is a deterministic model, where a point estimation is used. The stochastic model is shown to perform better than the deterministic model, at the expense of the computational time required to evaluate any of the solutions explored. The second part of the thesis is focused on the management of the loading and unloading areas in the city center. Urban distribution requires vehicles to temporarily stop to perform the last leg of the delivery by foot. If a spot is not available, vehicles resort to double parking which is a known cause of road congestion. Two booking management systems and the arising routing problems are presented. The solutions provided by the two systems are compared with the current state of the distribution.