A genetic algorithm to solve the integrated vehicle routing and vehicle sequencing problem with a single-door depot

Abstract

Vehicle Routing Problem (VRP) is a well-known combinatorial optimization problem. In the case of single-door at the depot to enter, vehicles have to wait in the parking yard until they get their turn to unload their accumulated products. This waiting creates additional transportation cost and therefore, this idle time of each vehicle in the parking needs to be reduced. A proper mechanism to sequence the routed vehicles to the door is essential. Therefore the objective of this study is to test the compatibility of the developed model to the integrated VRP and Sequencing Vehicles (VRP&SV) to a single-door depot problem and propose a Genetic Algorithm (GA) to solve it. In the proposed GA, tournament selection, order crossover and swap mutation are chosen as the best combination of the operators for the robustness of the algorithm by employing the Taguchi method. The accuracy of GA is tested using the Branch and Bound (BB) algorithm. When the vehicles return to the depot, after serving the suppliers, the sequencing those vehicles to the door at depot is purely based on the principle of first come first serve basis. The factors of the total cost of VRP&SV are due to travelling between suppliers, preparation to load the quantities and loading them at suppliers, vehicle waiting at the parking yard, vehicle changeover to the door and unloading the accumulated quantities by vehicles. The results of small-scale instances not only confirm the feasibility of the proposed GA to solve the integrated VRP&SV but also reveals that the exact optimal solution can be reached by GA in less than 5 seconds even to the instance with 100 suppliers. Therefore, it can be concluded that the applicability of the integrated problem is confirmed. Further, it is recommended that the proposed GA can be employed at last time planning of VRP&SV models.