Optimizing Single Vehicle Many-to-Many Operations with Desired Delivery Times: I. Scheduling

Abstract

A set of n customers is given. Each customer has a desired point of pickup, a desired point of delivery and a desired time of delivery. The problem is to determine the order of pickup and delivery and the times of pickup and delivery of these n customers by a single vehicle in order to minimize total customer inconvenience. Here, a mathematical programming formulating of this problem is subjected to Benders' decomposition procedure. The result is a heuristic routing and scheduling algorithm which is shown to produce high quality solutions in reasonable computation time by testing on moderately sized real data bases from both Gaithers-burg, Maryland, and Baltimore, Maryland. This study is divided into two parts, the first detailing the scheduling analysis and the second focusing on the routing component.