Multi-objective Optimization for Green Delivery Routing Problems with Flexible Time Windows

Abstract

This paper presents a model and heuristic solution algorithms for the Green Vehicle Routing Problem with Flexible Time Windows. A scenario of new vehicle routing is analyzed in which customers are asked to provide alternative time windows to offer flexibility to help route planners find more fuel-efficient routes (“green delivery”). Customers can rank their preferred time windows as first, second, and third. The optimization model aims to reduce tour costs, promote electromobility over fossil fuels, such as diesel, and meet customer preferences when possible and affordable. The study incorporates a multi-objective optimization model with three objectives, which are overall cost, use of fossil fuel, and customer satisfaction. For the new problem, a set of realistic benchmark problems is created and four mainstream solvers are applied for the Pareto front approximation: NSGA-II, NSGA-III, MOEA/D, and SMS-EMOA. These algorithms are compared in terms of their effectiveness in achieving the objectives of minimizing travel costs, promoting electromobility, and meeting customer preferences. The study uses five different problems of single-vehicle route planning. Two major findings are that the selection of the metaheuristic can make a big difference in terms of algorithm performance. The resulting 3-D Pareto fronts reveal the nature of this new class of problems: Interestingly, in the new model with flexible time windows, most users can still be delivered in their most preferred time windows with only small concessions to the other objectives. However, using only one time window per user can lead to an increasingly drastic cost and fossil fuel consumption.