The Capacitated Pickup And Delivery Problem With Max Duration

The existing researches on vehicle routing problem with backhauls usually assumes that the demands of customers are independent of each other, and the vehicles need to deliver goods to customers and return to the depot with goods from customers. In Vehicle Routing Problems with Pickups and Deliveries, the customer may just have either pickup demand or delivery demand although their demands have the pair constraint. However, in the industrial park of large manufacture enterprises, the delivery of raw material and semi-finished products among different storage locations always has paired pickup node and delivery node. In addition, each storage location may not only receive goods from other storage location but also deliver goods to others, which means each location may both have pickup demand and delivery demand. Aiming at the problem, the capacitated pickup and delivery problem with max duration (CPDPMD) is raised in this paper, in which each customer can both have pickup and delivery demand, while pickup node and delivery node are in pair in each demand. The objective is to find a set of routes with minimized cost under the capacity and max duration constraints. The problem can be applied to the distribution of raw material, semi-finished products and other goods in the industrial park of large manufacture enterprises.A mathematical model with the objective of minimizing the total trip distance is established in this paper. Meanwhile, an improved scatter search is proposed to solve CPDPMD. Six aspects of scatter search are introduced in detail, which are coding method, diversification generation method, reference set generation and update method, improvement method, subset generation method and solution combination method. Firstly, a greedy insertion is applied to generate a set of diverse trial solutions. Afterwards, the improvement method based on local search algorithm is used to enhance a solution and to generate the initial reference in which solutions are selected for the quality and diversity. Subset can be created by using subset generation method, consisting of 2-element subsets,3-element subsets,4-element subsets and the subsets including the best r (for r=5 to b) elements. With the solution combination method basing on arc combination and sweep algorithm, new solutions will be generated to update the reference set until the iteration is terminated.To assess the effectiveness of the scatter search proposed in this paper, the benchmarks for CPDMD are constructed by modified the data set for the Vehicle Routing Problems with Pickups and Deliveries (VRPPD). After testing related parameters in the algorithm, the effectiveness of improvement method is evaluated by the proposed data. After that, the scatter search is applied to solve the Traveling Salesman Problem with Pickup and Delivery (TSPPD), which is a special case of CPDPMD. Computational results are compared with the results obtained by the exact method. And the results show the effectiveness of the proposed scatter search.Besides, the mathematical model of CPDPMD is applied to the delivery of raw material and semi-finished products in A company. With the process of encoding, partition of demands, calculation of loading and unloading time and distance, confirmation of distribution time among the storage location, the delivery task in A company can be regarded as CPDPMD. Afterward, the proposed scatter search is used to solve the standardized problem. The distribution routes are obtained, which shows the effectiveness and practicability of the CPDPMD model.