A large neighborhood search approach to the vehicle routing problem with delivery options

To reduce delivery failures in last mile delivery, several types of delivery options have been proposed in the past twenty years. Still, customer satisfaction is a challenge because a single location is chosen independently of the time at which the customer’s order will be delivered. In addition, delivery at shared locations such as lockers and shops also experience failure due to capacity or opening-time issues at the moment of delivery. To address this issue and foster consolidation at shared delivery locations, the authors investigate the case where a customer can specify several delivery options together with preference levels and time windows. The authors define, in this article, the Vehicle Routing Problem with Delivery Options, which integrates several types of delivery locations. It consists of designing a set of routes for a fleet of vehicles that deliver to each customer at one of his/her options during the corresponding time window. These routes should respect capacities at shared locations such as lockers and minimum service level requirements, while minimizing the total routing costs. This problem is solved with a large neighborhood search in which a set partitioning problem is periodically used to reassemble routes. Specific ruin and recreate operators are proposed and combined with numerous operators from the literature. A thorough experimental study was carried out to determine a subset of efficient and complementary operators. The proposed method outperforms existing algorithms from the literature on particular cases of the problem under consideration, such as the vehicle routing problem with roaming delivery locations and the vehicle routing problem with home and roaming delivery locations. New instances are generated and used both to serve as a benchmark and to propose some managerial insight into the vehicle routing problem with alternative delivery options.


  • English

Media Info

Subject/Index Terms

Filing Info

  • Accession Number: 01767740
  • Record Type: Publication
  • Files: TRIS
  • Created Date: Jan 13 2021 3:07PM