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

رحیمی, امیرمسعود; رجبی توارات, وحید

doi:10.22060/ceej.2016.576

دانشگاه صنعتی امیرکبیر

تعداد نشریات	4
تعداد شماره‌ها	157
تعداد مقالات	1,849
تعداد مشاهده مقاله	1,009,305
تعداد دریافت فایل اصل مقاله	785,317

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

نشریه مهندسی عمران امیرکبیر

مقاله 3، دوره 48، شماره 4، زمستان 1395، صفحه 375-386 اصل مقاله (1072 K)

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

شناسه دیجیتال (DOI): 10.22060/ceej.2016.576

نویسندگان

امیرمسعود رحیمی

¹؛ وحید رجبی توارات²

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

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

چکیده

مسأله مسیریابی وسیله نقلیه (VRP) از مباحث مهمی است که در چند دهه‌ی اخیر کاربرد زیادی برای بهره‌وری و کارایی سیستم‌های حمل‌ و نقل داشته است. یکی از توسعه‌های معروف و پُرکاربرد VRP، مسأله مسیریابی وسیله نقلیه با دریافت و تحویل همزمان کالا (VRPSPD) است که در آن عمل تحویل و جمع‌آوری کالا برای هر مشتری به طور همزمان انجام می‌شود، یعنی هر مشتری به طور همزمان هم کالا تحویل می‌گیرد و هم کالا تحویل می‌دهد.
الگوریتم پیشنهادی در این مقاله، ترکیبی از سه الگوریتم ابتکاری نزدیک‌ترین همسایگی ، ارزان‌ترین الحاقی و ژنتیک است. که دو الگوریتم اول به همراه یک روش تصادفی، جواب ابتدایی را برای الگوریتم سوم فراهم می‌کنند. با تغییراتی که در این تحقیق روی روش‌های نزدیک‌ترین همسایگی و ارزان‌ترین الحاقی ایجاد شد، منجر به تولید جمعیت اولیه با حل‌های باکیفیت گردید که نهایتاً به الگوریتم ژنتیک جهت رسیدن به نسل آینده برتر کمک می‌کند. همچنین عملگرهایی برای الگوریتم ژنتیک به منظور افزایش فضای جستجو و فرار از بهینه‌های محلی پیشنهاد شده است. الگوریتم پیشنهادی روی 40 مثال استاندارد و متنوع اجرا شده است. با مقایسه نتایج بدست آمده از آن و بهترین جواب‌های موجود از سایر الگوریتم‌ها، در 3 مثال نتیجه بهتری بدست آمده که بسیار رضایتبخش است.

کلیدواژه ها

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

موضوعات

راه و ترابری و حمل و نقل - مدل سازی

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

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

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

Amir Masoud Rahimi, vahid rajabi to

چکیده [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 algorithms. A probability function have 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 optimizationis. The proposed algorithms has implemented on 40 different standard examples. After comparing the results by this algorithm and the best solutions by other algorithms, improvement is observed in 3 of the examples.

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

Hybrid meta-heuristic algorithm, Vehicle routing problem, simultaneous delivery and pick-up, genetic algurithm, Dethloff problems

مراجع

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

آمار

تعداد مشاهده مقاله: 1,400

تعداد دریافت فایل اصل مقاله: 1,483

Journal Management System. Designed by sinaweb.