An Efficient Hybrid Approach in Solving the Multiple Postman Problem

  • Authors

    • Asaad Shakir Hameed
    • Burhanuddin Mohd Aboobaider
    • Ngo Hea Choon
    • Wassim Habib Bilal
    • Modhi Lafta Mutar
    2018-12-09
    https://doi.org/10.14419/ijet.v7i4.36.23736
  • Traveling Salesman Problem, Sweep Algorithm, 3-opt local search, Ant Colony Algorithm.

  • Abstract

    In this study, the proposed algorithm contributed to the enhancing of solutions of the Multiple Postman Problem m-PP, which is one of the optimization problems that, has attracted a lot of attention at the present time. It is a problem of the NP-hard type. However, because of the complication of polynomial time, there is still no algorithm providing us with the optimal solution of this problem. All the used algorithms give solutions that are close to the optimal one. In this research, we will present the Hybrid Algorithm HA in two phases. In the first phase the Sweep Algorithm SW is applied, and in the second one, the Ant Colony Algorithm and the local search 3-opt are applied. we will then compare the quality of the solution resulted from this hybrid approach with the results of well-known standard tests to determine the effectiveness of the presented approach.

     

     

  • References

    1. [1] G. B. D. and J.H.Ramser, “The Truck Dispatching Problem,†JASTOR, vol. 6, no. 1, pp. 80–91, 1959.

      [2] J. E. Bell and P. R. McMullen, “Ant colony optimization techniques for the vehicle routing problem,†Adv. Eng. Informatics, vol. 18, no. 1, pp. 41–48, 2004.

      [3] M. Branch and F. Science, “Ant colony system method to vehicle routing problems,†vol. 6, no. 3, pp. 32–41, 2015.

      [4] Mohammed, M.A., Ghani, M.K.A., Arunkumar, N., Hamed, R.I., Mostafa, S.A., Abdullah, M.K. and Burhanuddin, M.A., 2018. Decision support system for nasopharyngeal carcinoma discrimination from endoscopic images using artificial neural network. The Journal of Supercomputing, https://doi.org/10.1007/s11227-018-2587-z.

      [5] J. K. Lenstra, “Complexity of Vehicle Routing and Scheduling Problems,†vol. 11, pp. 221–227, 1981.

      [6] L. De Boeck, “A Model Enhancement Approach for Optimizing the Integrated Shift Scheduling and Vehicle Routing Problem in Waste Collection,†Eur. J. Oper. Res., pp. 1–31, 2017.

      [7] A. Gutierrez, L. Dieulle, N. Labadie, and N. Velasco, “PT,†Comput. Oper. Res., 2018.

      [8] X. Zhang and L. Tang, “A new hybrid ant colony optimization algorithm for the vehicle routing problem,†Pattern Recognit. Lett., vol. 30, no. 9, pp. 848–855, 2009.

      [9] M. Song, J. Li, L. Li, and W. Yong, “Application of Ant Colony Algorithms to Solve the Vehicle Routing Problem,†vol. 4, pp. 831–840, 2018.

      [10] R. J. Mullen, D. Monekosso, S. Barman, and P. Remagnino, “Expert Systems with Applications A review of ant algorithms,†Expert Syst. Appl., vol. 36, no. 6, pp. 9608–9617, 2009.

      [11] H. Bhalani, S. Mahajan, and P. Z. Vyas, “Swarm Intelligence Technique ACO and Traveling Salesman Problem,†pp. 1002–1004, 2017.

      [12] G. B. Dantzlg and D. R. Fulkerson, “aASSIFIED ervices Tecliiiicännforniationflgency,†1954.

      [13] B. L. Golden, “Capacitated Arc Routing Problems,†vol. 11, pp. 305–315, 1981.

      [14] B. E. Gillett and L. R. Miller, “A Heuristic Algorithm for the Vehicle-Dispatch Problem,†no. August 2015, 1974.

      [15] Mohammed, M.A., Al-Khateeb, B., Rashid, A.N., Ibrahim, D.A., Ghani, M.K.A. and Mostafa, S.A., 2018. Neural network and multi-fractal dimension features for breast cancer classification from ultrasound images. Computers & Electrical Engineering.70,pp.871-882.

      [16] C. Blum, M. Jos, B. Aguilera, A. Roli, and M. Sampels, Hybrid Metaheuristics Studies in Computational Intelligence , Volume 114. 2008.

      [17] D. TOTH, P., VIGO, “Vehicle Routing: Problems, Methods, and Applications,†vol. 18, pp. 25–35, 2014.

      [18] D. Pisinger and S. Ropke, “A general heuristic for vehicle routing problems,†vol. 34, pp. 2403–2435, 2007.

      [19] P. Huachi, V. Penna, T. Vidal, and C. Prins, “A Hybrid Heuristic for a Broad Class of Vehicle Routing Problems with Heterogeneous Fleet,†pp. 1–48, 2018.

      [20] M. Schmidt et al., “GasLib – A Library of Gas Network Instances,†no. 2015, pp. 1–19, 2017.

      [21] Mohammed, M.A., Ghani, M.K.A., Arunkumar, N., Hamed, R.I., Abdullah, M.K. and Burhanuddin, M.A., 2018. A real time computer aided object detection of nasopharyngeal carcinoma using genetic algorithm and artificial neural network based on Haar feature fear. Future Generation Computer Systems, 89, pp.539-547.

      [22] Mohammed, M.A., Ghani, M.K.A., Arunkumar, N., Obaid, O.I., Mostafa, S.A., Jaber, M.M., Burhanuddin, M.A., Matar, B.M. and Ibrahim, D.A., 2018. Genetic case-based reasoning for improved mobile phone faults diagnosis. Computers & Electrical Engineering, 71, pp.212-222.

      [23] Mostafa, S.A., Mustapha, A., Mohammed, M.A., Ahmad, M.S. and Mahmoud, M.A., 2018. A fuzzy logic control in adjustable autonomy of a multi-agent system for an automated elderly movement monitoring application. International journal of medical informatics, 112, pp.173-184.

      [24] Mostafa, S.A., Mustapha, A., Hazeem, A.A., Khaleefah, S.H. and Mohammed, M.A., 2018. An Agent-Based Inference Engine for Efficient and Reliable Automated Car Failure Diagnosis Assistance. IEEE Access, 6, pp.8322-8331.

      [25] Ghani, M.K.A., Mohammed, M.A., Ibrahim, M.S., Mostafa, S.A. And Ibrahim, D.A., 2017. Implementing An Efficient Expert System For Services Center Management By Fuzzy Logic Controller. Journal of Theoretical & Applied Information Technology, 95(13).

  • Downloads

  • How to Cite

    Shakir Hameed, A., Mohd Aboobaider, B., Hea Choon, N., Habib Bilal, W., & Lafta Mutar, M. (2018). An Efficient Hybrid Approach in Solving the Multiple Postman Problem. International Journal of Engineering & Technology, 7(4.36), 154-159. https://doi.org/10.14419/ijet.v7i4.36.23736

    Received date: 2018-12-12

    Accepted date: 2018-12-12

    Published date: 2018-12-09