A bi-objective vehicle routing problem with time windows: A real case in Tenerife

•This work considers a bi-objective VRPTW to minimize both total distance and time-balance of the routes.•We propose a mathematical formulation alternative to the classical models that do not consider time balancing.•We develop two alternative versions of the population-based algorithm based on scatter search.•An extensive computational experience has been carried out with several purposes.•The solution corresponding to a real instance provided by a company in Tenerife, Spain, is compared to the solutions obtained by the two proposed algorithms.

This work is motivated by a real problem posed to the authors by a company in Tenerife, Spain. Given a fleet of vehicles, daily routes have to be designed in order to minimize the total traveled distance while balancing the workload of drivers. This balance has been defined in relation to the length of the routes, regarding to the required time. A bi-objective mixed-integer linear model for the problem is proposed and a solution approach, based on the scatter search metaheuristic, is developed. An extensive computational experience is carried out, using benchmark instances with 25, 50 and 100 customers, to test several components of the proposed method. Comparisons with the exact Pareto fronts for instances up to 25 customers show that the proposed methods obtain good approximations. For comparison purposes, an NSGA-II algorithm has also been implemented. Results obtained on a real case instance are also discussed. In this case, the solution provided by the method proposed in this paper improves the solution implemented by the company.

Graphical abstractFigure optionsDownload full-size imageDownload as PowerPoint slide