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

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

نویسندگان

1 دانشکده فنی و مهندسی، دانشگاه پیام نور، تهران، ایران

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

چکیده

یکی از فرآیندهای محوری در سیستم بانکداری، انتقال پول از انبار (خزانه) به مشتریان (شعب) و برگشت آن به خزانه،در بازه‏های زمانی مشخص و محدود است. عوامل متعددی مانند تعداد و محل خزانه‏ها، نحوه تخصیص شعب به خزانه‏ها، مسایل امنیتی، ناوگان حمل، مسیرهای انتقال و پراکندگی جغرافیایی شعب در انجام بهینه فرآیند انتقال پول مؤثر است. اما کلیدی‏ترین پارامتر در انجام موفق این فرآیند انتخاب مسیر مناسب به نحوی است که بتوان فرآیند پول‏رسانی را در کم‏ترین زمان با کم‏ترین ریسک به شرط اتمام فرآیند پول‏رسانی در بازه زمانی مشخص انجام داد.در این مقاله جهت حل این مسأله، یک مدل مسیریابی چندانباره دوهدفه با در نظر گرفتن نوع کالای حمل شده، طراحی شده است.برای محاسبه ریسک مسیر از شاخصهایی مانند نوع خیابان، نوع تردد مجاز، عرض خیابان و متوسط ترافیک خیابان که قبل از حل مسأله قابل سنجش است، استفاده می‏شود و شاخص‏هایی همچون ترافیک لحظه‏ای یا حوادث پیش‏بینی نشده،‏ نادیده گرفته می‏شود. با توجه به NP-hard بودن مسایل مسیریابی جهت حل مدل، از یک الگوریتم خفاش چند هدفه برای مسایل واقعی یک بانک استفاده شده است. به دلیل ماهیت پیوسته الگوریتم، نحوه تولید و رمزگشایی، جواب جدیدی طراحی شده است که منجر به کاهش زمان حل نیز می‏شود. نتایج حل نیز با الگوریتم NSGA-II مقایسه شده است. مقایسه نتایج الگوریتم‏ها با شاخص‏های چند هدفه،کارآیی الگوریتم خفاش را برای مسأله موردنظر نشان می‏دهد.

کلیدواژه‌ها


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

Solving A Multi-Depot Vehicle Routing Problem Based On Reduction Risk by a Multi-Objective Bat Algorithm

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

  • Atefeh Kahfi 1
  • Reza Tavakkoli-Moghaddam 2
چکیده [English]

One of the key processes in a banking system is the money transfer process from the depot (i.e., treasury) to customers (i.e., branches) and returns it in the limited time. A number of factors (e.g., the number and location of treasury, allocation of branches to treasury, security problem, fleet and routes of transmission and geographical distribution of branches) are effective in the optimal or appropriate performance of the money transfer process. However, the key parameter to be successful in such a process is to choose the correctness path so that the money transfer process ends in the lowest time with the lowest risk. In this paper, a bi-objective model for a multi-depot vehicle routing problem is designed. The value of path risk is depended on some measures, such as type of street (a major or minor street), permitted traffic type (one-way and two-way), street width and average of street traffic can be used. Other measures, such as traffic moment and suddenly events (e.g., accidents) can be ignored. Since the vehicle routing problem (VRP) is NP-hard, a multi-objective bat algorithm (MOBA) is proposed and the associated results are compared with the well-known multi-objective evolutionary algorithm, namely non-dominated sorting genetic algorithm-II (NSGA-II). Despite the continuous nature of the proposed MOBA and the complexity of the proposed model, a simple efficient solution representation is used, in which feasible solutions are produced in each step. Because of the continuous nature of the proposed MOBA algorithm, new coding and decoding representations are designed that result in decreasing the computational time. The comparison of the proposed MOBA results in terms of the objective function value is illustrated in order to show the efficiency of the proposed MOBA.

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

  • Multi-depot vehicle routing problem
  • Multi-objective bath algorithm
  • NSGA-II