عنوان مقاله [English]
This paper considers the vehicle routing problem with backhaul (VRPB) and some applicable constraints, in which a set of costumers are divided into two subsets of linehaul and backhaul costumers. Each linehaul costumer requires its demands to be delivered from the depot. In addition, a specified quantity of products should be picked up from the backhaul nodes to the depot. The main point in this study is that the customer demands, which are over than the maximum of available vehicles, can be divided to different customers. In addition, there is limited vehicle access availability for some costumers. The central depot includes a fleet of vehicles with different capacities, in which the number of vehicles of each type is not limited and customer demands are dynamic and can change in each period. This problem is a well-known NP-hard one; therefore, a new multi-ant colony optimization algorithm is proposed to solve the given problem. This proposed algorithm contains two phases, namely clustering and routing. Finally, the numerical results of designed test problems have been discussed and analyzed.
Anily, S., 1996. The vehicle-routing problem with delivery and back-haul options. Naval Research Logistics 43, 415–434.
Anbuudayasankar, S.P., Ganesh, K., Lenny Koh, S.C., Ducq, Y. (2012). Modified savings heuristics and genetic algorithm for bi-objective vehicle routing problem with forced backhauls. Expert Systems with Applications 39(3), 2296–2305.
Brandao, J., 2006. A new tabu search algorithm for the vehicle routing problem with backhauls. European Journal of Operational Research 173, 540–555.
Bullnheimer, B., Hartl, R.F., Strauss, C., 1999. An improved ant system algorithm for the vehicle routing problem. Annals of Operations Research 89, 319–328.
Barnhart, C. and Laporte, G. (Eds.), 2007, Handbook in OR & MS, Chapter 6 -Vehicle Routing Vol. 14.
Dorigo, M., Maniezzo, V., Colorni, A., 1996. The ant system: Optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man and Cybernetics – Part B 26, 29–41.
Duhamel, C., Potvin, J.Y., Rousseau, J.M., 1997. A tabu search heuristic for the vehicle routing problem with backhauls and time windows. Transportation Science 31, 49–59.
Gambardella, L.M., Taillard, E., Agazzi, G., 1999. MACS-VRPTW: A multiple ant colony system for vehicle routing problems with time windows. In: Corne, D., Dorigo, M., Glover, F. (Eds.), New Ideas in Optimization. McGraw-Hill, pp. 63–76.
Goetschalckx, M., Jacobsblecha, C., 1989. The vehicle-routing problem with backhauls. European Journal of Operational Research 42, 39–51.
Goetschalckx, M., Jacobsblecha, C., 1993. The vehicle routing problem with backhauls: Properties and solution algorithms. Georgia Institute of Technology, Technical Report, MHRC-TR-88-13.
Liu. S. C., Chung. C. H., 2009, “A heuristic method for the vehicle routing problem with backhauls and inventory”, Journal of Intelligent Manufacturing 20(1), 29–42.
Osman, I.H., Wassan, N.A., 2002. A reactive tabu search meta-heuristic for the vehicle routing problem with back-hauls. Journal of Scheduling 5, 263–285.
Potvin, J.-Y., Duhamel, C., Guertin, F., 1996. A genetic algorithm for vehicle routing with backhauling. Applied Intelligence 6, 345–355.
Reimann, M., Doerner, K., Hartl, R.F., 2002. Insertion based ants for vehicle routing problems with backhauls and time windows. Lecture Notes in Computer Science, 135–148.
Reimann, M., Doerner, K., Hartl, R.F., Ants, D., 2004. Savings based ants divide and conquer the vehicle routing problem. Computers and Operations Research 31, 563–591.
Salhi, S., Wassan, N., Hajarat, M. (2013). The fleet size and mix vehicle routing problem with backhauls: formulation and set partitioning-based heuristics. Transportation Research - Part E: Logistics and Transportation Review, 56, 22–35.
Tavakkoli-Moghaddam, R., Saremi, A.R., Ziaee M.S., 2006, “A memetic algorithm for a vehicle routing problem with backhauls”. Applied Mathematics and Computation 181, 1049–1060.
Thangiah, S., Potvin, J., Sun, T. 1996. “Heuristic approaches to vehicle routing with backhauls and time windows” International Journal of Computers and operations Research 23(11), 1043–1057.
Thangiah, S.R., Potvin, J.Y., Sun, T., 1996. Heuristic approaches to vehicle routing with backhauls and time windows. Computers and Operations Research 23, 1043–1058.
Toth, P., Vigo, D., 1996. A heuristic algorithm for the vehicle routing problem with backhauls. In: Bianco, L., Toth, P. (Eds.), In: Advanced Method in Transportation Analysis. Springer-Verlag, Berlin, pp. 585–608.
Toth, P., Vigo, D., 1997. An exact algorithm for the vehicle routing problem with backhauls. Transportation Science 31, 372–385.
Toth, P., Vigo, D., 1999. A heuristic algorithm for the symmetric and asymmetric vehicle routing problems with backhauls. European Journal of Operational Research 113, 528–543.
Tütüncü, G. Y. (2010). An interactive GRAMPS algorithm for the heterogeneous fixed fleet vehicle routing problem with and without backhauls. European Journal of Operational Research 201(2), 593–600.
Wade, A.C., Salhi, S., 2002. An investigation into a new class of vehicle routing problem with backhauls. Omega 30, 479–487.
Wade, A.C., Salhi, S., 2004. An ant system algorithm for the mixed vehicle routing problem with backhauls. Metaheuristics: Computer Decision-making. Kluwer Academic Publishers, pp. 699–719.
Wassan, N., 2004. Reactive tabu adaptive memory programming search for the vehicle routing problem with backhauls Canterbury Business School, University of Kent, Working Paper No. 56.
Yano, C., Chan, T., Richter, L., Cutler, T., Murty, K., McGettigan, D., 1987. Vehicle routing at quality stores. Interfaces 17, 52–63.
Zachariadis, E.E., Kiranoudis, C.T. (2012). An effective local search approach for the vehicle routing problem with backhauls. Expert Systems with Applications 39(3), 3174-3184.
Zhen, T., Zhu, Y., Zhang, Q., 2008. “A hybrid ant colony algorithm for the capacitated vehicle routing problem”, Proceedings of IEEE International Symposium on IT in Medicine and Education, pp. 935–939.