Research Reports from the Department of Operations
Document Type
Dissertation
Publication Date
8-1-1987
Abstract
In the problem considered, the objective is to minimize the total tardiness in a schedule which includes many pickup and many delivery locations. Due to the large number of items and fixed number of vehicles, a feasible schedule picking all items up after their known ready time and delivering them before their due times generally does not exist. Algorithms for single and multivehicle instances are developed. A branch and bound algorithm developed for the single vehicle finds an optimal solution. However, its use is limited to comparatively small problems. The alternative heuristic consists of 2 phases. First, the vehicle is routed and scheduled by choosing ensuing locations based on an aggregate measure of the urgencies of items associated with each location. Detours are devised. Second, an improvement routine is performed. Stops are systematically eliminated and the vehicle rescheduled using the first phase. This algorithm creates routes and schedules for item pickup and deliveries evenly spread throughout the day on the average 1.5 times the optimum using only a few seconds of CPU time. The single vehicle algorithm is adapted for the multivehicle problem utilizing an innovative technique for evaluating transfers. In addition, a mixed integer formulation of the multivehicle problem is provided. An optimal procedure of selecting the vehicle to move at each leg of the route and its use in a branch and bound procedure is demonstrated.
Keywords
Operations research, Delivery of goods--Mathematical models, Transportation--Management--Mathematical models, Algorithms, Integer programming
Publication Title
Dissertation/Technical Memorandums from the Department of Operations, School of Management, Case Western Reserve University
Issue
Technical memorandum no. 623 ; Submitted in partial fulfillment of the requirements for the Degree of Doctor of Philosophy.
Rights
This work is in the public domain and may be freely downloaded for personal or academic use
Recommended Citation
Cuff, Carolyn Kidder, "Minimization of Total Tardiness in Many-to-Many Pickup and Delivery Systems" (1987). Research Reports from the Department of Operations. 310.
https://commons.case.edu/wsom-ops-reports/310
