A multi-depot vehicle routing problem with weight-related costs

In this paper, a multi-depot vehicle routing problem with weight-related cost (MDVRPWRC) is discussed. It is an extension of the classical multi-depot vehicle routing problem (MDVRP) by treating the vehicle load, i.e. the total weight of freight in a vehicle, as a variable in the objective of model. The corresponding costs incurred by the vehicle load are considered in the objective function when determining vehicle routes in order to minimize the total costs. A scatter search framework is proposed to solve the MDVRPWRC. The heuristic method of arc selection and combination is used to generate new solutions. Several local search methods are integrated to construct an iterative descending algorithm for improving the solutions. Computational experiments were carried out on typical MDVRP benchmark problems. The results show that MDVRPWRC can formulate the vehicle routing problem more explicitly and reduce the total costs compared with the general MDVRP model.