Reyes Rodriguez, Luis Damian Reyes ; Savelsbergh, Martin W. P. Erera, Alan L. Industrial and Systems Engineering Toriello, Alejandro Sun, Andy Kalkanci, Basak ; Savelsbergh, Martin W. P.
In the last decade, tied to the rise of e-commerce activities, direct-to-consumer deliveries have grown at a rapid pace in metropolitan areas across the world, and expectations on service standards become higher and higher every year. The economic, social and environmental sustainability of last-mile logistics poses a formidable societal challenge, demanding major organizational changes and technological inventions in transportation, the success of which will critically depend on the availability of appropriate optimization tools. In this thesis, we study two recent innovations in last-mile delivery from an optimization perspective: i) roaming delivery systems, where the customer orders are delivered to the trunk of their cars, as opposed to traditional home delivery; and ii) dynamic delivery systems, where vehicles deliver goods locally from an origin depot (or, perhaps a small number of origin depots) to customer locations, and the requests for delivery arise during the vehicle operating period, which, if accepted, must be satisfied within a service window (e.g., meal delivery) or by the end of the day (e.g., same-day delivery). We introduce the Vehicle Routing Problem with Roaming Delivery Locations and the Meal Delivery Routing Problem, to formalize and conduct a systematic study of the essential features of these systems, and then develop heuristics and optimization-based tools that enable their successful deployment. On a more basic level, we contribute to the understanding of the relation between cost and service quality objectives in dynamic delivery systems, through the study of a series of models with a highly simplified geometry, exploring the structure of optimal solutions and providing efficient algorithms to solve some vehicle routing and demand management (order acceptance strategies used when the system is overwhelmed by demand) problems. In Chapter 2, after defining the Vehicle Routing Problem with Roaming Delivery Locations (VRPRDL), we develop construction and improvement heuristics based on problem-specific techniques. Results from a computational study suggest that roaming delivery systems can have a positive economic and environmental impact, as their deployment can lead to a significant reduction in total distance traveled, especially when used in conjunction to traditional home delivery. In Chapter 3, we begin our investigation of dynamic delivery systems with a study on the complexity of single depot dispatching problems in which a delivery to a customer must occur within a pre-specified time after the customer places the order. Thus, each order has a release date (the earliest time that the order can be dispatched on a route) and a service guarantee that implies a deadline (when the order needs to be delivered). We show that single and multiple vehicle variants where customers are located on a half-line can be solved to optimality in polynomial time. In Chapter 4, we define the Meal Delivery Routing Problem (MDRP) and propose optimization-based algorithms tailored to solve the courier assignment (dynamic vehicle routing) and capacity management (offline shift scheduling) problems in meal delivery systems. Computational experiments on instances with realistic size, geography, urgency and dynamism (based on data provided by our industry partner, Grubhub) demonstrate that our algorithmic ideas can be valuable in real-world implementations. In Chapter 5, we conduct an initial exploration of demand management interventions that can be used when dynamic delivery systems are overwhelmed by demand. We specifically assess the effectiveness of temporarily reducing the coverage area of the system (rejecting orders farther away than a given radius from the depot). We extend the models from Chapter 3 to add order acceptance decisions and prove that some variants can still be solved in polynomial time. Then we propose a series of dynamic algorithms and test them through simulation. Results illustrate that successful heuristics for ``same-day'' delivery may not be well suited for ``next hour'' delivery.
PDF
download
878987797
028-85220240
