A scatter search algorithm for solving vehicle routing problem with loading cost

摘要

The vehicle routing problem (VRP) is an important scientific problem addressed in distribution management. In classical VRP and its variants, the vehicle load is often regarded as a constant during transportation; therefore the loading cost associated with the amount of the load on the vehicle, are neglected in the objective function when optimizing a vehicle routine. However, in real-world, the vehicle load varies from one customer to another in a vehicle route. Thus, the vehicle route without considering the effect of loading cost may lead to sub-optimal routes. In this paper, we investigate VRP with loading cost (VRPLC), which considers the costs associated with the amount of the load on the vehicle when determining the vehicle routes. Considering the features of the VRPLC, a scatter search (SS) is proposed. By introducing customer-oriented three-dimensional encoding method, sweep algorithm and optimal splitting procedure are combined to obtain better trial solutions. The arc combination and improved nearest neighbor heuristic are adopted as a solution combination method and an improvement method to generate and improve new solutions, respectively. Computational experiments were carried out on benchmark problems of capacitated VRP with seven categories of distribution scenarios. The computational results show that the SS is competitive and superior to other algorithms on most instances, and that the VRPLC can more reasonably and exactly formulate the vehicle routing problem with more cost savings than general VRP models.