Routing the vehicles for minimizing traveling distance under green and multi-depot context

Thumbnail Image
Zhang, Weiheng
Journal Title
Journal ISSN
Volume Title
In this thesis, an Ant Colony System with Variable Neighborhood Search algorithm (ACSVNS) is proposed to solve Multi-depot Vehicle Routing Problem (MDVRP). A new variant of vehicle routing problem, Multi-depot Green Vehicle Routing Problem (MDGVRP), is also formulated. In ACSVNS, two types of ants are used for two different purposes. The first type of ant is used to assign customers to depots while the second type of ant is used to find the routes. ACSVNS applies perturbation scheme, relocate local search and revised swap local search to improve the solution quality. Based on the experiment results of the 23 benchmark instances of MDVRP, ACSVNS can match the existing best known solution for 16 instances, which is the third best in all algorithms. Additionally, ACSVNS found new best solutions for the instance 5, 6 and 7. These results prove that ACSVNS has a good performance on solving MDVRP. Besides, in this thesis, a Multi-depot Green Vehicle Routing Problem (MDGVRP) is also formulated. Based on ACSVNS, a Two-stage Ant Colony System (TSACS) algorithm is proposed to find solutions for this problem. The solution for MDGVRP is useful for companies which employ the Alternative Fuel-Powered Vehicles (AFVs) to deal with the obstacles brought by the limited number of the Alternative Fuel Stations (AFSs). This thesis adds vehicles capacity and tank capacity constraints to make it more meaningful and closer to real-world case. The numerical experiment is performed on randomly generated problem instances to evaluate the performance of proposed algorithms.
Supply Chain Management
Zhang, S. , Zhang, W., Gajpal, Y., Appadoo, S. S. (2018). Ant Colony Algorithm for Routing Alternate Fuel Vehicles in Multi-depot Vehicle Routing Problem. Decision Science in Action, 251-260