توضیحات
ABSTRACT
Given the demand between each origin-destination pair on a network, the planar hub location problem is to locate the multiple hubs anywhere on the plane and to assign the traffic to them so as to minimize the total travelling cost. The trips between any two points can be nonstop (no hubs used) or started by visiting any of the hubs. The travel cost between hubs is discounted with a factor. It is assumed that each point can be served by multiple hubs. We propose a probabilistic clustering method for the planar hub-location problem which is analogous to the method of Iyigun and Ben-Israel (in Operations Research Letters 38, 207–214, 2010; Computational Optmization and Applications, 2013) for the solution of the multi-facility location problem. The proposed method is an iterative probabilistic approach assuming that all trips can be taken with probabilities that depend on the travel costs based on the hub locations. Each hub location is the convex combination of all data points and other hubs. The probabilities are updated at each iteration together with the hub locations. Computations stop when the hub locations stop moving. Fermat-Weber problem and multi-facility location problem are the special cases of the proposed approach.
INTRODUCTION
To accommodate all traffic and make it more efficient, some (or all) of the traffic is directed through hubs. A hub is a facility where passengers from several nearby origins can be pooled for a trip to a common destination, or to another hub (from where the passengers continue to their destinations). By combining trips and directing them through hubs, the sum of distances traveled in the system can be reduced. Another advantage is greater efficiency of travel, because typically bigger planes are used between hubs, and they are flown at higher altitudes The hub location problem (HLP) is to locate K hubs in the network so as to minimize the total travel cost in the system. In some HLP cases the hub locations are constrained to lie in a given subset of the plane, in particular a given subset of the data points. This constrained problem is called discrete hub location model. It was first considered by O’Kelly (1987), introducing a quadratic integer program for location of interacting hub facilities. Alternative integer linear programming formulations of discrete hub location problems have also been provided by Campbell (1994a), Bryan (1998), Ernst and Krishnamoorthy (1996, 1998), and O’Kelly et al. (1996).
چکیده
با توجه به تقاضا بین هر جفت مقصد اصلی و مقصد در یک شبکه، مشکل موقعیت مکانی مسطح این است که چندین توپی را در هر نقطه از هواپیما قرار دهیم و ترافیک را به آنها اختصاص دهیم تا کل هزینه سفر به حداقل برسد. سفر بین هر دو نقطه می تواند بدون توقف (بدون مراکز استفاده شده) و یا با مراجعه به هر یک از مراکز شروع شده است. هزینه سفر بین هاب ها با یک عامل تخفیف می شود. فرض بر این است که هر نقطه می تواند توسط چند توپی خدمت کند. ما یک روش خوشهبندی احتمالاتی برای مسأله مساحت مسطح مسطح ارائه میدهیم که مشابه روشهای Iyigun و Ben-Israel است (در تحقیقات عملیاتی Letters 38، 207-214، 2010؛ Optmization Computing and Applications، 2013) برای راه حل مشکل محل چندین مرکز. روش پیشنهادی یک رویکرد احتمالاتی تکراری است، فرض بر این است که تمام سفرها با احتمالاتی که به هزینه های سفر بر اساس مکان های توپی بستگی دارد، می تواند مورد استفاده قرار گیرد. هر مکان توپی ترکیبی محدب از تمام نقاط داده و دیگر توپی است. احتمالات در هر تکرار همراه با مکان های توپی به روز می شود. محاسبات زمانی متوقف می شود که مکان های توپی متوقف شوند. مسئله فرما-وبر و مسافت چند مكانی محل موارد خاصی از رویکرد پیشنهادی است.
مقدمه
برای تطبیق با تمام ترافیک و کارآیی آن، برخی (یا همه) ترافیک از طریق هاب هدایت می شوند. هاب یک مرکز است که مسافرین از چند ریشه های اطراف آن می توانند برای سفر به مقصد مشترک یا به مرکز دیگری (از جایی که مسافران به مقصد خود) ادامه می دهند. با ترکیب سفرها و هدایت آنها از طریق هاب ها، مجموع فاصله های سفر شده در سیستم می تواند کاهش یابد. یکی دیگر از مزایای بهره وری بیشتر از سفر است، زیرا هواپیما های بزرگتر از میان هاب ها استفاده می شوند و در ارتفاعات بالاتر پرواز می کنند. مشکل موقعیت مکانی (HLP) این است که مکان های K را در شبکه قرار دهند تا هزینه کل سفر در سیستم را به حداقل برساند . در برخی از موارد HLP، مکان های توپی محدود به دروازه در یک زیر مجموعه ای از هواپیما، به ویژه یک زیر مجموعه ای از نقاط داده شده است. این مسئله محدود شده است که به نام مدل دیفرانسیل متصل شده است. این اولین بار توسط O’Kelly (1987) مورد توجه قرار گرفت، معرفی یک برنامه عدد صحیح درجه دوم برای محل تسهیلات توپی تعاملی. کامپبل (1994a)، برین (1998)، ارنست و کریشنا نورتوث (1996، 1998) و O’Kelly و همکاران، فرمول های برنامه نویسی خطی جایگزین را نیز ارائه داده اند. (1996).
Year: 2013
Publisher: SPRINGER
By : Cem Iyigun
File Information: English Language/ 16 Page / size: 1.48 KB
Only site members can download free of charge after registering and adding to the cart
سال : 1392
ناشر : SPRINGER
کاری از : Cem Iyigun
اطلاعات فایل : زبان انگلیسی / 16 صفحه / حجم : KB 1.48
نقد و بررسیها
هنوز بررسیای ثبت نشده است.