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

Irina Ioachim, Jacques Desrosiers, Yvan Dumas, Marius M. Solomon and Daniel Villeneuve
Additional contact information
Irina Ioachim: GERAD and École Polytechnique, Montréal, Canada H3T 1V6
Jacques Desrosiers: GERAD and École des Hautes Études Commerciales, Montréal, Canada H3T 1V6
Yvan Dumas: GERAD and École des Hautes Études Commerciales, Montréal, Canada H3T 1V6
Marius M. Solomon: Northeastern University, Boston, Massachusetts 02115
Daniel Villeneuve: GERAD and École Polytechnique, Montréal, Canada H3T 1V6

Transportation Science, 1995, vol. 29, issue 1, 63-78

Abstract: 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.

Date: 1995
References: Add references at CitEc
Citations: View citations in EconPapers (40)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.29.1.63 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:29:y:1995:i:1:p:63-78

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().