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

Periodic Vehicle Routing Problem with Time Windows in a Competitive Environment by an Improved Simulated Annealing Method

در اين مقاله، حالت جديدي از تركيب مساله مسريابي دوره اي با در نظر گرفتن پنجره‌ زماني در حالت رقابتي مورد بررسي قرار مي‌گيرد. با توجه به دنياي واقعي، هميشه، چندين توزيع كننده به منظور خدمت‌دهي به مشتريان وجود دارد. بر اين اساس هميشه رقابت بين رقبا و تمايل به دسترسي سريع تر به مشتريان با ارزش بالا براي كسب نقدينگي بيشتر علاوه بر يافتن مسيرهاي كوتاه وجود دارد. به همين جهت، هدف اين مقاله ارايه مدلي است كه با كوتاه ترين مسير و كمترين هزينه، در زود‌ترين زمان ممكن و زود‌تر از رقبا به مشتريان سرويس‌دهي كند تا حداكثر سود را كسب كنند. به دليل كاربرد فراوان اين مدل در توزيع دوره اي محصولات، مساله مسيريابي وسايط نقليه دوره‌اي در حالت رقابتي در اين مقاله مورد توجه قرار گرفته است. با توجه به اينكه مساله مورد نظر حالتي از مسيريابي وسايط نقليه است، اين مساله جز مسايل NP-Hard قرار مي گيرد. از همين رو در اين مقاله، از روش شبيه‌سازي تبريد (SA) و روش شبيه‌سازي تبريد بهبود يافته(ISA) جهت حل مدل پيشنهادي استفاده مي شود. از اين رو تعدادي مساله در ابعاد متنوع توليد شده و سپس براي نشان دادن كارآيي الگوريتم‌هاي ارايه شده پاسخ‌هاي به دست آمده با الگوريتم دقيق شاخه و كران مقايسه مي شود و پاسخ‌هاي به دست آمده مورد تجزيه و تحليل قرار مي گيرد. نتايج نشان دهنده‌ آن است كه درصد خطاي روش SA و ISA در ابعاد كوچك به طور ميانگين به ترتيب ا درصد و صفر درصد است كه كارآيي الگوريتم هاي پيشنهادي را نشان مي‌دهد. علاوه بر اين، زمان حل مسايل در روشهاي فرا ابتكاري نشان دهنده خطي بودن افزايش زمان رسيدن به پاسخ با افزايش ابعاد مساله است، ولي مدت زمان رسيدن به پاسخ توسط روش دقيق با افزايش ابعاد مساله به صورت نمايي افزايش مي يابد. در ابعاد بزرگ به طور ميانگين از نظر زماني الگوريتم ISA تقريبا 20 درصد كند تر از روش SA عمل مي كند، اما كيفيت پاسخ هاي الگوريتم به طور ميانگين ISA 3 درصد بهتر از الگوريتم SA است. همچنين حداكثر ميزان بهبود روش ISA نسبت به SA نيز 7 درصد بوده است. اين امر نشان مي دهد كه بهبود ايجاد شده در الگوريتم SA تاثير مناسبي در بهبود پاسخ‌ها داشته است.

This paper considers a periodic vehicle routing problem (PVRP) with time windows in a competitive environment. In a real-world environment, there are several competitive distributers exist between them in order to access to customers earlier than other distributers to gain more market share in a minimum travelling cost. In this paper, a mathematical model for this situation is presented that minimizes the travel cost and maximizes the market share simultaneously. Due to the complexity of this problem, it is so difficult to optimally solve it in a reasonably computational time by exact methods. Thus, two meta-heuristic algorithms are proposed based on simulated annealing (SA) and improved simulated annealing (ISA). In addition, to show the efficiency of the proposed algorithms, a number of test problems are solved and the obtained results are evaluated with the result obtained by the Lingo software. Finally, the associated results are analyzed and the conclusion is presented. Furthermore, with increasing in dimension of the problem the running time of the meta-heuristics increases linearly. However, the running time rises exponentially in the exact algorithm. In large-scale problems, SA performs 20% better than ISA but the quality of the solutions obtained by ISA is 3% better than the SA algorithm. Furthermore, the maximum improvement made by ISA in comparison to SA is 7%.