Research On Multi-depot Vehicle Scheduling Problem With Full Car Load

In recent years, with the reduction of available resources and the growing awareness of rational resources distribution, people increasingly pay attention to using third-part logistics transportation. Besides, the "Saving Society" policy supported by the government makes the cooperative work of multi-depot led by third-part logistics becoming a requirement of the times. Therefore, a great many of research interests have been shown on multi-depot vehicle routing problem (MVRP) and multi-depot vehicle scheduling problem (MVSP).Current research on real-life MVSP is still superficial. Moreover, due to the multiple constraints and complex models in current practical problem, algorithms with less running time and relative acceptable problem-solving ability are crucial in practice. With the aim of solving the difficulties, an "assignment first, optimize second" multi-phase heuristic algorithm is into the blue. According to characteristic that the problem has supply depots and demand depots, we first introduce "transportation node" constructed by one supply depot and one demand depot to simplify the problem to multi-depot vehicle routing problem with only transportation nodes. Therefore, we can get that the definite interior cost of one transportation node, and asymmetric cost matrix of transportation nodes. Secondly, we deploy different depots with Hungarian Algorithm used to assign transpotation nodes to depots according to the distances between them. Finally, assign everyday service tasks to every vehicle using modified Generalized Assignment algorithm, and optimize the result. In the process of optimization, in order to reduce total distance and vehicle numbers, Farthest Insert algorithm is used to choose seed customers and adjust the routes which total time is far from the restriction on everyday working hours. This process will increase running time in an acceptable way. To sum up, the modified Generalized Assignment algorithm is superior to original algorithm. It can also get a more feasible solution within reasonable time.At last, an industrial case from a log transportation company is given and the solution is tested on it. The result obtained shows that compared with handwork does, it can save empty loading distance by5.2%, and reduce running time from3hours to3minutes. In aspects of vehicle numbers and optimization effect, the method succeeds in finding more effective solutions to this class of problems than Tabu Search algorithm. Its running time is1/3of Tabu Search algorithm’s. Therefore, it can be used to solve the real-life multi-depot vehicle scheduling problem.