A Request Clustering Algorithm for Door-to-Door Handicapped Transportation

This paper examines whether there is a substantial additional payoff to be derived from using mathematical optimization techniques to globally define a set of mini-clusters. Specifically, we present a new approximate method to mini-clustering that involves solving a multi-vehicle pick-up and delivery problem with time windows by column generation. To solve this problem we have enhanced an existing optimal algorithm in several ways. First, we present an original network design based on lists of neighboring transportation requests. Second, we have developed a specialized initialization procedure which reduces the processing time by nearly 40%. Third, the algorithm was easily generalized to multi-dimensional capacity. Finally, we have also developed a heuristic to reduce the size of the network, while incurring only small losses in solution quality. This allows the application of our approach to much larger problems. To be able to compare the results of optimization-based and local heuristic mini-clustering, we also present a parallel insertion approach to mini-clustering. Our computational results highlight the success of our approach. On test problems with up to 250 requests, our optimization-based method reduced the travel time within the mini-clusters by an average of 10% over the parallel insertion approach. Furthermore, for an actual problem with 2545 requests, a substantial 5.9% improvement in total traveling time was achieved over the heuristic.