The Multi-depot Vehicle Routing Problem of Heterogeneous Fleet of Vehicles with Time Windows for Perishable Commodities

Abstract

This paper discusses the multi-depot vehicle routing problem of heterogeneous fleet of vehicles with time windows for perishable commodities. The objective of the problem is to minimize the total time required for servicing all customers that is equivalent to the total cost. Commodities are delivered to the customers with defined time windows by a fleet of heterogeneous vehicles, which have limited capacities. The mentioned problem is a more general version of vehicle routing problem (VRP), hence it belongs to NP-complete complexity class and we present a Max-Min ant colony algorithm to solve the model approximately in practical dimensions. Finally, the experimental results have shown that the presented algorithm has appropriate performance in comparison with well-known instances in a reasonable time.

Keywords

References

[1]       P. Toth and D. Vigo. “The Vehicle Routing Problem”. SIAM Monographs on Discrete Mathematics and Applications. SIAM, Philadelphia, PA, 2002.
[2]       G. B. Dantzig and J. H. Ramser. “The Truck Dispatching Problem”. Management Science, 6:80-91, 1959.
[3]       L. Tansini, M. Urquhart, O. Viera. “Comparing Assignment Algorithms for the Multi-Depot VRP”. Computers and Operations Research,20(7), 783–791.
[4]       B. Crevier, J. F. Cordeau, G. Laporte. “The multi-depot vehicle routing problem with inter-depot routes”. Eurpean Journal of Operational Research, 176:756-773, 2007.
[5]       T. Vidal, T. G. Crainic, M. Gendreau, N. Lahrichi, W. Rei. “A Hybrid Genetic Algorithm for Multi-Depot and Periodic Vehicle Routing Problem”. Interuniversity Research Centre on Enterprise Networks, Logistics and Transportation, 2011.
[6]       Malandraki, C., &Daskin, M. S.,“Time dependent vehicle routing problems: Formulations, properties and heuristic algorithms”. TransportationScience, 26(3), 185–199,1992.
[7]       Tarantilis, C. D., &Kiranoudis, C. T.,“A meta-heuristic algorithmfor the efficient distribution of perishable foods”. Journal of FoodEngineering, 50, 1–9,2001.
[8]       Prindezis, N., Kiranoudis, C. T.,&Marinos-Kouris, D.,“A business-to-business fleet management service provider for central food market enterprises”. Journal of Food Engineering, 60(2), 203–210,2003.
[9]       Chaug-Ing Hsu, et al.,“Vehicle routing problem with time-windows for perishable food delivery”. Journal of Food Engineering 80 (2007) 465-475,2007.
[10]  Osvald A, Stirn L.,“A vehicle routing algorithm for the distribution of fresh vegetables and similar perishable food”. J Food Eng 85(2):285–295,2008.
[11]  Dorigo, M., "Optimization, Learning and natural algorithms", Ph.D. Thesis, Dip.Electtronica e Informazion, Politecnico di,1992.
[12]  F. Cano Sevilla, C. Simo’n de Blas, “vehicle routing problem with time windows and intermediate facilities”,in:S.E.I.O_.03 Edicions de la Universitat de Lleida, pp. 3088-3096, 2003.
[13]  J.-F. Cordeau, G. Laporte, and A. Mercier.“Improved tabu search algorithm forthe handling of route duration constraints in vehicle routing problems with time windows”. Journal of the Operational Research, 55(5):542_546, May 2004.

Files

History

  • Receive Date: 30 April 2014
  • Revise Date: 22 May 2014
  • Accept Date: 15 June 2014
  • Publish Date: 21 September 2014

Share

How to cite

Statistics