A heuristic algorithm based on tabu search for vehicle routing problems with backhauls

Abstract: In this paper, a heuristic algorithm based on Tabu Search Approach for solving the Vehicle Routing Problem with Backhauls (VRPB) is proposed. The problem considers a set of customers divided in two subsets: Linehaul and Backhaul customers. Each Linehaul customer requires the delivery of a given quantity of product from the depot, whereas a given quantity of product must be picked up from each Backhaul customer and transported to the depot. In the proposed algorithm, each route consists of one sub-route in which only the delivery task is done, and one sub-route in which only the collection process is performed. The search process allows obtaining a correct order to visit all the customers on each sub-route. In addition, the proposed algorithm determines the best connections among the sub-routes in order to obtain a global solution with the minimum traveling cost. The efficiency of the algorithm is evaluated on a set of benchmark instances taken from the literature. The results show that the computing times are greatly reduced with a high quality of solutions. Finally, conclusions and suggestions for future works are presented.

How to cite this paper

 Chávez, J., Escobar, J., Echeverri, M & Meneses, C. (2018). A heuristic algorithm based on tabu search for vehicle routing problems with backhauls.Decision Science Letters , 7(2), 171-180.

Refrences

Aguado, J. S. (2009). Fixed Charge Transportation Problems: a new heuristic approach based on Lagrangean relaxation and the solving of core problems. Annals of Operations Research, 172(1), 45.
Chávez, J. J., Escobar, J. W., & Echeverri, M. G. (2016). A multi-objective Pareto Ant Colony algorithm for the Multi-Depot Vehicle Routing problem with Backhauls. International Journal of Industrial Engineering Computations, 7(1), 35 – 48.
Escobar, J. W., & Linfati, R. (2012). Un algoritmo metaheurístico basado en recocido simulado con espacio de búsqueda granular para el problema de localización y ruteo con restricciones de capacidad. Revista Ingenierías Universidad de Medellín, 11(21), 139-150.
Escobar, J. W. (2014). Heuristic algorithms for the capacitated location-routing problem and the multi-depot vehicle routing problem. 4OR, 12(1), 99.
Escobar, J. W., Linfati, R., & Toth, P. (2013). A two-phase hybrid heuristic algorithm for the capacitated location-routing problem. Computers & Operations Research, 40(1), 70-79.
Escobar, J. W., Linfati, R., Toth, P., & Baldoquin, M. G. (2014a). A hybrid granular tabu search algorithm for the multi-depot vehicle routing problem. Journal of Heuristics, 20(5), 483-509.
Escobar, J. W., Linfati, R., Baldoquin, M. G., & Toth, P. (2014b). A Granular Variable Tabu Neighborhood Search for the capacitated location-routing problem. Transportation Research Part B: Methodological, 67, 344-356.
Escobar, J. W., Linfati, R., & Adarme-Jaimes, W. (2015). A hybrid metaheuristic algorithm for the capacitated location routing problem. Dyna, 82(189), 243-251.
Mingozzi, A., Giorgi, S., & Baldacci, R. (1999). An exact method for the vehicle routing problem with backhauls. Transportation Science, 33(3), 315-329.
Bazaraa, M. S., Sherali, H. D., & Shetty, C. M. (2006). Nonlinear Programming. New Jersey: A John Wily & Sons, Inc., Publication.
Deif, I., & Bodin, L. (1984). Extension of the Clarke and Wright algorithm for solving the vehicle routing problem with backhauling. In Proceedings of the Babson conference on software uses in transportation and logistics management (pp. 75-96). Babson Park, MA.
Dorigo, M., & Gambardella, L. M. (1997). Ant colony system: a cooperative learning approach to the traveling salesman problem. IEEE Transactions on Evolutionary Computation, 1(1), 53-66.
Glover, F. (1989). Tabu search—part I. ORSA Journal on computing, 1(3), 190-206.
Laporte, G. (2009). Fifty years of vehicle routing. Transportation Science, 43(4), 408-416.
Lu, Q., & Dessouky, M. (2004). An exact algorithm for the multiple vehicle pickup and delivery problem. Transportation Science, 38(4), 503-514.
Olivera, A. (2004). Heurísticas para problemas de ruteo de vehículos. Reportes Técnicos 04-08.
Toth, P., & Vigo, D. (1999). A heuristic algorithm for the symmetric and asymmetric vehicle routing problems with backhauls. European Journal of Operational Research, 113(3), 528-543.
Toth, P., & Vigo, D. (1997). An exact algorithm for the vehicle routing problem with backhauls. Transportation science, 31(4), 372-385.

Journals

DSL Volumes

Keywords

Authors

Countries

Decision Science Letters

A heuristic algorithm based on tabu search for vehicle routing problems with backhauls Pages 171-180 Download PDF

Add Reviews