Scheduling the covering delivery problem in last mile delivery

Abstract This study proposes a covering delivery problem (CDP), which has practical applications in last mile parcel delivery in online shopping. A set of vertices are considered, including depot, facilities, customers that must be covered, customers that must be visited, and customers that can be visited or covered. The goal is to construct a Hamiltonian cycle with minimum total costs over a subset of vertices, in which each customer is visited by the cycle or covered by a facility on the cycle. Flow-based and bilevel programming models are proposed to formulate the problem. Essentially, the bilevel programming formulations consist of one leader and one follower subproblems. On the basis of the bilevel programming ideas, a hybrid biogeography-based optimization (HBBO) is developed to solve the problem. In HBBO, BBO and 3-opt are used to solve the leader and follower problems, respectively. Lastly, computational experiments on a set of randomly generated and benchmark instances indicate the effectiveness of the proposed method.