Research On Optimization Models And Algorithms For Vehicle Routing Problem With Simultaneous Pickup And Delivery

With the dwindling availability of natural resources and the increasing of people’s environmental awareness, more and more attention has been paid to recycled material by the government and enterprises. Many countries have enacted relevant environmental protection laws, and disposal companies should be mainly responsible for the product’s service and recycle. More and more enterprises are encouraged for product recycling. Logistics transportation is an important part of logistics system, and the transport route will directly affect the distribution cost and quality of service whether it is reasonable or not. In order to effectively reduce the distribution cost, improve the quality of service and decrease waste of vehicle carrying capacity by avoiding forward and reverse logistics isolated, disposal companies always consider making load and unload operations integrated to delivery and pickup simultaneously, resulting in vehicle routing problem with simultaneous pickup and delivery (VRPSPD). Although vehicle routing problem (VRP) can be seen as one special case of VRPSPD in which one kind of demands about all customer nodes is zero, for VRPSPD the load of vehicle throughout the service is no longer in law of increasing or decreasing monotonically but fluctuated erratically, therefore the optimization models and methods for VRP cannot be widely used for VRPSPD. In the practical application, VRPSPD is restricted by the time windows of vehicles and/or depots, the maximum travel distance of vehicles and the uncertain demands of customers, which makes it more difficult to be solved. In consequence, this paper devotes to the optimization models and algorithms of VRPSPD, in order to get the satisfactory solution and make decision supporting for managers of disposal companies. The research contents of the dissertation are as follows:(1) The basic VRPSPD is discussed. In this problem, there is one depot with a certain number of homogeneous vehicles under capacity constraint and maximum distance constraint. The objective is to minimize the total distribution costs which include dispatching cost of vehicles and travelling cost of routes. And then an adaptive parallel genetic algorithm is presented. Finally, the algorithm is tested on Augerat benchmark instances. The computational results are compared with the results which are obtained by other algorithms, to verify the performance of model and algorithm.(2) The vehicle routing problem with time windows and simultaneous pickup and delivery (VRPTWSPD) is presented. In this problem, there exists a time window for each customer and the depot, respectively. A mixed integer programming model is established, which considers the relative weight of vehicle dispatching cost and route cost. And a hybrid discrete particle swarm optimization algorithm is proposed for the solving problem. The computational results for the modified Solomon instances validate the effectiveness of the algorithm proposed in this paper.(3) Multi-depot vehicle routing problem with fuzzy demands and simultaneous pickup and delivery (MDVRPFDSPD) is presented. In this problem, there exists more than one depot to provide service for customers, and the delivery demand of each customer is deterministic, but the pickup demand of each customer is a fuzzy variable. During the service on the planned route, route failure will occur when customer demands exceed the capacity of vehicle. Considering that the probability of route failure is influenced by the subjective decision of managers, the driver preference index and the logistics center allocation preference index are introduced, and their computational formulas are discussed in detail based on credibility measure theory. On the basis, to minimize the total travel distance of vehicles, a fuzzy chance-constrained programming model is established, in which the pickup demand of each customer is a triangular fuzzy variable. Moreover, a combinational greedy fuzzy clustering approach is presented and tested on designed instances. The computational results not only show that the proposed method is effective, but also show that the total travel distance of vehicles is minimized when the driver preference index is 0.6.(4) The optimization system of vehicle routing with simultaneous pickup and delivery for product recycling enterprise is developed, in which the above models and algorithms are embedded. The system is used in the public good library in Hefei to get the optimal solutions of determining the optimal lease libraries and performing more excellent services of delivery and pickup for their leasehold customers than other mothods.