واژههای کلیدی : مسئله مسیریابی ویزیتورها، تعادل بار کاری، الگوریتم ژنتیک، الگوریتم کلونی مورچگان عنوان فهرست مطالب صفحه فهرست جداول ....... ثفهرست اشکال .......... جفصل اول: مقدمه و کلیات پژوهش...... 11-1- مقدمه ......... 21-2- تعریف موضوع ..... 31-3- بیان مساله....... 51-4- ضرورت انجام تحقيق...... 61-5- اهداف تحقیق........ 61-6- مفروضات مساله ..................................................................................................................... 71-7- روش پژوهش ......................................................................................................................... 71-7-1- مطالعات مورد کاوی و تجربی .................................................................................. 81-7-2- چهار چوبها ، دسته بندی و مرور ادبیات ............................................................... 81-7-3- مدلهای کمی ............................................................................................................ 81-8- مراحل اجرای تحقیق و روش های گرد آوری اطلاعات ......................................................... 81-9- جامعه آماری و روش های گرد آوری اطلاعات ..................................................................... 9فصل دوم: ادبیات و پیشینه تحقیق .........................................................................................102-1- مقدمه .................................................................................................................................... 112-2- مروری بر مسائل VRP ......................................................................................................... 122-3- تاریخچه VRP ...................................................................................................................... 132-4- تقسیم بندی مساله VRP کلاسیک ........................................................................................ 132-4-1- مسیریابی وسیله ی نقلیه با دیدگاه ظرفیت (CVRP) ................................................ 142-4-2- مسیریابی وسیله ی نقلیه با حمل در بازگشت (VRPB) .......................................... 152-4-3- مسیریابی وسیله ی نقلیه با چنجره ی زمانی(VRPTW) .......................................... 152-4-4- مسیریابی وسیله ی نقلیه با تقاضای دریافت و تحویل (VRPPD) ........................... 162-4-5- مسیریابی دوره ای وسیله ی نقلیه(PVRP) .............................................................. 162-4-6- مسیریابی وسیله ی نقلیه با چهارچوب اتفاقی (SVRP) ........................................... 172-5- مرور ادبیات مسیریابی وسایل نقلیه با تقاضای تحویل و دریافت همزمان (VRPSPD) ....... 182-6- مروری بر تحقیقات انجام شده در مورد مساله مسیریابی وسایل نقلیه دارای چند مرکز تامین (MDVRP) .................................................................................................................................... 242-7- جمع بندی ............................................................................................................................ 27فصل سوم: مدل ریاضی پیشنهادی ......................................................................................... 283-1- مقدمه .................................................................................................................................... 293-2- تعریف مسئله ........................................................................................................................ 293-2-1- مفروضات مسئله ..................................................................................................... 303-3- مدل ریاضی پیشنهادی .......................................................................................................... 303-3-1- اندیس ها .................................................................................................................313-3-2- پارامترهای ورودی مدل .......................................................................................... 313-3-3- متغیر های تصمیم گیری ......................................................................................... 313-3-4- تابع هدف ............................................................................................................... 323-3-5- محدودیت ها .......................................................................................................... 323-4- اعتبارسنجی مدل ................................................................................................................... 353-5- پیچیدگی مدل مورد بررسی .................................................................................................. 363-6- جمع بندی ............................................................................................................................ 39فصل چهارم: الگوریتم فراابتکاری پیشنهادی .......................................................................... 404-1- مقدمه ای بر مسائل بهینه سازی ............................................................................................ 414-1-1- تئوری پیچیدگی ...................................................................................................... 414-1-2- روش های بهینه سازی ............................................................................................ 424-2- الگوریتم ژنتیک ..................................................................................................................... 464-2-1- برخی از اصطلاحات الگوریتم ژنتیک ..................................................................... 484-2-2- روش های انتخاب کروموزوم ................................................................................. 504-2-3- تقاطع ....................................................................................................................... 524-2-4- جهش ...................................................................................................................... 534-3- الگوریتم کلونی مورچگان ..................................................................................................... 544-3-1- مزیتهای روش کلونی مورچگان ........................................................................... 604-3-2- مراحل پیادهسازی الگوریتم کلونی مورچگان .......................................................... 614-4- الگوریتم مورچگان پیشنهادی ............................................................................................... 624-4-1- تبدیل مسئله به یک گراف جهتدار ......................................................................... 624-4-2- نحوهی ساختن پاسخ برای مسئله .............................................................................. 624-4-3- بروزرسانی فرومون ها .............................................................................................. 634-5- ارزیابی الگوریتم ها ............................................................................................................... 634-5-1- مجموعه داده ها ...................................................................................................... 644-5-2- مقایسه عملکرد الگوریتم ها برای مسائل با ابعاد کوچک ........................................ 654-5-3- مقایسه عملکرد الگوریتم ها برای مسائل با ابعاد متوسط تا بزرگ ........................... 674-6- مطالعه موردی ....................................................................................................................... 694-7- جمع بندی ............................................................................................................................ 72فصل پنجم: نتیجه گیری و پیشنهادات .................................................................................... 735-1- مقدمه .................................................................................................................................... 745-2- نتیجه گیری ........................................................................................................................... 745-3- پیشنهادات آتی ...................................................................................................................... 75فهرست منابع و مآخذ ...................................................................................................................... 76 عنوان فهرست جداول صفحه جدول 3-1 : داده های مسئله آزمایشی مربوط به هر گره ............................................................ 35 جدول 3-2: داده های مسئله آزمایشی مربوط به فواصل زمانی بین گره ها ................................. 35جدول 3-3 : زمان های تکمیل ویزیت هر گره در مسئله آزمایشی ............................................. 36جدول 4-1 : مقادیر داده های ورودی به مسائل آزمایشی ............................................................ 65جدول 4-2 : نتایج محاسباتی حاصل از حل مسائل با ابعاد کوچک ............................................ 66جدول 4-3 : زمان های محاسباتی و میانگین جواب های حاصل از حل مسائل با ابعاد کوچک... 66جدول 4-4 : نتایج محاسباتی حاصل از حل مسائل با ابعاد متوسط تا بزرگ ................................ 68جدول 4-5 : نتایج محاسباتی حاصل از حل مسئله کاربردی ........................................................ 71 عنوان فهرست اشکال صفحه شکل 1-1 : مسأله فروشنده دوره گرد ............................................................................................. 4شکل 1-2 : مسأله مسیریابی وسیله نقلیه ......................................................................................... 4شکل 1-3 : نشان دهندهی ارتباط بین نمونههای مختلف VRP ..................................................... 5شکل 3-1 : سلسله مراتب پیچیدگی محیط های کارگاهی در مسائل زمانبندی ............................ 38شکل 3-2 : سلسله مراتب پیچیدگی توابع هدف در مسائل زمانبندی ........................................... 38شکل 4-1 : انواع روش های بهینه سازی ...................................................................................... 43شکل 4-2 : مکانیزم انجام عملگر تقاطع یک نقطه ای در مسائل جایگشتی .................................. 53شکل 4-3 : نحوه انجام عملگر تعویض در مسائل جایگشتی ...................................................... 54شکل 4-4 : رفت و برگشت مورچگان به آشیانه و منبع غذایی .................................................... 56شکل 4-5 : ایجاد یک مانع در مسیر آشیانه تا منبع غذایی مورچگان ............................................ 57شکل 4-6 : ادامه حرکت مورچگان علی رغم حضور مانع ............................................................. 57شکل 4-7 : انتخاب مسیر کوتاهتر توسط همهی مورچه ها ............................................................ 58شکل 4-8 : مقایسه زمانهای محاسباتی مورد نیاز نرم افزار لینگو و الگوریتمهای پیشنهادی ......... 67شکل 4-9 : عکس هوایی از 161 سوپر مارکت مورد بررسی ........................................................ 70 فصل اولمقدمه و کلیات پژوهش 1-1- مقدمهاز آنجاییکه فروش کالا به عنوان شریان اصلی هر سازمان محسوب میشود. بنابراین بهبود کارايي در عملکرد کاری فروشندگان و افزایش سطح رضایتمندی آنها کمک بسزایی در افزایش سطج تحقق اهداف تعیین شده فروش سازمان مینماید. . بيشتر مسايل حوزه تخصیص مسیر مناسب و بهینه ميتوانند به صورت مساله مسيريابي وسيله نقليه[1] (VRP) درنظر گرفته شوند که تعميم مساله فروشنده دوره گرد[2] است و يکي از مسايل مهم در محدوده مسايل بهينه سازي ترکيبي است که روشهاي مکاشفهاي زيادي براي حل آن ايجاد شده است.مساله مسيريابي وسيلهء نقليه، شامل تعدادي مشتري است که هر يک به ميزان خاصي کالا نياز دارند که بايد به آنها تحويل گردد. هدف، تعيين مجموعهاي از مسيرها (يا تورها) است که کمترين مجموع هزينه را دارا بوده، در انبار آغاز شده و در آن پايان يابند، هر مشتري دقيقا يکبار و توسط يک فروشنده بازديد شود و کل تقاضاي گرههاي هر مسير از ظرفيت وسيله تجاوز نکند.که در این پژوهش فروشنده نقش وسیله نقلیه را در مدل VRP بازی می کند.از آنجا که VRP يک مساله بهينه سازي ترکيبي است و حل آن با روشهاي دقيق به زمان نمايي نياز دارد، روشهاي مکاشفهاي زيادي براي حل آن به کاررفته است. در اين پژوهش از الگوريتم ژنتیک(GA) و مورچگان(ACO) براي حل VRP استفاده شده است.سیاست های اجرایی در این پایان نامه عبارت است از : 1-2- تعریف موضوعمسائل مسیریابی وسایل نقلیه یکی از مفاهیم مورد توجه در زمینۀ تحقیق در عملیات است که در دو دهۀ اخیر تلاشها و به تبع آن پیشرفت های عظیمی در این زمینه انجام گرفته است. مسأله مسیر یابی وسایل نقلیه به مسائلی گفته میشود که در آن ناوگانی از چندین وسیلۀ نقلیه از یک یا چند تسهیل (قرارگاه) به سرویسدهی مشتریان در نقاط تقاضا می پردازند. به نحوی که هزینههای انجام کار حداقل گردد. وسیلۀ نقلیه با شروع از قرارگاههای مرکزی پس از ارائه خدمت به متقاضیان باز میگردد.هر وسیله میتواند دارای ظرفیت محدود بوده و همۀ مسیرهای مربوط از مبدأ (قرارگاه مرکزی) شروع و بعد از خدمترسانی به آن باز میگردد. تابع هدف این مسائل میتواند ارائه خدمت به مشتریان با کمترین تعداد خودرو، برآورده شدن همۀ تقاضاها و حداقل مسافت طی شده تعریف گردد.مسأله مسیریابی وسیلهی نقلیه، تعمیم یافتهی مدل فروشنده دوره گرد است. مسأله فروشندهی دوره گرد یکی از بنیادی ترین مسائل مسیر یابی و برنامه ریزی حمل و نقل است. در مسأله فروشنده دوره گرد هدف یافتن کوتاه ترین مسیری است که از همهی شهرها عبور کند و از هر شهر فقط یک بار ملاقات به عمل آید و سپس به شهر اولیه که از آن شروع به حرکت کرده است، باز گردد.این در حالی است که مسأله مسیر یابی وسیلۀ نقلیه می تواند به وسیلۀ یک گراف (V ,A ,D )=G نشان داده شود که {V0 ,V1 ,V2 ,… ,Vn}= Vمجموعه ای از گره ها و {i : (Vi ,Vj)} = Aمجموعه ای از کمان های متصل کننده گره ها هستند. D نیز متناسب با فاصله بین این گره ها یا طول کمان هاست. نقطۀ نشانگر قرارگاه و تا مشتریان را نشان می دهد. که با هر کمان (i, j ) مرتبط است نشانگر مسافت یا زمان مسافرت و یا هزینه مسافرت است. برای هر مشتری Vi یک تقاضای qi و یک زمان خدمتدر نظر گرفته شده است و هدف پیدا کردن حداقل هزینهی مسیرهای حمل و نقل است که در آن :¨ هرمشتری دقیقاً از یک وسیلهی نقلیه خدمت بگیرد¨ تمام مسیرهای وسایل نقلیه از قرارگاه مرکزی شروع و به آن ختم می شود¨ محدودیت های واقعی موجود در نظر گرفته می شود.به وضوح مشخص است که مسأله مسیر یابی وسیلۀ نقلیه پیچیدهتر از مسأله فروشندهی دوره گرد است، زیرا مسأله فروشندهی دوره گرد همان مسأله مسیریابی وسایل نقلیه است؛ با یک وسیلۀ نقلیه، بدون محدودیت و مبدأ مشخص، به طوری که مشتریان فاقد تقاضا هستند. در واقع حالت سادهی مسأله مسیریابی وسیلۀ نقلیه مسیرها به گونهای تعیین می شود که از هر گره فقط یک بار و با یک وسیلهی نقلیه ملاقات شود، و این در حالی است که پایان مسیرها یک نقطه است.در نتیجه مسأله مسیریابی وسایل نقلیه به دنبال آن است تا مسافت طی شده، زمان کل سفر، تعداد وسایل حمل و نقل، جریمه های دیرکرد و در نتیجه تابع هزینۀ حمل و نقل حداقل گردد و در نهایت رضایت مشتریان به حداکثر برسد. شکل های1-1 و 1-2 به ترتیب مربوط به مسیریابی وسیله نقلیه و مسأله فروشنده دوره گرد می باشد.شکل (1-1) : مسأله فروشنده دوره گردشکل (1-2) : مسأله مسیریابی وسیله نقلیهمسائل VRP در حالتهای متنوعی قابل بررسی می باشد. ولی در حالت کلی به 5 دسته عمده تقسیم می شوند:1)مسیر یابی وسیلۀ نقلیه ظرفیت دار شده با محدودیت ( CVRP )2) مسیر یابی وسیلۀ نقلیه با پنجره زمانی ( VRPTW )3)مسیر یابی وسیلۀ نقلیه با حمل در بازگشت ( VRPB )4) مسیر یابی وسیلۀ نقلیه با حمل در بازگشت و پنجرۀ زمانی ( VRPBTW )5) مسیر یابی وسیلۀ نقلیه با جمع آوری و توزیع ( VRPPD )شکل (1-3) نشان دهندهی ارتباط بین نمونههای مختلف VRP است. شکل (1-3) : نشان دهندهی ارتباط بین نمونههای مختلف VRP1-3- بیان مسالهسازمانهای امروزی در عرصه ملیوجهانی به منظور کسب جایگاهی مناسب و حفظ آن، نیازمند بهره گیری از الگویی مناسب برای سیستم فروش خود که به عنوان شاهرگ اصلی سازمان تلقی می شود ، می باشند. در این پژوهش نگارنده با مديريت و بهینه سازی مسیر بندی ویزیت فروشندگان و یکنواختی بار کاری آن ها به دنبال اتخاذ راهکارهايي جهت تحقق هرچه بهتر اهداف تعيين شده براي سازمان فروش مي باشد و با تعیین مسیر ویزیت مناسب و بهینه با درنظر گرفتن مهارت فروشندگان ، سعی در افزایش سطح رضایتمندی ویزیتور ها دارد. هدف از اجرای این پایان نامه ، تخصیص مسیر ویزیت مناسب به ویزیتور ها به گونه ای فشار کاری بین آن ها متعادل شود و توانایی آن ها برای رسیدن به اهداف فروش با برنامه ریزی صحیح افزایش یابد که منجر به تحق اهداف فروش آنها شود . از آن جا که تحقق اهداف فروش مستقیما با سطح در آمد آن ها رابطه مستقیم دارد و افزایش سطح درآمد به عنوان متغییر مهمی در افزایش سطح رضایتمندی ویزیتورها تلقی میشود تاثیر زیادی در افزایش فروش سازمان خواهد داشت.در جهت آزمون مدل یکی از مناطق ویزیت ، شرکت فروش و توزیع مویرگی بريون با هدف بهینه سازی مسیر ویزیت فروشندگان و تعادل بار کاری و افزایش درآمد بنگاه مورد نظر مورد آزمون قرار گرفته است. 1-4- ضرورت انجام تحقيقدر بسياري از سازمانهاي فروش بر اساس يك قاعدهي تجربي به منظور مسيربندي فروش فروشندگان تنها به متغييرهاي كمي همانند تعداد مشتريان در هر مسير توجه و پارامترهايي از قبيل سطح مهارت فروشندگان را ناديده ميگيرند كه اين امر منجر به كاهش بهرهوري و انگيزش فروشندگان خواهد شد. در اين پژوهش نگارنده با مسيربندي بهينه و در نظر گرفتن سطح مهارت فروشندگان منجر به افزايش سطح انگيزش آنها و كمك به تحقق اهداف فروش و رشد فروش سازماني ميشود.1-5- اهداف تحقیقاهداف اصلي تحقيق عبارت است از :يكي از اصلي ترين متغيير ها در جهت افزايش رضايتمندي فروشندگان ميزان عايدي آن ها در پايان هر ماه مي باشد كه اين ميزان درآمد به درصد تحقق اهداف وابسته مي باشد. در شكل فروش سنتي مسير بندي فروش به سطح توانمندي فروشندگان توجه نمي شود و تعداد ثابتي مشتري را به همه ي فروشندگان تخصيص مي دهد. كه اين مساله منجر به آن مي شود تا فروشندگان قوي تر تعداد مشتري هاي كمتري را نسبت به سطح توانايي خود ويزيت كرده و در نتيجه اهداف فروش خود را محقق كرده كه اين امر موجب مي شود تا سازمان نتواند از توانايي فروشنده خود بيه درستي بهرمند شود. و از آن سمت فروشندگان ضعيف توانايي ويزيت مشتريان بزرك را نخواهند داشت كه اين مساله باعث عدم تحقق اهداف آن ها ، كاهش عايدي و كاهش رضايتمندي شغلي در آن ها مي شود.
ارائه مدلي جهت بهینه سازی مسیر ویزیت فروشندگان با در نظر گرفتن یکنواختی بار کاری و حل مدل با الگوریتم ژنتیک (GA)و مقایسه خروجی نتایج با الگوریتم مورچگ
واژههای کلیدی : مسئله مسیریابی ویزیتورها، تعادل بار کاری، الگوریتم ژنتیک، الگوریتم کلونی مورچگان عنوان فهرست مطالب صفحه فهرست جداول ....... ثفهرست اشکال .......... جفصل اول: مقدمه و کلیات پژوهش...... 11-1- مقدمه ......... 21-2- تعریف موضوع ..... 31-3- بیان مساله....... 51-4- ضرورت انجام تحقيق...... 61-5- اهداف تحقیق........ 61-6- مفروضات مساله ..................................................................................................................... 71-7- روش پژوهش ......................................................................................................................... 71-7-1- مطالعات مورد کاوی و تجربی .................................................................................. 81-7-2- چهار چوبها ، دسته بندی و مرور ادبیات ............................................................... 81-7-3- مدلهای کمی ............................................................................................................ 81-8- مراحل اجرای تحقیق و روش های گرد آوری اطلاعات ......................................................... 81-9- جامعه آماری و روش های گرد آوری اطلاعات ..................................................................... 9فصل دوم: ادبیات و پیشینه تحقیق .........................................................................................102-1- مقدمه .................................................................................................................................... 112-2- مروری بر مسائل VRP ......................................................................................................... 122-3- تاریخچه VRP ...................................................................................................................... 132-4- تقسیم بندی مساله VRP کلاسیک ........................................................................................ 132-4-1- مسیریابی وسیله ی نقلیه با دیدگاه ظرفیت (CVRP) ................................................ 142-4-2- مسیریابی وسیله ی نقلیه با حمل در بازگشت (VRPB) .......................................... 152-4-3- مسیریابی وسیله ی نقلیه با چنجره ی زمانی(VRPTW) .......................................... 152-4-4- مسیریابی وسیله ی نقلیه با تقاضای دریافت و تحویل (VRPPD) ........................... 162-4-5- مسیریابی دوره ای وسیله ی نقلیه(PVRP) .............................................................. 162-4-6- مسیریابی وسیله ی نقلیه با چهارچوب اتفاقی (SVRP) ........................................... 172-5- مرور ادبیات مسیریابی وسایل نقلیه با تقاضای تحویل و دریافت همزمان (VRPSPD) ....... 182-6- مروری بر تحقیقات انجام شده در مورد مساله مسیریابی وسایل نقلیه دارای چند مرکز تامین (MDVRP) .................................................................................................................................... 242-7- جمع بندی ............................................................................................................................ 27فصل سوم: مدل ریاضی پیشنهادی ......................................................................................... 283-1- مقدمه .................................................................................................................................... 293-2- تعریف مسئله ........................................................................................................................ 293-2-1- مفروضات مسئله ..................................................................................................... 303-3- مدل ریاضی پیشنهادی .......................................................................................................... 303-3-1- اندیس ها .................................................................................................................313-3-2- پارامترهای ورودی مدل .......................................................................................... 313-3-3- متغیر های تصمیم گیری ......................................................................................... 313-3-4- تابع هدف ............................................................................................................... 323-3-5- محدودیت ها .......................................................................................................... 323-4- اعتبارسنجی مدل ................................................................................................................... 353-5- پیچیدگی مدل مورد بررسی .................................................................................................. 363-6- جمع بندی ............................................................................................................................ 39فصل چهارم: الگوریتم فراابتکاری پیشنهادی .......................................................................... 404-1- مقدمه ای بر مسائل بهینه سازی ............................................................................................ 414-1-1- تئوری پیچیدگی ...................................................................................................... 414-1-2- روش های بهینه سازی ............................................................................................ 424-2- الگوریتم ژنتیک ..................................................................................................................... 464-2-1- برخی از اصطلاحات الگوریتم ژنتیک ..................................................................... 484-2-2- روش های انتخاب کروموزوم ................................................................................. 504-2-3- تقاطع ....................................................................................................................... 524-2-4- جهش ...................................................................................................................... 534-3- الگوریتم کلونی مورچگان ..................................................................................................... 544-3-1- مزیتهای روش کلونی مورچگان ........................................................................... 604-3-2- مراحل پیادهسازی الگوریتم کلونی مورچگان .......................................................... 614-4- الگوریتم مورچگان پیشنهادی ............................................................................................... 624-4-1- تبدیل مسئله به یک گراف جهتدار ......................................................................... 624-4-2- نحوهی ساختن پاسخ برای مسئله .............................................................................. 624-4-3- بروزرسانی فرومون ها .............................................................................................. 634-5- ارزیابی الگوریتم ها ............................................................................................................... 634-5-1- مجموعه داده ها ...................................................................................................... 644-5-2- مقایسه عملکرد الگوریتم ها برای مسائل با ابعاد کوچک ........................................ 654-5-3- مقایسه عملکرد الگوریتم ها برای مسائل با ابعاد متوسط تا بزرگ ........................... 674-6- مطالعه موردی ....................................................................................................................... 694-7- جمع بندی ............................................................................................................................ 72فصل پنجم: نتیجه گیری و پیشنهادات .................................................................................... 735-1- مقدمه .................................................................................................................................... 745-2- نتیجه گیری ........................................................................................................................... 745-3- پیشنهادات آتی ...................................................................................................................... 75فهرست منابع و مآخذ ...................................................................................................................... 76 عنوان فهرست جداول صفحه جدول 3-1 : داده های مسئله آزمایشی مربوط به هر گره ............................................................ 35 جدول 3-2: داده های مسئله آزمایشی مربوط به فواصل زمانی بین گره ها ................................. 35جدول 3-3 : زمان های تکمیل ویزیت هر گره در مسئله آزمایشی ............................................. 36جدول 4-1 : مقادیر داده های ورودی به مسائل آزمایشی ............................................................ 65جدول 4-2 : نتایج محاسباتی حاصل از حل مسائل با ابعاد کوچک ............................................ 66جدول 4-3 : زمان های محاسباتی و میانگین جواب های حاصل از حل مسائل با ابعاد کوچک... 66جدول 4-4 : نتایج محاسباتی حاصل از حل مسائل با ابعاد متوسط تا بزرگ ................................ 68جدول 4-5 : نتایج محاسباتی حاصل از حل مسئله کاربردی ........................................................ 71 عنوان فهرست اشکال صفحه شکل 1-1 : مسأله فروشنده دوره گرد ............................................................................................. 4شکل 1-2 : مسأله مسیریابی وسیله نقلیه ......................................................................................... 4شکل 1-3 : نشان دهندهی ارتباط بین نمونههای مختلف VRP ..................................................... 5شکل 3-1 : سلسله مراتب پیچیدگی محیط های کارگاهی در مسائل زمانبندی ............................ 38شکل 3-2 : سلسله مراتب پیچیدگی توابع هدف در مسائل زمانبندی ........................................... 38شکل 4-1 : انواع روش های بهینه سازی ...................................................................................... 43شکل 4-2 : مکانیزم انجام عملگر تقاطع یک نقطه ای در مسائل جایگشتی .................................. 53شکل 4-3 : نحوه انجام عملگر تعویض در مسائل جایگشتی ...................................................... 54شکل 4-4 : رفت و برگشت مورچگان به آشیانه و منبع غذایی .................................................... 56شکل 4-5 : ایجاد یک مانع در مسیر آشیانه تا منبع غذایی مورچگان ............................................ 57شکل 4-6 : ادامه حرکت مورچگان علی رغم حضور مانع ............................................................. 57شکل 4-7 : انتخاب مسیر کوتاهتر توسط همهی مورچه ها ............................................................ 58شکل 4-8 : مقایسه زمانهای محاسباتی مورد نیاز نرم افزار لینگو و الگوریتمهای پیشنهادی ......... 67شکل 4-9 : عکس هوایی از 161 سوپر مارکت مورد بررسی ........................................................ 70 فصل اولمقدمه و کلیات پژوهش 1-1- مقدمهاز آنجاییکه فروش کالا به عنوان شریان اصلی هر سازمان محسوب میشود. بنابراین بهبود کارايي در عملکرد کاری فروشندگان و افزایش سطح رضایتمندی آنها کمک بسزایی در افزایش سطج تحقق اهداف تعیین شده فروش سازمان مینماید. . بيشتر مسايل حوزه تخصیص مسیر مناسب و بهینه ميتوانند به صورت مساله مسيريابي وسيله نقليه[1] (VRP) درنظر گرفته شوند که تعميم مساله فروشنده دوره گرد[2] است و يکي از مسايل مهم در محدوده مسايل بهينه سازي ترکيبي است که روشهاي مکاشفهاي زيادي براي حل آن ايجاد شده است.مساله مسيريابي وسيلهء نقليه، شامل تعدادي مشتري است که هر يک به ميزان خاصي کالا نياز دارند که بايد به آنها تحويل گردد. هدف، تعيين مجموعهاي از مسيرها (يا تورها) است که کمترين مجموع هزينه را دارا بوده، در انبار آغاز شده و در آن پايان يابند، هر مشتري دقيقا يکبار و توسط يک فروشنده بازديد شود و کل تقاضاي گرههاي هر مسير از ظرفيت وسيله تجاوز نکند.که در این پژوهش فروشنده نقش وسیله نقلیه را در مدل VRP بازی می کند.از آنجا که VRP يک مساله بهينه سازي ترکيبي است و حل آن با روشهاي دقيق به زمان نمايي نياز دارد، روشهاي مکاشفهاي زيادي براي حل آن به کاررفته است. در اين پژوهش از الگوريتم ژنتیک(GA) و مورچگان(ACO) براي حل VRP استفاده شده است.سیاست های اجرایی در این پایان نامه عبارت است از : 1-2- تعریف موضوعمسائل مسیریابی وسایل نقلیه یکی از مفاهیم مورد توجه در زمینۀ تحقیق در عملیات است که در دو دهۀ اخیر تلاشها و به تبع آن پیشرفت های عظیمی در این زمینه انجام گرفته است. مسأله مسیر یابی وسایل نقلیه به مسائلی گفته میشود که در آن ناوگانی از چندین وسیلۀ نقلیه از یک یا چند تسهیل (قرارگاه) به سرویسدهی مشتریان در نقاط تقاضا می پردازند. به نحوی که هزینههای انجام کار حداقل گردد. وسیلۀ نقلیه با شروع از قرارگاههای مرکزی پس از ارائه خدمت به متقاضیان باز میگردد.هر وسیله میتواند دارای ظرفیت محدود بوده و همۀ مسیرهای مربوط از مبدأ (قرارگاه مرکزی) شروع و بعد از خدمترسانی به آن باز میگردد. تابع هدف این مسائل میتواند ارائه خدمت به مشتریان با کمترین تعداد خودرو، برآورده شدن همۀ تقاضاها و حداقل مسافت طی شده تعریف گردد.مسأله مسیریابی وسیلهی نقلیه، تعمیم یافتهی مدل فروشنده دوره گرد است. مسأله فروشندهی دوره گرد یکی از بنیادی ترین مسائل مسیر یابی و برنامه ریزی حمل و نقل است. در مسأله فروشنده دوره گرد هدف یافتن کوتاه ترین مسیری است که از همهی شهرها عبور کند و از هر شهر فقط یک بار ملاقات به عمل آید و سپس به شهر اولیه که از آن شروع به حرکت کرده است، باز گردد.این در حالی است که مسأله مسیر یابی وسیلۀ نقلیه می تواند به وسیلۀ یک گراف (V ,A ,D )=G نشان داده شود که {V0 ,V1 ,V2 ,… ,Vn}= Vمجموعه ای از گره ها و {i : (Vi ,Vj)} = Aمجموعه ای از کمان های متصل کننده گره ها هستند. D نیز متناسب با فاصله بین این گره ها یا طول کمان هاست. نقطۀ نشانگر قرارگاه و تا مشتریان را نشان می دهد. که با هر کمان (i, j ) مرتبط است نشانگر مسافت یا زمان مسافرت و یا هزینه مسافرت است. برای هر مشتری Vi یک تقاضای qi و یک زمان خدمتدر نظر گرفته شده است و هدف پیدا کردن حداقل هزینهی مسیرهای حمل و نقل است که در آن :¨ هرمشتری دقیقاً از یک وسیلهی نقلیه خدمت بگیرد¨ تمام مسیرهای وسایل نقلیه از قرارگاه مرکزی شروع و به آن ختم می شود¨ محدودیت های واقعی موجود در نظر گرفته می شود.به وضوح مشخص است که مسأله مسیر یابی وسیلۀ نقلیه پیچیدهتر از مسأله فروشندهی دوره گرد است، زیرا مسأله فروشندهی دوره گرد همان مسأله مسیریابی وسایل نقلیه است؛ با یک وسیلۀ نقلیه، بدون محدودیت و مبدأ مشخص، به طوری که مشتریان فاقد تقاضا هستند. در واقع حالت سادهی مسأله مسیریابی وسیلۀ نقلیه مسیرها به گونهای تعیین می شود که از هر گره فقط یک بار و با یک وسیلهی نقلیه ملاقات شود، و این در حالی است که پایان مسیرها یک نقطه است.در نتیجه مسأله مسیریابی وسایل نقلیه به دنبال آن است تا مسافت طی شده، زمان کل سفر، تعداد وسایل حمل و نقل، جریمه های دیرکرد و در نتیجه تابع هزینۀ حمل و نقل حداقل گردد و در نهایت رضایت مشتریان به حداکثر برسد. شکل های1-1 و 1-2 به ترتیب مربوط به مسیریابی وسیله نقلیه و مسأله فروشنده دوره گرد می باشد.شکل (1-1) : مسأله فروشنده دوره گردشکل (1-2) : مسأله مسیریابی وسیله نقلیهمسائل VRP در حالتهای متنوعی قابل بررسی می باشد. ولی در حالت کلی به 5 دسته عمده تقسیم می شوند:1)مسیر یابی وسیلۀ نقلیه ظرفیت دار شده با محدودیت ( CVRP )2) مسیر یابی وسیلۀ نقلیه با پنجره زمانی ( VRPTW )3)مسیر یابی وسیلۀ نقلیه با حمل در بازگشت ( VRPB )4) مسیر یابی وسیلۀ نقلیه با حمل در بازگشت و پنجرۀ زمانی ( VRPBTW )5) مسیر یابی وسیلۀ نقلیه با جمع آوری و توزیع ( VRPPD )شکل (1-3) نشان دهندهی ارتباط بین نمونههای مختلف VRP است. شکل (1-3) : نشان دهندهی ارتباط بین نمونههای مختلف VRP1-3- بیان مسالهسازمانهای امروزی در عرصه ملیوجهانی به منظور کسب جایگاهی مناسب و حفظ آن، نیازمند بهره گیری از الگویی مناسب برای سیستم فروش خود که به عنوان شاهرگ اصلی سازمان تلقی می شود ، می باشند. در این پژوهش نگارنده با مديريت و بهینه سازی مسیر بندی ویزیت فروشندگان و یکنواختی بار کاری آن ها به دنبال اتخاذ راهکارهايي جهت تحقق هرچه بهتر اهداف تعيين شده براي سازمان فروش مي باشد و با تعیین مسیر ویزیت مناسب و بهینه با درنظر گرفتن مهارت فروشندگان ، سعی در افزایش سطح رضایتمندی ویزیتور ها دارد. هدف از اجرای این پایان نامه ، تخصیص مسیر ویزیت مناسب به ویزیتور ها به گونه ای فشار کاری بین آن ها متعادل شود و توانایی آن ها برای رسیدن به اهداف فروش با برنامه ریزی صحیح افزایش یابد که منجر به تحق اهداف فروش آنها شود . از آن جا که تحقق اهداف فروش مستقیما با سطح در آمد آن ها رابطه مستقیم دارد و افزایش سطح درآمد به عنوان متغییر مهمی در افزایش سطح رضایتمندی ویزیتورها تلقی میشود تاثیر زیادی در افزایش فروش سازمان خواهد داشت.در جهت آزمون مدل یکی از مناطق ویزیت ، شرکت فروش و توزیع مویرگی بريون با هدف بهینه سازی مسیر ویزیت فروشندگان و تعادل بار کاری و افزایش درآمد بنگاه مورد نظر مورد آزمون قرار گرفته است. 1-4- ضرورت انجام تحقيقدر بسياري از سازمانهاي فروش بر اساس يك قاعدهي تجربي به منظور مسيربندي فروش فروشندگان تنها به متغييرهاي كمي همانند تعداد مشتريان در هر مسير توجه و پارامترهايي از قبيل سطح مهارت فروشندگان را ناديده ميگيرند كه اين امر منجر به كاهش بهرهوري و انگيزش فروشندگان خواهد شد. در اين پژوهش نگارنده با مسيربندي بهينه و در نظر گرفتن سطح مهارت فروشندگان منجر به افزايش سطح انگيزش آنها و كمك به تحقق اهداف فروش و رشد فروش سازماني ميشود.1-5- اهداف تحقیقاهداف اصلي تحقيق عبارت است از :يكي از اصلي ترين متغيير ها در جهت افزايش رضايتمندي فروشندگان ميزان عايدي آن ها در پايان هر ماه مي باشد كه اين ميزان درآمد به درصد تحقق اهداف وابسته مي باشد. در شكل فروش سنتي مسير بندي فروش به سطح توانمندي فروشندگان توجه نمي شود و تعداد ثابتي مشتري را به همه ي فروشندگان تخصيص مي دهد. كه اين مساله منجر به آن مي شود تا فروشندگان قوي تر تعداد مشتري هاي كمتري را نسبت به سطح توانايي خود ويزيت كرده و در نتيجه اهداف فروش خود را محقق كرده كه اين امر موجب مي شود تا سازمان نتواند از توانايي فروشنده خود بيه درستي بهرمند شود. و از آن سمت فروشندگان ضعيف توانايي ويزيت مشتريان بزرك را نخواهند داشت كه اين مساله باعث عدم تحقق اهداف آن ها ، كاهش عايدي و كاهش رضايتمندي شغلي در آن ها مي شود.