Hybrid artificial immune algorithm for optimizing a Van-Robot E-grocery delivery system

Abstract Same-day delivery and on-demand delivery with driverless delivery robots (DDRs) are becoming new attractive options for more customers looking for grocery or medication delivery, as these delivery methods can customize time demand and meet consumers’ safety expectations. However, meeting these requirements for instant shipping necessarily increases the need for more vans and DDRs for last-mile delivery, thus increasing the economic and ecological costs. To optimize the economic costs and environmental effects of the delivery network, and also to meet customer satisfaction simultaneously, an effective model considering the new constraints of the van-DDR system and an efficient algorithm are needed to obtain the solutions. Therefore, the goals of this study are to establish a model and develop an algorithm for a multi-objective multi-depot two-tier location routing problem with parcel transshipment (MOMD-2T-LRP-PT), where vans and DDRs serve the two tiers, respectively. In this study, we split the MOMD-2T-LRP-PT model into two subproblems: the location-allocation problem and the vehicle routing problem. The two problems are solved sequentially and iteratively with a “k-prototype cluster” and a hybrid artificial immune algorithm (HAIA). We firstly illustrate the effectiveness of the MOMD-2T-LRP-PT model with the ∊-constraint method on a small-scale data set. Then the proposed HAIA algorithm is compared with a nondominated sorting genetic algorithm II (NSGA-II) using different data sets including a real case test. Both the analytic results and the real case application show that the ∊-constraint method can produce the best solution with up to six customers, and the HAIA algorithm produces better-optimized results than NSGA-II in real-life applications. These results imply that the MOMD-2T-LRP-PT model and the proposed HAIA algorithm are promising and effective in optimizing practical E-grocery delivery that can achieve optimization and balance among economic costs, environmental effects, and customer satisfaction.