A Simulated Annealing Algorithm for the Vehicle Routing Problem With Parcel Lockers

Due to the growth in e-commerce, city logistics needs to cope with the rise of customers’ demand. Consequently, it adds to the complexity of the last-mile delivery process. Moreover, this process often contributes significantly to the distribution cost of companies. An alternative to alleviate the problem is the utilization of parcel lockers. It allows the delivery to be extended not only for home delivery but also for locker delivery, which brings several advantages in terms of cost-saving. However, considering multiple delivery options means adding new complexity to the delivery system. In the previous works, vehicle routing problem with time windows (VRPTW) has been widely dealt by only considering home delivery. This research proposes a new VRPTW variant by adding locker delivery as one of the delivery options. The developed problem is called the vehicle routing problem with parcel lockers (VRPPL). The goal of VRPPL is to minimize the total traveling cost. In this research, we formulate a new mathematical programming model and develop a simulated annealing (SA) algorithm to deal with VRPPL. A newly generated set of instances was developed from the well-known Solomon’s VRPTW instances. The performance of the proposed algorithm is also presented.