Missed deliveries are a major issue for package carriers and a source of great hassle for the customers. Either the carrier attempts to redeliver the package, incurring the additional expense of visiting the same house up to three times, or they leave the package on the doorstep, vulnerable to package thieves. In this dissertation, a system of collection-and-delivery-points (CDPs) has been proposed to improve customer service and reduce carrier costs. A CDP is a place, either in an existing business or a new location, where the carrier drops any missed deliveries and the customers can pick the packages at their convenience.
To examine the viability of a CDP system in North America, a variation on a location-routing problem (LRP) was created, a mixed-integer programming model called the CDP-LRP. Unlike standard LRPs, the CDP-LRP takes into account both the delivery truck route distance and the direct customer travel to the CDPs. Also, the facilities being placed are not located at the beginning and ending of the truck routes, but are stops along the routes. After testing, it became clear that, because of the size and complexity of the problem, the CDP-LRP is unable to be solved exactly in a reasonable amount of time. Heuristics developed for the standard LRP cannot be applied to the CDP-LRP because of the differences between the models. Therefore, three heuristics were created to approximate the solution to the CDP-LRP, each with two different embedded modified vehicle routing problem (VRP) algorithms, the Clark-Wright and the Sweep, modified to handle the additional restrictions caused by the CDPs. The first is an improvement heuristic, in which each closed CDP is tested as a replacement for each open CDP, and the move that creates the most savings is implemented. The second begins with every CDP open, and closes them one at a time, while the third does the reverse and begins will only one open CDP, then opens the others one by one. In each case, a penalty is applied if the customer travel distance is too long. Each heuristic was tested for each possible number of open CDPs, and the least expensive was chosen as the best solution.
Each heuristic and VRP algorithm combination was tested using three delivery failure rates and different data sets: three small data sets pulled from VRP literature, and randomly generated clustered and uniformly distributed data sets with three different numbers of customers. OpenAll and OpenOne produced better solutions than Replacement in most instances, and the Sweep Algorithm outperformed the Clark-Wright in both solution quality and time in almost every test. To judge the quality of the heuristic solutions, the results were compared to the results of a simple locate-first, route-second sequential algorithm that represents the way the decision would commonly be made in industry today. The CDPs were located using a simple facility location model, then the delivery routes were created with the Sweep algorithm. These results were mixed: for the uniformly distributed data sets, if the customer travel penalty threshold and customer density are low enough, the heuristics outperform the sequential algorithm. For the clustered data sets, the sequential algorithm produces solutions as good as or slightly better than the sequential algorithm, because the location of the potential CDP inside the clusters means that the penalty has less impact, and the addition of more open CDPs has less effect on the delivery route distances.
The heuristic solutions were also compared to a second value – the route costs incurred by the carrier in the current system of redeliveries, calculated by placing additional customers in the routes and running the Sweep algorithm – to judge the potential savings that could be realized by implementing a CDP system in North America. Though in some circumstances the current system is less expensive, depending on the geographic distribution of the customers and the delivery failure rate, in other circumstances the cost savings to the carrier could be as high as 27.1%. Though the decision of whether or not to set up a CDP system in an area would need to be made on a case-by-case basis, the results of this study suggest that such a system could be successful in North America. / Doctor of Philosophy / Missed deliveries are a major issue for package carriers and a source of great hassle for the customers. Either the carrier attempts to redeliver the package, incurring the additional expense of visiting the same house up to three times, or they leave the package on the doorstep, vulnerable to package thieves. In this dissertation, a system of collection-and-delivery-points (CDPs) has been proposed to improve customer service and reduce carrier costs. A CDP is a place, either in an existing business or a new location, where the carrier drops any missed deliveries and the customers can pick the packages at their convenience. To examine the viability of a CDP system in North America, a mathematical programming model was created called the CDP-LRP. Because of the size and complexity of the problem, it is unable to be solved exactly in a reasonable amount of time. Therefore, three heuristics were created to approximate the solution to the CDP-LRP, each with two different embedded modified vehicle routing problem (VRP) algorithms. For all the heuristics, a penalty is applied if the customer travel distance is too long. Each heuristic and VRP algorithm combination was tested using different data sets: three small data sets pulled from VRP literature, and randomly generated clustered and uniformly distributed data sets with three different numbers of customers. To judge the quality of the heuristic solutions, the results were compared to the results of a simple locate-first, route-second sequential algorithm that represents the way the decision would commonly be made in industry today. These results were mixed: for the uniformly distributed data sets, if the customer travel penalty threshold and customer density are low enough, the heuristics outperform the sequential algorithm. For the clustered data sets, the sequential algorithm produces solutions as good as or slightly better than the sequential algorithm, because the location of the potential CDP inside the clusters means that the penalty has less impact, and the addition of more open CDPs has less effect on the delivery route distances. The heuristic solutions were also compared to a second value – the route costs incurred by the carrier in the current system of redeliveries – to judge the potential savings that could be realized by implementing a CDP system in North America. Though in some circumstances the current system is less expensive, depending on the geographic distribution of the customers and the delivery failure rate, in other circumstances the cost savings to the carrier could be as high as 27.1%. Though the decision of whether or not to set up a CDP system in an area would need to be made on a case-by-case basis, the results of this study suggest that such a system could be successful in North America.
| Identifer | oai:union.ndltd.org:VTETD/oai:vtechworks.lib.vt.edu:10919/93955 |
| Date | 20 September 2019 |
| Creators | Savage, Laura Elizabeth |
| Contributors | Industrial and Systems Engineering, Taylor, G. Don, Fraticelli, Barbara M. P., Ellis, Kimberly P., Russell, Roberta S. |
| Publisher | Virginia Tech |
| Source Sets | Virginia Tech Theses and Dissertation |
| Detected Language | English |
| Type | Dissertation |
| Format | ETD, application/pdf |
| Rights | In Copyright, http://rightsstatements.org/vocab/InC/1.0/ |
Page generated in 0.0031 seconds