Developing Genetic Algorithm to Solve Vehicle Routing Problem with Simultaneous Pickup and Delivery

One of the well-known and highly used extensions of vehicle routing problem (VRP) is Vehicle Routing Problem with Simultaneous Pickup and Delivery (VRPSPD), in which delivery and pickup for each customer is carried out simultaneously. In this study, it is attempted to present an optimal method for solving VRPSPD using genetic algorithm. In this method, genetic algorithm is improved by modifying genetic parameters and presenting efficient and proper operators. Three Randomized, Nearest neighbor and Cheapest Insertion algorithms are utilized to create the initial population. Given the different structure used in each of these methods, the initial solutions are varied and include all feasible regions. In addition, by making modifications in these methods, the initial population was tried to be created through higher quality solutions to help genetic algorithm reach a better future generation. Also, 4 algorithms were invented for mutation operators, which prevented convergence in local optimums and helped finding better solutions by comparing the results. The proposed algorithm is executed on 40 different standard examples. After comparing the results by this algorithm and the best solutions by other algorithms, improvement is observed in 3 of the examples.

Keywords:

NP-hard problems , vehicle routing problem , Genetic Algorithm