Towards delivery-as-a-service: Effective neighborhood search strategies for integrated delivery optimization of E-commerce and static O2O parcels

In this paper, the authors investigate a new variant of last-mile delivery that integrates the scheduling of static E-commerce parcels and Online-to-Offline (O2O) parcels. The O2O parcels, such as flowers and cakes, are often delivered intra city with a time window constraint. It is driven by the concept of delivery-as-a-service, which targets at building consolidated infrastructure and using the same fleet of vehicles to provide standardized delivery services for different types of merchants. The authors formulate it as an integration of Multi-Depot Multi-Trip Vehicle Routing Problem (MDMTVRP) and Paired Pickup and Delivery Problem with Time Window (PPDPTW). To solve the mixed problem of MDMTVRP and PPDPTW, the authors present its Mixed-Integer Programming (MIP) model to obtain the optimal solution for small-scale instances. To solve large-scale problems, the authors propose a hybrid neighborhood search strategy to effectively combine the merits of ALNS and tabu search. The authors also present a two-level pruning strategy that can significantly accelerate the local search procedure. The authors conduct extensive numeric experiments on multiple datasets, and results showed that their hybrid approach achieved near-optimal performance and established clear superiority over ALNS and tabu search.

Language

  • English

Media Info

Subject/Index Terms

Filing Info

  • Accession Number: 01744872
  • Record Type: Publication
  • Files: TRIS
  • Created Date: Jun 23 2020 3:06PM