J. Min, C. Jin

Pages: 35-48

Abstract
This paper describes a mathematical model of the vehicle routing problem with simultaneous delivery and pickup under capacity limitations and time constraints. The objective is to minimize the vehicle start-up cost, travel distance cost, and penalty charges subject to multiple constraints. A genetic algorithm-based approach is used to realize this objective. The multiple constraints and objectives are satisfied separately, with the “hard” constraints considered first and the “soft” constraints later. First, the fewest initial sub-routes are adopted to minimize the vehicle start-up costs, and then the vehicle capacity limitations and customer’s dual load demands are satisfied. Second, the genetic operators of selection, crossover, and mutation are modified to retain the best genetic traits in the next generation. Third, a restarting large loop is used to extract the global optimal individual and overcome the influence of premature local convergence. A case study verifies the feasibility, convergence, and effectiveness of this algorithm. The results show that the performance of the proposed genetic algorithm-based approach is better than that of conventional genetic algorithms in terms of finding an optimized solution.
Keywords: vehicle routing problem; simultaneous delivery and pickup; improved genetic algorithm; multi-constraint; multi-objective; restarting large loop