مشخصات مقاله | |
ترجمه عنوان مقاله | یک الگوریتم شاخه و برش و ارزش برای پیکاپ جداگانه چند گردشی و مشکل تحویل با دریچه های زمانی در مشتریان و امکانات |
عنوان انگلیسی مقاله | A Branch-and-Cut-and-Price algorithm for the Multi-trip Separate Pickup and Delivery Problem with Time Windows at Customers and Facilities |
انتشار | مقاله سال ۲۰۱۹ |
تعداد صفحات مقاله انگلیسی | ۱۶ صفحه |
هزینه | دانلود مقاله انگلیسی رایگان میباشد. |
پایگاه داده | نشریه الزویر |
نوع نگارش مقاله |
مقاله پژوهشی (Research Article) |
مقاله بیس | این مقاله بیس میباشد |
نمایه (index) | Scopus – Master Journals List – JCR |
نوع مقاله | ISI |
فرمت مقاله انگلیسی | |
ایمپکت فاکتور(IF) |
۴٫۷۱۲ در سال ۲۰۱۸ |
شاخص H_index | ۲۲۶ در سال ۲۰۱۹ |
شاخص SJR | ۲٫۲۰۵ در سال ۲۰۱۸ |
شناسه ISSN | ۰۳۷۷-۲۲۱۷ |
شاخص Quartile (چارک) | Q1 در سال ۲۰۱۸ |
مدل مفهومی | ندارد |
پرسشنامه | ندارد |
متغیر | دارد |
رفرنس | دارد |
رشته های مرتبط | مدیریت |
گرایش های مرتبط | بازاریابی |
نوع ارائه مقاله |
ژورنال |
مجله / کنفرانس | مجله اروپایی درباره تحقیقات عملیاتی – European Journal of Operational Research |
دانشگاه | OPTIT Srl Viale Amendola 56/D, Imola (BO) 40026, Italy |
کلمات کلیدی | مسیریابی، پیکاپ جداگانه و مشکل تحویل، شاخه و برش و ارزش، برنامه نویسی دینامیکی دو جهته |
کلمات کلیدی انگلیسی | Routing، Separate Pickup and Delivery Problem، Branch-and-Cut-and-Price، Bi-directional dynamic programming |
شناسه دیجیتال – doi |
https://doi.org/10.1016/j.ejor.2019.06.032 |
کد محصول | E13523 |
وضعیت ترجمه مقاله | ترجمه آماده این مقاله موجود نمیباشد. میتوانید از طریق دکمه پایین سفارش دهید. |
دانلود رایگان مقاله | دانلود رایگان مقاله انگلیسی |
سفارش ترجمه این مقاله | سفارش ترجمه این مقاله |
فهرست مطالب مقاله: |
Abstract ۱٫ Introduction ۲٫ Literature review ۳٫ Problem description and ILP formulation ۴٫ Solution method ۵٫ Experimental analysis ۶٫ Conclusion and future work Acknowledgments Appendix A. Notation Appendix B. Backward propagation References |
بخشی از متن مقاله: |
Abstract
We study the Multi-trip Separate Pickup and Delivery Problem with Time Windows at Customers and Facilities (MT-PDTWCF), arising in two-tiered city logistics systems. The first tier refers to the transportation between the city distribution centers, in the outskirts of the city, and intermediate facilities, while the second tier refers to the transportation of goods between the intermediate facilities and the (pickup and delivery) customers. We focus on the second tier, and consider that customers and facilities have time windows in which they can be visited. Waiting is possible at waiting stations for free or at customers and facilities at a given cost or penalty. Therefore, it is relevant to coordinate the arrivals of vehicles at facilities and customers with the corresponding time windows. The MT-PDTWCF calls for determining minimum (fixed, routing and waiting) cost multi-trip routes, for a given fleet of vehicles, to service separately pickup and delivery customers, while taking into account vehicle capacity and time windows both at customers and facilities. We propose the first exact algorithm for MT-PDTWCF, namely a Branch-and-Cut-and-Price algorithm. It is based on column generation, where the pricing problem is solved by a bi-directional dynamic programming algorithm designed to cope with the features of the problem. Subset-row and rounded capacity inequalities are adapted to deal with MT-PDTWCF and inserted in the Branch-and-Cut-and-Price algorithm. The performance of the proposed algorithm is tested on benchmark instances with up to 200 customers, showing its effectiveness. Introduction We address the Multi-trip Separate Pickup and Delivery Problem with Time Windows at Customers and Facilities (MT-PDTWCF), which arises in the context of two-tiered City Logistics systems (Cattaruzza, Absi, Feillet, & González-Feliu, 2017; Crainic, Errico, Rei, & Ricciardi, 2012; Crainic, Ricciardi, & Storchi, 2009). In these systems, the first tier refers to the consolidation and transportation of loads between the city distribution centers (CDCs), in the outskirts of the city, and intermediate facilities without storage or waiting areas, called satellites, located inside the city (or close to it), by using large-capacity vehicles. The second tier considers the delivery/pickup of goods between the satellites and the customers, by using smaller-capacity vehicles that can travel inside the city. The usefulness of two-tier City Logistics systems stands in reducing the nuisances caused by freight transportation in urban areas (Crainic et al., 2009): larger trucks transport freight to satellites using corridors surrounding the city, while only small vehicles enter the city center, and the coordination of the two tiers at satellites allows the reduction of traffic congestion. In this paper, we focus on the second tier problem and consider that both customers and facilities have time windows, so that it is essential to coordinate the arrivals of vehicles at facilities and customers with the corresponding time windows. This class of problems has recently received significant attention (see, e.g., Crainic, Gajpal, & Gendreau, 2015b; Crainic, Nguyen, & Toulouse, 2016; Grangier, Gendreau, Lehuédé, & Rousseau, 2016; Guastaroba, Speranza, & Vigo, 2016; Nguyen, Crainic, & Toulouse, 2013; Nguyen, Crainic, & Toulouse, 2017), as environmental issues and traffic congestion have become more critical in every day life (Guastaroba et al., 2016). |