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

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

چکیده

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

کلیدواژه‌ها

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

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

چکیده [English]

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%.

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

  • Periodic vehicle routing problem
  • Competitive time windows
  • Simulated Annealing
  • Improved simulated annealing

مراجع

-  توکلی مقدم، رضا، ربانی، مسعود، شریعت، محمد علی و صفائی، نیما (1385) " حل مسایل مسیریابی وسایط نقلیه با پنجره‌های زمانی نرم با استفاده از یک الگوریتم فرا ابتکاری  تلفیقی" نشریه فنی دانشگاه تهران، جلد 40، شماره 4، مهر 1385، ص. 476-469.
-  ربانی، یوسف، سپهری،  محمدمهدی، ذگردی، سید حسام الدین (1387)" مسأله مسیریابی وسیله نقلیه متصل به حمل ونقل چند وجهی رویکرد یکپارچه" پژوهشنامه حمل و نقل، سال پنجم، شماره چهارم، زمستان 1387 ص. 307-318.
-  سپهری، محمد مهدی و حسینی مطلق، سید مهدی (1387) "‌مسیر‌یابی بهینه‌ سیستم‌های حمل و نقل در انبار‌های اتوماتیک"، پژوهشنامه حمل و نقل، سال پنجم، شماره 2،  ص. 127-144.
-        Alegre, J., Laguna, M. and Pacheco, J. (2007) "Optimizing the periodic pick-up of raw materials for a manufacturer of auto parts", European Journal of Operational Research, Vol. 179, No. 3‌, June, pp.‌736–746.
 
-        Beltrami, E.J. and Bodin, L.D. (1974)‌ "Networks and vehicle routing for municipal waste collection", Networks‌, Vol. 4, No. 1, pp. 65–94.
 
-        Carter, M.W, Farvolden, J. M. Laporte, G and Xu, J. (1996) "Solving an integrated logistics problem arising in grocery distribution". INFOR, Vol. 34, No. 4, ‌pp. 290–306.
 
-        Chang, C.T. and Chang C. C. (2000) "A linearization method for mixed 0–1 polynomial programs", Computers & Operations Research, Vol. 27, No. 10, September, ‌pp.1005–1016.
 
-        Chao, I. M., Golden, B. L. and Wasil, E.A. (1995)‌ "An improved heuristic for the period vehicle routing problem",   Networks‌, Vol. 26, No. 1, pp. 25–44.
 
-        Christofides, N. and Beasley, J. E. (1984)‌ "The period routing problem", Networks, Vol. 14, No.1, pp. 237–256.
 
-        Claassen, G.D.H. and Hendriks, T. H. B. (2007)"An application of Special Ordered Sets to a periodic milk collection problem". European Journal of Operational Research, Vol.‌ 180, No. 2, July, pp. 754–769.
 
-        Clarke, G. and Wright, J. (1964) ‌ "Scheduling of vehicles from a central depot to a number of delivery points", Operations Research‌, Vol.‌ 12, No. 4, July, pp. 568–581.
 
-        Cordeau, F., Gendreau, M. and Laporte, G.‌ (1997) "A tabu search heuristic for periodic and multi-depot vehicle", Journal routing problems, Networks, Vol. 30, No. 2, pp.105-119.
 
-        Drummond, L.‌M.A., Ochi, L.S. and Vianna, D.S. (2001) "An asynchronous parallel metaheuristic for the period vehicle routing problem", Future Generation Compute Systems‌, Vol. 17, No. 4‌, pp.‌379–386.
 
-        Gaur, V.‌ and Fisher, M. L. (2004) "A periodic inventory routing problem at a supermarket chain", Operations Research, Vol. 52, No. 6‌, pp.‌813–822.  
 
-        Golden, B. L. and Wasil, E.A.  (1987) "Computerized vehicle routing in the soft drink industry". Operations Research, Vol. 35, No. 1‌, pp.6–17.
 
-        Fisher, M. L. and Jaikumar, R. (1981)‌ "A generalized assignment heuristic for vehicle  routing problems", Networks, Vol. 11, No. 2, pp.109–124.
 
-        Francis, P. M., Smilowitz, K.R. and Tzur, M. (2006) "The period vehicle routing problem with service choice", Transportation Science‌, Vol. 40, No. 4, October, ‌pp. 439–454.
 
-        Gaudioso, M. and Paletta, G. (1992) ‌ “A heuristic for the period vehicle routing problem” Transportation Science,  Vol. 26, No. 2, pp. 86–92.
 
-        Glover F. and Woolsey, L. (1974) "Converting the 0–1 polynomial programming problem to a 0–1 linear program", Operation Research, Vol. 22, No. 1, January, ‌pp. 180–182.
 
-        Golden, B.L., Magnanti, T. L. and Nguyen, H. Q. (1977)‌ "Implementing vehicle routing algorithms", Networks, Vol. 7, No. 2, pp. 113–148.
 
-        Hajek, B. (1985) "Cooling schedules for optimal annealing", Mathematics of Operations Research, Vol. 13, No. 2, May, ‌pp. 311–329.
 
-        Hemmelmayr, V., Doerner, K. and Hartl, R. (2009) "A variable neighborhood search heuristic for periodic routing problems", European Journal of Operational Research, Vol. 195, No. 3‌, June, pp. 791–802.
 
-        Kirkpatrick, F., Gelatt, C. and Vecci, M. (1983) "Optimization by simulated annealing", American Association for the Advancement of Science, Vol. 220, No. 4598, May, ‌pp. 671–680.
 
-        le Blanc, H. M., F. Cruijssen, H. A. Fleuren, and M. B. M. de Koster. Factory gate pricing: An analysis of the Dutch retail distribution. Working paper; http://econpapers.repec.org/paper/dgreureri/30001575.htm. (2004).
 
-        Lin, S. and Kernighan, B.W.  (1973) "An effective heuristic for the traveling salesman problem" Operations Research‌, Vol. 21, No. 2, March, pp. 498–516.
 
-        Mourgaya, M. and Vanderbeck, F. (2006) "Column generation based heuristic for tactical planning in multi-period vehicle routing", European Journal of Operational Research, Vol. 183, No. 3‌, pp. 1028–1041.
 
-        Norouzi, N., Tavakkoli-Moghaddam, R., Ghazanfari, M., Alinaghian, M. and salamatbakhsh, A. (2012) "A new multiobjective competitive open vehicle routing problem solved by particle swarm optimization", Networks and Spatial Economics, Vol. 14, No.4, ‌pp. 603–633.
 
-            Parthanadee, P. and Logendran, R. (2006) "Periodic product distribution from multi-depots under limited supplies", IIE Transactions, Vol. 38, No. 11, pp. 1009–1026.
 
-        Russell, R. A. (1977) "An effective heuristic for the M-tour traveling salesman problem with some side conditions" Operations Research, Vol. 25, No. 3, pp. 517–524.
 
-        Russell, R. A. and Gribbin, D. (1991)‌ "A multiphase approach to the period routing problem", Networks‌, Vol. 21, No‌. 7‌, pp.‌ 747–765.
 
-        Russell, R. A. and Igo, W. (1979) "An assignment routing problem", Networks, Vol. 9, No. 1, pp. 1–17.
 
-          Tan, C. C. R. and Beasley, J. E. (1984)‌ "A heuristic algorithm for the period vehicle routing problem", Omega, Vol. 12, No. 5, pp. 497–504.
 
-        Tavakkoli-Moghaddam, R., Ghazanfari, M., Alinaghian, M., salamatbakhsh, A. and Nourozi, N. (2011) "A new mathematical model for a competitive vehicle routing problem with time windows solved by simulated annealing", Journal of Manufacturing Systems, Vol. 30, No. 2, ‌pp. 83–92.
 
-       Toth, P. and Vigo, D. (2002) "The vehicle routing problem", University Degli Studi di Bologna, Italy.
 
 

فایل ها

سابقه مقاله

  • تاریخ دریافت: 25 تیر 1392
  • تاریخ پذیرش: 14 اسفند 1392

هم رسانی

ارجاع به این مقاله

آمار