حل یک مدل ریاضی جدید برای مسأله‌ی مسیریابی وسایل نقلیه با برداشت و تحویل همزمان توسط الگوریتم تکامل تفاضلی چندهدفه

نویسندگان

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

2 استاد، دانشکده مهندسی صنایع، پردیس دانشکده‌های فنی، دانشگاه تهران، تهران، ایران

چکیده

مدل ارائه شده در این تحقیق، جزو مسائل مسیریابی وسایل نقلیه با حمل در بازگشت می­باشد که در آن فرآیند برداشت و تحویل بطور همزمان صورت می­گیرد. مسأله بصورت دوهدفه مدلسازی شده است که اهداف آن عبارتند از: کمینه سازی هزینه کل حمل و نقل شامل هزینه ثابت استفاده از وسیله نقلیه و هزینه متغیر مسافت طی شده و نیز افزایش رضایت­مندی رانندگان از طریق توازن توزیع کالا میان وسایل نقلیه. به جهت NP_سخت بودن مسائل مسیریابی وسایل نقلیه، جهت حل
مسأله­ی مسیریابی وسایل نقلیه با برداشت و تحویل همزمان الگوریتم فراابتکاری تکامل تفاضلی چندهدفه (MODE) پیشنهاد گردیده است. همچنین جهت بررسی عملکرد الگوریتم پیشنهادی، نتایج حاصل از این روش با روش جستجوی هارمونی چند هدفه (MOHS) مقایسه شده است. یک آزمون محاسباتی بر روی نمونه مسائل موجود در ادبیات موضوع صورت گرفته است. نتایج محاسباتی نشان می­دهد که الگوریتم پیشنهادی از نظر زمان محاسبات و کیفیت جواب­های بدست آمده از کارآمدی خوبی برخوردار می­باشد.
 
 
 

کلیدواژه‌ها


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

Solving a New Mathematical Model for a Vehicle Routing Problem with Simultaneous Pickup and Delivery by a Multi-Objective Differential Algorithm

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

  • H. Eghbali 1
  • R. Tavakkoli-Moghaddam 2
1 Ph.D. Student, Department of Industrial Engineering, Kurdistan University, Kurdistan, Iran
2 Professor, School of Industrial Engineering, College of Engineering, University of Tehran, Tehran, Iran
چکیده [English]

The model presented in this research belongs to a class of vehicle routing problems with backhaul, which the pickup and delivery process is carried out simultaneously. This problem is formulated in a bi-objective model, whose objectives are to minimize transportation costs (including the fixed cost of using vehicles and the variable cost of travelled distances) and increase the drivers satisfaction by balanced distribution of the product. Due to the NP-hardness of the problem, a multi-objective differential evaluation (MODE) algorithm is proposed to solve of the VRP with simultaneous pickup and delivery (VRPSPD). To show the performance of the proposed MODE, its results are compared with the results obtained by a multi-objective harmony search. Additionally, a computational test is carried out on a number of test problems taken from the literature. The computational results show the good efficiency of the proposed MODE in terms of solutions quality and time.  
 
 

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

  • Vehicle routing
  • simultaneous pickup and delivery
  • e-constraint method
  • Multi-objective meta-heuristic algorithms

-توکلی مقدم، ر.، علینقیان، م. و سلامت بخش، ع. (1388)، "ارایه و حل مدل برنامه­ریزی ریاضی جدید برای مسیریابی وسائط نقلیه در حالت رقابتی: یک مطالعه موردی"، پژوهشنامه حمل و نقل، سال ششم، شماره چهارم، زمستان 1388،
ص. 311-323.

- ساعی، س.، توکلی مقدم، ر. و علینقیان، م. (1394)، "مدلسازی ریاضی جدید برای مسیریابی وسایل نقلیه­ی چند دپو در شرایط بلایای طبیعی و حل آن با الگوریتم بهینه­سازی ذرات انبوه­"، پژوهشنامه حمل و نقل، سال دوازدهم، شماره اول، ص. 37-51.

-Angelelli E, Mansini R. (2002), The vehicle routing problem with time windows and simultaneous pickup and delivery. In: Klose A., Speranza MG, Van Wassenhove LN (eds.) Quantitative Approaches to Distribution Logistics and Supply Chain Management. Springer, Berlin-Heidelberg, pp.249–267.

-Berhan E, Krömer P, Kitaw D, Abraham A., Snásel V. (2013), ”­Solving stochastic vehicle routing problem with real simultaneous pickup and delivery using differential evolution. IBICA,
pp.187–200.

-Dell’Amico M., Righini G., Salani M., (2006),
“A branch-and-price approach to the vehicle routing problem with simultaneous distribution and collection”. Transport Sci 40: pp.235–247.

- Dethloff J. (2001), “Vehicle routing and reverse logistics: The vehicle routing problem with simultaneous delivery and pickup”. OR Spektrum 23, pp.79–96.

-Gendreau M, Laporte G, Vigo D. (1999), Heuristics for the traveling salesman problem with pickup and delivery. Comput Oper Res 26:
pp.699–714.

-Goksal F.P., Karaoglan E, Altiparmak F. (2013),
” A hybrid discrete particle swarm optimization for vehicle routing problem with simultaneous pickup and delivery”. Computers & Industrial Engineering 65: pp.39–53. 

-Kalayci C.B., Kaya, C. (2016), “An ant colony system empowered variable neighborhood search algorithm for the vehicle routing problem with simultaneous pickup and delivery”. Expert Systems with Applications 66: pp.163–175 

-Liu R., Xie X., Augusto V., Rodriguez C. (2012), “Heuristic algorithms for a vehicle routing problem with simultaneous delivery and pickup and time windows in home health care”. European Journal of Operational Research 230(3): pp.475–486.

-Min, H. (1989), “The multiple vehicle routing problem with simultaneous delivery and pickup points”. Transport Res A-Pol 23: pp.377–386.

-Nagy G., Salhi S., (2005), “­Heuristic algorithms for single and multiple depot vehicle routing problems with pickups and deliveries”. Eur J Oper Res 162: pp.126–141.