Document Type

Dissertation

Date of Degree

Summer 2015

Degree Name

PhD (Doctor of Philosophy)

Degree In

Business Administration

First Advisor

Ann M. Campbell

Second Advisor

Barrett W. Thomas

Abstract

When a package is shipped, the customer often requires the delivery to be made within a particular time window or by a deadline. However, meeting such time requirements is difficult, and delivery companies may not always know ahead of time which customers will need a delivery. In this thesis, we present models and solution approaches for two stochastic last-mile delivery problems in which customers have delivery time constraints and customer presence is known in advance only according to a probability distribution. Our solutions can help reduce the operational costs of delivery while improving customer service.

The first problem is the probabilistic traveling salesman problem with time windows (PTSPTW). In the PTSPTW, customers have both a time window and a probability of needing a delivery on any given day. The objective is to find a pre-planned route with an expected minimum cost. We present computational results that characterize the PTSPTW solutions. We provide insights for practitioners on when solving the PTSPTW is beneficial compared to solving the deterministic analogue of the problem.

The second problem is the same-day delivery problem (SDDP). The SDDP is a dynamic and stochastic pick-up and delivery problem. In the SDDP, customers make delivery requests throughout the day and vehicles are dispatched from a warehouse or brick and mortar store to serve the requests. Associated with each request is a request deadline or time window. In order to make better-informed decisions, our solution approach incorporates information about future requests into routing decisions by using a sample scenario planning approach with a consensus function. We also introduce an analytical result that identifies when it is beneficial for vehicles to wait at the depot. We present a wide range of computational experiments that demonstrate the value of our approaches.

Public Abstract

When a package is shipped, the customer often requires the delivery to be made within a particular time window or by a deadline. However, meeting such time requirements is difficult, and delivery companies may not always know ahead of time which customers will need a delivery. In this thesis, we present models and solution approaches for two last-mile delivery problems in which customers have delivery time constraints and customer presence is unknown in advance. Our solutions can help reduce the operational costs of delivery while improving customer service.

The first problem is the probabilistic traveling salesman problem with time windows (PTSPTW). In the PTSPTW, customers have both a time window and a probability of needing a delivery on any given day. The objective is to find a preplanned route with an expected minimum cost. We present computational results that characterize the PTSPTW solutions. We provide insights for practitioners on when solving the PTSPTW is beneficial compared to solving the deterministic analogue of the problem.

The second problem is the same-day delivery problem (SDDP). In the SDDP, customers make delivery requests throughout the day and vehicles are dispatched from a warehouse or brick and mortar store to serve the requests. In order to make better-informed decisions, our solution approach incorporates information about future requests into routing decisions. We also introduce an analytical result that identifies when it is beneficial for vehicles to wait at the depot. We present a wide range of computational experiments that demonstrate the value of our approaches.

Keywords

publicabstract, Deadlines, Dynamic Programming, Last-Mile Delivery, Stochastic, Time Windows, Vehicle Routing

Pages

xi, 110 pages

Bibliography

Includes bibliographical references (pages 105-110).

Copyright

Copyright 2015 Stacy Ann Voccia

Share

COinS