Capacitated Windy Rural Postman Problem with Several Vehicles: A Hybrid Multi-Objective Simulated Annealing Algorithm

Rabbani, Masoud; Famil Alamdar, Safoura; Farrokhi-Asl, Hamed

doi:10.22034/2015.4.03

Capacitated Windy Rural Postman Problem with Several Vehicles: A Hybrid Multi-Objective Simulated Annealing Algorithm

Document Type : Research Paper

Authors

¹ College of Engineering, University of Tehran, Tehran, Iran

² School of Industrial Engineering, College of Engineering, University of Tehran, Tehran, Iran

³ School of Industrial Engineering, Iran University of Science & Technology, Tehran, Iran

10.22034/2015.4.03

Abstract

This paper presents the capacitated Windy Rural Postman Problem with several vehicles. For this problem, two objectives are considered. One of them is the minimization of the total cost of all vehicle routes expressed by the sum of the total traversing cost and another one is reduction of the maximum cost of vehicle route in order to find a set of equitable tours for the vehicles. Mathematical formulation is provided. The multi-objective simulated annealing (MOSA) algorithm has been modified for solving this bi-objective NP-hard problem. To increase algorithm performance, Taguchi technique is applied to design experiments for tuning parameters of the algorithm. Numerical experiments are proposed to show efficiency of the model. Finally, the results of the MOSA have been compared with MOCS (multi-objective Cuckoo Search algorithm) to validate the performance of the proposed algorithm. The experimental results indicate that the proposed algorithm provides good solutions and performs significantly better than the MOCS.

Keywords

Main Subjects

optimization in supply chain management

References

Ahr, D., & Reinelt, G. (2006). A Tabu search Algorithm for the Min-Max k-Chinese Postman Problem. Computers & Operations Research, Vol. 33, pp. 3403-3422.

Bandyopadhyay, S., Saha, S., Maulik, U., & Deb, K. (2008). A simulated annealing based multiobjective optimization algorithm: AMOSA. IEEE Transactions on Evolutionary Computation, Vol. 12(3), pp. 269–283.

Benavent, E., Corberán, A., Piñana, E., Isaac, P., & Sanchis, J. M. (2005). New heuristic algorithms for the windy rural postman problem. Computers & Operations Research, Vol. 32, pp. 3111 – 3128.

Benavent, E., Carrotta, A., Corberán, A., Sanchisc, J. M., & Vigo, D. (2007). Lower bounds and heuristics for the Windy Rural Postman Problem. European Journal of Operational Research, Vol. 176, pp. 855–869.

Benavent, E., Corberán, A., Sanchis, J. M., & Isaac, P. (2009). Min-Max K-vehicles Windy Rural Postman Problem. Wiley Periodicals, Inc. NETWORKS, Vol. 54(4), pp. 216–226.

Benavent, E., Corberán, A., & Sanchisc, J. M. (2010). A metaheuristic for the min–max windy rural postman problem with K vehicles. Computational Management Science, Vol. 7(3), pp. 269-287.

Benavent, E., Corberán, A., Isaac, P., & Sanchis, J. M. (2011). New facets and an enhanced branch-and-cut for the min–max K-vehicles windy rural postman problem. Wiley Periodicals, Inc. NETWORKS, Vol. 58(4), pp. 255–272.

Brucker, P. (1980). The Chinese postman problem for mixed graphs. InGraphtheoretic Concepts in Computer Science (pp. 354-366). Springer Berlin Heidelberg.

Christoﬁdes, N., Campos, V., Corberán, A., & Mota, E. (1986). An algorithm for the rural postman problem on a directed graph. Mathematical Programming Study, Vol. 26, pp. 155–66.

Corber n, A., Plana, I., & Sanchis, J. M. (2005). The Windy General Routing Polyhedron: A global view of many known Arc Routing Polyhedra. SIAM Journal on Discrete Mathematics, 22(2), 606–628.

Corber n, A., Plana, I., & Sanchis, J. M. (2007). A branch & cut algorithm for the windy general routing problem and special cases. Wiley Periodicals, Inc. NETWORKS, Vol. 49(4), pp. 245–257.

Czyzak, P., & Jaszkiewicz, A. (1998). Pareto simulated annealing – A metaheuristic technique for multipleobjective combinatorial optimization. Journal of Multi-Criteria Decision Analysis, Vol. 7, pp. 34–47.

Dror, M. (Ed.). (2012). Arc routing: theory, solutions and applications. Springer Science & Business Media.

Dussault, B., Golden, B., Groer, C., & Wasil, E. (2013). Plowing with precedence: A variant of the windy postman problem. Computers & Operations Research, Vol. 40, pp. 1047–1059.

Edmonds, J., & Johnson, E. (1973). Matching, Euler Tours and the Chinese Postman Problem. Mathematical Programming, Vol. 5, pp. 88-124.

Grötschel, M., & Win, Z. (1992). A cutting plane algorithm for the windy postman problem. Mathematical Programming, Vol. 55, pp. 339–58.

Guan, M. (1962). Graphic programming using odd or even points. Chinese Mathematics, Vol. 1, pp. 273-277.

Guan, M. (1984). On the windy postman problem. Discrete Applied Mathematics, Vol. 9(1), pp. 41–6.

Gun, H. (1993). Polyhedral structure and efficient algorithms for certain classes of the directed rural postman problem.
Kirkpatrick, S., Gerlatt, C. D., & Vecchi, N. P. (1983). Optimization by simulated annealing. Science, Vol. 220, pp. 671–680.

Martínez. F. J. Z. (2008). Series–parallel graphs are windy postman perfect. Discrete Mathematics, Vol. 308, pp. 1366 – 1374.

Micó, J. C., & Soler, D. (2011). The capacitated general windy routing problem with turn penalties. Operations Research, Vol. 39, pp. 265–271.

Minieka, E. (1979). The Chinese postman problem for mixed networks. Management Science, Vol. 25, pp. 643–8.

Orloff, C. (1974). A fundamental problem in vehicle routing. Wiley Periodicals, Inc. NETWORKS, Vol. 27, pp. 95-108.

Papadimitriou, C. H. (1976). on the complexity of edge traversing. Journal of the ACM (JACM), Vol. 23(3), pp. 544-554.

Pearn, W. L., & Li, M. L. (1994). Algorithms for the Windy Postman Problem. Computers & Operations Research, Vol. 21, pp. 641–651.

Rabbani, M., Farrokhi-Asl, H., & Ameli, M. (2016). Solving a fuzzy multi-objective products and time planning using hybrid meta-heuristic algorithm: Gas refinery case study. Uncertain Supply Chain Management, Vol. 4(2), pp. 93-106.

Rabbani, M., Ramezankhani, M. J., Farshbaf-Geranmayeh, A., & Farrokhi-Asl, H. (2015). Vehicle Routing with Time Windows and Customer Selection for Perishable Goods. International Journal of Supply and Operations Management, Vol. 2(2), pp. 700-719.

Savall, J. V. (1990). Polyhedral results and approximate algorithms for the directed rural postman problem (Doctoral dissertation, PhD dissertation).

Suman, B., & Kumar, P. (2006). A survey of simulated annealing as a tool for single and multiobjective optimization. Journal of Operational Research Society, Vol. 57, pp. 1143–1160.

Mori, T. (1991). The new experimental design: Taguchi's approach to quality engineering. Dearborn, Michigan: ASI press.

Win, Z. (1987). Contributions to routing problems. PhD dissertation, University of Augsburg, Germany.

Win, Z. (1989). On the windy postman problem on Eulerian graphs. Mathematical Programming, Vol. 44, pp. 97–112.

Yang, X. S., & Deb, S. (2009, December). Cuckoo search via Lévy flights. InNature & Biologically Inspired Computing, 2009. NaBIC 2009. World Congress on (pp. 210-214). IEEE.

Yang, X. S., & Deb, S. (2010). Engineering optimisation by cuckoo search. International Journal of Mathematical Modelling and Numerical Optimisation, Vol. 1, pp. 330–343.