کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
10347167 699096 2012 17 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Large-scale pickup and delivery work area design
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر علوم کامپیوتر (عمومی)
پیش نمایش صفحه اول مقاله
Large-scale pickup and delivery work area design
چکیده انگلیسی
This paper presents a new approach to rationalizing the design of work areas for drivers who pickup and deliver hundreds of packages a day. Taking into account the random nature of demand, visit frequency, and service time, the objective is to partition the customers into the minimum number of convex, continuous clusters such that each can be serviced by a single vehicle within the time available in a day. An additional requirement is that the aspect ratio of a work area must satisfy certain geometric conditions. The problem is formulated as a generic capacitated clustering problem with side constraints and solved with a combination of aggregation to achieve analytic tractability, column generation to determine good clusters, regeneration to diversify the exploration of the feasible region, and heuristic variable fixing to find good feasible solutions. A novel set of geometric constraints allows for the implicit generation of clusters, and several valid inequalities are introduced to strengthen the pricing subproblem formulation. In addition, ideas from tabu search are adopted to limit the number of subproblems that are solved at each iteration. This greatly improved the efficiency of the column generation algorithm without sacrificing quality. The methodology was tested with data provided by a leading carrier. Six data sets were examined, ranging in size from roughly 6000 to 45,000 customers. The results showed that much more compact work areas could be obtained than currently exist, and that the number of drivers could be reduced by an average of 7.6%. This translates into millions of dollars in annual saving when all service areas across the U.S. are taken into account.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computers & Operations Research - Volume 39, Issue 12, December 2012, Pages 3102-3118
نویسندگان
, ,