دانلود مقاله ISI انگلیسی شماره 20811 + ترجمه فارسی
عنوان فارسی مقاله

ابتکاری ترکیبی برای حل مساله مسیریابی محل موجودی با استفاده از تقاضای قطعی

کد مقاله سال انتشار مقاله انگلیسی ترجمه فارسی
20811 2013 12 صفحه PDF 35 صفحه WORD
خرید مقاله
پس از پرداخت، فوراً می توانید مقاله را دانلود فرمایید.
عنوان انگلیسی
Hybrid heuristic for the inventory location-routing problem with deterministic demand
منبع

Publisher : Elsevier - Science Direct (الزویر - ساینس دایرکت)

Journal : International Journal of Production Economics, Volume 146, Issue 1, November 2013, Pages 359–370

فهرست مطالب ترجمه فارسی
چکیده
کلمات کلیدی
1- مقدمه
2- تعریف مساله
جدول 1: طیقه‌بندی مسایل ترکیبی مسیریابی موجودی-مکان و روش‌ها
3- ابتکار ترکیبی
1-3 طرح زنجیره تامین
2-3 مسیریابی ابتکاری تصادفی شده
3-3 جستجوی محلی
شکل 1 -مثال در مورد تغییر تاریخ تحویل
4-3تشدید
5-3  بهینه‌سازی بعدی
6-3مروری بر الگوریتم
4-  بررسی محاسباتی 
1-4مثال‌ها
جدول 2: تاثیر مقدار نامعادلات معتبر
2-4عملکرد حل کننده MIP و تحلیل تاثیر نامعادلات
3-4 آزمایش های مقدماتی برای روش ابتکاری ترکیبی
4-4نتایج 
جدول 3: زمان های CPU و متوسط اختلاف برای HH، H1 و حل کننده برای نمونه های تصادفی ILRP
جدول 4: CPU و متوسط اختلاف برای HH، H1 و حل کننده برای نمونه های بزرگ ILRP
جدول 5: معیارسنجی نمونه های مساله مسیریابی محل
جدول 6: معیارسنجی در مورد نمونه های مساله مسیریابی موجودی
5- نتایج
پیوست 1- علائم اختصاری برای فرمولاسیون ریاضی
پیوست 2- علایم استفاده شده برای دستورالعمل ابتکاری
کلمات کلیدی
مشکل مسیریابی محل - مشکل مسیریابی موجودی - فن آوری فراهوشمند - مشکل مسیر یابی خودرو -
ترجمه چکیده
مساله مسیریابی محل موجودی با استفاده از تقاضای قطعی را می‌توان به عنوان روشی برای بهینه‌سازی طرح یک زنجیره تامین و به حداقل رساندن هزینه‌های عملیاتی آن در نظر گرفت. در این مساله فرض شده که خودروها می‌توانند در هر مسیر محصولات را به بیش از یک خرده فروش تحویل داده و تصمیمات مرتبط با مدیریت موجودی شامل یک سیستم چند انباری، چند خرده فروش با ظرفیت ذخیره‌سازی در برنامه‌ریزی با افق زمانی گسسته است. برای توصیف مساله و ایجاد ارتباط با راه‌حل‌ها یک مدل برنامه‌ریزی خطی ترکیبی- صحیح پیشنهاد شده است. این مدل توسط دو مجموعه از نامعادلات تاییدی همراه با تحلیلی در مورد تاثیر آن‌ها تایید شده است. چون مدل قادر به حل نمونه‌های هدف‌گذاری شده در یک بازه زمانی محاسباتی منطقی نیست، یک روش ترکیبی، قرار دادن روشی دقیق درون طرح استدلالی، ارائه شده است. عملکرد این روش بر روی سه مجموعه نمونه‌ برای مسایل مسیریابی محل موجودی، مسیریابی محل، و مسیریابی موجودی آزمایش شده است. نتایج نشان دهنده صرفه‌جویی‌های قابل توجه در مقایسه با استفاده از روش تجزیه شده و توانایی الگوریتم برای حل مساله است.
ترجمه مقدمه
طراحی زنجیره تامین به عنوان تصمیم‌گیری در سطح استراتژیکی در نظر گرفته شده است. این طراحی شامل شناسایی تعداد بهینه کارخانه برای افتتاح و محل‌های آن‌ها است به نحوی هزینه‌های حمل و نقل حداقل شوند. از طرف دیگر، مدیریت زنجیره تامین معمولاً با تصمیمات تاکتیکی و یا عملیاتی درگیر بوده و نگران همکاری بین امکانات برای به دست آوردن، انتقال، ذخیره و توزیع مواد که هزینه‌های لجستیکی را افزایش می‌دهد، است. متعادل کردن اهداف استراتژیکی با اهداف عملیاتی یک کار چالش‌برانگیز است. بیشتر مدل‌های محل امکانات فرض می‌کنند که توزیع توسط مسیرهای تعیین شده انجام می‌شود، یعنی یک خودرو حداکثر یک مشتری را ملاقات می‌کند. البته، در صورتی که سفارشات خیلی کمتر از ظرفیت خودرو باشد، این فرض دیگر اعتباری ندارد. تاثیرات نادیده گرفتن تصمیمات مرتبط با مسیریابی در زمان تعیین مکان انبارها توسط شن و کیویی (2007) و صالحی و راند(1989) بررسی شده است. وقتی خودروها سفرهای تک بازدیدی را انجام نمی‌دهند، تعیین محل انبارها، به نحوی که فواصل بین انبارها و خرده‌فروش‌ها حداقل شده باشد، پاسخ بهینه نیست. مدل مناسب‌تر نمونه‌ای است که در مسایل مسیریابی محل ارائه شده و در آن‌ها هدف این است که تصمیمات مربوط به محل همزمان با تصمیمات مربوط به مسیریابی بهینه شوند. نمونه‌ای از این دست توسط پرینز و همکارانش (2007)، بلنگور و همکارانش (2011) توضیح و بررسی آن توسط ناگی و صالحی (2007) ارائه شده است. در هر صورت، این مقالات با نمونه تک دوره ای سروکار داشته‌اند یا این که مساله چند دوره‌ای را با وزن‌گذاری سرویس به مشتریان به نحوی که در هر دوره از افق زمانی وزن‌ها برابر باشند، ساده کرده‌اند. در این اواخر، پرادهون (2011) یک نمونه دوره‌ای را حل ولی تصمیم‌گیری در مورد موجودی را مدیریت نکرد. در ادامه، میراندا و گاریدو (2009) تاثیر نادیده گرفتن تصمیمات مرتبط با موجودی در زمانی طراحی زنجیره تامین را توضیح دادند. آن‌ها نتیجه گرفتند که طرح تخصیص خرده‌فروش‌ها به انبارها دارای تاثیری مستقیم بر هزینه عملیاتی انبار است زیرا وقتی تقاضای کلی متفاوت باشد، هزینه‌های سفارش‌دهی و نگهداری می‌توانند به میزان قابل توجهی تغییر کنند. به علاوه، تصمیمات مرتبط با موجودی و مسیریابی به شدت به یکدیگر وابسته هستند. تصمیمات مرتبط با مدیریت توزیع و انبار به دو دلیل بر یکدیگر تاثیر می‌گذارند: اول، مجموعه مسیرهایی که هزینه را به حداقل می‌رسانند به صورت تابعی از مقادیری که در هر دوره تحویل داده می‌شود ایجاد شده که با توجه به سیاست‌های مرتبط با موجودی کالا تعیین شده است؛ و دوم، هزینه‌های سفارش نیاز به طراحی سیاست‌های موجودی دارد، که در این میان، هزینه حمل و نقل با توجه به انتخاب توالی که بر اساس آن به خرده‌فروش‌ها سرویس‌دهی می‌شود ایجاد شده است. تعادل بهینه بین هزینه‌های موجودی و توزیع در برتازی و همکارانش (2002) و آندرسون و همکارانش (2010) تحت عنوان مساله مسیریابی موجودی (IRP) شناخته شده است. در صورتی که مسایل موجودی و مسیریابی شامل تصمیم‌گیری محل نیز باشد، طراحی زنجیره تامین بسیار پیچیده خواهد شد. البته، لازم است که تصمیمات کوتاه مدت با تفکر بلند مدت متعادل شوند. در نتیجه، در مورد مساله مسیریابی محل موجودی (ILRP)، طرح به دست امده برای زنجیره تامین شامل دیدگاهی در زمینه موضوعات جامع است تا در مورد نحوه تامین تقاضای آتی با حداقل هزینه تصمیم‌گیری شود. منافع که در این رابطه مطرح می شوند عمدتاً ناشی از دو مورد است: وقتی نیاز به یک محل موقتی است. این حالت برای شرکت‌هایی است که به صورت استراتژیکی انبارهایی را اجاره و کرایه پرداخت می‌کنند. بنابراین، آن ها انعطاف‌پذیرتر بوده و می‌توانند به راحتی و به صورت دوره‌ای محل انبارها را تغییر دهند. این حالت هم چنین برای وقتی است که در راستای ماموریت‌های بشردوستانه و مدیریت فاجعه موجود‌ی‌ها با منابع مالی محدود و از طریق کمک‌های بلاعوض آزاد شوند (وایبارک، 2007؛ باکیک و همکارانش 2010). این فعالیت ها در اغلب موارد برای یک دوره زمانی کوتاه انجام می‌شوند. به علاوه، در حوزه حمل و نقل نظامی، تصمیم‌گیری در مورد مکان موقت اغلب برای توزیع مهمات و سایر ملزومات انجام می‌شود. در تمامی موارد، هزینه‌های محل (مثلاً اجاره) و هزینه های عملیاتی (توزیع و انبارداری) می‌توانند از نظر اندازه برابر باشند. وقتی که اهداف بلند مدت مستلزم طراحی زنجیره تامینی باشد که امکان تکرار تامین مجدد برای هر خرده‌فروش را فراهم کرده و توزیع با استفاده از خودروهایی انجام شود که قادر به بازدید از بیش از یک خرده‌فروش در هر مسیر باشند. این حالت وقتی مطرح است که فرض تصمیم‌گیری‌ها در مورد مسیریابی برای یک دوره (این فرض که مسیریابی در دوره‌های مشابه انجام می‌شود) یا مسیرهای تعیین شده (مسیرهایی که توسط یک خرده‌فروش بازدید می‌شوند) به اندازه‌کافی محقق نشده نباشند. بخش بزرگی از خرده‌فروشی یا تامین دارو و تجهیزات پزشکی از این دست هستند. دوباره، هزینه‌های باز کردن انبار باید بر روی افق مدل شده‌ای مقیاس‌گذاری شود که در تعادل با هزینه‌های عملیاتی باشد. به علاوه، اگر تقاضای آتی در بلند مدت در نظر گرفته نشده باشد، وارد کردن هزینه‌های موجودی و مسیریابی این امکان را فراهم می‌کند که در ساختار محل- تخصیص، تاثیرات فعالیت های غیر ثابت توزیع و تاثیرات متقابل بین تصمیمات مربوط به موجودی و مسیریابی نیز در نظر گرفته شوند. در این صورت، تصمیمات مربوط به محل مبتنی بر مجموعه‌ای از سناریوهای مسیریابی (یک سناریو برای هر دوره) در بلندمدت بسیار بهتر از تصمیمات مبتنی بر یک سناریو واحد برای مسیریابی اجزا خواند شد. توجه داشته باشید که این کاربردها نشان می‌دهند تقاضا می‌تواند ماهیتی غیر قابل پیش‌بینی داشته باشد ولی در مدل ما فرض می‌شود که داده‌ها شناخته شده هستند. وظیفه ما این است که نمونه قطعی مساله را به گونه ای حل کنیم که قبل از حل نمونه تصادفی ارجاعی اولین گام را برداریم. هم چنین یک ابزار تصمیم‌یار برای تحلیل «چرا- اگر» ایجاد کرده‌ایم. فرض کنید که یک تحلیلگر علاقمند به داشتن برآوردهای بهتری از هزینه‌هایی که مشخص کننده احتمال تجدید ساختار زنجیره تامین تحت فرضیات ویژه مربوط به تقاضای آتی هستند، باشد. چند مقاله به طور همزمان بر روی سه مساله کار می‌کنند: محل انبار، مسیریابی خودرو، و سیاست‌های بهینه‌سازی موجودی. جدول 1 مروری بر مدل‌ها و روش‌های حل برای ILRP را نشان می‌دهد. ستون‌های خرده‌فروش و انبار نشان می‌دهند که تصمیمات مرتبط با موجودی بر اساس خرده‌فروش‌ها، انبارها یا هر دو بوده‌اند. فرض کنید که مسریابی تک دوره‌ای، تصمیمات مربوط به محل بر اساس یک مجموعه گسسته، تقکیک یا انباشت درخواست غیر مجاز و تقاضا به صورت تصادفی است. ساختار هزینه ای که باید حداقل شود شامل هزینه های ثابت برای افتتاح، هزینه‌های پیش‌بینی شده انبارداری و خروج کالا، و هزینه‌های مسیریابی است. آمبروسینو و اسکیوتلا (2205) با در نظر گرفتن تقاضای قطعی مدل خطی برای ILRP ارائه کردند و نشان دادند که برای حالت تک دوره‌ای (LRP)، مدل استفاده شده در CPLEX 7.0 قادر به پیدا کردن پاسخ‌های بهینه ظرف مدت 25 ساعت برای نمونه هایی با 13 انبار و 95 خرده‌فروش نیست. در مورد تقاضای تصادفی، ما و دیویدراجو (2005) یک روش بهینه‌سازی ترتیبی تکراری را پیشنهاد کردند که در آن مساله به صورت یک سری مسایل فرعی و بدون چشم‌انداز کلی مطرح شده بود. به علاوه، در مورد این مساله دو مشخصه متفاوت وجود دارد. اول، برخی از محققان ادعا می‌کنند که وارد کردن LRP در تابع هدف یک بخش EOQ مانند (مدل ویلسون) با هدف به حداقل رساندن هزینه پیش‌بینی شده مدیریت موجودی در خرده‌فروش‌ها، منجر به ایجاد یک مدل غیر خطی می‌شود. دومین روش مقادیری که باید به خرده‌فروش‌ها تحویل داده شود را ثابت کرده و در عوض سیاست‌های موجودی در انبارها را بهینه می‌کند. این مقاله، ILRP را به عنوان پیامدی از تعیین محل انبارها و با در نظر گرفتن هزینه‌های ثابت افتتاح انبار بررسی کرده و هزینه‌های عملیاتی و تاکتیکی همانند هزینه مدیریت مسیریابی و موجودی را نیز در نظر می‌گیرد. مدل ریاضی و برخی از نامعادلات معتبر در بخش 2 ارائه شده‌اند. بخش 3 اکتشاف (ابتکار) ترکیبی را توصیف کرده و در بخش 4 بررسی محاسباتی ارائه شده است. نتایج در فصل 5 آورده شده‌اند.
پیش نمایش مقاله
پیش نمایش مقاله ابتکاری ترکیبی برای حل مساله مسیریابی محل موجودی با استفاده از تقاضای قطعی

چکیده انگلیسی

The Inventory Location-Routing Problem with deterministic demand can be seen as an approach to both optimize a supply chain design and minimize its operational costs. This problem considers that vehicles might deliver products to more than one retailer per route and that inventory management decisions are included for a multi-depot, multi-retailer system with storage capacity over a discrete time planning horizon. The problem is to determine a set of candidate depots to open, the quantities to ship from suppliers to depots and from depots to retailers per period, and the sequence in which retailers are replenished by an homogeneous fleet of vehicles. A mixed-integer linear programming model is proposed to describe the problem and to provide bounds on the solutions. It is strengthened by two sets of valid inequalities with an analysis of their impact. Since the model is not able to solve the targeted instances exactly within a reasonable computation time, a hybrid method, embedding an exact approach within a heuristic scheme, is presented. Its performance is tested over three sets of instances for the inventory location routing, location-routing and inventory-routing problems. Results show important savings achieved when compared to a decomposed approach and the capability of the algorithm to solve the problem.

مقدمه انگلیسی

The design of a supply chain is considered as a strategic level decision. It consists of identifying the optimal number of plants to open and their locations so that logistics costs are minimal. On the other hand, the management of a supply chain is usually to tackle tactical and/or operational decisions and it concerns the cooperation between facilities in order to obtain, transform, store and distribute materials, which also entails logistical costs (Melo et al., 2009). Balancing strategic with operational objectives is the challenge. Most of the facility location models consider distribution to be performed by dedicated routes, i.e., one vehicle visits one client at most (see Gebennini et al., 2009). However, in the case where orders are much smaller than vehicle capacity, this assumption is not longer true. The effects of ignoring routing decisions when locating depots are studied by Shen and Qi (2007) and Salhi and Rand (1989). When vehicles are not performing single-visit tours, locating depots, so that the sum of the distances between depots and retailers is minimized, is not an optimal solution. A more appropriate model is the one depicted in Location-Routing problems, that propose to optimize location decisions simultaneously with routing decisions. Examples are described by Prins et al. (2007), Belenguer et al. (2011) and a review is presented by Nagy and Salhi (2007). Nevertheless, these papers deal with the single period version or they simplify the multi-period problem by weighting the service to customers to be the same on each period of the horizon. Recently, Prodhon (2011) solved a periodic version, but no inventory decision is managed. Then, Miranda and Garrido (2009) discuss the impact of ignoring inventory decisions when designing a supply chain. They conclude that the assignment scheme of retailers to depots has a direct impact on depot operation cost because ordering and holding costs might be significantly modified when the aggregated demand varies. In addition, inventory and routing decisions are strongly interdependent (Bell et al., 1983). Distribution and stock management decisions affect each other for two reasons: First, the set of minimal cost routes is built as a function of the quantities to deliver per period, which are determined by the inventory policies; and second, ordering costs required to design inventory policies include, among others, the transportation cost resulting from the choice of the sequence in which the retailers will be served. The optimal trade-off between inventory and distribution costs is known as the Inventory-Routing Problem (IRP) in Bertazzi et al. (2002), and Andersson et al. (2010). Designing a supply chain becomes more complex if inventory and routing problems are included in the location decision-making. However, it is essential to balance short-term decisions with longer term thinking. As a result, for the Inventory Location-Routing Problem (ILRP), the resulting supply chain design includes an insight into detailed topics in order to decide how to satisfy future demand at minimum cost. Interest arises mainly from two contexts: (i) When a temporary location is required. It is the case for companies that strategically lease depots and pay rent. Consequently, they are more flexible and might conveniently change locations periodically. It is also the case for humanitarian missions managing disaster relief inventories (Whybark, 2007 and Balcik et al., 2010) with limited financial resources through donations. These activities are often performed for a short time. Further, in the field of military logistics, temporary location decisions are often made in order to distribute ammunition and other supplies. In all cases, location costs (e.g., rent) and operational costs (distribution and inventory holding) could have similar orders of magnitude. (ii) When long-term objectives require a supply chain design allowing different frequencies of replenishment for each retailer and distribution to be performed by vehicles capable of visiting more than one retailer per route. It is the case when assuming single period routing decisions (assuming routing to be the same every period) or dedicated routes (routes visiting a single retailer) are not realistic enough. The large retail sector or pharmaceutical and medical equipment supply are some examples. Again, depot opening costs should be scaled on the modeled horizon to be in balance with the operational costs. Furthermore, even if the future demand is not considered in the long-term, including inventory and routing costs allows incorporating within the location–allocation structure the effects of non-constant distribution activities and the effects of the interactions between inventory and routing decisions. Then, location decisions based on a set of routing scenarios (one per period) will perform outstandingly better on the long-run than one based on a single routing scenario. Note that these applications suggest that demand might have an unpredictable nature while our model assumes known data. Our contribution is to solve the deterministic version of the problem in order to take the first step before solving a stochastic version with recourse. Even more, we also develop a decision-aid tool for “what-if” analysis. Think that an analyst might be interested in having better estimates of costs given the possibility of restructuring the supply chain under specific future demand assumptions. Few papers simultaneously work on the three problems: depot location, vehicle routing and optimizing inventory policies. Table 1 summarizes a literature review on models and solution methods for the ILRP. Columns Ret. and Dep. denote if inventory decisions are made either at retailers, at depots, or both. Table 1. A classification on combined inventory-location-routing problems and methods. Authors Demand Ret. Dep. Model Solution method Liu and Lee (2003) Stochastic ✓✓ Non-linear Route first-locate second Liu and Lin (2005) Stochastic ✓✓ Non-linear Sequential/improv. stage Ambrosino and Scutellà (2005) Determ. ✓✓ ✓✓ Linear Commercial solver Ma and Davidrajuh (2005) Stochastic ✓✓ ✓✓ Non-linear Sequential Shen and Qi (2007) Stochastic ✓✓ Non-linear Branch-and-bound Javid and Azad (2010) Stochastic ✓✓ Non-linear Tabu search Simulated Annealing Mete and Zabinsky, 2010 Stochastic ✓✓ Non-linear Sequential stochastic programming Sajjadi and Cheraghi (2011) Stochastic ✓✓ Non-linear Sequential/improv. stage Table options Most consider a single period routing, location decisions within a discrete set, demand splitting or backlogging not allowed and stochastic demand. The cost structure to be minimized comprises fixed opening costs for depots, expected holding and stock-out costs, and routing costs. Considering deterministic demand, Ambrosino and Scutellà (2005) propose a linear model for the ILRP and show that for the single period case (LRP), the model implemented in CPLEX 7.0 is not able to find optimal solutions within 25 h for instances with 13 depots and 95 retailers. For stochastic demand, Ma and Davidrajuh (2005) propose an iterative sequential optimization approach where the problem is tackled as a series of sub-problems and never with a global perspective. In addition, two different characterizations of this problem exist. First, some research papers tackle a LRP integrating in the objective function an EOQ-like component (Wilson model) aiming to minimize the expected inventory management cost at retailers, resulting in a non-linear model. The second approach fixes quantities to be delivered to retailers and optimizes inventory policies at depots instead. This paper studies the ILRP as the issue of locating depots considering depot fixed opening costs, operational and tactical costs such as routing and stock management cost are included. The mathematical model and some valid inequalities are presented in Section 2. Section 3 describes a hybrid heuristic and a computational study is presented in Section 4. Conclusions are given in Section 5.

نتیجه گیری انگلیسی

We present the combined Inventory-Location-Routing Problem (ILRP) as an approach to supply chain design considering inventory management and routing cost in order to overcome the fact that traditional approaches decompose decisions and often provide sub-optimal solutions. We consider a discrete and finite planning horizon and a two-echelon supply chain. Assumptions include a homogeneous fleet of vehicles, and deterministic, non-constant demand. Seasonal holding costs and obsolescence penalty costs are additional (but not restrictive) features of our model. Decisions that must be taken simultaneously are: (1) location decisions of depots, (2) inventory decisions at both echelons of the supply chain, (3) allocation decisions of retailers to depots, and (4) multi-period routing decisions. We propose a hybrid approach to solve a supply chain design problem with estimated distribution costs using exact methods while the remaining routing decisions are computed by heuristic procedures. By alternating between decisions spaces and information sharing, the algorithm manages to optimize globally the components of the problem without oversimplifying it. Results for randomly generated instances show significant cost savings over the traditional approach and efficient computation when compared to commercial solvers. The ILRP reduces to the LRP and the IRP under certain conditions. Our tests show a robust performance over larger benchmark instances for both the LRP and the IRP. Future research comprises the ILRP with two routing decision levels as in the 2E-LRP and the ILRP considering maritime transportation constraints.

خرید مقاله
پس از پرداخت، فوراً می توانید مقاله را دانلود فرمایید.