Multi-depot vehicle routing problem considering customer satisfaction

Multi-depot vehicle routing problem (MDVRP) is an important branch of vehicle routing problem (VRP). This paper investigates the multi-depot vehicle routing problem considering customer satisfaction (MDVRPCS). The problem is to program the vehicle path of multi-depot with limited resources to maximize the satisfaction of total customers. The prospect theory is used to describe the satisfaction of customer, and limited resource is considered as constraint. Furthermore, a mixed-integer mathematical model with nonlinear objective function is established. Due to the objective function is nonlinear, the improved variable neighborhood algorithm (IVNS) is used to solve this problem. The algorithm uses the improved K-means algorithm to generate the initial solution and an adaptive mechanism is added in the solution process. Finally, the computational results show that the improved variable neighborhood algorithm (IVNS) outperforms the variable neighborhood algorithm (VNS) in solving quality and time, and joint multi-depot service can result in cost savings and higher service satisfaction.