An Adaptive Large Neighborhood Search for an E-grocery Delivery Routing Problem

作     者：Emec, Ugur Catay, Bulent Bozkaya, Burcin 

作者机构：Sabanci Univ Fac Engn & Nat Sci TR-34956 Istanbul Turkey Sabanci Univ Sch Management TR-34956 Istanbul Turkey 

出 版 物：《COMPUTERS & OPERATIONS RESEARCH》 (计算机与运筹学研究)

年 卷 期：2016年第69卷

页      面：109-125页

核心收录：

学科分类：1201[管理学-管理科学与工程(可授管理学、工学学位)] 08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：E-grocery Delivery Routing Problem Home Delivery Services Vehicle Routing Problem with Time Windows Premium Good Premium Customer Adaptive Large Neighborhood Search 

摘      要：Online shopping has become ever more indispensable to many people with busy schedules who have a growing need for services ranging for a wide variety of goods, which include standard (or staple) goods as well as premium goods, i.e. goods such as organic food, specialty gifts, etc. that offer higher value to consumers and higher profit margins to retailers. In this paper, we introduce a new mathematical programming formulation and present an efficient solution approach for planning the delivery services of online groceries to fulfill this diverse consumer demand without incurring additional inventory costs. We refer to our proposed model as the E-grocery Delivery Routing Problem (EDRP) as it generically represents a family of problems that an online grocery is likely to face. The EDRP is based on a distribution network where premium goods are acquired from a set of external vendors at multiple locations in the supply network and delivered to customers in a single visit. To solve this problem, we develop an improved Adaptive Large Neighborhood Search (ALNS) heuristic by introducing new removal, insertion, and vendor selection/allocation mechanisms. We validate the performance of the proposed ALNS heuristic through an extensive computational study using both the well-known Vehicle Routing Problem with Time Windows instances of Solomon and a set of new benchmark instances generated for the EDRP. The results suggest that the proposed solution methodology is effective in obtaining high quality solutions fast. (C) 2015 Elsevier Ltd. All rights reserved.