دانلود رایگان مقاله مشکلات مکانی در هاب میانی اختصاصی

خلاصه

     مدل مکانی گسسته سفارشی میانی، ابزاری قدرتمند در مدل سازی کلاسیک و راه حلی برای مشکلات مکانی است که با موفقیت در گستره وسیعی از این مشکلات گسسته اعمال شده است. اگرچه این مدل ها از نقطه نظر مجموع، حداکثر و پوششی به خوبی آنالیز شده اند، اما هرگز به عنوان واحدی مشترک در نظر گرفته نشده اند. در این مقاله فرمول بندی جدیدی را ارایه می کنیم که اساس آن عملکرد میانی سفارشی برای مشکلات مکانی هاب با الگوی توزیع جدید در زنجیره تامین شبکه می باشد. در این روش برخی خطاهای مربوط به هزینه توزیع با در نظر گرفتن ترتیب قرار گیری این هزینه ها معرفی شده اند. در ابتدا فرمول بندی اساسی برای این مسئله و سپس فرمول بندی توسعه یافته ای ارایه خواهد شد. عملکرد تمامی این موارد به کمک آنالیز کامپیوتری مقایسه شده است. 

1- مقدمه 

      مباحث مربوط به موقعیت هاب، گستره وسیعی از مدل هایی را که هدف آنها به حداقل رساندن برخی عملکردهای محلی می باشد را شامل می شود. مقالات [1,9] و مراجع آنها مطالعه شود. علی رغم اینکه موضوع اکثر مقالات در مورد کاهش هزینه کلی انتقال می باشد، اما در برخی تحقیقات به سایر موارد در این زمینه پرداخته شده است. این مدل از سایر نقطه نظرات که امروزه مورد نیاز علم منطق می باشند بررسی نشده است. امروزه نیاز به مدل های بسیار انعطاف پذیر می باشد تا هرکدام نقشی را در شبکه ایفا کنند. می توان گفت که مدل های کلاسیک سعی در به حداقل رساندن مجموع هزینه های انتقال در هر مسیر را دارند. برای مثال سیستم از نقطه نظر منطقی بررسی می شود.  به مرجع 41 مراجعه شود. همچنین با توجه به نیروی محرک شبکه منطقی، می توان موارد مختلف مانند مشتری ها، تامین کننده ها و ترکیبی از این دو را از هم متمایز کرد. اولین تلاش در این زمینه در مراجع 2، 15، 16، 18، 19 و 41 آورده شده است و به طور عمده بر تفاوت نقش کاربران در شبکه زنجیره تامین در فاز توزیع تمرکز دارد. در این مقاله به شرح مسیر اشاره شده در بالا پرداخته و مدلی را ارایه دادیم که می تواند نقش بخش های مختلف در شبکه زنجیره هاب را مشخص کند. ابتدا انعطاف پذیری را به کمک فاکتور جبران یکپارچه می کنیم و سپس فرض می شود که نیروی محرک در زنجیره توسط تامین کنندگان و توزیع کنندگان سیستم به اشتراک گذاشته شده است. تامین کنندگان، هزینه انتقال از سایت مرجع به اولین هاب و توزیع کنندگان هزییه انتقال را از اولین هاب به به سایت مقصد را بر عهده می گیرند. 

     در این مقاله به معرفی و آنالیز موقعیت هاب با الگوی تو.زیع جدید که توسط کابران مختلف در زنجیره تامین استفاده شده است خواهیم پرداخت. در واقع شبکه زنجیره تامین را به گونه ای فرض می کنیم که عملیات داخل شبکه، شامل تحویل بخش به بخش مقدار نامشخصی از کالا باشد. هدف این است که به طور همزمان، موقعیت نقطه انتقال میانی(هاب) و مسیرهای تحویل(الگوهای توزیع) مشخص شوند. سعی بر این است که یک سیستم توزیع میانه با تعداد هاب های ثابت برای به حداقل رساندن هزینه کلی عملیات شبکه زنجیره تامین پایه گذاری شود. به علاوه فرض می شود که هر مسیر تحویل شامل دو بخش 1- مسیری که سایت مرجع را به اولین نقطه دسترسی وصل می کند و 2- مسیری که هاب اولی را به مقصد نهایی وصل می کند باشد. به علاوه جزء دوم خود شامل دو بخش 2-1- لینک داخلی هاب و 2-2- لینکی که هاب را به مقصد آخر وصل می کند می باشد. این ساختار به ما اجازه می دهد که بین اجزاء مختلف و نقش آنها در زنجیره تامین تمایز قائل شویم. فرض بر این است که هر مرجع باید هزینه ارسال به اولین هاب را تامین کند در حالی که سیستم توزیع میانی، هزینه های باقی مانده را تقبل می کند. برای مثال سیستم توزیع مسئول ارسال به هاب اولیه می باشد. این مورد شبیه شرکت های سهام است که در آن بخش های سطح اول، کالا را به مرکز توزیع رسانده و سپس به مقصد نهایی تحویل داده می شوند. 

     هر جزء از مسیر تحویل که در بالا شرح داده شده است، موجب افزایش هزینه ناشی از فاکتورهای جبران خواهد شد. از نقطه نظر کاربردی، تحویل های یکسان در سیستم توزیع مانند تحویل از اولین هاب به مقصد نهایی، باید ارزان تر از بخش اولیه هزینه باشد تا بتوان آن را به کمک تجهیزات بزرگتر و با هزینه کمتر انجام داد( به دلیل ابعاد بزرگ سیستم توزیع که تاثیر عمده ای در هزینه خواهد داشت). در نتیجه ما در مدل خود فرض کردیم که لینک های داخل هاب توسط تجهیزاتی مشابه ( هواپیما، کامیون های بزرگ و ... ) پوشش داده شده و هزینه مربوط به این لینک ها مقدار ثابت α بین 0 و 1 خواهد بود. به علاوه فرض می کنیم که لینک های بین هاب آخر و سایت های مقصد توسط تجهیزات متفاوتی پوشش داده می شوند و هزینه های مربوطه نیز با فاکتور δ بین 0 و 1 مشخص خواهند شد. دلیل استفاده از دو فاکتور مختلف برای این لینک ها، تفاوت بین بارگذلری و باربرداری در سیستم های مورد استفاده هاب می باشد. موقعیت هاب دلالت بر سیستم های اتوماتیک بارگذاری و باربرداری دارد که اجازه استفاده از تجهیزات بزرگ را خواهد داد در حالی که روش های سنتی فقط قابلیت استفاده از تجهیزات کوچک را دارند. 

     فرض می کنیم که کالای هر مرجع به هاب اولی انتقال یابد که نشان دهنده نقطه دسترسی به سیستم توزیع است. این مورد به صورت فاکتور جبران مشاهده می شود که سعی در کاهش و حذف موقعیت های نابرابر در سیستم توزیع دارد. خواننده باید توجه داشته باشد که ما به طور همزمان محل قرار گیری هاب برای تعیین سیستم توزیع و مسیر تحویل از سایت مرجع به مقصد نهایی را انتخاب می کنیم. در نتیجه راه حلی که برای کل سیستم مناسب است، به دلیل هزینه بالای آن، برای بخشی از سیستم مناسب نخواهد بود. برای مثال اگر راه حلی برای دسته ای از هاب ها قابل قبول باشد، هزینه دسترسی مرجع j ، بزرگتر از هزینه متناظر j´ خواهد بود ( توجه داشته باشید که در این موارد، سایت j´ را جریمه نمی کند اما در عوض j را به دلیل کاهش پرامندگی هزینه کمک می کند). برای سهیم کردن این موارد در هزینه کل، ضریب اصلاحی به آن اعمال می شود که وابسته به میزان هزینه، نسبت به هزینه های مشابه می باشد. برای مثال اگر هزینه انتقال کالا از سایت مرجع j پنجمین هزینه بالا باشد، خطای اعمالی نسبت به دومین هزینه بالا متفاوت خواهد بود. مراجع 3، 30، 30، 35 و 36 مطالعه شوند. همچنین می توان با اعمال خطای صفر، از برخی موارد چشم پوشی کرد. این قضیه موجب ایجاد مشکل در موقعیت هاب خواهد شد و راه حل و فرمول بندی را بسیار چالش برانگیز خواهد کرد. 

     هدف ارایه چهارچوب یکسان برای آنالیز این مدل ها با در نظر گرفتن اطلاعات معمول برای نیل به احتیاجات منطقی می باشد. به طور معمول هدف به حداقل رساندن هزینه انتقال کل در جریان های بین مرجع و مقصد می باشد.

     بقیه بخش های این مقاله به صورت زیر سازمان دهی شده است. در بخش 2 به شرح مدل و ایجاد یک فرمول بندی ریاضی با استفاده از 3 شاخص متغیر خواهیم پرداخت. در بخش 3 فرمول های جایگزین برای هاب را بررسی خواهیم کرد. در بخش 4 آنالیز مقدماتی را برای تعیین حدود حل مسئله با استفاده از حل گرهای MIP استاندارد انجام خواهیم داد. بخش 5 به توسعه فرمول بندی های قبلی و ایجاد فرمول بندی جدید می پردازد. نتایج این بخش به صورت آنالیز کامپیوتری در بخش 6 مقایسه می شوند که در آخر مقاله آورده شده اند.

2 – مدل و فرمول بندی سه شاخصه

     A نشان دهنده N سایت است که توسط اعداد صحیح 1 تا N نشان داده می شود. هر سایت به جمع آوری برخی کالا ها می پردازد که باید به سایت های باقی مانده ارسال شوند.    میزان کالای تامینی از سایت j ام به سایت   m ام برای تمامی   و   می باشد. در ادامه فرض می کنیم که تعداد سایت ها برای ایجاد هاب، مشابه سایت های A باشد.   نشان دهنده هزینه واحد ارسال کالا از سایت j ام به سایت m خواهد بود. فرض می کنیم که   و   تعداد هاب ها و   با  نشان دهنده سایت های در دسترس باشد. راه حل مسئله میزان X به علاوه یک جفت مسیر اتصالی در سایت های j و m برای تمامی j ها می باشد به طوری که هر مسیر حداقل 1 و حداکثر 2 هاب را از خود عبور دهد. برای بالا بردن دقت (i) اگر سایت مرجع و سایت مقصد به صورت هاب نباشند، جریان باید از طریف 1 یا 2 هاب میانی انتقال یابد. (ii) اگر سایت مرجع و یا مقصد به صورت هاب باشند، جریان بین آنها می تواند به طور مستقیم یا از طر یق یک هاب صورت گیرد. (iii) اگر سایت مرجع و مقصد به صورت هاب باشند، جریان به صورت مستقیم از سایت مرجع به مقصد خواهد رفت. 

     این مدل هزینه انتقال هاب در سایت مرجع را با استفاده از پارامترهای   جبران می کند. این فاکتورها با توجه به ترتیب هزینه های انتقال به مرجع اعمال می شوند. اگر کالا از سایت مرجع j توسط هاب k با هزینه تحویل   در رتبه i ام قرار گیرد، این هزینه توسط λ مقیاس دهی می شود. برای مثال تابع متناظر به صورت   خواهد بود. به علاوه پارامتر جبران را به صورت 0<α<1، برای تحویل بین هاب ها فرض می کنیم و پارامتر دیگر نیز به صورت 0<δ<1 خواهد بود. توجه داشته باشید که α<δ می باشد. این پارامترها دلالت بر این دارد که هاب دوم موجب ضعف ارتباط از هاب اول به مقصد نهایی خواهد شد.

     با توجه به انتخاب بردار λ می توان معیارهای مختلفی را برای براورد هزینه در انتقال از مرجع به مقصد نهایی استفاده کرد. برای مثال اگر   به عنوان تابع هدف در نظر گرفته شود، جمع بزرگترین k ها به عنوان هزینه کل خواهند بود. در ادامه رفتار متفاوتی ار مدل را برای بردارهای λ مختلف و تک هاب میانی نشان خواهیم داد. برای این منظور از داده های CAB موجود در استفاده خواهیم کرد که   و   می باشد . جدول 1 نشان دهنده سایت های هاب برای معیارهای مختلف ،  و  ،   و   نشان داده شده است. می توان گفت که راه حل های به دست آمده برای تمامی معیارها متفاوت خواهند بود. به علاوه در این جدول مشاهده می شود که در مواردی که یک سایت مشابه به عنوان هاب انتخاب شود، مسیر و الگوی سایت های مرجع به هاب متفاوت خواهند بود. برای مثال در راه حل بهینه برای هاب P میانی، تعداد 2 عدد هاب در سایت های 2 و 13 وجود دارد.

Abstract

     The discrete ordered median location model is a powerful tool in modeling classic and alternative location problems that have been applied with success to a large variety of discrete location problems. Nevertheless, although hub location models have been analyzed from the sum, maximum and coverage point of views, as far as we know, they have never been considered under an alternative unifying point of view. In this paper we consider new formulations, based on the ordered median objective function, for hub location problems with new distribution patterns induced by the different users’ roles within the supply chain network. This approach introduces some penalty factors associated with the position of an allocation cost with respect to the sorted sequence of these costs. First we present basic formulations for this problem, and then develop stronger formulations by exploiting properties of the model. The performance of all these formulations is compared by means of a computational analysis.

1. Introduction

      The literature of hub location covers a large variety of models where the main goal is to minimize some globalizing function of the operation costs. See the surveys [1,9] and the references therein. Despite that most papers have been devoted to the minimization of the overall transportation cost (sum) (see [4,7,8,11,13,14,17,24–29,37,40], among others), in some cases other objectives have also been taken into account. Among them we mention the minimization of the largest transportation cost and the coverage cost [5,10,20,21,23,31,38,39]. However, these models have never been considered under alternative points of view as required by nowadays logistics. Practitioners need, more and more, flexible models that incorporate the different roles of the parties in the supply chain network. Roughly speaking, the classical hub location models try to minimize the sum of the transportation costs of each origin–destination path, i.e. the system is analyzed from the logistics provider point of view, see [41]. However, depending on the driving force of the logistics network we can distinguish alternative points of views, as for instance, suppliers, clients or a combination of both points of views. A first attempt to deal with this flexibility has been already addressed with some success in certain classical location models (see e.g. [2,15,16,18,19,41]) and it is mainly concerned with the differentiation of users’ roles within the supply chain network or equivalently with the use of new or different distribution patterns (origin–destination delivery paths) in the distribution phase. In this paper, we elaborate on the direction mentioned above and present a model that allows to differentiate on the role played by the different parties in a hub-type supply chain network. First, we incorporate flexibility through rank dependent compensation factors. Second, we assume that the driving force in the supply chain is shared by the suppliers and the distribution system; suppliers support the transportation costs from the origin sites to the first hub and the distribution system supports the transportation cost from the first hub to the destination sites.

      In this paper, we introduce and analyze hub location problems with a new type of distribution pattern induced by the different roles of the users within the supply chain. Actually, we consider supply chain networks where the operations within the network consist of segmented origin–destination deliveries of known amounts of a commodity. The goal is to simultaneously make decisions on the location of the intermediate transhipment points (hubs) and on the origin–destination delivery paths (distribution patterns). We seek to establish an intermediate distribution system with a fixed number of hubs that minimizes the overall operation cost of the supply chain network. Moreover, we assume that any origin–destination delivery path is composed of, at most, two components: (1) the subpath that goes from an origin site to the first access point (first hub) to the distribution system, and (2) the subpath that links first hubs to final destinations. In addition, this last component is itself divided into two parts: (2.1) the inter-hubs link and (2.2) the link from the last hub to the final destination. This structure allows us to distinguish between different cost generating entities according to the roles played within the supply chain. On the one hand, we assume that each origin must support the cost to reach the first hub (i.e. the distribution system), while the intermediate distribution system supports the remaining delivery costs, namely the cost induced once the commodity has reached the first hub (from the first hub to the final destination), i.e., the distribution system is the responsible for any commodity once it reaches the first hub. It is somewhat similar to parcel companies where urban/first level franchises carry the commodities to the assigned distribution centers of the parcel company and then, the company delivers the product to its final destination.

      Each one of the components of any origin–destination delivery path described above gives rise to a cost that is weighted by different compensation factors depending on the role of the party that supports the cost. From an application point of view, consolidated deliveries within the distribution system, i.e. between hubs, and from the last hub to the final destinations, should be cheaper than the first component of the cost since they can be done using larger vehicles or cheaper transportation modes (due for instance to the larger size of the distribution system which implies a dominant position in price negotiation). Therefore, in our models we assume that the inter-hub links are covered by the same type of vehicles (planes, big trucks, etc.) and the costs associated with these links have a fixed discount 0oao1. Moreover, we also assume that the links between last-hub and the destination sites are also covered by a different type of vehicle (small trucks, vans, etc.) and the associated costs have another discount factor 0odo1. A possible reason of using two different discount factors for the inter-hub links and the links between the last-hub and destination sites may be due to the different loading and unloading systems used in the hubs with respect to the ones used in the destination sites (the location of hubs implies the implementation of automatic loading/unloading systems that allow to handle big trucks, while destination sites may use traditional methods that only works with small vehicles).

     In addition, deliveries from the origin sites to the distribution system are scaled by rank dependent weights. We assume that the commodity of each origin is transported to a single (unique) first hub that represents the access point to the distribution system. These weights can be seen as compensation factors that try to diminish unfair situations of the origin sites with respect to the distribution system. The reader may note that we are simultaneously making decisions on placing hubs that define the intermediate distribution system, and establishing the delivery paths from origin sites to final destination. Thus, a solution that is good for the system (the entire supply chain) might not be acceptable for single parties if in that solution their costs to reach the system are too high relative to similar costs for other parties. In this situation some compensation to unhappy sites may be expected to prevent those sites from not using the system. The goal of our rank dependent weights is to compensate unfair situations, such as those described above. For instance, if a solution places a set of hubs so that the accessibility cost of origin j is greater than the corresponding cost of origin ju, the model tries to favor j with respect to ju assigning weights lj rlju. (Note that these weights do not penalize site ju but instead they compensate site j because these lambdas reduce the dispersion of the costs.) In order to incorporate this ordinal information in the overall transportation cost, the objective function applies a correction factor to the transportation cost of the commodity that is sent from each origin to a first hub (to reach the system) which is dependent on the position of that cost relative to similar costs from other origin sites. For example, a different penalty might be applied if the transportation cost of the commodity from origin site j was the 5th-most expensive cost rather than the 2nd-most expensive, see [3,30,32,33,35,36]. It is even possible to neglect some origin by assigning a zero penalty. This adds a ‘‘sorting’’- problem to the underlying hub location problem, making formulation and solution much more challenging.

     Our goal is to present a unified framework to analyze these and related models of hub location that consider ordinal information to cope with actual requirements from logistics. Formally, the objective is to minimize the total transportation cost of the flows between each origin–destination pair, routed through at most two hubs, once we have applied rank dependent compensation factors on the transportation costs of the origin-first hub links, and fixed scaling factors for the inter-hub and hub-final destination transportation costs.

      The rest of the paper is organized as follows: In Section 2 we describe formally the model and provide a mathematical programming formulation using variables with three indices. Section 3 studies alternative formulations for this hub location problem using covering variables. In Section 4, we present a preliminary computational analysis to determine the limits of solving the problem with the 3-index variable and covering variable formulations using standard MIP solvers. Section 5 develops some improvements and strengthening with respect to the previous formulations and an alternative formulation under the hypothesis of l-weights given in non-decreasing order. These improvements are computationally compared in Section 6. The paper ends with some conclusions. In the Appendix, we provide a result stating that some constraints presented above, that in the general case are required to get a valid formulation, are redundant whenever the cost structure satisfies the triangular inequality.

2. The model and the 3-index formulation

     Let A denote a given set of N client sites and identify these with integers 1,y,N. Each site is collecting or gathering some commodity that must be sent to the remaining sites. Let wjmZ0 be the amount of commodity to be supplied from the j th- to the m th-site for all j,mAf1, ... ,Ng and let Wj ¼ PN m ¼ 1 wjm. In the following, we assume without loss of generality that the set of candidate sites for establishing hubs is identical to the set of sites A. Let cjmZ0 denote the unit cost of sending commodity from site j to site m (not necessarily satisfying the triangular inequality). We assume that cjj¼0, 8j ¼ 1, ... ,N. Let prN be the number of hubs to be located and X  A with jXj ¼ p denote a feasible set of candidate sites. A solution for the problem is a feasible set of candidate sites X, plus a set of paths connecting pairs (flow patterns) of sites j, m for all j,mAf1, ... ,Ng in such a way that each path traverses at least one and no more than two hubs from X. To be more precise, (i) if the origin site j and the destination site m are not hubs, the flow must go through one or two intermediate hubs; (ii) if either the origin or the destination sites are hubs, the flow between them can be either directly sent or sent through an additional hub; and (iii) if both origin and destination sites are hubs, the flow must go directly from the origin to the destination.

     In addition, this model compensates origin site-first hub transportation costs by using parameters l ¼ ðl1, ... ,lNÞ. These scaling factors will be assigned to the origins depending on the order of the sequence of transportation costs of the commodity with the same origin to the first hub. Indeed, if a solution sends the commodity from the origin site j via a first hub k and this delivery cost, namely Wjcjk, was ranked in the ith position among these type of costs then this term would be scaled by li, i.e. the corresponding objective function component would be liWjcjk. In addition, we also consider a compensation parameter 0oao1 for the deliveries between hubs and another parameter 0odo1, aod for the deliveries between hubs and final destination sites. These parameters may imply that, at times, using a second hub results in a cheaper connection than going directly from the first hub to the final destination.

     Observe that depending on the choices of the l-vector we can obtain different criteria to account for the costs from the origins to their first hubs in the objective function. For instance, if l ¼ ð0, ... ,0,1,... k ,1Þ, were considered the objective function would be the sum of the k-largest costs (k-centrum). In the following, we illustrate the different behavior of our model for different choices of the l-vector and the single allocation p-hub median. For this purpose we use the CAB data set publicly available at http://people.brunel.ac.uk/mastjjb/jeb/info.html (see [34]), with N¼20, p¼5, a ¼ 0:7 and d ¼ 1:2a. Indeed, Table 1 reports the locations of the hub sites for different criteria (p-center, i.e., l ¼ ð0, ... ,0,1Þ, trimmed mean with k1¼k2¼8, i.e., l ¼ ð0,... 8 ,0,1,1,1,1,0,... 8 ,0Þ, k-centrum with k¼9, i.e., l ¼ ð0, ... ,0,1,... 9 ,1Þ) and the locations of the hubs sites for the single allocation p-hub median. We can check that the solutions we obtained are different for all the considered criteria. Moreover, we observe, from Table 1, that even in those cases where the same site is chosen as a hub with respect to different criteria, the allocation pattern of origin sites to hubs is different. For instance, in the optimal solution for the center and the single allocation p-hub median there are two hubs at sites 2 and 13. However, the allocations are different. Indeed, 14!2 for the center problem and 14!13 for the single allocation p-hub median model.

خلاصه

1- مقدمه 

2 – مدل و فرمول بندی سه شاخصه

2-1- فرمول بندی سه شاخصه

3- فرمول بندی جایگزین بر پایه پوشش متغیرها ; پوشش فرمول بندی سه شاخصه 

4- مقایسه روابط 

5- بهبودها

5-1- رابطه جدید OT سه شاخصه

5-2- تثبیت متغیر

6- مقایسه روابط بهبود یافته

7- نتیجه گیری

Abstract

1. Introduction

2. The model and the 3-index formulation

2.1. 3-Index formulation

3. An alternative formulation based on covering variables : covering 3-index formulation

4. Comparing formulations

5. Improvements

5.1. An alternative formulation: OT-3-index

5.2. Variable fixing

6. Comparing improved formul

7. Conclusions

Appendix 

References