A Multicommodity, Simultaneous Split Pickup and Split Delivery Vehicle Routing Problem with Demand Allocation

Abstract: This paper introduces a new vehicle routing problem (VRP) variant, the multicommodity, simultaneous split pickup and split delivery vehicle routing problem with demand allocation (MCSVRPSPD-DA). The MCSVRPSPD-DA is motivated by a real-life urban–rural two-way distribution application, where the assignment of rural customers to pickup and delivery sites (PDS), the amount of each commodity to be picked up and delivered, and the routing of vehicles operated from a depot to serve rural customers at their designated sites and urban customers are jointly determined. The MCSVRPSPD-DA is formulated as an integer programming model, whose objective function is to minimize the total travel cost of vehicles and rural customers. As the routing and demand allocation decisions influence each other, this NP-hard problem poses substantial computational challenges. Therefore, a hybrid metaheuristic algorithm based on Tabu search and adaptive large neighborhood search (ALNS), denoted by T-ALNS, is proposed, where a special cooperation framework is introduced. An extensive experimental analysis shows the proposed T-ALNS substantially and consistently outperforms the optimization solver, Gurobi, and two existing heuristic algorithms for the small, medium, and large instances. Moreover, sensitivity analyses on vehicle loading capacity and PDS setting provide managerial insights for decision makers