Abstract: In order to extend market shares and provide high quality services for regional customers, numerous large manufacturers and chain retailers have built nationwide production or selling networks.For instance, for a Chinese manufacturer with several regional factories across the whole country,each factory stores a certain amount of different materials. Frequently, some factories face the shortages of specific certain materials but are abundant with other materials. Hence, the manufacturer needs to make proper allocations among these factories to their demand. This problem has already drawn great attention from the academic world and is named as the vehicle routing problem with pickup and delivery(VRPPD).Current researches on VRPPD conventionally involving several factors, e.g., depot numbers,trucks types, commodity categories, service times of customers.Relevant literature generally assumes the paired supply-demand, single truck parking depot, homogeneous vehicles, single commodity and one-time service of the pickup and delivery request with the aim of obtaining the shortest total travelling distance.However, from the perspective of practical operations, a good planned transportation scheme not only includes well-arranged visiting routes of customers, but also comprises well-connected supply-demand pairs among customers. Moreover, it is rational to jointly consider the travelling distance and the weights of the commodities when evaluating the logistics transportation costs. Besides, multi-depot, heterogeneous trucks and multi-commodity are all common practices in transportation networks and customers' demands usually larger than the capacity of a single truck, all these should be considered for modeling.Therefore, a new VRPPD is buitt to minimize the total of the transportation cost (given by the travelling distances×the weight of transportation commodities) and the fixed cost of the dispatching trucks (based on tonnage) under the conditions of multi-depot, heterogeneous trucks, multi-commodity, unpaired supply-demand and the split request of pickup and delivery. An iterated local search algorithm based on a large neighborhood search strategy is presented, in which a greedy strategy for improving transportation efficiency to quickly obtain high-quality initial feasible solutions is applied. Moreover, to enhance the global searching ability of the proposed algorithm, four removal operators, two repair operators, depots &type-based truck adjustment strategies are introduced, which helps expand the large-scale feasible search neighborhood to the utmost. The effectiveness of the above model and algorithm is verified by 18 instances in related literature and 6 actual cases in an enterprise. The experimental results demonstrate that:1) The proposed algorithm is superior to the existing algorithm in terms of solution quality and solution time, when solving the closely related problem in the literature. 2) Comparing to the manual allocation scheme, the allocation scheme proposed in this paper can help enterprises to save 33% of transportation costs and 21% of vehicle number. The research not only extends the existing theory of VRPPD, but also provides decision support for enterprises at the practical interactive allocation operations.

Key words: vehicle routing, split pickup and delivery, unpaired supply-demand, multi-Depot, multi-typetrucks