A Modified Ant Colony System Hybridized with Insert and Swap Heuristic Algorithms for the Vehicle Routing Problem with Time Windows

Document Type : Original Article

Authors

Abstract

The vehicle routing problem with time windows (VRPTW) is one of the most well-known combinatorial problems in the transportation domain. Because this problem belongs to NP-Hard problems, many researchers have presented meta-heuristics for it. In this paper, aimed at the disadvantages existed in the current Ant Colony System (ACS), a modification of this algorithm called HACS is proposed for solving VRPTW. To improve the performance of ACS, two neighborhood search in the name of insert and swap algorithms are used. This new algorithm can avoid premature convergence and exploit more strong solutions. Finally, the effectiveness of the HACS on solving a number of the Solomon’s 56 VRPTW is validated by comparing the computational results with those previously presented in the literature. The results show that not only the proposed HACS algorithm can find good solutions but also seven best known solutions of the benchmark problem are also found by the proposed method.
 
 

Keywords

References

─   Barfod, M. B., Salling, K. B. and Leleur, S. (2011) "Composite decision support by combining cost-benefit and multi-criteria decision analysis", Decision Support Systems, Vol. 51, pp. 167–175.
─   Berechman, J. and Paaswell, R. (2005) "Evaluation, prioritization and selection of transportation investment projects in New York City", Transportation, Vol. 32, pp. 223-249.
─   Button, K.J. and Pearman, A.D. (1983) "The Practice of Transportation Investment Appraisal", Avebury, UK.
─   Gerçek, H., Karpak, B. and Kilinçaslan, T. (2004) "A multiple criteria approach for the evaluation of the rail transit networks in Istanbul", Transportation, Vol. 31, pp. 203–228.
─   Iniestra, J. G. and Gutierrez, J. G. (2009) "Multicriteria decisions on interdependent infrastructure transportation projects using an evolutionary-based framework", Applied Soft Computing, Vol. 9, pp. 512-526.
─   Joumard, R. and Nicolas, J.-P. (2010) "Transport project assessment methodology within the framework of sustainable Development", Ecological Indicators, Vol. 10, pp. 136–142.
─   Kim B. J., Kim W. and Song, B. H. (2008) "Sequencing and scheduling highway network expansion using a discrete network design model", The Annals of Regional Science, 42:621–642.
─   Pan, N-F. (2008) "Fuzzy AHP approach for selecting the suitable bridge construction method", ‎Automation in Construction, Vol. 17, pp. 958–965.‎
─   Poorzahedy, H. and Rouhani, O.M. (2007) "Hybrid meta-heuristic algorithms for solving network design problem", European Journal of Operational Research, Vol. 182, No. 2,
pp. 578–596.
─   Selih, J., Kne, A., Srdic, A. and Zura, M. (2008) "Multiple-criteria decision support system in highway infrastructure management", Transport, Vol. 23, No. 4, pp. 299–305.
─   Shelton, J. and Medina, M. (2010) "Prioritizing Transportation Projects using an Integrated Multiple Criteria Decision Making Method", Transportation Research Record: Journal of the Transportation Research Board, Vol. 2174,
pp. 51-57.
─   Su, C. W., Cheng, M. Y. and Lin, F. B. (2006) "Simulation‐enhanced approach for ranking major transport projects", Journal of Civil Engineering and Management, Vol. 12, No. 4, pp. 285-291.
─   Teng, J. and Tzeng, G. (1996) "A multiobjective programming approach for selecting non-independent transportation investment alternatives", Transportation Research Part B: Methodological,  Vol. 30, pp. 291-307.
─   Teng, J. and Tzeng, G. (1998) "Transportation investment project selection using fuzzy multiobjective programming", Fuzzy Sets and Systems, Vol. 96, pp. 259-280.
─   Tsamboulas, D. A. (2007) "A tool for prioritizing multinational transport infrastructure investments", Transport Policy, Vol. 14,
pp. 11–26.
─   Ugwu, O.O., Kumaraswamy, M.M., Wong, A. and Ng, S.T. (2006) "Sustainability appraisal in infrastructure projects (SUSAIP). Part 1: Development of indicators and computational methods", Automation in Construction, Vol. 15, pp. 239–251.
─   Weng, K. and Qu, B. (2009) "The optimization of road building schedule based on budget restriction", Kybernetes, Vol. 38, No. 3, pp. 441-447.
─   Yang, H. and Zhou, J. (1998) "Optimal traffic counting location for origin-destination matrix estimation", Transportation Research Part B, Vol. 32, No. 2, pp. 109-126.
─   Ziara, M., Nigim, K., Enshassi, A. and Ayyub, B. M. (2002) "Strategic Implementation of Infrastructure Priority Projects: Case Study in Palestine", Journal of Infrastructure Systems, Vol. 8, No. 1, pp. 2-11.
─       رضایی، ع. و اصغرزاده، س. م.(1387) "ارزیابی
گزینه­های پیشنهادی برای حمل و نقل همگانی شهر مشهد"، چهارمین کنگره ملی مهندسی عمران، دانشگاه تهران.

Files

Share

How to cite

Statistics