حل مسئله مسيريابي وسايطنقليهبا استفاده از روش توليد ستون

حمل و نقل در سيستمهاي اقتصادي توليدي و خدماتي از جايگاه مهمي برخوردار است و بخـش قابـل تـوجهي از توليد ناخالص ملي يا GNP هر كشوري را به خود اختصاص مي دهد. به همين جهت محققان نسبت به بهبود مسيرها وحـذفسفرهاي غيرضروري و يا ايجاد مسيرهاي كوتاه جايگزين، اقدام كردهاند.مباحثي مانند فروشنده دورهگرد، مسئله مسيريابي حمل و نقل يا VRP و غيرهدر همين راستا توسعه يافتهاند. عموماً، در مورد مسيريابي تسهيلات فرض بر اين است كـهنوعي انحصار در محيط وجود دارد و هيچ گونه توجهي به تاثير بر مسيريابي مناسب بر رقابت در نظر گرفته نشده است. مسئله مسيريابي وسايط نقليه جزء مسائل NP-HARD است. ايـن مـسالهدرصدد است تا با مدلهاي رياضي و بهينهسازي به گونهاي عمـلكند كه مسافت طي شده، زمان كـل سـفر، تعـداد وسـايط نقليـه،جريمههاي ديركرد و در نهايت تابع هزينه حمل و نقـل كمينـه ودر نهايت رضايت مشتريان حداكثر شود. به علت ساختار بسيار مشكل مسئلهVRPالگوريتمهاي دقيق به ندرت براي اين مسئله مورد استفاده واقعشده است اماالگوريتمهاي ابتكاري و فراابتكاري از اقبالبيشتريبرخوردار بوده است. براي نمونه از الگوريتمهاي باكيفيت مي توان به روش توليد ستون يا CG اشاره كرد كه در اين تحقيق مورد استفاده قرار گرفته است.روش توليد ستون يك روش حل برنامه ريزي غير صحيح براي برنامه هاي كاربردي (با تقاضاي زياد) و گرد كردن به نزديكترين عدد صحيح باپاسخ رضايت بخش مي باشد.