یک روش اصلاحی جمعیت مورچگان ترکیب شده با الگوریتم‌های ابتکاری درج و جابه‌جایی برای حل مسئله مسیریابی وسیله‌نقلیه همراه با پنجره‌های زمانی

نوع مقاله : مقاله پژوهشی

نویسندگان

1 استادیار، دانشگاه آزاد اسلامی، واحد پرند، تهران، ایران

2 مربی، گروه ریاضی، دانشگاه پیام نور، تهران، ایران

3 استادیار، دانشکده ریاضی و علوم کامپیوتر، دانشگاه صنعتی امیرکبیر، تهران، ایران

4 دانشیار، دانشکده ریاضی و علوم کامپیوتر، دانشگاه صنعتی امیرکبیر، تهران، ایران

5 دانشگاه آزاد اسلامی، واحد همدان، باشگاه پژوهشگران و نخبگان، همدان، ایران

چکیده

مسئله مسیریابی وسیله نقلیه همراه با پنجره‌های زمانی (VRPTW) یکی از مشهورترین مسائل بهینه‌سازی ترکیباتی در حوزه حمل و نقل است. چون این مسئله متعلق به مسائل -NP سخت است، بسیاری از دانشمندان و محققین روش‌های فراابتکاری برای حل آن ارایه داده‌اند. در این مقاله، به علت ضعف‌های موجود در الگوریتم سیستم مورچگان (ACS)، نسخه‌ای اصلاحی از این الگوریتم به نام HACS برای حل مسئله VRPTW ارایه می‌گردد. به منظور افزایش کارایی الگوریتم، دو روش جستجوی همسایه به نام‌های درج و جابجایی مورد استفاده قرار گرفته شده است. این اصلاحات سبب می‌شود که الگوریتم جدید از همگرایی زودرس اجتناب کند و به جواب‌های بسیار خوبی دست پیدا ‌کند. در نهایت برای تست کارایی الگوریتم، تعدادی از مجموعه مثال 56 تایی سالامان در نظر گرفته و نتایج این الگوریتم با دیگر روش‌ها در ادبیات موضوع مقایسه شده است. نتایج نشان می‌دهد که نه تنها الگوریتم پیشنهادی توانسته جواب‌های بسیار خوبی را به دست آورد بلکه هفت عدد از بهترین جواب‌های تاکنون به دست آمده به وسیله الگوریتم HACSحاصل می­گردد.
  
 

کلیدواژه‌ها


عنوان مقاله [English]

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

نویسندگان [English]

  • SH Azami 1
  • P Basi ri 2
  • F Didehvar 3
  • F Rahmai 4
  • M Yosefi khoshbakht 5
1
2
3
4
5
چکیده [English]

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.
 
 

کلیدواژه‌ها [English]

  • Vehicle Routing Problem with Time Windows
  • ant colony system
  • Insert Move
  • Swap Move
  • Combinatorial Optimization Problems
─   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) "ارزیابی
گزینه­های پیشنهادی برای حمل و نقل همگانی شهر مشهد"، چهارمین کنگره ملی مهندسی عمران، دانشگاه تهران.