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.

Introduction

The net-zero emission goal by 2050 in the Paris Agreement requires governments, companies, and individuals to take actions to reduce the environmental impact of human activities. To achieve this goal, global final energy consumption has to be reduced by 40%. However, according to the European Environment Agency, freight transport demand is expected to triple by 2050 compared to the current demand. Currently, logistics contributes to 24% of greenhouse gas emissions, with ground transport accounts for 72% Grubler et al. (2018). Therefore, there is an urgent need to reduce gas emissions in transportation (Cao et al. 2021). In this paper, we will focus on green logistics optimization problems, aiming to reducing emissions while enhancing delivery efficiency and customer satisfactions in last-mile delivery. Additionally, we will analyze the trade-offs between these three different goals.

According to the International Energy Agency (IEA), global electric vehicle (EV) sales witnessed a remarkable doubling to 6.6 million units in 2021, as reported in a study on the expansion of electric vehicles in Europe 2021 (Razmjoo et al. 2022). Electric vehicles and hybrid vehicles (featuring both an electric and a diesel engine) will be used more extensively in the near future. Therefore, we will focus on using hybrid vehicles in this research.

Time windows have a direct impact on customer satisfaction of delivery services. They play a crucial role in determining the convenience and reliability of the delivery process. This is especially the case for delivery services that require customers to be present at home, such as delivery of large furniture and groceries. In general, a narrow time window is more preferable than a wide one. Delivery after the predefined time window tends to reduce customer satisfaction. Delivery companies have been striving to accommodate customers within feasible time windows, aiming to optimize customer satisfaction and enhance last-mile delivery efficiency. Various of delivery time schemes have been employed by delivery companies. For example, Albert Heijn (https://www.ah.nl/) and Sainsbury’s (https://www.sainsburys.co.uk/) offer time windows with varying widths, allowing customers who select wider time windows to pay lower delivery fees. Picnic (https://picnic.app/nl/) clusters customers into different regions, offering fixed time windows for those in each respective region. Amazon charges an extra fee for faster delivery. In this paper, we investigate an innovative delivery time window scheme where customers are asked to choose multiple time windows according their order of preferences. The delivery will be chosen from among those preferred by the customers. By simply requesting customers to select multiple time windows, this approach provides greater flexibility to delivery companies, potentially contributing to a more efficient delivery service.

This paper contributes by proposing an innovative scheme involving multiple time windows and modeling this scheme in a multi-objective route planning problem with hybrid vehicles. There are three main goals of this paper: First, we want to motivate our flexible time windows model and discuss the simplifying assumptions, but also its benefits. Second, we would like to understand which solvers can reliably compute a good Pareto front approximation for these problems. Finally, we would like to gain first insights into the trade-offs and provide an interpretation of the obtained Pareto fronts. Computational results demonstrate the feasibility and advantages of implementing this multiple time window scheme. The next section will present an extensive literature review, followed by a problem description that demonstrates the background of our model in the subsequent section. The setup of computational experiments will be introduced in Section 5, followed by the presentation of our main results. Conclusions will be summarized based on our computational findings, and future research directions will be proposed in the final section.

Literature Review

Vehicle routing problems (VRPs) have been extensively studied by researchers. An overview of earlier research up to 1992 on classic VRP models, including exact algorithms and heuristic algorithms, is provided in (Laporte 1992). In recent years, due to the limitations of exact algorithms for solving large-scale problems, researchers have developed numerous heuristic algorithms. The article (Konstantakopoulos, Gayialis, and Kechagias 2020) provides a comprehensive review of various of VRP models and algorithms for solving VRP variants from 2010 to 2020. In this paper, we concentrate on addressing multiple objectives in the context of hybrid vehicle routing problems with multiple time windows. Our goal is to achieve eco-friendly, cost-efficient, and customer-satisfactory last-mile logistics. In this section, we will present an extensive review of relevant literature in the related domain, covering topics such as green VRPs, VRP with electric vehicles and hybrid vehicles, routing problems with time windows, multi-objective routing problems, and algorithms for solving VRP variants. Research gaps will be summarized based on this comprehensive literature review.

VRP

The Vehicle Routing Problem (VRP) is a classic logistics problem aiming to minimize the total distance traveled by vehicles. Vehicle routing problems with one vehicle are also called Traveling Salesman Problems. When multiple vehicles are involved, optimization algorithms are used to generate route plans for a fleet to serve customers, taking into account various constraints such as vehicle capacity and customer demand. The problem can be formulated as a mathematical optimization problem and solved using various algorithms, such as metaheuristics or exact methods. VRP has a wide variety of applications in many real-world logistics and transportation scenarios, such as delivery routes and waste collection (Braekers, Ramaekers, and Van Nieuwenhuyse 2016; Wu et al. 2023).

Solving the VRP contributes to significant cost savings and efficiency improvements in many real-life scenarios. In practice, various VRP variations exist. One such variation is the Vehicle Routing Problem with Time Window (VRPTW), which is derived from a variation of the classic VRP. In VRPTW, each customer has a designated time window for service. VRPTW considers both the time constraints of customers and the route and vehicle capacity restrictions. In VRPTW, the aim is to minimize the total distance traveled by vehicles and to serve all customers within certain time windows. Here, in addition to the classic VRP, a specific delivery interval (time window) is defined for each customer. For this, it is necessary to find the most suitable route and timing for the vehicle fleet. This problem becomes more difficult to solve than the standard VRP due to the added time constraints (Brian et al. 2005; Desrochers, Desrosiers, and Solomon 1992; Van et al. 2024).

Green VRP

The Green Vehicle Routing Problem (GVRP) is another variation of the classic VRP that takes environmental considerations into account. The GVRP has attracted attention in recent years due to the increasing awareness of the impact of transportation on the environment. Solving the GVRP holds the potential for substantial environmental benefits, such as reducing greenhouse gas emissions and improving air quality while maintaining service quality and efficiency. The aim of GVRP is to minimize the total fuel consumption and emissions of the vehicle fleet while meeting the route and vehicle capacity constraints. Various approaches can be used to solve GVRP, such as using alternative fuels, electric, or hybrid vehicles, and optimizing vehicle speeds and routes to minimize emissions (Chen et al. 2023; Lin et al. 2014; Zheng, Gao, and Tong 2023).

Providing multiple time windows for customers is an effective way to improve service quality, increase customer satisfaction, and reduce overall transportation costs. It can also help improve the efficiency of the transport system and reduce the environmental impact of transport by reducing the number of unnecessary trips. For example, in some cases, when customers in nearby locations choose different times for delivery, vehicles have to come back to the same place. This is negative in terms of both economic cost, time, and environmental impact (Agatz, Fan, and Stam 2021; Wu and Wu 2022).

Routing Problems of Hybrid Vehicles and Electric Vehicles

In vehicle routing problems (VRPs) involving electric vehicles or hybrid vehicles, it is necessary to consider charging stations and battery exchange stations, which do not typically considered in classical VRPs (Huang et al. 2016; Schneider, Stenger, and Goeke 2014). VRP models with hybrid vehicles are studied in existing research aiming to minimize the overall cost or travel distance. For example, a VRP model with hybrid vehicles is proposed in (Vincent et al. 2017) aiming to minimize total travel cost, while dummy refueling and charging stations are considered in this model. In the VRP model proposed in (Seyfi et al. 2022), vehicles have four optional travel modes: pure combustion, pure electric, charging while driving, and boost modes. Charging stations are not considered in the model, assuming charging while driving. For solving an electric VRP with recharging stations and time windows, Schneider, Stenger, and Goeke (2014) propose a hybrid heuristic which is a combination of a neighborhood search algorithm and a tabu search heuristic. Similarly, the locations of recharging and refilling stations are considered in (Masmoudi, Coelho, and Demir 2022) for the waste collection problem aiming to minimize the total routing costs, while all charging stations are assumed to be homogeneous. In (Hiermann et al. 2019), a VRP model considering a mixture of conventional, electric, and hybrid vehicles is proposed. Hybrid vehicles can switch between fossil fuel and electric engine.

Lian, Lucas, and Sörensen (2023) address the Electric On-Demand Bus Routing Problem (EODBRP), an extension of Electric Vehicle Routing Problems (EVRPs) to on-demand bus transportation. It involves assigning buses to stations, considering passengers with multiple boarding or alighting stations to minimize total user ride time (URT). The EODBRP integrates realistic features like time windows, a nonlinear charging function, and a partial charging policy. The proposed solution includes a “charging first, routing second” greedy insertion method and a Large Neighborhood Search (LNS) with local search (LS) operators. The algorithm, tested with realistic city map data, proves effective in solving the EODBRP.

Hou et al. (2023) introduce a novel approach to tackle the Service-oriented Cooperative Vehicle Routing Problem (SoC-VRP) within Cooperative Intelligent Transportation Systems (C-ITS). Addressing varying urgency levels and traveling constraints, a Deep Reinforcement Learning (DRL)-based prioritized route planning mechanism is proposed. The model, utilizing Rainbow DQN, categorizes vehicles into High, Medium, and Low urgency degrees, prioritizing routes accordingly. Experimental results demonstrate the effectiveness of this hybrid prioritized route planning mechanism in the SoC-ITS framework.

Moradi, Sadati, and Çatay (2023) explore the application of Autonomous Delivery Vehicles (ADVs) in last-mile delivery, focusing on the Autonomous Delivery Vehicle Routing Problem (ADVRP). The goal is to minimize route and vehicle usage costs while considering constraints such as load and battery capacities, maximum route duration for ADVs, and maximum customer walking distance. A mixed-integer linear programming formulation for ADVRP is presented, and a two-phase metaheuristic approach is proposed to address its NP-hardness. The methodology clusters customers and determines stopping locations in the first phase, followed by optimal route determination using hybrid variable neighborhood search and simulated annealing. Computational experiments demonstrate the efficiency of this approach, providing high-quality solutions for ADVRP instances and outperforming an exact solver in related Vehicle Routing Problems (VRPs). Sensitivity analyses and a case study in Istanbul, Turkey offer managerial insights for the implementation of ADVs in urban logistics.

Frey et al. (2023) introduce a variant of the vehicle routing problem: the VRP with time windows and flexible delivery locations (VRPTW-FL). Unlike traditional VRPs, VRPTW-FL allows each customer to be served at one of several potential locations, each with its own capacity. This variant has practical applications in parcel delivery, routing with limited parking space, and hospital-wide scheduling of physical therapists. The paper presents a mathematical model and a hybrid adaptive large neighborhood search to address the challenge of limited location capacities. The heuristic uses an innovative backtracking approach during construction and employs novel neighborhoods and dynamic updates of objective violation weights in the meta-heuristic phase. Computational analysis using hospital data demonstrates the utility of flexible delivery locations and various cost functions, with considerable improvements in solution quality through the proposed algorithmic features.

Amiri, Zolfagharinia, and Amiri, Zolfagharinia, and Hassanzadeh Amin (2023) tackle the challenges of integrating Battery Electric Vehicles (BEVs) in the Vehicle Routing Problem (VRP), focusing on Heavy-duty Electric Trucks with limited range and extended recharging times. A robust mathematical model for the Electric Vehicle Routing Problem (EVRP) is proposed, considering uncertainties in energy consumption for short-haul deliveries. The EVRP is formulated as a bi-objective problem, minimizing transportation costs and maximizing customer satisfaction through on-time deliveries. Two metaheuristic algorithms, Nondominated Sorting Genetic Algorithm II (NSGA-II) and Adaptive Large Neighborhood Search (ALNS), are developed. Results highlight the superior performance of ALNS combined with the weighted-sum method. Additionally, a simulation study analyzes robust solutions under varying uncertainty levels, offering valuable managerial insights for decision-makers.

Tan, Chai, and Li (2023) address the Vehicle Routing Problem with Time Windows (VRPTW) under uncertainty, crucial in the logistics industry amid the rise of e-commerce. The introduced Robust Multi-Objective VRPTW (RMOVRPTW) model aims to simultaneously optimize total distance and the number of required vehicles for transport. The proposed Robust Optimization Algorithm, R-MOEAD-VRP, is based on MOEA/D. The encoding prioritizes customers’ service, and Order Crossover and Exchange mutation operators enhance population diversity. Monte-Carlo tests verify the feasibility of routes considering uncertainty. Feasible routes are assessed for robustness values, and a set of highly robust and relatively optimal solutions is generated. Simulation experiments on Solomon’s benchmark problems compared with related algorithms demonstrate the proposed algorithm’s effectiveness in providing robust and non-dominated solutions under uncertainty, achieving commendable performance.

Routing Problems with Time-Windows

Delivering within time windows of customer choice is crucial for improving the level of customer service. This is especially true for attended home delivery, where customers need to be at home to receive packages, such as groceries and furniture (Emmerich, Gülmez, and Fan 2023). Researchers have studied the Vehicle Routing Problem with Time Windows (VRPTW) in recent years, and a systematic review of algorithms for solving VRPTW is provided in (Bräysy and Gendreau 2005). From the perspective of demand management, incentivizing customers to choose certain time windows potentially reducing travel costs and emissions in last-mile delivery (Agatz, Fan, and Stam 2021; Campbell and Savelsbergh 2006). Beyond choosing certain time windows, customers choosing wider time windows allows each vehicle to visit more customers which would increase the efficiency of last-mile delivery (Ombuki, Ross, and Hanshar 2006). Many existing studies on VRPTW only consider a single time window for each customer. Alternatively, in some research, customers are asked to choose one from a list of time windows (Waßmuth et al. 2023). Another strategy is to allow customers to select multiple preferred time windows, deliveries will arrive during one of the chosen time windows. This offers greater flexibility but also increases computing complexity (Hoogeboom et al. 2020).

A multiple time window gases distribution problem is described in (Bell et al. 1983). Strategies for transforming single time window problems into multiple time window problems by adding constraints are studied in (Pesant et al. 1999). In (Favaretto, Moretti, and Pellegrini 2007), a VRP model with multiple time windows (VRPMTW) is developed and an Ant Colony-based algorithm is proposed and implemented for solving the model. VRP problems with multiple time windows are also studied in (Belhaiza et al. 2019; Li et al. 2020; Wu and Wu 2022). Belhaiza et al. (2019) studied a single-objective VRPMTW aiming to minimizing the sum of travel time, waiting time, and service time. An evolutionary heuristics combining a genetic algorithm and a tabu search was developed to solve the model. Li et al. (2020) developed the branch-and-price-and-cut algorithm for solving VRPMTW. They designed time intervals as constraints instead of the objective function. A large neighborhood search algorithm is developed for solving VRPMTW in (Schaap et al. 2022).

Praxedes et al. (2024) propose a unified Branch-Cut-and-Price (BCP) algorithm to address 10 variants of the Vehicle Routing Problem with Simultaneous Pickup and Delivery (VRPSPD). The problem involves determining cost-efficient routes while meeting pickup and delivery demands without violating vehicle capacity constraints. The unified approach considers additional attributes such as a heterogeneous fleet, time windows, route duration, multiple depots, and location decisions. The generalized problem is formulated as a Heterogeneous Location Routing Problem with Simultaneous Pickup and Delivery and Time Windows (HLRPSPDTW). Computational experiments on 550 benchmark instances showcase the algorithm’s effectiveness, yielding new optimal solutions and improved lower bounds for all addressed variants.

Muñoz-Villamizar, Velazquez-Martínez, and Caballero-Caballero (2024) introduces a novel approach to address the challenges of last-mile delivery in the rapidly growing e-commerce industry. Focusing on home deliveries, the proposed consolidation-based model optimizes vehicle utilization while accommodating extended delivery windows and future demand expectations. The approach utilizes a Mixed Integer Linear Programming model and a custom metaheuristic, demonstrating significant improvements in vehicle utilization, distance traveled, time, and overall transportation costs. Applied to one of Mexico’s largest retailers, the approach outperforms existing transportation systems, achieving cost savings. The increased vehicle utilization enhances operational efficiency, presenting a practical and highly effective solution for large-scale last-mile delivery scenarios.

Dubey and Tanksale (2023) address the challenge faced by food banks employing a front-end model, focusing on the collection and redistribution of surplus food using a fleet of vehicles from various volunteer depots within specified time windows. The problem is formulated as a Multi-Depot Vehicle Routing Problem with Time Windows, Split Pickup, and Split Delivery (MDVRP-TW-SP-SD), a rich variant of the classic VRP. The objective is to minimize the total cost of hiring vehicles, routing, and penalties for unmet demand. This is the first attempt to formulate MDVRP-TW-SP-SD as a mixed-integer programming problem. To solve it efficiently, the study proposes both an elitist Genetic Algorithm (GA) and a GA hybridized with local search. Computational experiments on 180 benchmark instances demonstrate the superiority of the GA hybridized with 3-opt local search. The study concludes with a real-world case of the Robin Hood Army operating in Lucknow, India, showcasing the practical applicability of the proposed model.

Zahedi, Kia, and Khalilzadeh (2023) address VRP with a focus on developing a green logistic system for environmental sustainability. It introduces a bi-objective mathematical model for the Capacitated Electric VRP with Time Windows and Partial Recharge. The first objective minimizes vehicle routing costs, emphasizing reduced route lengths, while the second minimizes the delay of arrival vehicles to depots based on soft time windows. The proposed solution employs a hybrid metaheuristic algorithm, NSGA-II-TLBO, which combines non-dominated sorting genetic algorithm (NSGA-II) and teaching-learning-based optimization (TLBO). The algorithm’s performance is evaluated and compared to NSGA-II and multi-objective simulated annealing (MOSA) using various numerical instances. Results indicate the hybrid algorithm’s superiority in terms of spacing and Rate of Achievement for two objective: simultaneously (RAS) indexes showcasing its efficacy in generating diverse and spaced solutions. Sensitivity analysis explores the impacts of changing model parameters, contributing valuable insights into environmentally friendly transportation systems and algorithm performance for the bi-objective VRP.

Ransikarbum, Wattanasaeng, and Chalil Madathil (2023) explore the application of renewable energy, specifically biofuel, in the context of the biofuel supply chain. The study begins by employing the K-means algorithm to identify potential collection site locations upstream in the supply chain. Subsequently, a multi-objective vehicle routing problem model is proposed, incorporating flexible time windows. The integrated model considers both economic and social aspects, evaluating total cost as a surrogate criterion for the economic perspective, and lateness for delivery and maximum delivery time as surrogate criteria for the social perspective. The model is applied to a regional case study based on wood-biomass data from the biofuel supply chain in Thailand, with the use of geographic information systems. The research aims to provide insights into the dynamics of open innovation within the renewable energy sector, emphasizing the use of biofuel in sustainable supply chains.

Ransikarbum et al. (2023) focus on logistics and supply chain management in the healthcare sector, specifically addressing last-mile delivery decisions for transporting healthcare products. The study begins by developing a Vehicle Routing Problem with Time Window (VRPTW) and introduces a minimax objective function to model the driver perspective, considering urgent healthcare product deliveries within time constraints for temperature control in the healthcare cold chain (HCC). A sensitivity analysis evaluates the model’s performance with varying numbers of vehicles. The study is validated using a case study from a third-party logistics (3PL) company, showing promising results. Ongoing development aims to enhance the healthcare cold-chain optimization model.

Multi-Objective Routing Problems

Decision makers often confront conflicting goals when enhancing the sustainability of last-mile logistics systems. For example, they strive to minimize costs and travel distance (time) while maximizing customer service levels. Multi-objective optimization is an extension of single-optimization. Compared to single-objective optimization, multi-objective optimization is more suitable for solving real-world problems as it provides decision support by revealing trade-offs among various objectives. A bi-objective vehicle routing problem aiming to minimize the economic cost and maximize customer satisfaction, considering multiple time windows for receiving fresh agricultural products for each customer is studied in (Wu and Wu 2022).

Belhaiza, Hansen, and Laporte (2014) studied a multi-time-interval problem that takes into account the minimum waiting time and minimum delays. They proposed a hybrid variable neighborhood-taboo search algorithm to solve the model. Jabir, Panicker, and Sridharan (2015) hybridized the ant colony algorithm with the variable neighbor search algorithm and used this algorithm to solve a multi-objective optimization problem aimed at minimizing distance and emission. Gupta et al. (2022) aim to minimize travel time and emission rate. They used the travel times as fuzzy. They used a genetic algorithm for the results. Elgharably et al. (2023) studied a three-objective optimization problem to minimize travel time, reduce fuel consumption, and increase customer satisfaction. They used genetic algorithm and local heuristic algorithms.

A bi-objective linear goal programming model with time windows aiming to minimize the travel time and customer waiting time is proposed in (Hong and Park 1999). A two-stage heuristic algorithm, consisting of an insertion method for clustering customers as the first stage and a sequential linear goal programming procedure for routing in the second stage, is proposed for solving the model.

He et al. (2023) address the vehicle routing problem (VRP) in industrial product delivery to meet high requirements for timeliness and cost-effectiveness. The study considers multiple distribution centers and various vehicle models, incorporating real-world constraints like vehicle load and time windows. A multi-objective optimization model is formulated to minimize distribution time and cost while maximizing the loading rate of vehicles. To solve this problem, an Improved Life-cycle Swarm Optimization (ILSO) algorithm is proposed based on life cycle theory. The algorithm is applied to order data from Yunnan Power Grid Company for a dispatching experiment. Results demonstrate that the ILSO algorithm reduces transportation costs.

Yin (2023) focuses on optimizing the routing of distribution vehicles in urban logistics to reduce energy consumption and carbon emissions. Using the Vehicle Routing Problem (VRP) as a basis, the study aims to flexibly plan actual pathing while meeting customer cargo demand and time requirements. The Non-dominated Sorting Genetic Algorithm (NSGA-II) is improved for efficiency and convergence by introducing the Multifactorial Evolutionary Algorithm (MFEA), resulting in the proposed NSGA-II algorithm based on Multifactorial Evolutionary Algorithm (M-NSGA-II). In 10 experiments, M-NSGA-II consistently demonstrated lower distribution costs compared to three standard algorithms. The algorithm’s solution duration was 85.2 s with an average frontier value of 20, showcasing its effectiveness in optimizing distribution routes for reduced carbon emissions while satisfying customer requirements. The multi-objective path optimization model presented holds significant value in enhancing sustainability in urban logistics.

Kuo et al. (2023) address the growing complexity of the global supply chain by proposing a mathematical model for a multi-objective Vehicle Routing Problem with Time Windows (VRPTW). The model focuses on minimizing the total supply chain cost and carbon emissions while considering disruptions in the supply chain. The proposed model includes a two-stage VRPTW to handle disruptions, with the first stage representing the supply chain in ideal conditions and the second stage reflecting disruptions. To solve this problem, an improved Multi-Objective Particle Swarm Optimization algorithm (MOPSO) is introduced. Computational results show that the improved MOPSO outperforms other algorithms in terms of hypervolume and spacing, indicating its effectiveness in solving disruptions in the two-stage VRPTW. The study highlights the importance of considering disruptions and sustainability in optimizing vehicle routing for real-world applications in the context of the complex global supply chain.

Despite extensive research in multi-objective VRPs, there is a lack of general model that suitable for various problems, including complex ones.

Methods and Algorithms for Solving Routing Problems

Various methods have been developed for solving VRP variants. An extensive reviewing of methods for solving multi-objective TRPs, e.g., scalar techniques and Pareto methods, has been developed in (Jozefowiez, Semet, and Talbi 2008). Weighted linear aggregation, goal programming methods, and $\mathit{\epsilon }$-constraint methods belong to the branch of scalar techniques, while evolutionary algorithms, hybrid algorithms, and Pareto local search are Pareto methods. Some researchers study methods for solving a range of problems. For instance, Yusuf, Sapiyan Baba, and Iksan (2014) presented a genetic algorithm for solving the classical single-objective VRP (without time windows) and various of its variants. Many of the existing algorithms for solving multi-objective VRPs perform well only for specific problems or with a limited amount of variants. For example, Zacharia et al. (2021) propose a genetic algorithm to solve a bi-objective VRP with fuzzy payloads that minimizes travel distance and fuel consumption.

Algorithms for solving general multi-objective optimization problems can also be used for solving multi-criterion VRPs. For example, a Non-dominated Sorting Genetic Algorithm (NSGA) was proposed by Srinivas and Deb (1994) as one of the earliest algorithms for solving multi-objective optimization problems. However, the high computational complexity of NSGA makes it expensive to apply to large-scale problems. Based on NSGA, Deb et al. (2000) further propose a non-dominated sorting based multi-objective evolutionary algorithm, NSGA-II, which outperforms other algorithms for multi-objective optimization including Knowles and Corne (1999)’s Pareto-archived evolution strategy and Zitzler and Thiele (1998)’s strength Pareto evolutionary algorithms. To fulfill the need of solving problems with many objectives (four or more), a reference-point-based many objective evolutionary algorithm, NSGA-III, is proposed in (Deb and Jain 2013; Jain and Deb 2013). By decomposing a multi-objective optimization problem into scalar subproblems and solving these subproblems in parallel, Zhang and Li (2007) propose a decomposition-based multi-objective evolutionary algorithm (MOEA/D) which performs as good as or better than NSGA-II on binarial or continuous multi-objective optimization problems. As hypervolume is an often used indicator for measuring the quality of multiobjective optimization algorithms, Beume, Naujoks, and Emmerich (2007) propose a metric selection EMOA (SMS-EMOA) with the aim of maximizing the hypervolume combining with the non-dominated sorting strategy. Results show that SMS-EMOA outperforms NSGA-II for optimization problems with two and three objectives in terms of convergence and the hypervolume. Lian, Lucas, and Sörensen (2023) use Large Neighborhood Search and local search operators to solve Electric Vehicle Routing Problems. Deep reinforcement learning-based route planning algorithm is proposed by Hou et al. (2023). Moradi, Sadati, and Çatay (2023) propose mixed integer linear programming model for their multi-objective VRP problem. Also they use two-phase metaheuristic approach. Hybrid variable neighborhood search and simulating annealing. Amiri, Zolfagharinia, and Amiri, Zolfagharinia, and Hassanzadeh Amin (2023) propose two metaheuristic algorithm NSGA-II and Adaptive Large Neighborhood Search. Tan, Chai, and Li (2023) applies MOEA/D-based algorithm and Robust Optimization Algorithm to multi-objective problem. Praxedes et al. (2024) used Branch-Cut-and-Price method to solve big-sized problems. Muñoz-Villamizar, Velazquez-Martínez, and Caballero-Caballero (2024) proposed Mixed Integer Linear Programming model and a custom metaheuristic for Mexico VRP dataset. Dubey and Tanksale (2023) modeled the problem as mixed-integer programming problem. They used Genetic Algorithm and GA hybridized with local search algorithm with 3-opt local search. Zahedi, Kia, and Khalilzadeh (2023) offered a hybrid metaheuristic algorithm, NSGA-II-TLBO, which combines a nondominated sorting genetic algorithm (NSGA-II) and optimization based on teaching and learning (TLBO). Ransikarbum, Wattanasaeng, and Chalil Madathil (2023) employed the K-means algorithm. In the literature, there are various algorithms and hybrid algorithms.

Research Gaps

We summarize existing research related to our paper according to the type of VRP models in Table 1. We add our paper at the end for comparison. From Table 1, we can see that this is the first research considering multi-objective vRP with hybrid vehicles and multiple time windows.

Table 1. Summary of literature.

Article	VT^a	TW^b	OF^c	Objectives
(Elgharably et al. 2023)	Fuel oil	1	3	Minimize total cost, minimize fuel consumption, and maximize customer satisfaction
(Ransikarbum et al. 2023)	-	1	3	Minimize total cost, minimize lateness time, minimize the maximum time the last time
(Amiri, Zolfagharinia, and Hassanzadeh Amin 2023)	Electric	1	2	Minimize cost, minimize delay
(Hong and Park 1999)	-	1	2	Minimize travel time, minimize customer waiting time
(Kuo et al. 2023)	-	1	2	Minimize total cost, minimize emission
(Ombuki, Ross, and Hanshar 2006)	-	1	2	Minimize the number of vehicles, minimize total travel time
(Tan, Chai, and Li 2023)	-	1	2	Minimize total distance, minimize the number of vehicles
(Zahedi, Kia, and Khalilzadeh 2023)	Electric	1	2	Minimize total cost, minimize total delay
(Dubey and Tanksale 2023)	-	1	1	Minimize total cost
(Frey et al. 2023)	-	1	1	Minimize total cost
(Muñoz-Villamizar, Velazquez-Martínez, and Caballero-Caballero 2024)	-	1	1	Minimize total cost
(Praxedes et al. 2024)	-	1	1	Minimize total cost
(Schneider, Stenger, and Goeke 2014)	Electric	1	1	Minimize total cost
(Chen et al. 2023)	Electric, diesel, gasoline	1	1	Minimize total cost
(Agatz, Fan, and Stam 2021)	-	Multiple	3	Minimize routing distance, minimize cost, maximize per-customer revenue
(Wu and Wu 2022)	-	Multiple	2	Minimize total cost, maximize average customer satisfaction
(Belhaiza, Hansen, and Laporte 2014)	-	Multiple	1	Minimize total travel time
(Belhaiza et al. 2019)	-	Multiple	1	Minimize total cost
(Hoogeboom et al. 2020)	-	Multiple	1	Minimize total cost
(Li et al. 2020)	-	Multiple	1	Minimize total cost
(Schaap et al. 2022)	-	Multiple	1	Minimize total cost
(He et al. 2023)	-	-	3	Minimize distribution cost, minimize delivery time, maximize loading rate of vehicles
(Huang et al. 2016)	Electric	-	3	Minimize the lowest charging cost, minimize the shortest charging waiting time, minimize the shortest distance between an EV and the optimal charging location
(Jozefowiez, Semet, and Talbi 2008)	-	-	3	Minimize the number of vehicles, minimize traveling distance, minimize the total length of the tour
(Yin 2023)	Electric, diesel, gasoline, hybrid	-	3	Minimize cost, maximize customer satisfaction, minimize carbon emissions
(Yusuf, Sapiyan Baba, and Iksan 2014)	-	-	3	Minimize total fuel consumption, maximize ports of call, maximize load factor
(Gupta et al. 2022)	Fuel oil	-	2	Minimize travel time, minimize fuel emission
(Jabir, Panicker, and Sridharan 2015)	-	-	2	Minimize total cost, minimize emission
(Zacharia et al. 2021)	Fuel oil	-	2	Minimize travel distance, minimize fuel consumption
(Hiermann et al. 2019)	Hybrid, electric	-	1	Minimize total cost
(Lian, Lucas, and Sörensen 2023)	Electric	-	1	Minimize total charging time
(Masmoudi, Coelho, and Demir 2022)	Hybrid	-	1	Minimize total distance
(Moradi, Sadati, and Çatay 2023)	Electric	-	1	Minimize total cost
(Seyfi et al. 2022)	Hybrid	-	1	Minimize total cost
(Vincent et al. 2017)	Hybrid	-	1	Minimize total cost
This paper	Hybrid	3	3	Minimize total cost, minimize emission, minimize customer dissatisfaction

^aThe engine type of vehicles

^bThe number of time windows

^cThe number of objectives

Our paper aims to address two limitations in the current research: First, the existing methods do not take into account the trade-offs between customer flexibility, environmental impact, and economic costs in a multi-objective manner, considering flexible time windows with ranked preferences. Second, previous studies have focused either on flexible time windows or electro mobility, but not both simultaneously.

While previous studies have touched on sustainability in the context of last-mile logistics, there is also still a significant gap in the widespread adoption of sustainable strategies. To promote more sustainable last mile logistics, it is necessary to build optimization and simulation models that accurately capture real-world challenges and account for the use of sustainable vehicles such as electric vehicles, hybrid vehicles, and autonomous vehicles (Cunneen, Mullins, and Murphy 2019; Taniguchi, Thompson, and Qureshi 2020). In addition, innovative approaches are required to better align the interests of the delivery companies, the delivery personnel, the customers, the society, and the natural environment in terms of profitability.

In this paper, we bridge the gap by proposing a hybrid vehicle routing model with three objectives, including minimizing costs, minimizing diesel oil usage, and minimizing customer dissatisfaction levels. In our model, each customer provides three preferred time windows. The aim is to make deliveries during one of the customer’s preferred time windows as frequently as possible. To highlight our contribution:

• Three time windows alternatives are provided for the customers, which differ from previous studies in the literature.

• A novel mathematical model is created related to the novel problem type.

• Minimizing cost, decreasing fossil fuel usage, and minimizing customer dissatisfaction are considered as objectives.

Problem Description

In this paper, we consider hybrid vehicles equipped with both an electric engine and a diesel engine. Driving on electric engine offers advantages over using a diesel engine in urban environment due to zero emission and reduced noise levels. The electric engine is more Eco-friendly than the diesel engine when the vehicle is idling, such as at traffic lights or in heavy traffic. Electric engines are more efficient than diesel engines at low speeds and during stop-and-go driving. Moreover, electric engines are quieter than diesel engines; this can reduce noise pollution in urban areas and provide a more comfortable ride for the driver and passengers. Additionally, the lower noise pollution of electric engines can benefit urban areas with significant noise pollution. Overall, electric engines are well suited for short-distance and city driving due to their efficient power distribution, regenerative braking, and low pollution.

However, electric engines have limited capacity and require recharging (which takes time) or switching to another engine (if available) after driving a certain distance on them. Electric-powered hybrid vehicles require charging infrastructure that is not commonly available or inaccessible in some regions. This may limit the practicality of electric-powered hybrid trucks in certain applications. When electric engines run out of energy, the truck will need to rely solely on the diesel engine or recharge, which can take time and limit the vehicle’s range. Also, the charging times are long. In addition, the driver loses time for charging, and the paid salary is spent ineffectively.

Diesel engines are generally more suitable for long-distance and long-distance driving. Diesel engines typically have a longer range than electric engines and can be refueled quickly and easily at existing gas stations. This makes them well-suited for long-haul trucking, where range and fuel infrastructure are key factors.

An electric engine and a diesel engine complement each other in urban last-mile logistics, which is why we consider hybrid vehicles in our model. We aim to use electric engines for stop-and-go driving in heavy traffic, as it provides additional power during acceleration and recover energy during braking. For long-distance driving in rural areas, or when the electric engine is powered off, switching to the diesel engine helps increase delivery efficiency.

For attended home delivery, customers are usually asked to choose one time window from a menu to receive their goods. In this paper, we assume that each customer chooses multiple time windows when they are available to receive goods and prioritize these time windows. Deliverers would then attempt to make deliveries within higher-priority time windows chosen by each customer. This strategy allows customers to select time windows according to their own availability, without being limited by a menu. However, considering multiple time windows for each customer does increase the computing complexity.

In this paper, we present a three-objective route planning model designed to obtain Pareto optimal solutions (including delivery time windows for each customer and sequence of customers to visit) to minimize economic cost, reduce environmental impact (diesel distance), and maximize customer satisfaction (or minimize customer dissatisfaction). Based on our solutions, we construct 3-D Pareto fronts that show the trade-offs among the different objectives which helps route planners to interpret solutions and make the right decision. Figure 1 shows an overview, depicting the input, output, the three objectives, and the main constraints of our model. First, customers are requested choose three preferred time windows based on their preference order. Subsequently, Pareto optimal route plans, which minimize the three objectives, can be generated and visualized by solving the model.

Figure 1. Problem Statement.

The following assumptions are made for our model: 1) Customers have different preferences on different time windows. Customers are more satisfied when a delivery is made within a more preferred time window. 2) Hybrid vehicles (with both diesel and electric engines) are used for delivery. The diesel engine is only used for long-hauls, and the electric engine is used for short-hauls. 3) When electric engine is below the level required for the next delivery, the vehicle has to be charged. Drivers receive payment according to working time, including the time when a vehicle has to be charged in between. 4) Decision-makers not only care about economic costs in last-mile delivery but also care about the environmental impact and customer satisfaction level. Based on these assumptions, we will develop our model in the next section.

Model

In this section, we will introduce a three-objective three-time window optimization model for hybrid vehicle routing in last-mile logistics. In the following we will provide a formulation for the ILP solver of GUROBI. Before outlining the details of the model, let us address the issue of how conditions and disjunctive constraints are handled. In the given model, simple if-then-else conditions based on binary decision variables can be represented by disjunctive constraints. Let us consider a binary decision variable $\mathit{x}\in \{0,1\}$ which represents two alternatives. Disjunctive constraints are formulated based on the value of $\mathit{x}$. When $\mathit{x}=0$, a set of constraints $\{C_0\}$ becomes active, and when $\mathit{x}=1$, a different set of constraints $\{C_1\}$ is applied. To activate or deactivate constraints the large constant or “large M” technique or is used (Diwekar 2020). For each alternative, additional decision variables can be introduced, which are connected to $\mathit{x}$ through constraints. The objective function, which is to be optimized, is a function of both $\mathit{x}$ and these additional variables. This approach proves to be effective in scenarios where choices are clearly binary.

Parameters and Variables

The symbols used in the model are seen in Table 2. $t_s$, $t_{\mathit{ij}}$, $t_{ij}^s$, $t_{ij}^e$, $t_c$, $t_e$, and $t_i^a$ are in minute unit. $c_s$, $c_d$, and $c_e$ are in euro unit. $d_{\mathit{ij}}$, $b_c$, and $b_i$ are in kilometer unit.

Table 2. Parameters and variables.

Parameters
$t_s$	Start time of the delivery
$t_{\mathit{ij}}$	Travel time between i and j
$c_s$	Cost of deliverer’s salary per minute
$c_d$	Cost of diesel per km
$c_e$	Cost of electricity per km
$c_i^p$	Customer dissatisfaction level when delivery is made during the time window with the preference order of $\mathit{i},c_1^p=0$ and $c_i^p<c_{(i+1)}^p$
$t_{ik}^s$	The beginning of the $\mathit{k}$-th preferred time window for customer $\mathit{i}$
$t_{ik}^e$	The end of the $\mathit{k}$-th preferred time window for customer $\mathit{i}$
$d_{\mathit{ij}}$	Distance between point i and j
$l_e$	Threshold distance for switching an electric engine to a diesel engine, i.e., if the travel distance to the next destination is longer than $l_e$, the diesel engine is used
$t_c$	Fixed time for re-charging
$b_c$	The hybrid vehicle’s battery capacity, which is measured in terms of travel distance (kms)
$\mathit{M}$	A large constant
Variables
$X_{\mathit{ij}}$	Binary variable indicating the transportation route, 1 – travel from i to j, 0 – otherwise
$X_{ij}^d$	Binary variable, 1 – using diesel mode from i to j, 0 – otherwise
$X_{ij}^e$	Binary variable, 1 – using electric mode from i to j, 0 – otherwise
$T_e$	End time of the delivery
$T_i^a$	Arrival time of point $\mathit{i}$
$U_i$	Auxiliary variables to avoid subtour
$B_i$	Represents the battery level, measured in travel distance (kms), at customer $\mathit{i}$
$B_{ij}^e$	Auxiliary binary variables, while 1 indicates that the battery is sufficient for the delivery task from $\mathit{i}$ to $\mathit{j}$, and 0 otherwise.
$B_{ij}^{ee}$	Auxiliary binary variables, while 1 indicates that the electric engine is required and the battery level is sufficient for the delivery task from $\mathit{i}$ to $\mathit{j}$, and 0 otherwise.
$P_{\mathit{ik}}$	Binary variable indicating the preference order of the time windows chosen by each customer, where $\mathit{k}\in$ {1, 2, 3, 4}, with 1, 2, and 3 representing the most, the second most, and the third most preferred time windows, respectively, and 4 indicating any other time beyond the three chosen time windows

Objectives

We have three objectives aiming to minimize the economic cost (see F1 in (1)), minimize diesel usage/distance (see F2 in (2)), and minimize customer dissatisfaction (see F3 in (3)). In the first objective, F1, drivers’ salaries (depending working time $t_e$) and energy cost (depending on electricity usage per kilometer and diesel usage per kilometer) are considered. In the third objective, F3, penalty costs for not delivering at the customers’ most preferred time windows are taken into account.

(1) $min{F}_1=T_e\cdot c_s+\sum _{\mathit{i}=0}^n\sum _{\mathit{j}=0}^n(d_{\mathit{ij}}\cdot c_d\cdot X_{ij}^d)+\sum _{\mathit{i}=0}^n\sum _{\mathit{j}=0}^n(d_{\mathit{ij}}\cdot c_e\cdot X_{ij}^e)$(1)

(2) $min{F}_2=\sum _{\mathit{i}=0}^n\sum _{\mathit{j}=0}^n\left(d_{\mathit{ij}}\cdot X_{ij}^d\right)$(2)

(3) $min{F}_3=\sum _{\mathit{i}=0}^n\left[\left(c_1^p\cdot P_{\mathit{i}1}\right)+\left(c_2^p\cdot P_{\mathit{i}2}\right)+\left(c_3^p\cdot P_{\mathit{i}3}\right)+\left(c_4^p\cdot P_{\mathit{i}4}\right)\right]$(3)

Constraints

We use the following two constraints (4) and (5) to ensure that customers are only visited once.

(4) $\sum _{\mathit{i}=0}^n{X}_{\mathit{ij}}=1,\mathit{i}\ne \mathit{j},\mathrm{\forall i}\in \mathit{N}$(4)

(5) $\sum _{\mathit{j}=0}^n{X}_{\mathit{ij}}=1,\mathit{i}\ne \mathit{j},\mathrm{\forall j}\in \mathit{N}$(5)

To avoid sub-tours, we add auxiliary variables $U_i$ in the constraints below:

(6) $U_i-U_j+\mathit{n}\cdot X_{\mathit{ij}}\le \mathit{n}-1,\mathrm{\forall i},\mathit{j}\in \mathit{N},\mathit{j}\ne 1,\mathit{i}\ne 1$(6)

(7) $2\le U_i\le \mathit{n},\mathrm{\forall i}\in \mathit{N},\mathit{n}=|\mathit{N}|$(7)

The threshold distance of switch between diesel and electricity is $l_e$, we use the following two constraints to ensure that electricity is used when the travel distance between two subsequent customers is not longer than $l_e$; otherwise, diesel is utilized.

(8) $X_{ij}^d=0|d_{\mathit{ij}}\le l_e,\mathrm{\forall i},\mathit{j}\in \mathit{N}$(8)

(9) $X_{ij}^e=0|d_{\mathit{ij}}>l_e,\mathrm{\forall i},\mathit{j}\in \mathit{N}$(9)

The following constraint ensures that either diesel or electricity is used for a delivery task, but the two cannot be used simultaneously.

(10) $X_{ij}^d+X_{ij}^e=X_{\mathit{ij}},\mathrm{\forall i},\mathit{j}\in \mathit{N}$(10)

(11) $B_{ij}^e=\left\{\begin{array}{cc}1,& \mathrm{if}{B}_i\ge d_{\mathit{ij}}\\ 0,& \mathrm{Otherwise}\end{array}\right.$(11)

To ensure our model is solvable in Gurobi, we used constraints (12)-(14) as the transformation of conditional equation (11)(11) $B_{ij}^e=\left\{\begin{array}{cc}1,& \mathrm{if}{B}_i\ge d_{\mathit{ij}}\\ 0,& \mathrm{Otherwise}\end{array}\right.$(11) . $\mathit{M}$ is a large constant and $B_{ij}^{ee}$ is an auxiliary binary variable.

(12) $\mathit{M}\cdot B_{ij}^{ee}\ge B_i-d_{\mathit{ij}},\mathrm{\forall i},\mathit{j}+1\in \mathit{N}$(12)

(13) $\mathit{M}\cdot (1-B_{ij}^{ee})\ge d_{\mathit{ij}}-B_i,\mathrm{\forall i},\mathit{j}+1\in \mathit{N}$(13)

(14) $B_{ij}^e=\left\{\begin{array}{cc}1,& \mathrm{if}{B}_{ij}^{ee}=1\\ 0,& \mathrm{Otherwise}\end{array}\right.$(14)

If the battery level is insufficient for the delivery task ($B_{ij}^e=0$) from $\mathit{i}$ to $\mathit{j}$, and electric engine is required for this trip ($X_{ij}^e=1$), extra charging time, $t_c$, is added to the estimated time of arrival at customer $\mathit{j}$. Otherwise, if diesel engine is required or battery level is sufficient, the delivery time for customer $\mathit{j}$ is calculated by adding the travel time of this task to the arrival time for customer $\mathit{i}$. These conditions are enforced in the following constraints:

(15) $T_j^a=\left\{\begin{array}{cc}{T}_i^a+t_{\mathit{ij}},& \mathrm{if}{X}_{ij}^d=1\\ T_i^a+t_{\mathit{ij}},& \mathrm{if}{X}_{ij}^e=1,B_{ij}^e=1\\ T_i^a+t_{\mathit{ij}}+t_c,& \mathrm{if}{X}_{ij}^e=1,B_{ij}^e=0\\ \mathit{\hspace{0.17em}}& \mathit{\hspace{0.17em}}\end{array}\right.\mathrm{\forall i},\mathit{j}+1\in \mathit{N}$(15)

When the hybrid vehicle has sufficient battery level for the next delivery task on electricity (from $\mathit{i}$ to $\mathit{j}$), the battery level is decreased based on the usage during this task upon reaching $\mathit{j}$. When the battery level falls below the required amount for the next delivery task (from $\mathit{i}$ to $\mathit{j}$), the deliverer is obligated to charge the battery after the completing the delivery to $\mathit{i}$ and then continue with the remaining delivering tasks once the hybrid vehicle is fully charged, restoring the battery to its upper bound capacity $b_c$. When diesel engine is required, the battery level remains at the same level. These conditions are enforced in the following constraints:

(16) $B_j=\left\{\begin{array}{cc}{B}_i& \mathrm{if}{X}_{ij}^d=1\\ B_i-d_{\mathit{ij}}& \mathrm{if}{X}_{ij}^e=1,B_{ij}^e=1\\ b_c& \mathrm{if}{X}_{ij}^e=1,B_{ij}^e=0\end{array}\right.\mathrm{\forall }\mathit{i},\mathit{j}+1\in \mathit{N}$(16)

Similar to the transformation used for (11), auxiliary binary variables and big “M” are used to transform (15) and (16) for solving using Gurobi.

(17) $P^{\mathit{ik}}=\left\{\begin{array}{cc}1,& \mathrm{if}{t}_{ik}^s\le T_i^a\le t_{ik}^e\\ 0,& \mathrm{Otherwise}\end{array}\right.$(17)

Each customer served within one of the preferred time windows is enforced by constraint (18).

(18) $P_{\mathit{i}1}+P_{\mathit{i}2}+P_{\mathit{i}3}+P_{\mathit{i}4}=1,\mathrm{\forall }\mathit{i}\in \mathit{N}$(18)

Computational Experiments

In our computational experiments, we will generate instances randomly and utilize NSGA-II, NSGA-III, MOEA/D, and SMS-EMOA algorithms to solve the model. These algorithms are recognized as state-of-the-art metaheuristics for approximating Pareto fronts in multiobjective scenarios. For a comprehensive review, please refer to (Emmerich and Deutz 2018). Our goal is to determine the most effective algorithms for our model by comparing computational outcomes. Additionally, we evaluate the results by varying the number of time windows requested from customers in our experiments. This allows us to assess the benefits of requesting three time windows compared to one or two. The computational results will be presented and analyzed in the following section.

Instances

We created a small set of new, realistic, benchmark problems for this new problem class. The benchmark problems are inspired by an industrial optimization case for an office supply company in Germany for which one of the authors (ME) worked. The office company is located in a rural district in Germany, where they distribute office supplies (paper, printers, or furniture) to local clients (small firms, schools, etc.). They have a single delivery car, who needs to deliver ca. 40 items to places located in five different small towns of the district. We assume that similar, single driver delivery services are quite commonly offered by companies who supply single, but large items, such as gardening companies, furniture companies, etc., and thus our specific algorithms and models have the potential to serve a wider community of practitioners who need to plan daily routes for delivery vehicles.

We randomly generated five instances (of which two are small sizes and three are big sizes) for testing our model and various solvers. Since this is an NP-hard problem, the computing time increases exponentially as the size of the instance increases. Given the complexity of the model, in this research, we only focus on comparatively small size instances. Large size instances and algorithms for solving large instances are not considered in this paper. We first randomly generate two small-size instances, with 10 and 11 customers, respectively, to initially test our model and solvers.

Then, we randomly generated three big-sized problems:

• Instance 3–60: containing 60 customers located in 3 cities

• Instance 4–40: containing 40 customers located in 4 cities

• Instance 5–30: containing 30 customers located in 5 cities

Each instance has one depot. For each instance, a driver drives a hybrid vehicle from a depot and travels back to the depot after delivering packages to customers located in multiple cities. For each customer, we randomly generate three non-overlapping time windows as their preferred time windows. We assume that diesel is used when the travel distance between two nodes is longer than the $l_e$. Otherwise, the electric engine is used.

Solvers and Computational Complexity

The vehicle routing problem and its variations are generally considered to be NP-hard problems. This also applies to the traveling salesperson problem (TSP), which is a specific case of the problem with a single vehicle (Toth and Vigo 2002). As a result, finding an exact solution for the model is only feasible for relatively small instances of the problem. For larger instances, we often need to rely on metaheuristics or approximate solutions. When the problem is made multiobjective, we either have to solve the models multiple times with different scalarizations and weightings of the objectives, or we can optimize a population of points simultaneously, which is usually faster than running a single run for each point in a Pareto front approximation.

The model is built in Python. To solve this model, we used Gurobi, NSGA-II, NSGA-III, MOEA/D, and SMS-EMOA. In these algorithms, some special type of operators are used, because this problem is permutation problem type. For the initial solutions random permutation sampling is used. For crossover process, order crossover is used. Two parent chromosomes (solutions) are selected from the current population. These parents represent potential solutions to the optimization problem. Two crossover points are randomly chosen along the chromosomes. These points determine the segment that will be transferred between the parents. A segment between the two crossover points is selected from one parent and copied directly to the offspring. The remaining positions in the offspring are filled with the remaining unused elements from the second parent, preserving the order of elements as they appear in the second parent. To ensure that all elements are unique in the offspring, any duplicate elements in the segment copied from the first parent are replaced with elements from the second parent, maintaining the order. In mutation process, inversion mutation is applied. Two mutation points are randomly chosen along the sequence. These points determine the segment that will be inverted. The segment between the two mutation points is inverted or reversed. This means that the order of elements within this segment is reversed.

In the following section, we examine the effectiveness and constraints of an advanced exact integer linear programming solver, as well as the time and quality achieved by metaheuristics in relation to approximations of the Pareto front. To understand the complexity and scalability in practice we also report the CPU times required for the computations.

Results

The results are taken using 8 GB RAM, 2.30 GHZ 4 cores CPU laptop. The codes are written in Python. For mathematical model Gurobi Solver is used using Python library.

Initial Results of Small-Size Instances

We initially solve two small-size instances with 11 nodes (10 customers and one depot) or less using Gurobi while fixing the weights of the three objectives. Computational results in Table 3 shows that computing time is exceptionally long for instances with 11 nodes when the three objectives are considered. Therefore, we will not use Gurobi for large-size instances (with 30, 40, and 60 customers) or generating Pareto fronts in the rest of this paper.

Table 3. Gurobi solver results of the small-sized instances.

	10-node instance				11-node instance
Obj.Weight^a	F1	F2	F3	Time^b	F1	F2	F3	Time
1, 0, 0	112.488	22	32	728.035	114.236	22	32	3453.449
0, 1, 0	120.085	22	32	25.954	191.932	0	36	0.734
0, 0, 1	165.697	79.007	16	519.441	154.738	73.109	16	2731.551
$\frac{1}{3},\frac{1}{3},\frac{1}{3}$	112.488	22	32	1221.201	194.778	0	21	18259.832

^aThe weights assigned to the three objectives, respectively

^bComputing time in seconds

In Figure 2, we visualize the results presented in Table 3. Nodes labeled “0” represent depots, and other nodes represent customers. The shapes of routes differ when distinct weights are assigned to the three objectives. Particularly, when F3 is the dominant objective, detours must be made to satisfy customers as much as possible. It implies that the three objectives considered in our model are conflicting.

Figure 2. Routes for small instances.

The results above show routes with fixed weights for the three objectives. Next, we use NSGA-II, NSGA-III, MOEA/D, and SMS-EMOA to generate Pareto fronts for the two instances. Figure 3 shows 3D Pareto fronts generated using the four methods, each with 300 running iterations. Results show that NSGA-II and SMS-EMOA generate the highest number of Pareto optimal solutions, while NSGA-III provides the least number of Pareto optimal solutions among the four.

Figure 3. Pareto fronts of small instances.

Convergence tendencies in Figure 4 show that the four methods help to generate Pareto optimal solutions are running 50 iterations or less. However, the convergence tendencies show dependency on instances. For example, NSGA-III and MOEA/D for 11-node instances still converge to better solutions after 150 iterations.

Figure 4. Convergence tendencies for NSGA-II, NSGA-III, MOEA/D and SMS-EMOA.

Results of Big-Size Instances

For our computational experiments with larger size instances, we use NSGA-III, NSGA-II, MOEA/D, and SMS-EMOA for generating Pareto optimal solutions. We run each algorithm 10 times with 300 iterations per run for each instance. The average values of hyper-volumes are presented in Table 4 and Figure 5. The hypervolume metric quantifies the volume of the dominant region in the objective space and is particularly valuable due to its strict adherence to Pareto optimality (Beume, Naujoks, and Emmerich 2007). We see that NSGA-II and SMS-EMOA perform better than the others in terms of the hypervolume measure, while MOEA/D has the shortest computing time among the four and SMS-EMOA takes the longest computing times among the four. NSGA-III takes similar computing time as NSGA-II, while has lower hypervolume measure. Results also show that the computing time of the four methods linearly increases with customer volume. Overall, there is a trade-off in choosing algorithms. NSGA-II and SMS-EMOA gives the best results, but they are slower than the others. On the other hand, MOEA/D produces results very quickly, the quality of the results seems less favorable.

Figure 5. Comparison of the algorithms’ hypervolumes for all instances.

Table 4. Hypervolume results.

	Hypervolume		Time
Algorithm	Mean	Stdev	Mean	Stdev
(a) 60-customer instance
NSGA-II	0.305	0.036	1132.646	33.643
NSGA-III	0.291	0.034	1092.858	9.148
MOEA/D	0.294	0.036	415.255	8.962
SMS-EMOA	0.299	0.035	2865.694	428.330
(b) 40-customer instance
NSGA-II	0.427	0.032	879.861	18.293
NSGA-III	0.412	0.034	732.394	15.890
MOEA/D	0.420	0.024	272.534	6.638
SMS-EMOA	0.430	0.030	2173.747	510.884
(c) 30-customer instance
NSGA-II	0.540	0.026	688.565	8.023
NSGA-III	0.529	0.026	589.528	6.260
MOEA/D	0.519	0.020	242.609	4.137
SMS-EMOA	0.534	0.023	3129.497	557.273

To analyze and visualize the trade-offs between different objectives, we present routes with dominant objectives in Figures 6–8, where the green and orange lines represent the use of electric and diesel engines, respectively. The green, blue, yellow, and red points represent the preference order of the delivery time. Results show that routes with minimum cost have the least number of crossovers and detours. In routes with the lowest emissions, diesel (yellow lines) is used less frequently, but at the cost of more detours. Routes with the highest customer satisfaction levels prioritize serving most customers within their most preferred time windows (nodes colored green), resulting in fewer green lines (trips using the electric motor) and more crossovers (distances).

Figure 6. Routes for different objectives in 60-customer instance.

Figure 7. Routes for different objectives in 40-customer instance.

Figure 8. Routes for different objectives in 30-customer instance.

To quantify the trade-offs: Compared to routes with the minimum cost, routes with the lowest emissions can potentially reduce emissions by up to 74%, increasing cost by up 50%, and decreasing customer satisfaction level by up to 9%, according to the metric used in our research. Routes with the highest satisfaction can potentially increase customer satisfaction by up to 82%, but this comes at the cost of up to 53% higher costs and up to 29% more emissions.

Comparison of Time Windows and Managerial Insights

Figure 9–11 show the impact of varying numbers of time windows on the objective values of Pareto optimal routes. The values for each instance are obtained from 10 runs. The results show that, compared to having only one time window for each customer, requesting three alternative time windows from customers helps to reduce the cost and improving customer service levels. The impact of having multiple time windows also depends on instances. For example, in the 40-customer instance, having three time windows clearly reduces cost (by about 8%) and improves customer satisfaction (by about 24%), while maintaining similar emissions (see Figure 10). In 30-customer instance, having three time windows results in a 1% cost reduction and a 73% increase in customer satisfaction levels. In the 60-customer instance, three time windows bring a 4% cost reduction and a 43% improvement in customer satisfaction levels.

Figure 9. Time windows and objectives in 60-customer instance (Pareto optimal solutions generated with NSGA-II).

Figure 10. Time windows and objectives in 40-customer instance (Pareto optimal solutions generated with SMS-EMOA).

Figure 11. Time windows and objectives in 30-customer instance (Pareto optimal solutions generated with NSGA-II).

In summary, we can conclude that requesting customers to choose three preferred time windows, as opposed to just one or two, leads to a reduction in economic costs and an increase in customer satisfaction. Similarly, requesting two time windows rather than just one results in higher customer satisfaction and, in most cases, leads to lower economic costs. However, in very rare cases, requesting two time windows may slightly increase economic costs. Requesting different number of time windows does not lead to a decrease in the environmental impact of delivery. This is because diesel usage is closely tied to the long-haul distance according to the setup of this research, which cannot be fully avoided due to customers being located in different cities.

Conclusion

This paper proposes an innovative strategy of requesting multiple time windows from customers in last-mile delivery. This approach aims to reduce economic cost while simultaneously increasing customer satisfaction level and reducing emissions. Our computational results demonstrate that requesting multiple time windows from customers provides deliverers with greater flexibility in routing planning, facilitating an eco-friendly, cost-efficient, and customer-satisfactory solution. Although considering multiple time windows in a route planning model increases computational complexity, computational results show that evolutionary algorithms (NSGA-II, NSGA-III, MOEA/D, and SMS-EMOA) effectively solve these problems within a reasonable computing time. Among these algorithms, NSGA-II and SMS-EMOA outperform other algorithms in most cases, even though its computing time for 100 iterations is slightly longer than that of MOEA/D. In this sense, we can say that this paper not only presents an innovative strategy for last-mile delivery but also outlines a practical implementation path for real-world last-mile delivery scenarios.

For the next step, we will extend our model for large-size problems, e.g., with more customers and multiple depots, as well as considering the locations of charging stations. Developing algorithms for fast solving large-size instances is also within the research scope of our next step. Moreover, given the increasing importance of environmental concerns, researchers should prioritize studying the reduction of emissions in urban area. In existing research, emissions are often assumed to be a linear function of travel distance or travel time. A more accurate calculation is needed because emissions are influenced by various factors, including drivers’ experience, travel speed, load weight, road conditions, traffic conditions, and more. Moreover, addressing dynamics and stochastic factors to provide accurate decision support is crucial in vehicle routing problems, particularly when autonomous vehicles are employed for deliveries. Ethical considerations should also be taken into account when autonomous vehicles operate on the road. Finally, since heuristic algorithms are unreliable in terms of achieving optimality, we propose two directions of improvement: First, by reduction of the number of variables, the MILP solver can be applied for larger problem sizes. A viable direction would be the introduction of hubs, one per cluster, and restrict long-haul distances between clusters to travels between hubs and then from the hub to the next client. Second, based on problem features, one may use automated algorithm selection to chose the best metaheuristic for the given problem instance.

Acknowledgements

Burak Gülmez acknowledges financial support under the TUBITAK 2219 postdoctoral fellow grant scheme (Scientific and Technological Research Council of Türkiye).

Disclosure Statement

No potential conflict of interest was reported by the author(s).

Data Availability Statement

The datasets used are at this link: https://github.com/burakgulmez/Multi-objective-VRP-with-multiple-time-windows

Supplementary material

Supplemental data for this article can be accessed online at https://doi.org/10.1080/08839514.2024.2325302.

Additional information

Funding

The work was supported by the Türkiye Bilimsel ve Teknolojik Araştırma Kurumu [1059B192202739].