Allocation Games Model And Variable Neighborhood Search For Crowd-Shipping Problem With Time Windows, Transshipment Nodes, And Delivery Options

Abstract

The study focuses on the Crowdshipping Problem with Time Windows, Transshipment Nodes, and Delivery Options (CSPTW-TN-DO), addressing the complexities of last-mile delivery in the context of e-commerce growth. The research problem is to enhance traditional vehicle routing problems (VRP) by utilizing various transportation models such as occasional and dedicated vehicles, and the incorporation of transshipment nodes (TNs) and alternative delivery points (ADPs) to reduce costs and improve delivery times. A Mixed Integer Nonlinear Programming (MINLP) model is formulated for small-scale problems, while a combination of Game Theory and Variable Neighborhood Search (VNS) is employed for larger-scale scenarios. To be more specific, the methodology involves grouping customers based on geographic location using K-means Clustering, optimizing decision-making processes with Game Theory, and route optimization with VNS heuristics. The Game Theory model operates on two levels: assigning customers to either dedicated or occasional drivers and allocating customers to particular occasional drivers. Results show that this proposed methodology significantly lowers distribution costs, outperforming an existing method, Adaptive Large Neighborhood Search (ALNS). After analyzing several scenarios, the finding suggests that considering occasional drivers, transshipment nodes, and delivery options offers a great opportunity for a last-mile delivery system to reduce the total distribution cost by the proposed heuristic. Furthermore, the study also highlights the potential implications including substantial benefits for urban logistics, enhancing both efficiency and environmental sustainability.