A Travelling Salesman Problem With Carbon Emission Reduction in the Last Mile Delivery

The development of e-commerce has led to a surge in the number of online shopping parcels. However, given the lack of scale effect, last mile delivery is inefficient, expensive, and produces a considerable amount of carbon emissions, which has become an obstacle to the development of a sustainable economy. This work proposes a traveling salesman problem with carbon emission reduction in last mile delivery. The proposed problem aims to reduce the total costs and carbon emissions of last mile delivery by deciding on the allocation of parcel lockers while scheduling delivery routes. In addition, we take the customer self-collection intention into consideration and translate it into self-collection costs, which are included in the objective. An iterated local search (ILS) algorithm is proposed, and four new local search operators are designed to improve customer allocation. The proposed method is tested on a set of scattered and clustered instances, including a real-world instance. The computational results show the superiority and competitiveness of the proposed algorithm.