Optimizing of Open Vehicle Routing Problem by Using an Efficient Hybrid Meta-heuristic Algorithm

Subject Areas : Industrial Management

Majid Yousefi khoshbakht ¹ , Hassan Zarie ² , Zahra Sadati Eskandari ³ , Narges Mahmmudi Daranie ⁴ , Ahmad Mahmmud Janlo ⁵

1 - Member of Faculty Staff and Member of Young Researchers Club, Islamic Azad University, Hamadan Branch, Hamadan, Iran
2 - Faculty of Mathematics, Payam Noor University, Hamadan, Hamadan, Iran
3 - M. A Graduated and Member of Young Researchers Club, Islamic Azad University, Faridan Branch,
4 - Member of Faculty Staff, Islamic Azad University, Robat Karim Branch, Robat Karim. Tehran
5 - M.A Graduated, Faculty of Mathematics and Computer Sciences, Amirkabir University of Technology, Tehran, Iran

Received: 2018-01-08 Accepted : 2018-01-08 Published : 2013-08-23

Keywords:

Abstract :

The Open Vehicle Routing Problem (OVRP) is one of the most intensively studied problems in computational mathematics that nowadays and it has been receiving much attention by researchers and scientists. In this Problem, the objective is to define minimized distance traveled of the several vehicles that start to move simultaneously from the depot and visit some customers. It is noted that against to the Vehicle Routing Problem (VRP), it is not necessary that vehicles return to the depot after servicing the customers. This paper proposes a meta-heuristic algorithm in which at the first stage, a modified elite ant colony (EAS) is applied for finding a suboptimal solution, and at the second stage, the insert and swap local search algorithms are used for finding better solutions. Computational results on fifteen standard benchmark problem instances show that the proposed algorithm is comparable in terms of solution quality of other meta-heuristic algorithms.  

References:

1-      Bodin, L., Golden, B., Assad, A. & Ball, M. (1983). Routing and scheduling of vehicles and crews: the state of the art. Computers & Operations Research, 10, 63–211.

2-      Brandão, J. (2004). A tabu search algorithm for the open vehicle routing problem. European Journal of Operational Research, 157, 52–64.

3-      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, 121(2), 752-767.

4-      Christofides, N., Mingozzi, A. & Toth, P. (1979). The vehicle routing problem, In: Christofides N, Mingozzi A, Toth P, Sandi C, editors. Combinatorial optimization. Chichester, UK: Wiley, 315-338.

5-      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(1), 29–41.

6-      Fleszar, K., Osman, I. H. & Hindi, K. S. (2009). A variable neighborhood search algorithm for the open vehicle routing problem. European Journal of Operational Research, 195(3), 803-809.

7-      Fu, Z., Eglese, R. & Li, L. (2005). A new tabu search heuristic for the open vehicle routing problem. Journal of the Operational Research Society, 56, 267–274.

8-      Levy, L. (2005). Private communication, in RouteSmart Technologies.

9-      Li, F., Golden, B. & Wasil, E. (2005). Very large-scale vehicle routing: new test problems, algorithms, and results. Computers & Operations Research, 32,  1165–1179.

10-  Li, F., Golden, B. &Wasil, E. (2007). The open vehicle routing problem: Algorithms, large-scale test problems, and computational results. Computers & Operations Research, 34(10), 2918-2930.

11-  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, 58, 1642–1651.

12-  MirHassani, S. A. & Abolghasemi, N. (2011). A particle swarm optimization algorithm for open vehicle routing problem. Expert Systems with Applications, 38(9), 11547-11551.

13-  Pisinger, D. & Ropke, S. (2005). A general heuristic for vehicle routing problems. University of Copenhagen, Technical Report 05/01, DIKU.

14-  Repoussisa, P. P., Tarantilisa, C. D., Braysy, O. & Ioannoua, G. (2010). A hybrid evolution strategy for the open vehicle routing problem. Computers & Operations Research, 37, 443-455.

15-  Russell, R., Chiang, W. C. & David, Z. (2008). Integrating multi-product production and distribution in newspaper logistics. Computers & Operations Research, 35(5),  1576-1588.

16-  Saadati Eskandari, Z. & Yousefikhoshbakht, M. (2012). Solving the vehicle routing problem by using an effective reactive bone route algorithm. Transportation Research Journal, 1, 51-67.

17-  Salari, M., Toth, P. &Tramontani, A. (2010). An ILP improvement procedure for the Open Vehicle Routing Problem. Computers & Operations Research, 37(12), 2106-2120.

18-  Sariklis, D. & Powell, S. (2000). A heuristic method for the open vehicle routing problem. Journal of the Operational Research Society, 51, 64–73.

19-  Schrage, L. (1981). Formulation and structure of more complex/realistic routing and scheduling problems. Networks, 11, 229–232.

20-  Taillard, R. (1995). Probabilistic diversification and intensification in local search for vehicle routing. Journal of Heuristics, 1(1), 147–167.

21-  Tarantilis, C., Diakoulaki, D. & Kiranoudis, C. (2004). Combination of geographical information system and efficient routing algorithms for real life distribution operations. European Journal of Operational Research, 152, 37–53.

22-  Tarantilis, C., Ioannou, G., Kiranoudis, C. & Prastacos, G. (2004). A threshold accepting approach to the open vehicle routing problem, RAIRO Operations Research, 38, 345–360.

23-  Yousefikhoshbakht, M., Didehvar, F., Rahmati, R. & Saadati Eskandari, Z. (2012). A hybrid ant colony system for the heterogeneous fixed fleet vehicle routing problem. Transportation Research Journal, 9(2), 191-207.

24-  Yousefikhoshbakht, M., Didehvar, F., Rahmati, R. & Sedighpour, M. (2012). An effective imperialist competitive algorithm for solving the open vehicle routing problem. Transportation Research Journal, 9(1), 83-95

25-  Yousefikhoshbakht1, M. & Khorram, E. (2012). Solving the vehicle routing problem by a hybrid meta-heuristic algorithm. Journal of Industrial Engineering International, 8(11), 1-9.

26-  Yousefikhoshbakht, M. & Rahmati, R. (2011). An Improved Ant Colony System for Solving the Vehicle Routing Problem with Simultaneous Pickup and Delivery. Transportation Research Journal, 8(2), 183-198.

27-  Yu, S., Ding, C. & Zhu, K. 2011. A hybrid GA–TS algorithm for open vehicle routing optimization of coal mines material. Expert Systems with Applications, 38(8), 10568-10573.

28-   Zafari, A., Tashakori , S. M. & Yousefikhoshbakht  M. (2010). A Hybrid Effective Genetic Algorithm for Solving the Vehicle Routing Problem. International Journal of Industrial Engineering and Production Management, 21 (2), 63-76.