Package Merging And Time Windows:A Two-Stage Optimization Algorithm To Improve Package Delivery

Pickup and Delivery Problems(PDP) appear in a wide range of logistics systems in the transportation science domain. Their optimization seeks for an assignment, which can be in the form of a schedule, of a set of pickup and delivery requests to a fleet of vehicles in a way that satisfies the defined constraints and at the same time minimizes a particular cost function. The work presented in this thesis introduces the Package Merging Pickup and Delivery Problem(PM-PDP) attached to an optimization time scheduling model. In this version of problem, the PDP is extended to consider single, multiple, arbitrary and dynamic transfer points where vehicles can exchange, pick up or deliver load at multiple locations. We define and present a complete mathematical formulation of the general case of the PDP, followed by an explanation of how adding transfers makes the problem more challenging and the respective mathematical depiction.To solve the problem, the PDP model is embedded in a two-stage optimization framework. The first stage consists of applying a directed graph solution approach to build delivery schedules with transfers from scratch, contrasting the tendency in literature of inserting transfer heuristics once the initial solution is obtained. The second stage consists of an optimization model to rearrange sequential tasks. By splitting the implementation into two stages we are able to, first, build arrays of smaller-scale schedules which together construct a complete operation schedule; and second, to maximize the productive vehicle operating time usually generated when working under hard time window constraints. This approach is beneficial mainly because solving the PDP optimally for large scale problems is impractical, and because the rearrangement of the output schedule transforms the maximum possible unproductive time in productive.Furthermore, computational results that show the benefits of the model are provided, obtaining near optimal solutions by implementing it on realistic instances. Additional contributions include analytical and computational validations of the model, an analysis of the benefits of implementing multiple stage models in delivery processes, and the setup and solution of a real-life prototype system.