关键词: 共享经济, 众包配送, 车辆协作, 分散搜索

Abstract: For the past years, the prosperity of commerce, especially the rapid development of e-commerce, has led to a surge delivery demand both in urban and rural areas. With the popularity of e-commerce and the spatial locations of customers, the delivery demands among regions are extremely unbalanced. In addition, with the characteristics of small batch, high frequency and personalized demand, logistics service providers are faced with great challenges in operation cost and customers’ satisfaction when independently carrying out delivery services. Effective integration of logistics resources to innovate and intensify delivery models is a crucial measure to improve operational efficiency and reduce operational costs.
Based on the temporal and spatial distribution of crowdsourcing vehicles in the sharing economy environment, this paper proposes a collaborative delivery optimization research based on the crowdsourcing vehicle piggyback cooperation. This problem can be defined as the traveling salesman problem with time window under crowdsourcing piggyback collaboration. The problem is described as follows: There are two types of vehicles in the system, basic vehicle and available crowdsourcing vehicles. All customers have time windows, which are traversed by both basic vehicles and crowdsourcing vehicles. Basic vehicles start from the depot, visit customers in turn, transport the requests that need to be collaborated to the designated transfer points, and return to the depot after completing the delivery task. The selected crowdsourcing vehicles start from the starting point as piggy-back vehicles, receive one or more requests to be piggy-back at the transfer points, complete the delivery in turn, and return to the destination. The innovation of this problem is in the following three aspects: (i)There are differences in the capacity of crowdsourcing vehicles; (ii)The requests need to be transferred from basic vehicle to crowdsourcing vehicles at the transfer points; (iii)Each crowdsourcing vehicle can fulfill multiple delivery requests.
In order to solve the problem effectively, a hybrid scatter search algorithm based on variable neighborhood search is designed according to the characteristics of the problem. In order to construct high quality initial solutions, a two-phase heuristic algorithm of “High quality seed solution followed by diversified population” is proposed to generate high quality initial population. For the construction of seed solution, a three-stage algorithm of “basic vehicle route-basic vehicle route optimization-cooperative delivery routes” is designed, and then several random construction operators are applied to the construction of diversified initial population based on the seed solution. In addition, to improve the efficiency of the algorithm, a progressive usage strategy of neighborhood structure based on variable probability is designed.
The comparison between the constructed TSPTW-CSC instances and the TSPTW benchmark instances shows that the crowdsourcing multi-tasking collaboration can significantly reduce the operation cost, with a maximum cost saving of 23.9%. Meanwhile, the effect of collaboration is significantly affected by piggyback compensation cost. The selection of crowdsourcing vehicles with low operating cost can help contribute better piggyback collaboration. The comparison of algorithms under different algorithm components shows that the proposed two-stage population construction strategy of “high quality seed solution followed by diversified population” and the progressive neighborhood structure usage strategy based on variable probability can improve the solving quality of the algorithm and significantly improve the convergence speed.

Key words: sharing economy, crowd-delivery, vehicle coordination, scatter search