Models And Algorithms For Vehicle Routing Problem Of Distribution Companies

With the development of market economy, the impact of the distribution on the economy is more and more obvious. Vehicle routing problem (VRP) is an important part of optimizing distribution activities, which minimizes the distribution cost and improves the customer satisfaction. This paper reviewed the state-of-the-art of VRP problem, studies three VRP variant problem which are most common and urgent to address for distribution companies in reality, and proposed meta-heuristics to solve the problem. The main contributions are as follows:1. Consider simultaneous pickup and delivery, and study the vehicle routing problem with simultaneous pickup and delivery (VRPSPD)Customers, in reality, request the pickup and delivery service, which prompt many companies incorporate reverse logistics into their distribution channels. This is a VRPSPD problem. This paper proposed a simulated annealing algorithm based on tabu list (Hybrid SA, HSA). HSA algorithm learns the idea of Tabu Search (TS), and use tabu list in the annealing process, which avoid the recently visited solution in a certain extent and accelerate the search process. First, the RCRS heuristic was used to generate an initial solution, and four kinds of local search moves within the structure of SA were then executed to optimize the initial solution.The approach was tested using the Dethloff data set (40small-scale instances), the Salhi and Nagy data set (14medium-scale instances) and Montane and Galvao data set (18large-scale instances). Therefore, the approach was tested using72benchmark instances with50to400customers. The comparison with state-of-the-art metaheuristics shows that the proposed HSA is competitive with other well-known methods in terms of quality of solution, although computation time was slower than other algorithms, it was acceptable. Caution is urged since the reported CPU times are for different computer configurations.2. Consider simultaneous pickup-delivery and time windows, and study the vehicle routing problem with simultaneous pickup-delivery and time windows (VRPSPDTW)Besides simultaneous pickup and delivery, customers in reality request specific service time. In order to increase the service quality, the logistics companies often provide services to meet such requests, which is a VRPSPDTW problem. This paper has proposed a parallel-SA(p-SA) meta-heuristic to solve this problem. The p-S A algorithm used the Multiple Markov chains (MMC) strategy, integrated asynchronous and synchronous MMC approach, paralleled the sequential SAin a master-slave paradigm.In order to demonstrate the effectiveness of the p-SA algorithm, an experimental study has been carried out using65test problems from Wang and Chen’s benchmark and compared to a GA meta-heuristic. The experimental results show the effectiveness of the proposed algorithm for solving the VRPSPDTW problem. A set of30new instances with200,400,600,800and1000customers were generated and utilized as a new data set for the large-scale VRPSPDTW. The results of p-SA algorithm provided a benchmark for researchers to test their algorithms in the large-scale instances.3. Consider distribution center optimization, and study the two-echelon location-routing problem with simultaneous pickup-delivery and time windows (2E-LRPSPDTW)With the growing of city’s traffic congestion, the majority of cities has adopted a a series of restrictive measures for large vans into the city. Therefore, the distribution companies could not transport goods from the central distribution center to the customers by vans, and need to establish a transit point between the facility and the demand point. The small trucks would be used to ship goods from the central distribution center to the regional distribution centers and the electric tricycles would be used to ship goods from the regional distribution centers to customers, which the two distribution systems including the "central distribution center","regional distribution center" and "customers". This paper built the2E-LRPSPDTW problem and proposed a p-SA-PR algorithm to solve this problem. The traditional approach separates LRP problem into location allocation problem (LAP) and vehicle routing problem, and solve these two problems individually, which does not consider the impact and constraints of the LAP and VRP. The p-SA-PR algorithm studied the LPR problem as a whole, redesign and improves the solution by analysis of the structure of the LRP solutions.The approach was tested using the Nguyen data set (24instances), Prodhon data set (30instances), and Sterle data set (30instances). Therefore, the experimental results are reported for84benchmark instances with8to200customers. The comparison with state-of-the-art metaheuristics shows that the proposed the p-SA-PR algorithm is an effective method, which could solve the2E-LRPSPDTW problem in a short time.4. Investigate the CSYB distribution enterprise, and optimize CSYB’s vehicle distribution routes.The CSYB enterprise has a central distribution center and55regional distribution centers, which is responsible for delivery goods to1622communities within the5th ring twice daily. The proposed algorithms were used to optimize the CSYB’s current distribution routes. The results show that the proposed approach could reduce the number of vehicles and total travel distance.