A covering traveling salesman problem with profit in the last mile delivery

This paper introduces and formulates a covering traveling salesman problem with profit arose in the last mile delivery. In this problem, a set of vertices including a central depot, customers and parcel lockers (PL) are given, and the goal is to construct a Hamiltonian cycle within a pre-defined cost over a subset of customers and/or PLs to collect maximum profits, each unvisited customer is covered by a PL in the cycle or outsourced. To solve the problem, a two-phase heuristic combined with a feasible solution construction procedure and an improvement procedure is proposed. The algorithm is evaluated on two sets of instances, and the computational results indicated its efficiency.