Variable neighbourhood search based on Metropolis criterion for crowdsourced delivery scheduling problem in dispatch model

With the growing demand for last-mile delivery, primarily because of booming e-commerce and online-to-offline industries, crowdsourced delivery has been playing a more important role. This study explores the crowdsourcing delivery scheduling problem in dispatch mode (CDSPDM), which is a combination of order allocation and path planning. CDSPDM is a new combinatorial optimisation problem. Herein, a variable neighbourhood search based on the Metropolis criterion (VNSMC) is proposed to solve CDSPDM. The proposed VNSMC is a variant of fixed neighbourhood search (FNS) that incorporates the idea of the simulated annealing algorithm (SA), whereby a new solution using the Metropolis criterion is obtained to enhance the exploration capability of the solution space. In VNSMC, a shaking procedure based on order reassignment is proposed to expand the search scope of the solution space. Thereafter, a local search based on the combination of two local search operators is conducted to obtain local optimal solutions, and the branch-and-bound method is used to plan the travel routes for each rider. To evaluate the performance of the proposed VNSMC for CDSPDM, a genetic algorithm (GA) was adapted to the state-of-the-art CDSPDM. Consequently, a fixed neighbourhood search algorithm without the Metropolis criterion, and a simulated annealing algorithm that uses the two proposed local search operators were developed to solve the CDSPDM. The experimental results showed that the proposed VNSMC obtains better solutions than the adapted GA, FNS, and SA for CDSPDM.