A Heuristic Algorithm for Crowdshipping Problem with Time Windows

Abstract

The boom of e-commerce has promoted a great demand for delivery Meanwhile with the rise of environmental awareness many logistics companies start to ponder how to reduce carbon emission A new logistics way is “crowdshipping” that package delivery is outsourced to the crowd or occasional drivers They deliver parcels through a detour from their original route or on their way This problem is called Vehicle Routing Problem with Occasional Drivers (VRPOD) This thesis applies crowdshipping to delivery of item-sharing platform It assigns the supplied items to compatible requesters and decides a best delivery pattern for each shared item among three alternatives including self-sourcing home delivery and neighborhood delivery to maximize the platform’s profit We proposed a mixed integer programming model and another “best transportation combinations” model and made a comparison The results show that the latter has better efficiency and can solve larger-scale problems As for still larger instances we adopted three heuristic methods based on the second model to reduce the number of transportation combinations and solution time The results indicate that heuristic methods can acquire a solution within a reasonable time Besides combining three methods can retain their respective advantages and they complement one another well Finally we applied rolling horizon to this problem but it’s not suitable for this problem owing to its poorest solution quality

Date of Award	2020
Original language	English
Supervisor	Shiow-Yun Chang (Supervisor)