Abstract
In the Vehicle Routing Problem with Backhauls and Time Windows (VRPBTW) customers either receive goods from the depot or send goods to the depot and pickup or delivery at a customer has to occur within a pre-specified time window. The main objective is to minimize the total required fleet size for serving all customers. Secondary objectives are to minimize the total distance travelled or to minimize the total route duration of all vehicles. In this paper we consider a variant of the mixed VRPBTW where backhauls may be served before linehauls on any given route. Besides the modelling aspect of this variant we will study its performance implications when compared to the standard VRPBTW using a heuristic algorithm based on Ant Colony Optimization.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Toth, P. and Vigo, D. (Eds.): The Vehicle Routing Problem, Siam Monographs on Discrete Mathematics and Applications, Philadelphia (2002).
Bräysy, O. and Gendreau, M.: Metaheuristics for the Vehicle Routing Problem with Time Windows, to appear in: Transportation Science
Cordeau, J. F., Gendreau, M. and Laporte, G.: A Tabu Search Heuristic for Periodic and Multi-Depot Vehicle Routing Problems, Networks 30 (1997) 105–119
http://ww.top.sintef.no/
Cordeau, J. F., Laporte, G. and Mercier, A.: A Unified Tabu Search Heuristic for Vehicle Routing Problems with Time Windows, Journal of the Operational Research Society 52 (2001) 928–936
Cordeau, J. F., Gendreau, M., Laporte, G., Potvin, J. Y. and Semet, F.: A guide to vehicle routing heuristics, Journal of the Operational Research Society 53(5) (2002) 512–522.
Toth, P. and Vigo, D.: VRP with Backhauls, in: Toth, P. and Vigo, D. (Eds): The Vehicle Routing Problem, Siam Monographs on Discrete Mathematics and Applications, Philadelphia (2002) 195–224
Savelsbergh, M. W. P.: Local search for routing problems with time windows, Annals of Operations Research 4 (1985) 285–305
Gelinas, S., Desrochers, M., Desrosiers, J. and Solomon, M. M.: A new branching strategy for time constrained routing problems with application to backhauling. Annals of Operations Research 61 (1995) 91–109
Thangiah, S. R., Potvin, J. Y. and Sun, T.: Heuristic approaches to Vehicle Routing with Backhauls and Time Windows, Computers and Operations Research 23 (1996) 1043–1057
Duhamel, C., Potvin, J. Y. and Rousseau, J. M.: A Tabu Search Heuristic for the Vehicle Routing Problem with Backhauls and Time Windows, Transportation Science 31 (1997) 49–59
Ropke, S. and Pisinger, D.: A Unified Heuristic for Vehicle Routing Problems with Backhauls, to appear in: European Journal of Operational Research
Kontoravdis, G. and Bard, J. F.: A GRASP for the Vehicle Routing Problem with Time Windows, ORSA Journal of Computing 7(1) (1995) 10–23
Zhong, Y. and Cole, M.H.: A vehicle routing problem with backhauls and time windows: a guided local search solution, Transportation Research Part E 41(2) (2005) 131–144
Wade, A.C. and Salhi, S.: An investigation into a new class of vehicle routing problems with backhauls, Omega 30 (2002) 479–487
Casco, O., Golden, B. and Wasil, E.: Vehicle Routing with Backhauls: models, algorithms and case studies, in: Golden, B. and Assad, A. (Eds.): Vehicle routing: methods and studies, North Holland, Amsterdam (1988) 127–147
Colorni, A., Dorigo, M. and Maniezzo, V.: Distributed Optimization by Ant Colonies, in: Varela, F. and Bourgine, P. (Eds.): Proceedings of the European Conference on Artificial Life, Elsevier, Amsterdam (1991) 134–142
Dorigo, M. and Stuetzle, Th.: Ant Colony Optimization, MIT Press, Cambridge (2004)
Gutjahr, W. J.: ACO algorithms with guaranteed convergence to the optimal solution, Information Processing Letters 82 (2002) 145–153
Reimann, M., Doerner, K. and Hartl, R. F.: Insertion based Ants for Vehicle Routing Problems with Backhauls and Time Windows, in: Dorigo, M. et al. (Eds.): Ant Algorithms, Springer LNCS 2463, Berlin/Heidelberg (2002) 135–147
Reimann, M., Doerner, K. and Hartl, R. F.: Analyzing a unified Ant System for the VRP and some of its variants, in: Raidl, G. et al. (Eds.): Applications of Evolutionary Computing, Springer LNCS 2611, Berlin/Heidelberg (2003) 300–310
Solomon, M. M.: Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints, Operations Research 35 (1987) 254–265
Osman, I. H.: Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem, Annals of Operations Research 41 (1993) 421–451
Reimann, M.: Combining an exact algorithm with an Ant System for Travelling Salesman Problems, Working Paper, Department of Management Science, University of Vienna, 2003.
Blum, C. and Dorigo, M.: The Hyper-Cube framework for ant colony optimization, IEEE Transactions on Systems, Man and Cybernetics B 34(2) (2004) 1161–1772.
Jozefowiez, N., Semet, F. and Talbi, E.: Parallel and Hybrid Models for Multi-objective Optimization: Application to the Vehicle Routing Problem, in: Guervos, J. M. et al. (Eds): Parallel Problem Solving from Nature-PPSN VII, Springer LNCS 2439, Berlin/Heidelberg (2002) 271–280
Gambardella, L. M., Taillard, E. and Agazzi G.: MACS-VRPTW: A Multiple Ant Colony System for Vehicle Routing Problems with Time Windows, in: Corne, D. et al. (Eds.): New Ideas in Optimization, McGraw-Hill, London, (1999) 63–73
Doerner, K., Hartl, R.F. and Reimann, M.: CompetAnts for problem solving—the case of full truckload transportation, Central European Journal of Operations Research 11(2) (2003) 115–141
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Reimann, M., Ulrich, H. Comparing backhauling strategies in vehicle routing using Ant Colony Optimization. cent.eur.j.oper.res. 14, 105–123 (2006). https://doi.org/10.1007/s10100-006-0163-8
Issue Date:
DOI: https://doi.org/10.1007/s10100-006-0163-8