Algorithm Design And Implementation For "Last-Mile" Logistics Optimization

In this paper,we investigate a new variant of last-mile delivery.In recent years,the research on last-mile delivery has gained a lot of attention,not only because the rapid development of the Internet has generated a large number of e-commerce package de-livery demands,but also the popularization of mobile Internet has made the demand for online-to-offline(020)package rise sharply.For e-commerce packages,the biggest char-acteristic of such packages is that there is a big difference in the volume and weight of each package,and the daily delivery demand of each outlet in the city is huge.020 generally includes flowers and cakes delivery,this kind of package is usually delivered in the same city,which request the service provider to provide delivery capacity,shipping back and forth between the beginning and end of the package in the city,and the customers of this kind of package usually require a complete delivery within the time specified,namely this kind of package has time window constraints.The characteristics of these two types of packages pose significant challenges to delivery providers,including delivery plan-ning and coordination.In order to solve the above problems and challenges,this paper proposes a kind of problem variants that integrates the scheduling of static E-commerce parcels and 020 parcels.It is driven by the concept of delivery-as-a-service,which tar-gets at building consolidated infrastructure and using the same fleet of vehicles to provide standardized delivery services for different types of merchants.We formulate it as an in-tegration of Multi-Depot Multi-Trip Vehicle Routing Problem(MD-MT-VRP)and Paired Pickup and Delivery Problem with Time Window(PPDPTW).To solve the mixed prob-lem of MD-MT-VRP and PPDPTW,we present its Mixed-Integer Programming(MIP)model to obtain the optimal solution for small-scale instances.To solve large-scale prob-lems,we propose a hybrid neighborhood search strategy to effectively combine the merits of ALNS and tabu search.Base on the feature of the problem,we propose a lot of new operators to improve the diversification of the algorithm,and we find and use the auxil-iary information to prove the lower and upper bound during the search,so we can present a two-level pruning strategy that can significantly accelerate the local search procedure.We conduct extensive numeric experiments on multiple datasets,includes small scale and real life scale datasets,to analysis the performance and behavior of the algorithm.The re-sults showed that our hybrid approach achieved near-optimal performance and established clear superiority over ALNS and tabu search.We also conduct a series of experiments on similar problem datasets to show the generalization of the algorithm.