عنوان

ارائه الگوریتمی برای تعیین ساختار ائتلاف حاملان در مسئله برداشت و تحویل

Number

۲۴۶۰پ

.Language of Text, Soundtrack etc

فارسی

Language of Original Work

فارسی

Title Proper

ارائه الگوریتمی برای تعیین ساختار ائتلاف حاملان در مسئله برداشت و تحویل

General Material Designation

[پایان نامه]

First Statement of Responsibility

/ سمیرا شاه‌منصوری

Place of Publication, Distribution, etc.

سنندج

Name of Publisher, Distributor, etc.

: دانشگاه کردستان، دانشکده مهندسی

Date of Publication, Distribution, etc.

، ۱۳۹۵

Specific Material Designation and Extent of Item

ح، ۱۲۵ص

Other Physical Details

: مصور (بخشی رنگی)، جدول

Accompanying Material

+ لوح فشرده

Text of Note

چکیده فارسی - انگلیسی

Text of Note

کتابنامه: ص. ۱۲۱-۱۲۵

Dissertation or thesis details and type of degree

کارشناسی ارشد

Discipline of degree

صنایع

Body granting the degree

کردستان

Text preceding or following the note

۲۰

Text of Note

شرکت‌های ارائهدهنده خدمات توزیع کالا می‌توانند با عقد قراردادهای همکاری برای به اشتراک‌گذاری تقاضا و ناوگان، باعث کاهش هزینه‌ها، کاهش مصرف سوخت، دست‌یابی به مزیت اقتصاد مقیاس و جلب رضایت مشتریان با پاسخگویی سریع‌تر شوند. در تحقیقات گذشته همکاری در مسائل مختلف حمل‌ونقل و ازجمله انواع کلاس‌های مسئله مسیریابی وسیله نقلیه، موردبررسی قرار گرفته است. تفاوت اصلی مسئله این پژوهش با تحقیقات دیگر، تعداد زیاد اعضای ائتلاف و امکان‌پذیر نبودن تشکیل یک ائتلاف با حضور تمام اعضاء است. مسئله حمل‌ونقل مورد بررسی در این پژوهش، مسئله مسیریابی وسیله نقلیه با برداشت و تحویل و پنجره زمانی (PDPTW) است. ماهیت NP-hard این مسئله موجب ابهام در اثرگذاری مثبت همکاری در کاهش هزینه‌ها با بزرگ شدن اندازه مسئله در شرایط همکاری می‌شود. ائتلاف‌های بزرگ در مسائل حمل‌‌ونقل ممکن است پیچیدگی مدیریتی و عملیاتی زیادی داشته باشند. روش‌های تقسیم عواید در بازی‌های همکارانه دارای تابع مشخصه نمایی از تعداد بازیکنان هستند و در بازی با تعداد بازیکن زیاد، عملاً انجام یک تخصیص مبتنی بر این روش‌ها ممکن نیست. ازآنجاکه حضور در ائتلاف داوطلبانه است، روشی مانند تخصیص‌ تناسبی نمی‌تواند تضمین‌کننده تخصیصی عادلانه و پایدار باشد و بازیکن منفعت‌طلب را به شرکت در ائتلاف قانع کند. هدف این پژوهش ارائه یک روش ابتکاری برای حل چالش‌های عنوان‌شده و تعیین بهترین ساختار ائتلاف از لحاظ اندازه و کارایی است. در این تحقیق یک الگوریتم ابتکاری سلسله مراتبی برای تعیین ساختار ائتلاف ارائه شده است. برای حل مسئله متمرکز و زیرمسائل ائتلاف‌های تشکیل‌شده، از الگوریتم ابتکاری جستجوی همسایگی بزرگ انطباقی (ALNS) استفاده شده است. برای تقسیم عواید حاصل از همکاری، از روش مقدار شپلی به دلیل یکتایی و عادلانه بودن تخصیص حاصل از آن، استفاده شده است. برای بررسی کیفیت عملکرد الگوریتم ALNS، نتایج به‌دست‌آمده از آن، با نتایج حاصل از حل‌کننده CPLEX برای نمونه‌مسائل کوچک، مقایسه شده و کیفیت جواب و زمان حل الگوریتم ALNS، عملکرد مناسب آن را برای این دسته از نمونه‌مسائل نشان می‌دهد. برای بررسی بیشتر کارایی الگوریتم برخی نمونه‌مسائل موجود در ادبیات تحقیق مسئله PDPTW هم با این الگوریتم حل شده و نتایج حاصل، با بهترین جواب‌های موجود برای آن‌ها مقایسه شده است. نتایج به‌دست‌آمده، مناسب بودن عملکرد الگوریتم تا اندازه‌های نسبتاً بزرگ را نشان می‌دهد. نمونه مسائل همکارانه در فاز اول با الگوریتم تعیین ساختار ائتلاف ارائه‌شده، به ائتلاف‌های مطلوب تجزیه شده‌اند. در فاز دوم، مسئله هر ائتلاف که یک مسئله PDPTW متمرکز (CPDPTW) است، با الگوریتم ALNS حل شده است. در پایان، هزینه کل با روش مقدار شپلی بین بازیکنان تقسیم شده است. نتایج نشان می‌دهند که تمام ائتلاف‌های حاصل دارای صرفه‌جویی مثبت بوده و درنتیجه عملکرد الگوریتم تعیین ساختار ائتلاف و الگوریتم ALNS قابل قبول است.

Text of Note

Companies that are the distribution services provider, by contract for sharing demand and fleet, can reduce costs, reduce fuel consumption, achieving the economies of scale advantage and customer satisfaction with faster response. In previous research, cooperation in various transportation problems, including the classes of vehicle routing problem is studied. The main difference between this research and other publications is the large number of collaborators and impossibility of forming the one coalition with the participation of all members.Transportation problem that examined in this study is vehicle routing problem with pickup and delivery and time window (PDPTW). Since the problem size in collaborative condition is larger than the problem size of each carries; so NP-hardness of PDPTW problem creates uncertainty in the positive effect of the cooperation. Managing and operation in large coalitions in transportation problems may be complex. Most methods of cost allocation in cooperative game theory has an exponential characteristic function of the number of players; so in a game with large number of players, allocation by this methods is not possible and since participation in coalition is voluntary, so proportional allocation can’t satisfy the selfish players to cooperation. The purpose of this paper is to providing an algorithm in order to solve the mentioned challenges and determine the best coalitions of grand coalition in terms of size and performance. In this research a hierarchical heuristic algorithm is developed to determining the coalition structure. To solve the problems and sub problems of each formed coalition, an Adaptive Large Neighborhood Search heuristic algorithm have been implemented. For divide the saving in each formed coalition Shapley Value method is performed because of fairness and uniqueness of allocations of this method. To evaluate the performance of ALNS algorithm, the results with the results of CPLEX solver, for small instances, compared and quality of the solution and the solution time of the ALNS algorithm, shows the appropriateness of the algorithm performance for this range of instances size. To further evaluate the algorithm performance, some benchmarks for PDPTW have been solved with ALNS algorithm and results have been compared with best known solutions. The results show the suitability of the algorithm performance for problems with relatively large sizes. Collaborative instances, in first phase decompose in best availabe coalition. In second phase the CPDPTW of each coalition solve by ALNS algorithm. Finally, collaborative cost have been divide between carries by shapely value. All saving is positive and the performance of the algorithms is acceptable.

fa

ba

Subject Term

collaborative transportation

Subject Term

coalition structure

Subject Term

cooperative game theory

Subject Term

adaptive large neighborhood search algorithm

Subject Term

vehicle routing problem with pickup and delivery

Entry Element

شاه منصوری

Part of Name Other than Entry Element

سمیرا

Relator Code

پديدآور

Entry Element

فرورش،

Part of Name Other than Entry Element

حمید

Relator Code

استاد راهنما

Entry Element

دانشگاه کردستان

Subdivision

. دانشکده مهندسی

Country

ایران

Agency

کتابخانه مرکزی دانشگاه کردستان

Call Number

EEI۲۶۲۵ ۱۳۹۵ کتابخانه مرکزی

p

TF

92029

1

a

Y