A Hybrid Modified Ant Colony for Solving the Capacitated Open Vehicle Routing Problem

Document Type : Research Paper

Authors

1 university

2 Young Researchers & Elite Club, Tehran North Branch, Islamic Azad University, Tehran, Iran

3 Department of Mathematics and Computer Science, Amirkabir University of Technology, Tehran, Iran

Abstract

The vehicle routing problem (VRP) involves routing a fleet of vehicles for serving to a number of customers, with the objective of minimizing the total distance traveled by all the vehicles. In this Problem, the vehicles are required to return to the depot after completing service. The open vehicle routing problem (OVRP) is different from most variants of vehicle routing problems from the literature in that the vehicle does not return to the depot after serving the last customer. The constraints considered in this problem are the following: all the vehicles have the same capacity the traveling time of each vehicle should not exceed a given threshold, which is defined by the drivers_ legal traveling time the total demand of all the customers on a route must not exceed the capacity of the vehicle each customer is visited just once by one of the vehicles, and its requirements must be completely fulfilled. The ant colony system (ACS) is one of the most famous metaheuristic algorithms that differs from the other ant colony optimization (ACO) instances due to its transition rule and updating pheromone. Aimed at the disadvantages existed in the current ACS algorithms for solving the OVRP, two effective modificitions including heuristic information and transition rule are proposed in this paper. Furthermore, this algorithm is mixed with lin-kernigan local search for improving solutions of the ants and exploites more strong solutions. Computational results on sixteen standard benchmark problem instances show that the proposed algorithm is comparable in terms of solution quality to the best performing published heuristics.

Keywords


[1] YousefiKhoshbakht, M., Sedighpour, M. (2012). “A Combination of Sweep Algorithm and Elite Ant Colony
Optimization for Solving the Multiple Traveling Salesman Problem”, Proceedings of the Romanian
Academy A, Vol 13, No. 4, pp. 295-302
[2] YousefiKhoshbakht, M., Didehvar, F., Rahmati, F. (2014). “An Efficient Solution for the Vehicle Routing
Problem by Using a Hybrid Elite Ant Colony Optimization”, International Journal of Computers,
Communications & Control, Vol. 9, No. 3, pp. 56-62
3[ یوسسی خوشب ت، مجیدد، دیدهیر، فرز دد، رحمتی، فرهاد ی هدیقپور، محمدد ) 1391 ( " لروریتم مو ر ر ا تی فر ویر ر ی حب مساله [
95 د -۸3 ، مسیریا ی یسیله نقلیه از “، پژیه نامه حمب ی نقب، دیره 9 ، شماره 1
[4] YousefiKhoshbakht, M., Didehvar, F., Rahmati, F. (2014). “A Combination of Modified Tabu Search and
Elite Ant System to Solve the Vehicle Routing Problem with Simultaneous Pickup and Delivery”,
Journal of Industrial and Production Engineering, Vol. 31, No. 2, pp. 65-75
[5] YousefiKhoshbakht, M., Didehvar, F., Rahmati, F. (2014). “Solving the Heterogeneous Fixed Fleet Open
Vehicle Routing Problem by a Combined Meta-heuristic Algorithm”, International Journal of
Production Research, Vol. 52, No. 9, pp. 2565-2575
[6] Schrage, L. (1981). “Formulation and structure of more complex/realistic routing and scheduling problems”, Networks, Vol. 11, pp. 229–232.
[7] Bodin, L., Golden, B., Assad, A.(1983). “Ball M. Routing and scheduling of vehicles and crews: the state of the art”, Computers & Operations Research, Vol. 10, No. 2, pp. 63–211.
[8] Sariklis, D., Powell, S. (2000). “A heuristic method for the open vehicle routing problem”, Journal of the Operational Research Society, Vol. 51, pp. 564–73.
[9] Tarantilis, C. D., Diakoulaki, D. and Kiranoudis, C. T. (2004). “Combination of geographical information system and efficient routing algorithms for real life distribution operations”, European Journal of Operational Research, Vol. 152, pp. 437–453.
[10] Tarantilis, C. D., Ioannou, G., Kiranoudis, C. T., Prastacos, G. P. (2005). “Solving the open vehicle routing problem via a single parameter metaheuristic algorithm”, Journal of the Operational Research Society, Vol. 56, pp. 588–596.
[11] Brand˜ao, J. (2004). “A tabu search algorithm for the open vehicle routing problem”, European Journal of Operational Research, Vol. 157, 552–564.
[12] Fu, Z., Eglese, R. and Li, L. Y. O. (2006). “A new tabu search heuristic for the open vehicle routing problem”, Journal of the Operational Research Society, Vol. 57, pp. 1018.
[13] Pisinger, D. and Ropke, S. (2007). “A general heuristic for vehicle routing problems”, Computers & Operations Research, Vol. 34, No. 8, pp. 2403-2435.
[14] Vincent, F. Yu, Parida Jewpanya, AAN Perwira Redi. (2016). "Open vehicle routing problem with cross-docking." Computers & Industrial Engineering, Vol. 94, pp. 6-17.
[15] Brito, Julio, et al. (2015). "An ACO hybrid metaheuristic for close–open vehicle routing problems with time windows and fuzzy constraints." Applied Soft Computing, Vol. 32, pp. 154-163.
[16] Li, X., Tian, P. (2006). “An ant colony system for the open vehicle routing problem”, Lecture Notes in Computer Science, 4150, pp. 356–63.
[17] Letchford, A. N., Lysgaard, J., Eglese, R. W. (2007). “A branch-and-cut algorithm for the capacitated open vehicle routing problem”, Journal of the Operational Research Society, Vol. 58, pp. 1642–51.
[18] Li, F., Golden, B., Wasil, E. (2007). “The open vehicle routing problem: Algorithms, large-scale test problems, and computational results”, Computers & Operations Research, Vol. 34, No. 10, pp. 2918-2930.
[19] Russell, R., Chiang, W. C., David, Z. (2008). “Integrating multi-product production and distribution in newspaper logistics”, Computers & Operations Research, Vol. 35, No. 5, pp. 1576-1588.
[20] Chiang, W. C., Russell, R., Xu, X., Zepeda, D. (2009). “A simulation/metaheuristic approach to newspaper production and distribution supply chain problems”, International Journal of Production Economics, Vol. 121, No. 2, pp. 752-767.
[21] Fleszar, K., Osman, I. H., Hindi, K. S. (2009). “A variable neighbourhood search algorithm for the open vehicle routing problem”, European Journal of Operational Research, Vol. 195, No. 3, pp. 803-809.
[22] Repoussis, P.P., Tarantilis, C.D., Bräysy, O., Ioannou, G. (2010). “A hybrid evolution strategy for the open vehicle routing problem”, Computers & Operations Research, Vol. 37, No. 3, pp. 443-455.
[23] López-Sánchez, A. D., et al. (2014). "A multi-start algorithm for a balanced real-world Open Vehicle Routing Problem." European Journal of Operational Research, Vol. 238, No. 1, pp. 104-113.
[24] Sicilia, J. A., Quemada, C., Royo, B., & Escuín, D. (2016). An optimization algorithm for solving the rich vehicle routing problem based on Variable Neighborhood Search and Tabu Search metaheuristics. Journal of Computational and Applied Mathematics, Vol. 291, pp. 468-477.
[25] Marinakis, Yannis. (2015). "An improved particle swarm optimization algorithm for the capacitated location routing problem and for the location routing problem with stochastic demands." Applied Soft Computing, Vol. 37 pp. 680-701.
[26] Dorigo, M., Ganbardella, L. (1997). “Ant colony system: a cooperative learning approach to the traveling salesman problem,” IEEE trans. Evolutionary Computing, pp. 53-66.
[27] Lin, S., Kernighan, B. W. (1973). “An effective heuristic algorithm for the traveling salesman problem”, Operations Research Vol. 21, No. 2, pp. 498-516.
[28] Brandão, J. (2004). “A tabu search algorithm for the open vehicle routing problem”, European Journal of Operational Research, Vol. 157, No. 6, pp. 552–64.
[29] Pisinger, D., Ropke, S. (2006). “A general heuristic for vehicle routing problems”, Computers & Operations Research, Vol. 34, pp. 2403–2435.