ارائه الگوریتم ترکیبی حل مسئله مسیریابی وسیله نقلیه همراه با دریافت و تحویل همزمان کالا

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

نویسندگان

1 استادیار، دانشکده مهندسی (گروه عمران)، دانشگاه زنجان

2 دانشجوی کارشناسی ارشد راه و ترابری، دانشکده مهندسی، دانشگاه بین المللی امام خمینی

چکیده

مسئله مسیریابی وسیله نقلیه از مباحث مهمی است که در چند دهه اخیر کاربرد زیادی در بهره وری و کارایی سیستم های حمل ونقل داشته است. یکی از توسعه های معروف و پرکاربرد این موضوع، مسئله مسیریابی وسیله نقلیه با دریافت و تحویل همزمان کالا است که در آن، عمل تحویل و جمع آوری کالا برای هر مشتری به صورت همزمان انجام می گیرد. الگوریتم پیشنهادی در این مقاله، ترکیبی از سه الگوریتم ابتکاری نزدیک ترین همسایگی، ارزان ترین الحاقی و ژنتیک است که دو الگوریتم اول به همراه یک روش تصادفی، جواب ابتدایی را برای الگوریتم سوم فراهم می کنند. در روشهای نزدیک ترین همسایگی و ارزان ترین الحاقی، یک تابع احتمالی برای ایجاد جواب های بهتر ابداع شده است. همچنین عملگرهایی برای الگوریتم ژنتیک به منظور افزایش فضای جستجو و فرار از بهینه های محلی پیشنهاد شده و پس از آن، الگوریتم پیشنهادی بر روی چهل مثال استاندارد و متنوع اجرا شده و با مقایسه نتایج بدست آمده از آن و بهترین جواب های موجود از سایر الگوریتم ها، بهبود مناسبی نیز مشاهده گردیده است.

کلیدواژه‌ها

موضوعات

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

A Hybrid Meta-heuristic Algorithm for the Vehicle Routing Problem with Simultaneous Delivery and Pick-up

نویسندگان [English]

  • A. M. Rahimi 1
  • V. Rajabi-Tavarat 2
1 Assistant Professor, Faculty of Engineering (Department of Civil Engeineering), University of Zanjan
2 M.Sc. Student of Highway and Transportation Engineering, Faculty of Engineering, Imam Khomeini International University
چکیده [English]

Vehicle routing problem (VRP) is an important issue that has much used for productivity and efficiency
of transportation systems in recent decades. One of the most popular and widely used developments
VRP is the vehicle routing problem with simultaneous delivery and pick-up (VRPSPD). In other words,
each customer simultaneously receives and sends goods. The proposed procedure is a combination of
the three heuristic: nearest neighbor algorithm, cheapest insertions, genetic algorithm. The first two
algorithms with a random method provided the initial solution for the third algorithm. A probability
function has been developed in the nearest neighbors and cheapest insertions to construct better solutions
as well as operations proposed for the genetic algorithm to increase the search space and avoiding local
optimizations. The proposed algorithms have implemented on forty different standard examples. By
comparing, the results obtained from the best available solutions than other algorithms, improvement
observed in some examples.

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

  • Hybrid Meta-Heuristic Algorithm
  • Vehicle Routing Problem
  • Simultaneous Delivery and Pick-up
  • genetic algorithm

مراجع

[1]Dantzig, G. B. and Ramser, R. H.; “The Truck Dispatching Problem,” Management Science, Vol. 6, No. 1, pp. 80–91, 1958.
[2]Min, H.; “The Multiple the Vehicle Routing Problem with Simultaneous Delivery and Pick-up Points,” Transportation Research-Part A, Vol. 23, No. 5, pp. 377–386, 1989.
[3]Salhi, S. and Nagy, G.; “A Cluster Insertion Heuristic for Single and Multiple Depot Vehicle Routing Problems with Backhauling,” Journal of the Operational Research Society, Vol. 50, No. 10, pp. 1034–1042, 1999
[4]Dethloff, J.; “Vehicle Routing and Reverse Logistics: The Vehicle Routing Problem with Simultaneous Delivery and Pick-up,” OR Spektrum, Vol. 23, No. 1, pp. 79–96, 2001.
[5]Montane, F. A. T. and Galvao, R. D.; “Vehicle Routing Problems with Simultaneous Pick-up and Delivery Service,” OPSEARCH, Vol. 39, No. 1, pp. 19–33, 2002.
[6]Angelelli, E. and Mansini, R.; “The Vehicle Routing Problem with Time Windows and Simultaneous Pick-up and Delivery,” Quantitative Approaches to Distribution Logistics and Supply Chain Management, Lecture Notes in Economics and Mathematical Systems, Springer-Verlag, pp. 249–267, 2002.
[7]Nagy, G. and Salhi, S.; “Heuristic Algorithms for Single and Multiple Depot Vehicle Routing Problems with Pickups and Deliveries,” European Journal of Operational Research, Vol. 162, No. 1, pp. 126–141, 2005.
[8]Chen, J. F. and Wu, T. H.; “Vehicle Routing Problem with Simultaneous Deliveries and Pickups,” Journal of the Operational Research Society, Vol. 57, No. 5, pp. 579–587, 2006.
[9]Tang-Montane, F. A. and Galvao, R. D.; “A Tabu Search Algorithm for the Vehicle Routing Problem with Simultaneous Pick-up and Delivery Service,” Computers and Operations Research, Vol. 33, No. 3, pp. 595–619, 2006.
[10]Bianchessi, N. and Righini, G.; “Heuristic Algorithms for the Vehicle Routing Problem with Simultaneous Pick-up and Delivery,” Computers and Operations Research, Vol. 34, pp. 2578–594, 2007.
[11]Zachariadis, E.; Tarantilis, D. and Kiranoudis, T.; “A Hybrid Metaheuristic Algorithm for the Vehicle Routing Problem with Simultaneous Delivery and Pick-up Service,” Expert Systems with Applications, Vol. 36, No. 2, pp. 1070–1081, 2009.
[12]Gajpal, Y. and Abad, P.; “An Ant Colony System (ACS) for Vehicle Routing Problem with Simultaneous Delivery and Pick-up,” Computers and Operations Research, Vol. 36, No. 12, pp. 3215–3223, 2009.
[13]Catay, B.; “A New Saving-based Ant Algorithm for the Vehicle Routing Problem with Simultaneous Pick-up and Delivery,” Expert Systems with Applications, Vol. 37, No. 10, pp. 6809–6817, 2010.
[14]Davis, L.; “Applying Algorithms to Epistatic Domains,” International Joint Conferences on Artificial Intelligence, Vol. 85, pp. 162–164, 1985.
[15]Zachariadis, E. E. and Kiranoudis, C. T.; “A Local Search Meta-heuristic Algorithm for the Vehicle Routing Problem with Simultaneous Pick-ups and Deliveries,” Expert Systems with Applications, Vol. 38, No. 3, pp. 2717–2726, 2011.
نشریه مهندسی عمران امیرکبیر
دوره 48، شماره 4
دی 1395
صفحه 375-386

فایل ها

هم رسانی

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

آمار