Vehicle Routing and Scheduling Problem with Time Windows and Stochastic Demand
Abstract
A real-world vehicle routing and scheduling problem in which a set of known customers is served by a number of vehicles with known capacity is considered. The demand for each customer is stochastic and needs to be served within a given time window. Strict adherence to the time window constraints for customers who practice the just-in-time concept of inventory management is requisite. One or several factors of vehicle routing and scheduling problems are stochastic. This has a major impact on how the problem is both formulated and solved. A three-index model that is a mixed-integer stochastic program with recourse is proposed. A metaheuristic algorithm for solving this problem is developed. Computation of the objective function of this model is computationally expensive. The proxies to evaluate the moves in tabu search are embedded in this heuristic algorithm. The heuristic was tested with Solomon's 100-customer Euclidean vehicle routing problems with time windows but with the customer demands and vehicle capacity excluded. The test results revealed that problem difficulty was relevant not only to the number of customers but also to the average filling coefficients. A routing schedule with a lower value of the average filling coefficient is made to serve a scattering flock of customers.
Get full access to this article
View all access and purchase options for this article.
References
1. Gendreau M., Laporte G., and Seguin R. Stochastic Vehicle Routing. European Journal of Operational Research, Vol. 88, 1996, pp. 3–12.
2. Tillman F. A. The Multiple Terminal Delivery Problem with Probabilistic Demands. Transportation Science, Vol. 3, 1969, pp. 192–204.
3. Stewart W. R., and Golden B. L. Stochastic Vehicle Routing: A Comprehensive Approach. European Journal of Operational Research, Vol. 14, 1983, pp. 371–385.
4. Laporte G., Louveaux F. V., and Mercure H. Models and Exact Solutions for a Class of Stochastic Location-Routing Problems. European Journal of Operational Research, Vol. 39, 1989, pp. 71–78.
5. Gendreau M., Laporte G., and Seguin R. An Exact Algorithm for the Vehicle Routing Problem with Stochastic Demands and Customers. Transportation Science, Vol. 29, 1995, pp. 143–155.
6. Laporte G., and Louveaux F. V. The Integer L-Shaped Method for Stochastic Integer Program with Complete Recourse. Operations Research Letter, Vol. 13, 1993, pp. 133–142.
7. Hjorring C., and Holt J. New Optimality Cuts for a Single-Vehicle Stochastic Routing Problem. Annals of Operations Research, Vol. 86, 1999, pp. 569–584.
8. Dror M., Laporte G., and Trudeau P. Vehicle Routing with Stochastic Demands: Properties and Solution Frameworks. Transportation Science, Vol. 23, 1989, pp. 166–176.
9. Dror M. Modeling Vehicle Routing with Uncertain Demands as a Stochastic Program: Properties of the Corresponding Solution. European Journal of Operational Research, Vol. 64, 1993, pp. 432–441.
10. Laporte G., and Louveaux F. V. Formulations and Bounds for the Stochastic Capacitated Vehicle Routing Problem with Uncertain Supplies. In Economic Decision Making: Games, Economics and Optimization, North-Holland, Amsterdam, Netherlands, 1990, pp. 443–455.
11. Bastian C., and Rinnooy Kan A. H. G. The Stochastic Vehicle Routing Problem Revisited. European Journal of Operational Research, Vol. 56, 1992, pp. 407–412.
12. Bertsimas D. J. A Vehicle Routing Problem with Stochastic Demand. Operations Research, Vol. 40, 1992, pp. 574–585.
13. Dror M., and Trudeau P. Stochastic Vehicle Routing with Modified Savings Algorithm. European Journal of Operational Research, Vol. 23, 1986, pp. 228–235.
14. Bouzaiene-Ayari B., Dror M., and Laporte G. Routing with Stochastic Demands and Split Deliveries. Foundations of Computer and Decision Science, Vol. 18, 1993, pp. 63–69.
15. Bertsimas D. J., Chervi P., and Peterson M. Computational Approaches to Stochastic Routing. Transportation Science, Vol. 29, 1995, pp. 342–352.
16. Yang W. H., Mathur K., and Ballou R. H. Stochastic Vehicle Routing Problem with Restocking. Transportation Science, Vol. 34, No. 1, 2000, pp. 99–112.
17. Dror M., Ball M. O., and Golden B. L. Computational Comparison of Algorithms for Inventory Routing. Annals of Operations Research, Vol. 3, 1985, pp. 3–23.
18. Lason R. C. Transportation of Sludge to the 106-Mile Site: An Inventory Routing Algorithm for Fleet Sizing and Logistics System Design. Transportation Science, Vol. 22, 1988, pp. 186–198.
19. Lambert V., Laporte G., and Louveaux F. V. Designing Collection Routes Through Bank Branches. Computers and Operations Research, Vol. 20, 1993, pp. 783–791.
20. Gendreau M., Laporte G., and Seguin R. A Tabu Search Heuristic for the Vehicle Routing Problem with Stochastic Demands and Customers. Operations Research, Vol. 44, 1996, pp. 469–477.
21. Solomon M. M. Algorithms for the Vehicle Routing and Scheduling Problems with Time Windows Constraints. Operations Research, Vol. 35, No. 2, 1987, pp. 254–265.
22. Gendreau M., Hertz A., and Laporte G. A Tabu Search Heuristic for the Vehicle Routing Problem. Management Science, Vol. 40, 1994, pp. 1276–1290.
23. Glover F. Tabu Search: Part I. Operations Research Society of America Journal on Computing, Vol. 1, No. 3, 1989, pp. 190–206.
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: January 2004
Issue published: January 2004
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: 25
*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: 3
- Optimizing the Number of Express Freight Trains on a High-speed Railwa...
- The impact of traffic congestion when optimising delivery routes in re...
- Hybrid Metaheuristics Algorithms for Inventory Management Problems
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.
