基于众包捎带协作的协同配送优化研究

Research on Collaborative Delivery Optimization Based on Crowdsourcing and Piggyback Collaboration

基于共享经济环境下众包车辆的时空分布性,研究利用众包车辆顺路捎带开展协作的协同配送优化问题。考虑众包车辆时间、空间、能力等个体差异,提出支持众包车辆多任务捎带的协同配送模型。基于问题特征,设计融合多样性初始种群构造算法和基于变邻域搜索算法的混合分散搜索算法求解。仿真实验表明,提出协同配送模型能够有效降低配送成本,设计的改进分散搜索算法寻优性能可靠。

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.