An improved multi-directional local search algorithm for vehicle routing problem with time windows and route balance

The Vehicle Routing Problem with Route Balance (VRPRB) aims to balance distribution costs and workloads and achieve important nonmonetary benefits with a more equitable distribution scheme. Considering time window constraints for the VRPRB will have an impact on the workload balance, which has rarely been studied before. The existence of a time window constraint can significantly affect the allocation of duration, and the analysis method under the traditional model is no longer applicable. This paper combined the time window constraint, established the Vehicle Routing Problem with Time Windows and Route Balance (VRPTWRB) model, and conducted a numerical study on the reasonable selection of workload resources and equity functions. An improved multi-directional local search (IMDLS) algorithm was proposed to solve the model and approximate the Pareto frontier. The IMDLS algorithm limits the archive size and adaptively determines the number of current solutions and the search direction. A large neighbourhood search (LNS) framework was employed as an local search to find effective solutions and update the approximate Pareto frontier in each iteration. The performance of the IMDLS was compared to the MDLS, and the effect of the choice of workload resource and the equity function on fairness were further studied. The computational results showed that the duration was more suitable for evaluating workload resources than distance when considering the time window constraints; and more complex equity functions could effectively find high-quality nondominated solutions with good equity.