Research On Urban Crowdsourced Logistics Via Multi-Hop Delivery

The rapid development of the e-commerce industry has greatly stimulated the growth of the demand for package delivery within the city.However,it is difficult for traditional urban logistics to tradeoff the speed and cost of package delivery.As the important means of transportation,there are a large number of taxis operating in cities with an excellent coverage for urban areas.When delivering passengers,taxis usually have a large amount of carrying capacity left.If the under-used transporting capacity of taxis is fully utilized,the increasing demand of package delivery can be satisfied without increasing dedicated logistics vans.In this way,we can reduce the transportation cost without impairing package delivery speed.In recent years,researchers have proposed a series of crowdsourcing logistics delivery models based on the mobility of taxis.These researches mainly focus on matching the package delivery request with a single taxi,which may suffer the from low successful matching rate due to the incompatible in time and space patterns of passenger flow and package flow.To worse still,the package delivery routes recommended in these studies could lead a long-distance detour,increasing the driver's extra transportation costs.To this end,this thesis proposes the following two innovative and effective solutions to solve aforementioned problems in the direct delivery of packages by passenger taxis:Firstly,this thesis proposes an offline model of multi-hop delivery of packages with the goal to minimize the extra travel distance.Specifically: first,we build a crowdsourcing delivery network based on analyzing the historical trajectories of taxis.Secondly,we propose a route search algorithm called CFlow to find the appropriate transit stations for packages.Then,we establish an integer linear optimization model that aims to minimize additional driving distance and use a linear optimizer exhaustively to solves the optimal matching between taxi and package.Finally,the real data set is used for experimental evaluation.We compared the proposed algorithm with the direct delivery algorithm.And experimental results confirm that our algorithm can effectively reduce the transportation cost of package delivery.Secondly,in order to solve the problem that the offline delivery model cannot deliver packages in real-time,this thesis further proposes multi-hop delivery route model for real-time package delivery.Specifically: first,we propose an online dynamic optimization framework including order collection,generation solution and package delivery.The goal of the proposed framework is to match the package delivery request into different taxis in real time.For each package delivery request,a selection delivery strategy called Sd Plan is proposed to judges whether the package should be delivered by the current matched taxi.Finally,we use the real data sets to evaluate the performance of the system.The experimental results show that each package only need 0.357 second to find the best matched taxi that has the shortest detour distance.Comparing with the direct delivery algorithms,the proposed method can significantly improve the success rate of package delivery.