مسئله مسیریابی خوشه ای یک نوع از مسئله مسیریابی کلاسیک محسوب می شود که مشتریان آنرا به خوشه هایی تقسیم می کنند و فرض می شودکه هر خوشه قبل از خوشه بعدی خدمتی را به طورکامل دریافت نماید. مسئله به سه زیر مسئله تقسیم می شود، یعنی تخصیص خوشه ها به مسیرها، مسیریابی در درون هرخوشه و توالی خوشه ها در مسیریابی. دومین مسئله مهم در این نوع مسیریابی حل کردن مسیرهای چندگانه برای وجود امکان مسیریابی بهینه از طریق خوشه هاست. ما از قبل یک مسیر همیلتونی برای هر دو مشتری از یک خوشه را محاسبه می کنیم. یک جستجوی همسایگی چندگانه را ارائه می دهیم که با استفاده از تخریب چندین خوشه و تعمیر اپراتورها و سرازیری متغیر همسایگی (VND) برای پس از بهینه سازی استفاده می کند. VND براساس همسایگی های کلاسیک مانند جابه جا کردن دو انتخاب و مبادله همه کارها در سطح یک خوشه و تعمیم همسایگی بالاس سیمونتی به طور هم زمان، مسیرهای داخل یک خوشه و توالی خوشه ها را در یک مسیر تغییر می دهد. نتایج محاسباتی با رویکرد جدید ما،درمقایسه با رویکردهای موجود از مطالعات، مطلوب است. این پایان نامه براساس مرجع [37] است.
