Multi Routes Programming TSP Model Based on Shortest Path Method for Express Delivery
Download as PDF
With the rapid development of C2C economy, logistics distribution service has become an important industry of national economy, which greatly promotes the circulation of goods. However, the rapid development of express delivery business has brought great challenge to the express delivery service. At the same time, with the upgrading of distribution services, in order to meet the specific requirements of customers, some mails need to be distributed within the specified time. How to reasonably arrange the delivery order of mails and minimize the delivery time is a very meaningful task for optimizing the delivery service. Different from the traditional route programming problem, express delivery needs multi trips to and from the Express Center due to the limited loading capacity of the couriers' vehicles. In this paper, a novel route programming model is designed based on the shortest path algorithm. It allows couriers to pass each delivery location multiple times. Firstly, the shortest path and path between any two locations are calculated by the shortest path algorithm. Then, the delivery locations are divided into multiple classes and delivered in different trips. In each trip, the optimization model of the total delivery distance is established on both the class and order of the locations to realize the multi routes programming for express delivery. In addition, we design a solution method based on genetic algorithm for the multi routes programming. The coding of this method includes two parts. One part is the order of delivery locations, and the other part encodes the trips of delivery locations. Finally, the model is verified by actual delivery tasks, and the experimental results fully verify the effectiveness of the proposed method.
Express delivery, Tsp, Route programming, Shortest path, Genetic algorithm