Short Review in Green Vehicle Routing Problem with Pick-up and Delivery and Time Windows Using Metaheuristics

2.1. Vehicle Routing Problem and its Variants

The Vehicle Routing Problem (VRP) was first introduced in 1959 [2]; this problem is considered as an important NP-hard combinatorial optimization problem in logistics and operational research. The main goal of classical VRP is to find the optimal routes for a fleet of vehicles that must start and end at a central depot to serve a set of customers to minimize operational costs. Since VRP is NP-hard, the computational feasibility of solutions is complex with increasing problem size; in practice, heuristics and metaheuristics are applied to serve this complexity and provide optimal solutions.

The literature on VRP research is growing, and this article will purposefully and quickly examine some of it. It established the truck dispatching problem, proposing a paradigm in which a single operations center supplies a fleet of uniform vehicles with the gas needed by several locations [2]. The goal of this concept was to reduce the truck drivers' distances between the stations.

Later, this subject was expanded [4] into a linear optimization issue, which typically addressed logistics and transportation operations incorporating a group of clients, depots, and a collection of vehicles. One of the earliest works closely resembles modern VRP models [4]. Subsequently, researchers in this domain have explored techniques and frameworks to enhance the routing issue and provide superior solutions. Models of routing problems were proposed [5], taking into account varying speeds and being time-dependent. Incorporating time-based features into VRP models was a significant milestone.

The VRP has been extensively studied by researchers. An overview of earlier research up to 1992 on classic VRP models, including exact algorithms and heuristic algorithms [6].

Research [7] examined the generic version of the TSP issue, known as the multiple traveling salesman problem (mTSP). The current VRP was developed as a consequence of this dilemma, which allows several salespeople to sell goods in a distribution chain. Reducing transportation costs was, nevertheless, a primary focus of VRP issues until recently.

The following flowchart represents the variants of the VRP:

Fig. (1) provides a complete categorization of the VRP and its extension, including the GVRP, highlighting their structural variations. It organizes the problem into specific configurations based on parameters such as the number of routes (single or multiple), vehicles (single or multiple), depots (single or multiple), fleet type (homogeneous or heterogeneous), vehicle capacity (limited or unlimited), delivery type (single or pick-up and delivery) and the presence of time constraints (with or without time windows). GVRP emphasizes sustainability by focusing on minimizing environmental impacts, such as CO₂ emissions, making it a central model for environmentally friendly logistics. This classification framework facilitates solution approaches for various logistics scenarios, particularly in the field of sustainable transport.

In this paper, we study the combination of the GVRP extension with the two variants Pickup and Delivery, and the time windows, which represent our GVRPPDTW variant.

2.2. Green Vehicle Routing Problem Pickup and Delivery with Time Windows

The GVRP is a concept introduced in 2012 as an alternative that takes into consideration the environmental damage caused by greenhouse gas emissions; this work demonstrated the feasibility of optimizing routes while accounting for environmental constraints, providing the foundation for future research in green logistics [8].

Additionally, a suggested heuristic technique produced an acceptable degree of accuracy when solving VRP, including PD. As was previously indicated, there are significant savings when commodities are picked up and delivered via common routes; however, this has not been well studied [9].

Researchers have recently shown a great deal of interest in GVRP because of its possible economic and environmental advantages. The goal of GVRP is to lower vehicle carbon dioxide emissions using a variety of techniques. For example, a study [10] conducted research that examined ways to lower carbon dioxide emissions. They proposed a model that balanced the conflicting objectives of maintaining financial profits and lowering pollution by using a capacitated vehicle routing issue and a multi-objective optimization approach. Furthermore, an environmental viewpoint on capacity constrained VRP with time windows. The model was based on a reasonable distribution arrangement and included variable speed restrictions for different times of the day [10, 11].

The Pick-Up and Delivery Problem (PDP) is a VRP variant considered a logistics and optimization challenge commonly encountered in transportation, supply chain management, and distribution networks. It involves designing efficient routes for vehicles to fulfill a set of transportation requests, where each request requires an item to be picked up at one location and delivered to another. Fig. (2) below represents a scheme of a network of PDP transportation.

The GVRPPDTW aims to minimize costs by efficiently allocating vehicles and routes, taking into account PD, vehicle load, time specifications, and ecological constraints. GVRPPDTW is focused on distributing and collecting items within a time-constrained transportation network. The PD system describes how the vehicle meets the demand at the destination node. The time windows reflect the specific periods when the fleet arrives at the customer's node. Each truck is required to adhere to two sorts of time windows to deliver items to clients within a specific period. The environmental impact represents the CO₂ emission reduction. The vehicle might not arrive at the client's location before opening time or after closing. The optimum path should be timely, fulfill capacity needs, and reduce distance and cost [12].

In Table 1 below, we present the works that have dealt with GVRPPDTW using metaheuristic approaches, focusing on the objective function studied, the metaheuristic method used, and the typology of the algorithm (H: Hybrid, S: Single).

Based on the above table, we observe that the GVRPPDTW is a highly relevant and contemporary research topic. The majority of the studies have been conducted within the past five years, highlighting the growing interest in this field and providing an opportunity to identify research gaps that can be addressed in future work. Additionally, we note that most studies have utilized the Genetic Algorithm, reflecting its adaptability for large-scale problems and its flexibility across various domains. In the following sections, we will present a comparative analysis of the most commonly used algorithms in these studies and discuss the results they have achieved.

3.1. Problem Definition

We have based our research on various studies of the GVRPPDTW. It is important to note that most potential constraints have been proposed in the past two decades, especially when sustainability is considered one of the most challenging aspects that should be integrated into the optimization of this type of logistics problem.

GVRPPDTW problem is a significant logistics issue in many applications, including beverage distribution, container transport, and so on. In today's competitive market, companies are increasingly focused on reducing total costs. The supply chain network consists of n nodes (customers and suppliers) and a single depot. The optimization model involves assigning the different nodes to different routes, minimizing the total distance traveled. The goal is to minimize the overall cost of transportation while fulfilling all consumer requests. This expense is correlated with the quantity of vehicles utilized and the distance traveled by every vehicle while respecting each customer's time window.

3.2. Mathematical Model

Let a graph be G = (N, A).

N = {i ∈ N/i = 0,1, 2,…,n} is the node-set, where n indicates a location.

The depot is indicated by node 0.

We have a pair of PD sites for each request. Let;

N⁺ = {i ∈ N / i =1, 2,…, n/2}: pick-up locations

N^- = {i ∈ N / i = (n/ 2) + 1,…, n} delivery locations.

In GPDPTW, the objective is to design a set of routes in such a way that:

(1) Only one vehicle at a time may satisfy a node (supply or customer);

(2) There is just a single depot;

(3) Constraints on capacity must be maintained;

(4) There are strict constraints for arrival times;

(5) Every vehicle leaves the depot at the beginning of its journey and should return to the depot at the end.

While the request is processed, the vehicle stays stopped at a node.

A vehicle should wait if it arrives at node i before the start of its period (a_i).

GVRPPDTW is expressed mathematically as a combination of a few studies [21, 22] and [11].

The following parameters describe the problem:

N: A list of the depot, supplier, and customer nodes;

N': List of nodes for suppliers and customers;

N⁺: list of the nodes that provide;

N^-: Each customer node;

K: Number of vehicles;

d_ij: The distance between nodes i and j; if d_ij = ∞, there is no path between i and j (dead end, pedestrian street,...);

t_ijk: The amount of time it takes for vehicle k to get from node i to node j;

(a_i, b_i): The time window for each node i;

st_i: Time stopping at node i;

q_i: Quantity to be processed at node i

If q_i > 0, the node is a supplier;

If q_i < 0, the node is a customer;

If q_i = 0 then the node has been served.

W_k: Capacity of vehicle k,

i = 0..N: Index of predecessor nodes,

j = 0..N: Index of successor nodes,

k = 1..K: vehicle index,

X_ijk: 1 If vehicle k travels from node i to node j else 0

A_i: Arrival time at node i,

y_ik: Amount in vehicle k that is at node i;

C_k: The vehicle k's transportation cost.

Our objective function is to minimize the total cost of each vehicle from i to j:

The environmental aspect of the GVRPPDTW is quantified through CO₂ emissions, which are calculated based on fuel consumption influenced by various transport-related factors. Here is a formulation for the GPDPTW that incorporates the time window, total tour duration, vehicle capacity, service time, and fuel consumption rate to minimize CO₂ emissions. The formula for fuel consumption, detailed [22], depends on the vehicle's load and the distance driven.

To calculate the rate of fuel consumption, we used the formula below:

Such as:

∂: the CO₂ emission factor according to the type of fuel

p: full load fuel consumption rate

p₀: initial fuel consumption rate with an empty load

q: distance traveled on arc ij

q_ijk: the load of vehicle k when it traverses arc (i,j)

W_k: The total capacity of vehicle k

So our second objective function will formulated as:

Now, we can deduct the total objective function: (Eq. 1)

(1)

Subject to:

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

(13)

(14)

Eqs. (2 and 3) confirm that a single vehicle serves each node. Eqs. (4 and 5) ensure that a vehicle's availability is not exceeded, meaning that a car only ever departs and returns to the depot. The node visited must likewise be departed from, according to Eq. (6), which guarantees the continuation of a vehicle tour. It is ensured by Eqs. (7-9) that a vehicle's transport capacity is not exceeded. Eqs. (10 and 11) ensure that precedence constraints are respected. Finally, Eqs. (12-14) verify that time windows are respected.

4.1. Evolutionary Algorithms

This category of algorithms is inspired by the behavior of Darwin’s theory of evolution. Each iteration in such an algorithm is known as a generation and is composed of parent selection, recombination (crossover), mutation, and survivor selection. While crossover and mutation are responsible for the exploration, parent, and child selection brings out the exploitation. One of the most popular evolutionary algorithms is the Genetic Algorithm (GA), first introduced in 1975 [24], by researchers who had developed an optimization method that mimicked the process of natural evolution. Each solution in a population was assigned a fitness value, and the algorithm iteratively bred new populations to search for optimal or near-optimal solutions. In 1989, a study [25] extended the first work in GA to reach the application of this algorithm in engineering problems. By the year 1992, the concept of GA had been developed into Genetic Programming (GP), where the evolved solutions were not fixed-length chromosomes but programs or functions represented as trees [26]. Later, in 2002, x the researchers proposed the NSGA-II (Non-dominated Sorting Genetic Algorithm II), one of the most efficient and widely used algorithms for multi-objective optimization [26, 27].

4.2. Swarm Intelligence-based Algorithms

This second category of metaheuristics algorithms, known as swarm intelligence, is inspired by the way social animals communicate and share knowledge within a group during the optimization process. These swarm algorithms (SA) are modeled on the collective behavior of animals and insects, such as ants and bees. The core idea behind these algorithms is that the information exchanged among individuals in the swarm directly influences each agent’s movement and decisions. By managing the flow of information between agents, swarm algorithms achieve a balance between exploration and exploitation. The first formal introduction of swarm intelligence as a concept was in 1989 [28]. The Ant Colony Algorithm was first introduced [29], inspired by the foraging behavior of real ants, which deposit pheromones to mark good paths to food sources. Artificial ants mimic this process, with pheromone trails guiding their search for optimal solutions. Later, in 2005, the Artificial Bee Colony was developed [30]; this algorithm has been widely applied to optimization problems, such as scheduling, function optimization, and clustering.

4.3. Physics-based Algorithms

The third category of metaheuristic algorithms consists of physics-based techniques, which replicate natural physical principles to guide the optimization process toward the best solution. These techniques are inspired by the fundamental laws of physics. One of the most widely used algorithms in this category is Simulated Annealing (SA), modeled after the metallurgical process of annealing, where materials are heated and then slowly cooled to minimize energy and reach a stable, optimized structure. The first time introduced the Simulated Annealing Algorithm was in 1983 by [31], who applied it to the

Traveling Salesman Problem (TSP) and demonstrated that the algorithm could escape local optima and converge to global solutions.

4.4. Human-based Algorithms

This category of algorithms is related to techniques inspired by human social behavior, decision-making processes, and problem-solving strategies. One of the most notable human-based algorithms is the Teaching-Learning-Based Optimization (TLBO), introduced in 2011 [32]. TLBO models the relationship between a teacher, which is considered “the best solution,” and students, considered “individual solutions,” allowing individuals to improve by learning phases.

In what follows, we have conducted a comprehensive comparison of four prominent metaheuristics—Genetic Algorithm (GA), Simulated Annealing (SA), Tabu Search (TS), and Local Search (LS)—that are widely employed for addressing GVRPPDTW. Table 1 shows that these are the algorithms most frequently used in works already dealing with GVRPPDTW.

Based on our literature review, each metaheuristic offers distinct advantages and limitations in optimizing complex routing scenarios while considering environmental factors and logistical constraints. GA excels in exploring large solution spaces but may suffer from slow convergence, whereas SA's probabilistic approach aids in escaping local optima but requires careful parameter tuning. TS provides robust solutions by intensively searching the solution space but may struggle with computational complexity, while LS efficiently improves solutions through iterative local improvements but may be sensitive to initial conditions. By evaluating these metaheuristics comprehensively, we aim to provide insights into their applicability and effectiveness in enhancing the sustainability and efficiency of vehicle routing operations under green logistics initiatives.

We have provided more details in Table 2 below.

We will present in the following Table 3 the results of these four algorithms as applied to the context of the GVRPPDTW, based on our analysis of previous studies. This discussion will provide insights into their performance, strengths, and limitations, highlighting how each algorithm contributes to addressing the complexities of the GVRPPDTW.