Stable Matching for Crowdsourcing Last-Mile Delivery

This study investigates a crowdsourcing last-mile delivery problem considering orders with different destinations and time windows and crowdsourced drivers with preplanned trips. In this problem, customers announce requests on a crowdsourced delivery platform to deliver orders from a depot to their destinations and crowdsourced drivers are willing to make a detour to deliver orders in exchange for rewards provided by the platform. The crowdsourced drivers have preference lists over groups of orders based on their profits and meanwhile each order has a preference list over crowdsourced drivers based on the drivers' arrival times at the depot. According to their preference lists, to maximize profits, crowdsourced drivers need to consider routing and scheduling decisions for delivering orders. This crowdsourced driver-order matching problem is considered to be a non-cooperative game between crowdsourced drivers. A Nash equilibrium for such a non-cooperative game is a stable matching between crowdsourced drivers and orders. We propose two exact algorithms to find stable matchings and develop a heuristic algorithm to find feasible matchings for large scale problem. The results from computational experiments demonstrate that the proposed approaches are highly efficient and effective, and the matching rate of stable matching is larger than that of feasible matching. Finally, we investigate two extensions to demonstrate the applicability of our methods and also extend to a stochastic setting with random release times of orders.