Economic Heuristic Optimization for Heterogeneous Fleet VRPHESTW
Publication: Journal of Transportation Engineering
Volume 132, Issue 4
Abstract
A three-step local search algorithm based on a probabilistic variable neighborhood search is presented for the vehicle routing problem with a heterogeneous fleet of vehicles and soft time windows (VRPHESTW). A generation mechanism based on a greedy randomized adaptive search procedure, a diversification procedure using an extinctive selection evolution strategy, and a postoptimization method based on a threshold algorithm with restarts are considered to solve the problem. The results show the convenience of using an economic objective function to analyze the influence of the changes in the economic environment on the transportation average profit of vehicle routing problems. Near real-world vehicle routing problems need (1) an economic objective function to measure the quality of the solutions as well as (2) an appropriate guide function, which may be different from the economic objective function, for each heuristic method and for each economic scenario.
Get full access to this article
View all available purchase options and get full access to this article.
Acknowledgments
The present study was partially financed by the Spanish Ministry of Science and Technology under Grant BFM2001-2759. The writers are grateful to Debra Westall for her revision of the English version of this paper.
References
Ball, M. O., Magnanti, T. L., Monna, C. L., and Nemhauser, G. L. eds. (1995). “Network routing.” Handbooks in operations research and management science, Vol. 8. North-Holland, Amsterdam, The Netherlands.
Barnhart, C., Boland, N. L., Clarke, L. W., Johnson, E. L., Nemhauser, G. L., and Shenoi, R. G. (1998). “Flight string models for aircraft fleeting and routing.” Transp. Sci., 32(3), 208–220.
Brandão, J., and Mercer, A. (1997). “A tabu search algorithm for the multi-trip vehicle routing and scheduling problem.” Eur. J. Oper. Res., 100(1), 180–191.
Cordeau, J. F., Toth, P., and Vigo, D. (1998). “A survey of optimization models for train routing and scheduling.” Transp. Sci., 32(2), 380–404.
Dueck, G., and Scheuer, T. (1990). “Threshold accepting: A general purpose optimization algorithm appearing superior to simulated annealing.” J. Comput. Phys., 90(1), 161–175.
Dullaert, W., Janssens, G. K., Sörensen, K., and Vernimmen, B. (2002). “New heuristics for the fleet size and mix vehicle routing problem with time windows.” J. Oper. Res. Soc., 53(11), 1232–1238.
Feo, T. A., and Resende, M. G. C. (1989). “A probabilistic heuristic for a computationally difficult set covering problem.” Oper. Res. Lett., 8(2), 67–71.
Gendreau, M., Laporte, G., Musaraganyi, C., and Taillard, É. D. (1999). “A tabu search heuristic for the heterogeneous fleet vehicle routing problem.” Comput. Oper. Res., 26(12), 1153–1173.
Homberger, J., and Gehring, H. (1999). “Two evolutionary metaheuristics for the vehicle routing problem with time windows.” INFOR, 37(3), 297–318.
Imam, M. O. (1998). “Optimal design of public bus service with demand equilibrium.” J. Transp. Eng., 124(5), 431–436.
Lenstra, J., and Rinnooy Kan, A. (1981). “Complexity for the vehicle routing and scheduling problems.” Networks, 11(2), 221–227.
Medina, J. R. (2001). “Estimation of incident and reflected waves using simulated annealing.” J. Waterw., Port, Coastal, Ocean Eng., 127(4), 213–221.
Medina, J. R., and Yepes, V. (2003). “Optimization of touristic distribution networks using genetic algorithms.” SORT, 27(1), 95–112.
Mladenovic, N., and Hansen, P. (1997). “Variable neighborhood search.” Comput. Oper. Res., 24(11), 1097–1100.
Osman, I. H. (1993). “Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problems.” Ann. Operat. Res., 41(1–4), 421–451.
Potvin, J. Y., and Rousseau, J. M. (1995). “An exchange heuristic for routing problems with time windows.” J. Oper. Res. Soc., 46(12), 1433–1446.
Rochat, Y., and Semet, F. (1994). “A tabu search approach for delivering pet food and flour in Switzerland.” J. Oper. Res. Soc., 45(11), 1233–1246.
Schrimpf, G., Scheneider, J., Stamm-Wilbrandt, H., and Dueck, G. (2000). “Record breaking optimization results using the ruin and recreate principle.” J. Comput. Phys., 159(2), 139–171.
Semet, F., and Taillard, É. D. (1993). “Solving real-life vehicle routing problems efficiently using taboo search.” Ann. Operat. Res., 41(1–4), 469–488.
Shih, L.-H., and Lin, Y.-T. (1999). “Optimal routing for infectious waste collection.” J. Environ. Eng., 125(5), 479–484.
Solomon, M. M. (1987). “Algorithms for the vehicle routing and scheduling problems with time window constraints.” Oper. Res., 35(2), 254–265.
Taillard, É. D., Badeau, P., Gendreau, M., Guertin, F., and Potvin, J.-Y. (1997). “A tabu search heuristic for the vehicle routing problem with soft time windows.” Transp. Sci., 31(2), 170–186.
Yepes, V. (2002). “Economic heuristic optimization applied to VRPTW type transportation networks.” Doctoral thesis, Dept. of Transportation Engineering, Univ. Politécnica de Valencia, Valencia, Spain (in Spanish).
Information & Authors
Information
Published In
Journal of Transportation Engineering
Volume 132 • Issue 4 • April 2006
Pages: 303 - 311
Copyright
© 2006 ASCE.
History
Received: May 4, 2004
Accepted: Jul 15, 2005
Published online: Apr 1, 2006
Published in print: Apr 2006
Authors
Metrics & Citations
Metrics
Citations
Download citation
If you have the appropriate software installed, you can download article citation data to the citation manager of your choice. Simply select your manager software from the list below and click Download.