Model and Algorithm considering Time-Varying Travel Times to Solve Static Multidepot Dial-a-Ride Problem
Abstract
This paper studies a static dial-a-ride problem (DARP) with time-varying travel times, soft time windows, and multiple depots. A static DARP model is formulated as a mixed-integer programming problem. To validate the model, several random small network problems are solved by using the commercial optimization package CPLEX. Three heuristic algorithms based on sequential insertion, parallel insertion, and clustering first-routing second are proposed to solve this problem within a reasonable time for implementation in a real-world situation. The results of the three heuristic methods are compared with the results obtained from exact solution by CPLEX to validate and evaluate the three heuristic algorithms. Computational results show that the three heuristic algorithms are superior to the exact algorithm in relation to the calculation time as the problem size (in number of demands) increases. Of the three heuristic algorithms, the one based on sequential insertion is more efficient than the other heuristic algorithms based on parallel insertion and clustering first-routing second.
Get full access to this article
View all access and purchase options for this article.
References
1. Baugh J., Kakivaya G., and Stone J. R. Intractability of the Dial-a-Ride Problem and a Multiobjective Solution Using Simulated Annealing. Engineering Optimization, Vol. 30, No. 2, 1998, pp. 91–123.
2. Savelsbergh M. W. P., and Solomon M. The General Pickup and Delivery Problem. Transportation Science, Vol. 29, No. 1, 1995, pp. 17–29.
3. Mitrovic-Minic S. Pickup and Delivery Problem with Time Window: A Survey. SFU CMPT TR 1998-12. Simon Fraser University, Burnaby, British Columbia, Canada, 1998.
4. Mitrovic-Minic S. The Dynamic Pickup and Delivery Problem with Time Window. PhD dissertation. Simon Fraser University, Burnaby, British Columbia, Canada, 2001.
5. Desaulniers G., Desrosiers J., Erdmann A., Solomon M. M., and Soumis F. VRP with Pickup and Delivery. In The Vehicle Routing Problem (Toth P., and Vigo D., eds.), SIAM Monographs on Discrete Mathematics and Applications, Philadelphia, Pa., 2002, pp. 225–242.
6. Cordeau J.-F., and Laporte G. The Dial-a-Ride Problem: Variants, Modeling Issues and Algorithms. 4OR: A Quarterly Journal of Operations Research, Vol. 1, No. 2, 2003, pp. 89–101.
7. Cordeau J.-F., and Laporte G. The Dial-A-Ride Problem: Models and Algorithms. Annals of Operations Research, Vol. 153, No. 1, 2007, pp. 29–46.
8. Jaw J.-J., Odoni A. R., Psaraftis H. N., and Wilson N. H. M. A Heuristic Algorithm for the Multi-Vehicle Advance Request Dial-a-Ride Problem with Time Windows. Transportation Research Part B, Vol. 20, No. 3, 1986, pp. 243–257.
9. Ioachim I., Desrosiers J., Dumas Y., and Solomon M. M. A Request Clustering Algorithm for Door-to-Door Handicapped Transportation. Transportation Science, Vol. 29, No. 1, 1995, pp. 63–78.
10. Toth P., and Vigo D. Heuristic Algorithms for the Handicapped Persons Transportation Problem. Transportation Science, Vol. 31, No. 1, 1997, pp. 60–71.
11. Fu L. Improving Paratransit Scheduling by Accounting for Dynamic and Stochastic Variations in Travel Time. In Transportation Research Record: Journal of the Transportation Research Board, No. 1666, TRB, National Research Council, Washington, D.C., 1999, pp. 74–81.
12. Fu L. Scheduling Dial-a-Ride Paratransit Under Time-Varying, Stochastic Congestion. Transportation Research Part B, Vol. 36, No. 6, 2002, pp. 485–506.
13. Cordeau J.-F., and Laporte G. A Tabu Search Heuristic for the Static Multi-Vehicle Dial-a-Ride Problem. Transportation Research Part B, Vol. 37, No. 6, 2003, pp. 579–594.
14. Diana M., and Dessouky M. M. A New Regret Insertion Heuristic for Solving Large-Scale Dial-a-Ride Problems with Time Windows. Transportation Research Part B, Vol. 38, No. 6, 2004, pp. 539–557.
15. Luo Y., and Schonfeld P. A Rejected-Reinsertion Heuristic for the Static Dial-A-Ride Problem. Transportation Research Part B, Vol. 41, No. 7, 2007, pp. 736–755.
16. Xiang Z., Chu C., and Chen H. A Fast Heuristic for Solving a Large-Scale Static Dial-a-Ride Problem Under Complex Constraints. European Journal of Operational Research, Vol. 174, No. 2, 2006, pp. 1117–1139.
17. Cherkassky B. B., Goldberg A. V., and Radzik T. Shortest Paths Algorithms: Theory and Experimental Evaluation. Report 93–1480. Computer Science Department, Stanford University, Calif., 1993.
18. Zhan F. B. Three Fastest Shortest Path Algorithms on Real Road Networks: Data Structures and Procedures. Journal of Geographic Information and Decision Analysis, Vol. 1, No. 1, 1997, pp. 69–82.
19. Sung K., Bell M. G. H., Seong M., and Park S. Shortest Paths in a Network with Time Dependent-Flow Speeds. European Journal of Operational Research, Vol. 121, No. 1, 2000, pp. 32–39.
Cite article
Cite article
Cite article
OR
Download to reference manager
If you have citation software installed, you can download article citation data to the citation manager of your choice
Information, rights and permissions
Information
Published In
Article first published online: January 1, 2011
Issue published: January 2011
Authors
Metrics and citations
Metrics
Journals metrics
This article was published in Transportation Research Record: Journal of the Transportation Research Board.
VIEW ALL JOURNAL METRICSArticle usage*
Total views and downloads: 38
*Article usage tracking started in December 2016
Altmetric
See the impact this article is making through the number of times it’s been read, and the Altmetric Score.
Learn more about the Altmetric Scores
Articles citing this one
Receive email alerts when this article is cited
Web of Science: 0
Crossref: 5
- Modeling an enhanced ridesharing system with meet points and time wind...
- Evaluating the Impact of Spatio-Temporal Factors on Construction Heuri...
- A revised branch-and-price algorithm for dial-a-ride problems with the...
- An Integrated Decision Support System to Assess the Sustainability of ...
- Integrating bus services with mixed fleets
Figures and tables
Figures & Media
Tables
View Options
Get access
Access options
If you have access to journal content via a personal subscription, university, library, employer or society, select from the options below:
loading institutional access options
Alternatively, view purchase options below:
Purchase 24 hour online access to view and download content.
Access journal content via a DeepDyve subscription or find out more about this option.
