Metaheuristic algorithms for multi objective vehicle routing problem

Abstract

Keywords: Alternative Links; Adaptive Large Neighborhood Search Algorithm; Simulated Annealing Algorithm; Sustainability; Vehicle Routing Problem

Introduction

Although vehicle routing problem (VRP) is an old problem, it is still studied by researchers. VRP still has a wide range of applications in different industries. Reducing CO2 emissions, one of the main factors of global warming, has also become an important issue for companies. In addition, transporters are bound by the legislation enforcing driver working hours. Also, unbalanced working hours might create problems among the workers and it may cause a trust problem towards the firm [1-3]. With the increasing sensitivity to environmental and social issues in recent years, these objectives are

considered together with financial objectives [4-6]. Motivated by these issues, vehicle routing problem considering financial, environmental, and social objectives are considered. In general VRP studies in the literature, it is assumed that there is only one direct link between each pair of nodes in the network [7]. However, in reality, there may be more than one direct connection between two nodes. In Figure 1, the first value on each link denotes the length of the link (in km) and the two values inside the parentheses denote two different speed levels (in km/hour) that the vehicles can choose to go on that link. Besides, these alternative

*Corresponding author. *E-mail address: ilknur.tukenmez@btu.edu.tr This paper was recommended for publication in revised form by Editor-in-Chief Ahmet Selim Dalkilic Published by Yıldız Technical University Press, İstanbul, Turkey © Author. This is an open access article under the CC BY-NC license (http://creativecommons.org/licenses/by-nc/4.0/).

Sigma J Eng Nat Sci, Vol. 44, No. 1, pp. 140−152, February, 2026

links might have different features as lengths, durations, and costs. For example, a short road might require a longer time due to traffic. Similarly, some roads require additional payments, leading to higher costs, or some roads may cause more CO2 emissions due to speed limits. In literature, even though the existence of alternative roads between different points is acknowledged, the shortest or the fastest of these roads is taken as a single link in the model, and the other alternatives are omitted, assuming that longer or slower roads will never be chosen based on the model objectives [8]. However, alternative links between nodes are studied by [9-11]. However, in real life, the shortest roads are not always the best ones due to speed limits, traffic jams, or toll roads. Depending on the objective function and constraints of the model, a faster but longer road might be chosen to go from

Figure 1. Sample of alternative links and speed choices between nodes.

one node to another node, even if a shorter road may be in the same network. As it is seen in Figure 2, 0 represents depot, 1 and 2 are customers. When there is no time window restriction in Figure 2 part of A, route is 0-1-2-0, and the length of selected alternative links are 20, 10 and 15, and selected speed levels are 50, 40, and 50. However, if there is time window restriction for node 1, the route is still the same, but, the selected alternative link is changed. In Figure 2 part of B, the selected length between the node of 0 and 1 is 50, and the selected speed level is 90. If the time window restriction is relaxed a little, the selected speed level between 0-1 could be 60 while the route and alternative links remain the same. In the literature, according to the objective functions and constraints, different types of VRP are found. However, the mostly papers that are related to our study are analyzed [6,12,13] review different types of VRP literature [14-16]. Also review the literature about green vehicle routing problem (G-VRP). The aim of G-VRP is minimizing CO2 emissions or fuel consumption [17]. Solve multi-objective G-VRP with the iterated local search algorithm. Cost, fuel consumption, and distance equity are considered as an objectives [18] add different carbon emission policies into the inventory routing problem with minimizing inventory holding cost, transportation cost, and fuel consumption cost [19]. Minimize operational and environmental costs for the green capacitated location-routing problem [20]. Study the time-dependent vehicle routing and scheduling problem to minimize CO2 emissions and develop an exact dynamic programming algorithm [21] are also interested in carbon emission. Speed of vehicle is separated into ranges, and so model linearized [22]. Compares metaheuristic algorithms for time window G-VRP. When looking the results, greedy randomized adaptive search procedure (GRASP) and ant colony optimization (ACO) gives better results than tabu search (TS) and variable neighborhood search (VNS) [23]

measured releasing CO2, NOx, CO with time-dependent Open-VRP [24]. Minimize total fuel cost and driver cost with a heterogeneous vehicle fleet [5] analyze the relationship between load and CO2 emissions using a heterogeneous fleet of vehicles. They show that, the used vehicle type, curb weight, and carried weight affect the fuel consumption used genetic algorithm and weighted superposition attraction algorithm to solve green VRP [25,26]. State that the vehicle type, speed, and load capacity affect the objective functions composed of distribution cost, customer satisfaction, and environmental pollution with adding time windows and heterogeneous vehicle fleet [27]. Also analyze the effect of different speed choices on fuel consumption and route times [28]. Study the time-dependent pollution routing problem to minimize total fuel cost and driver wages. They attract attention to rising driver wages because of low speeds in congested traffic at certain hours consider the green open vehicle routing problem with time windows [29]. Since the classical VRP is NP-Hard, heuristic and meta-heuristic methods are generally used in the literature to solve these problems [30]. States that the optimal solution is difficult to find with more than 10 nodes and thus presents an approximation algorithm for the solution of his models [31]. Develop an adaptive large neighborhood search (ALNS) heuristic for the pollution routing problem, and they offer a speed optimization algorithm to minimize fuel and driver costs [32]. Also employ an ALNS algorithm to solve a bi-objective pollution routing model that minimizes fuel consumption and delivery time [33]. Consider fuel emission cost and driver cost as an objective function of (G-VRP) with stochastic demands [34]. Hybridized genetic algorithm (GA) and VNS to cope with time-dependent GVRP with multiple depots and time windows [35]. Solves multi-objective GVRP fuzzy distances and split-delivery by using GA [36]. Solved multi depot green VRP with using ALNS. Two speeding up methods are used, and results are better than classic algorithm. As different perspective, [37] used multiple-depot to decrease carbon emission [38]. Combined GVRP with disassembly line problem. Several multi criteria decision making methods are used to determine best pareto optimal solutions [39]. Minimizes total cost and fuel consumption, and problem solves with strength pareto evolutionary algorithm (SPEA2) and Non-dominated Sorting-based Genetic Algorithm (NSGA-II). When comparing results, NSGA-II gives better results. As a different perspective, [40] considered the cost of perishable products along with the financial cost. To solve time-dependent GVRP, VNS and GA is hybridized [41]. Considered energy consumption, partial re-charging policy and carbon emissions simultaneously for Electric VRP, and ALNS and Cplex are used to solve the problem [42]. Used two construction algorithm and SA algorith to solve VRP with simultaneous linehauls and backhauls used GA and ACO to solve multi depot VRP [43]. In the literature, generally financial and environmental objectives are considered, and social considerations are studied less than others [44]. Considered economic,

Sigma J Eng Nat Sci, Vol. 44, No. 1, pp. 140−152, February, 2026

environmental, and social objectives simultaneously in facility location problem focus on environmental and social issues in multi-objective VRP [4]. Present an integer linear program for the balanced VRP and a rank-based ant system algorithm for the solution of their model [45,46]. Analyze a multi-depot vehicle routing problem with simultaneous pickup and delivery with the aim to have a balanced distribution of travels. They include the total routing cost, penalty cost for overworking of drivers, and fix costs of drivers’ employment in their objective function [47]. Study a bi-objective capacitated general routing problem solved VRP with using Particle Swarm Optimization (PSO) and ACO that takes into account route balancing handeled fresh cut flowers delivering problem [48-50]. Initial solution is obtained with the path cheapest arc heuristic, after solution is improved with guided local earch algorithm. Different from classical algorithms, [50] used conditional neural heuristic algorithm to solve multi objective VRP. In addition, [51] used deep reinforcement learning based algorithm to solve green VRP. Companies should regulate and comply with the laws of working and resting hours [52]. Notes that while regulations on drivers’ working hours significantly affect total travel times, the vehicle routing literature has largely overlooked these restrictions. They describe the regulations for drivers’ working hours in the European Union and present the vehicle routing problem considering these regulations [1]. Presents a model showing how driving periods, breaks, resting periods, and processing activities can be scheduled, and proposes a large neighbourhood search algorithm to create vehicle tours complying with the new regulations released by the European Union in 2007 [3]. And [2] also consider social legislations. [53] also study multi-objective GVRP as a financial, environmental and social objectives, and biased-randomized iterated greedy algorithm used to solve the problem. Financial cost consist of fixed vehicle costs, driver wages and fuel cost, the environmental cost is correlated with fuel consumption, and finally, social cost is accident risk cost. In this study, like [10], and [11], minimizing the fuel cost, drivers cost, and fixed vehicle cost are considered as the financial objective for the company, minimizing the CO2 emissions and oil usage are considered as the environmental objective, and the balancing drivers’ working hours and adjusting route times are considered as the social objectives. Which routes, which alternative links, and which speed choices will be selected are determined by considering the financial, environmental, and social objectives. Although the problem is discussed in this study is the same as [11], unlikely, to solve middle and large data sets, and different scenarios, heuristic algorithms are used in this study. In the next section, the problem is defined and model is explained. Then, in section 3, the Simulated Annealing (SA), and ALNS heuristic methods are presented to solve the problem. In section 4, numerical experiments with a discussion of the results are presented, and finally conclude our study in section 5.

Sigma J Eng Nat Sci, Vol. 44, No. 1, pp. 140−152, February, 2026

Problem Definition And Model

For a given set of n demand nodes and a depot, a directed graph is defined on these nodes. In the classical VRP problems, a single arc (i, j) is defined between a pair of nodes i and j. However, in our study, for more than one arc between each pair of nodes i and j is allowed, thus the notation (i, j, k) is used, where k denotes one of the alternative links between nodes i and j. Each link is assumed to have a distance denoted by dijk, and xijk denote the binary variable that is equal to 1 if a vehicle goes from i to j through link k. In addition, each vehicle can choose a different speed on each link and vijkn denotes the binary variable that is equal to 1 if a vehicle goes from i to j through link k at speed level n, and 0 otherwise. The possible speed levels that can be chosen at each arc are different from each other depending on the type of the arc. While vehicles can go at higher speeds on some arcs (i.e. highways), they need to choose slower speeds at others (i.e. inside the city). However, since faster roads might also be longer or more costly, the choice of the link depends on the parameters, constraints and the objectives of the problem. Even though different links have different characteristics, it is assumed that these characteristics are not time-dependent. Time-dependent speed choices and durations can be incorporated into the model, however since our focus is not on time-dependency, it is leaved for future studies as it makes the problem much more complicated and the solutions much harder to obtain. In this model, each demand node i has a demand quantity, denoted by qi, and if a demand node is visited, all of its demand needs to be delivered. In other words, partial delivery is not allowed. It is assumed a homogeneous fleet of vehicles and each vehicle is assumed to have a fixed capacity Q. In addition, time windows are considered in our problem, such that a delivery to a node i can only be made between times ai and bi, the earliest and latest service times for node i, respectively. If a truck arrives to a node before time ai, it needs to wait there until time ai, and it is not allowed to arrive a node i after time bi. ti is denoted the delivery service time at node i, such that each truck spends ti time units at node i to make the deliveries. RT denotes the allowed regular time for a route and if the total duration of a route exceeds the value of RT, the drivers need to make overtime and an overtime cost is applied. The indices, parameters, decision variables of the model are defined in the [11] as follows: Indices: i, j: Indices used for demand nodes k: Index used to denote alternative links between nodes n: Index used to denote the speed level Clusters: N=(0,…N) Set of nodes, 0 denoting the depot N0 = N/{0} Set of customers Nh = Set of speed levels K = Set of arcs

Parameters: qi: Quantity of demand at node i ai: the earliest service start time for node i bi: the latest service start time for node i Q: Vehicle capacity ti: Service time for node i m: Number of available vehicles M: A large number used in modeling fv: Cost per vehicle used fd: Cost of overtime for drivers on a route per unit time fs: Cost of drivers/vehicles per unit time fe: Social cost of unbalanced routes per unit difference fa: Social cost of overtime per unit time fb: CO2 emission(kg/lt) dijk: Distance between node i and j through link k Sijkn: Speed level n at link k between nodes i and j RT= Allowed regular time per route Decision Variables: xijk: Binary variable equal to 1 if a vehicle goes from i to j through link k; 0 otherwise vijkn: Binary variable equal to 1, if a vehicle goes from i to j through link k at speed level n; 0 otherwise fijk: Flow carried from i to j through link k yi: Start time of service at node i sj: Total time of a route when j is the last node of the route oj: Amount of overtime on a route eij: Difference between route times, when i and j are last nodes in two different routes Z: Objective function. It is known that the amount of fuel consumption depends on the speed of the vehicle, as well as the load of the vehicle, among others. Emissions and fuel consumption is computed using comprehensive modal emissions modelling (CMEM) developed by [54]. CMEM assumes that the vehicle is in a steady state between two consecutive locations and thus the vehicle’s speed is assumed to be constant [55]. Examine the precision of carbon emission and fuel consumption calculations in green vehicle routing. Even though speed fluctuations and real life driving conditions are seen to have an impact on the results, CMEM computations are widely used in literature and generally thought to provide a good estimation of fuel consumption under realistic driving conditions. Thus, assuming that the vehicles maintain a constant speed between any two nodes, the average speed is used in our model as an approximation to the exact consumption values, which is a common approach in the literature [31]. Use CMEM and present the relationship between fuel consumption, speed and load. They calculate the amount of fuel consumption depending on the speed, load, and other factors as below:

Sigma J Eng Nat Sci, Vol. 44, No. 1, pp. 140−152, February, 2026

In the above relation, v denotes the speed, d denotes the distance, f denotes the load. In addition, λ= ξ/кψ, λ = 1/1000 ntfη, α = τ + gsinθ + gCr cosθ, β = 0.5 CdρA are the values calculated using the constants given in Table 1. Most of the data provided in Table 1 are obtained from [31]. It is assumed that the acceleration and the angle of the road denoted as τ and θ, respectively, are assumed to be 0. Using the notation above and the decision variables in our model, the amount of fuel consumption is written as below:

For the objective functions, financial, environmental, and social costs are considered in our model. The economic cost of fuel consumption (fcFC), the cost for regular time, and overtime costs of drivers/vehicles (fs∑jsj + fd∑joj), and the fixed cost for the number of drivers/vehicles used (fv∑j ϵ N0 x0jk ) are considered as the financial cost. Since the

amount of fuel consumption defines the CO2 emissions, the environmental effect is calculated by multiplying FC with the emission factor, fb. Thus, fbFC is considered as the environmental cost. For the social cost, the overtime of drivers is considred firstly, which is socially undesirable. As the working hours of the drivers’ increase, they become more tired on the road and this will increase the risk of accidents. In addition, driving hour regulations in some countries enforce certain constraints on the tour durations. Even though tour durations are not considered as hard constraints in our model, as soft constraints such that any additional time over the regular working hours is penalized in the objective function is used. Thus, have as little overtime for the drivers as possible is aimed firstly. In addition, balanced route times between different drivers are desired. Unbalanced working hours lead to discussions between drivers and the company, and result in an unpleasant working environment. Sometimes drivers are paid by the duration of their services and the drivers who are assigned fewer driving hours than others tend to complain about the fairness of the managers. On the other hand, sometimes drivers who are assigned more driving hours also complain about the long working hours, especially when the additional payments they get do

Table 1. Definition of parameters and their values from real life data Notation

Sigma J Eng Nat Sci, Vol. 44, No. 1, pp. 140−152, February, 2026

not justify the additional working hours. Thus, have balanced durations between routes are aimed. The differences between the durations of the routes, denoted as eij where i and j are the last two nodes in two different routes are calculated, and si and sj are the total time of a route. Include these values as social cost factors in the objective function in order to obtain more balanced routes. As a result, the social cost of overtime for drivers with the social cost of unbalanced routes (fa∑joj + fe∑i,jei,j) are considered as the social objectives to be minimized. Thus, the model is developed in a multi-objective setting as follows.

The objective function contains financial, environmental and social objectives. (2) represents the fuel cost, regular and overtime costs for routes and fixed vehicle costs as the financial cost, (3) represents emissions associated with the fuel consumption amount as the environmental cost, and (4) represents the overtime cost of drivers, and the penalty cost for imbalances between route times as the social cost. Constraints (5-7) and (8) ensure that all vehicles leave from and return back to the depot, visiting each customer only once. (9) and (10) calculate the carried load at each node and make sure that each customer’s demand is satisfied. They also eliminate sub-tour formations in the solution. (11) and (12) calculate the service time and total route time, respectively. (13) ensures time window constraints. (14) guarantees that one-speed level is selected for each arc. (15) calculates the overtime for each route. (16) and (17) calculate the differences between route times. Finally, (1820) are nonnegativity constraints.

Metaheuristic Algorithm For VRP With Alternative Links

Showed that middle VRP can not be solved for exact methods. Because of that, it is needed to heuristic methods. In literature, there are many heuristic methods for VRP [56-63], used SA for different kind of routing problems [36,41,64-66], used ALNS algorithm to solve VRP. In this study, because of giving good solution for combinatorial optimization problems, and remarkable success of ALNS and SA algorithms in routing problems, both of them are used to solve the problems. SA is a stochastic search method. It is inspired by the annealing process of solids. Solids heat until a definite temperature, it is kept this temperature for a while, and it cools slowly. Different temperatures and cooling rate can be used. SA is introduced by [67,68] modified LNS by using different searching methods, and named ALNS. In ALNS algorithm, probability of selecting a neighborhood changes according to past performance in the searching process. The detailed structure of ALNS is explained in the algorithm. A mathematical model is used to solve this problem. For 20, 50, 75 and 100 nodes, and different scenarios are tried to

solve. But, the best solution can not be found within a time limit (3 hours). In our study, SA, and ALNS does not have start with a feasible solution. If a solution does not ensure constraints, penalty cost is incorporated into the objective function for each instance of infeasibility. Therefore, with every iteration, the result is close to a feasible solution. Initial solutions are generated using the Cheapest Insertion algorithm. The Cheapest Insertion Algorithm To find initial solution The Cheapest Insertion Algorithm (TCIA) is used. When starting with a better solution than a random solution, a better solution can be obtained with fewer iteration numbers. In addition, in most of the scenarios covered in this problem, there are time window constraints. In addition, a good solution based on a fit-only objective function may be far from a solution with time window constraints. With TCIA, compliance with time window constraints is also ensured. Initially, the vehicle starts the route from depot, and ends at the depot. Randomly a node is selected, and inserted to the route, and the best alternative link and speed is selected in accordance with the objective function. Until all nodes are inserted to the routes, every node is inserted between node i and j, and the objective function is calculated for every i-j position, and the best position is selected. This obtained solution is the initial solution of SA and ALNS. Simulated Annealing Algorithm Input: Demand, speed, distance, time windows, service time, initial temperature (T), cooling rate (t), iteration number (Y), and initial route values. 𝑋best←𝑋now←𝑋initial; T=T; While T<1 y=1; for y=1 to Y Generate 𝑋new If 𝑋new<𝑋now; Xnow←𝑋new; Else if v=𝑒−(𝑋new−𝑋now)/𝑇; Generate a random value(a) a ϵ [0,1]; If a<v; 𝑋now←𝑋new; End If End If; If 𝑋now<𝑋best; 𝑋best←𝑋now; End If y=y+1; T=T*t; Output: 𝑋best Adaptive Large Neighborhood Search The ALNS algorithm has four main components in [69,70] and same format is followed.

Sigma J Eng Nat Sci, Vol. 44, No. 1, pp. 140−152, February, 2026

Large neighborhoods: The current solution is changed by using seven neighborhood search procedures. These procedures are given in section 3.1. After modifying, the best link and speed levels are identified according to multi-objective functions. If there is any infeasibility due to capacity or time constraints, penalty cost is added to the objective function. Adaptive search engine: In each iteration of the algorithm, the neighborhood search procedure is chosen using a roulette-wheel mechanism. Each neighborhood is assigned a weight, determining its probability of selection. After a certain iteration, the weight of neighborhood is changed according to past performance of the neighborhoods in selecting new current solutions. Let wv be the weight of neighborhood v depending on its past performance. The neighborhood is selected with probability (NoN: Number of Neighborhoods defined in algorithm). Adaptive weight adjustment: Initially, each neighborhood has equal weight, and same probability of being selected. The iteration number of algorithm is divided into several phases that contains the same number of iterations named Ω. After finishing each phase, the weights of the neighborhoods wv are updated as reported by their performance of the current phase. The performance of each neighborhood is represented by πv, for neighborhood v. After finishing each iteration, the mark of the neighborhood selected at that iteration is updated as below, where α1, α2, α3 are integer numbers that α1> α2> α3, xnew is the new solution, xbest is the best solution, xnow is the current solution, and z is the objective function to be minimized. Generally ALNS is used SA based algorithm. if znew < zbest: πv: πv+ α1 else if znew < znow : πv: πv+ α2 else if znew is accepted as the next current solution by the SA criterion: πv: πv+ α3 else: πv: πv end if The aim of this process is enhancing probability of selecting the neighborhood v with better solution. After finishing each phase the weights are updated as follows:

ovj is the number of times neighborhood v is selected in the current phase j, and η is a controlling factor that affects the current weights. In our algorithm, the lenght of phase is 200, 300, 400 and 500 for 20, 50, 75 and 100 nodes respectively. The update score α1, α2, α3 is 6, 4 and 2 respectively. The controlling factor η is 0.3. When η is greater than 0.3,

Sigma J Eng Nat Sci, Vol. 44, No. 1, pp. 140−152, February, 2026

results are not of good quality. If η is less than 0.3, there will not be much difference between SA and ALNS. Stopping criteria: Stopping criteria is defined as an cooling temperature. Neighborhood Search Procedures Different neighborhood structures are used in VRP to enhance the quality of the solution, [70] are used some destroy and repair procedures. Some of them are used in accordance with the problem. Link-Speed Change: One route is selected, and one node is selected in that route. The best links and speed levels according to objective function between previous and next nodes are found and selected. Interroute 1-0 move: As seen in Figure 3-A, different two routes are chosen, and two nodes are chosen each selected route. A node at the first route is taken out, and this node is added at the second route after the selected node. Interroute 1-1 exchange: As seen in Figure 3-B, different two routes are chosen, and two nodes are chosen for each selected route. These nodes are swapped. Interrote 1-1-1 rotation: As seen in Figure 3-C, different three routes are chosen, and three nodes are chosen for each selected route. These nodes are swapped. Swap: As seen in Figure 3-D, one route is selected, and one node is selected in that route. Swap two nodes (before and after node of the selected node). Interroute 2-opt move: Two different routes are selected, and two nodes are chosen from each route. All the nodes following the chosen nodes are then swapped between the routes. A new objective function(𝑋new) value is calculated. For example, routes are: 0-1-2-3-4-0, and, 0-5-6-7-8-0, after procedure new routes are: 0-1-2-7-8-0, 0-5-6-3-4-0. Intraroute 2-Opt: As seen in Figure 3-E, one route is selected, and two-node is selected in that route. Those nodes between two nodes are reversed, ann connected again. For example, the route is: 0-1-2-3-4-5-6-0. 2 and 5 are selected.

2-3-4-5 is reversed, turned to 5-4-3-2, and connected again. Finally, route is 0-1-5-4-3-2-6-0. After implied neighborhood searching procedures, at new routes, the best link and speed levels between previous and next nodes are calculated and selected according to the multi-objective functions. According to link and speed values, the earliest starting service time is specified. If the starting service time exceeds the latest starting service time, the penalty cost is added to the objective function. Also, the new total demand of routes is calculated. If total demand exceeds the vehicle capacity the penalty cost is added to the objective function.

Numerical Results And Discussion

In this section, the computational results of the models are presented and explained above under different parameter settings. All the results in this section are obtained by solving the models using GAMS with the solver Cplex on a workstation with an Intel(R) Xeon(R) CPU E5-1650 v2 @ 3.50GHz, and 16 GB of RAM. [11], find optimal solution of 10 nodes. But, for larger problems, optimal solutions can not be found within a reasonable time limit by using GAMS, Cplex solver. Because of that, in this study, 20, 50, 75 and 100 nodes are tried to solve using SA and ALNS. In this case studies, a logistics company that serves different customers in Turkey at various locations and needs to deliver the products in the required time windows is considered. In all of models in this study, the same parameters are used as in the previous section and the data given in Table 1. In addition to the real-life data given in Table 1, it is assumed that RT=9 hours, ti=20 minutes for all nodes i, and fa=1.5 Turkish Lira (TL) per minute. Different scenarios are considered as explained below and the results of each

Sigma J Eng Nat Sci, Vol. 44, No. 1, pp. 140−152, February, 2026

scenario for 20, 50, 75 and 100 nodes respectively are presented in Table 2, Table 3, Table 4 and Table 5. The flexible time window is between 0 and 10 hours for all customers. For base case time windows there are 3-4 hours between early and late starting service times for these customers. In strict time windows, there are 2-3 hours between early and late starting time windows. For SA, T is used as a 300, t is 0.9, and y depends on the customer dimension, 1200, 1400, 1500 and 1800, is used for 20, 50, 75 and 100 nodes respectively. For each sample, SA was run 10 times and the best result is given. One cycle for 20 nodes is completed in an average of 180 seconds. For 50,75 and 100 nodes, this time averages 310, 500, and 620 seconds, respectively. For ALNS algorithm, T is used 900, t is 0.98, and y 200, 300, 400 and 500 for 20, 50, 75 and 100 nodes respectively. Since the weights of the neighborhood structures change after each phase, the number of iterations at each temperature is not increased much, the starting temperature of the algorithm is increased when comparing SA. When ALNS and SA are runned at the same iteration ALNS does not give close results to SA. Therefore, cooling temperature to stop is decreased, and iteration number is increased. When results does not change, it is stopped. Solution times of

ALNS are 200, 320, 600, 800 seconds for 20, 50, 75 and 100 nodes respectively. When number of nodes increases, problem can not be solved with exact methods, and GAP becomes so large. In addition, increasing the cost multiplier greatly increases the value of GAP. For exact method, 3 hours time limit is used. GAP values obtained with GAMS-Cplex solver are 12.8%, 17.5%, 7.36%, 15.8%, 32%, 94.6%, 97%, 90% for scenarios of 20 nodes respectively. As the number of nodes increases, larger GAP values appear. In this situation, the quality of metaheuristic algorithms are not compared with these GAP values. All of the samples the best results are obtained with SA. Therefore, Relative GAP is calculated, and results are compared according to SA. Result of SA is expressed by z1, and to calculate relative gap of ALNS z2 is expressed the result of ALNS, and to calculate GAP of CPLEX, z2 is expressed the result of CPLEX. Relative GAP is given in equation 4.1. (4.1) A larger number of customers and present the results for N=20, N=50, N=75, and N=100 customers, results of SA, relative gap of SA, results of ALNS, relative gap of ALNS, results of Cplex, and relative gap of Cplex are given in Table 2, respectively.

Sigma J Eng Nat Sci, Vol. 44, No. 1, pp. 140−152, February, 2026

When the exact solution method is compared with the heuristic methods, it is seen that the heuristic methods achieve better results in a shorter time than the exact solution method in every sample and scenario. In addition, all of the samples SA gives better results than ALNS. Solution time of ALNS and SA are close to each other. As seen in Table 2, relative gap of ALNS are close to results of SA. When looking at the results obtained with ALNS and Cplex for larger samples, it is seen that the relative gap value increases. Looking at the results in Tables 2-5, it is observed that the gap value obtained in scenarios with flexible time windows is lower than in other scenarios. The increase in cost parameters also increased the gap value. Generally, the best solutions found are obtained by SA. When the results obtained with ALNS and the exact solution method are compared, in some examples the ALNS, and in some examples the exact solution method give better results than other.

Conclusion

The vehicle routing problem on a network with multiple alternative links between nodes, considering the three main pillars of sustainability; financial, environmental and social

are analyzed. The optimal routes are determined to deliver the goods to a set of customers in order to minimize the delivery cost for the company, minimize the gas emissions to decrease environmental effects and improve the working conditions for drivers. A multi objective mixed integer linear model for this problem is solved with simulated annealing and adaptive large neighborhood solutions algorithms. The shortest path or the fastest path may not always be chosen according to the objective functions and constraints discussed in the problem. When the financial, environmental and social objectives are considered together, it is seen that alternative links and speed levels are also chosen. Even though the optimal solution is obtained for small sized problems, as the problem size increases, the optimal solution could not be obtained in a reasonable time limit. Therefore, heuristic methods are used to solve problem in resonable time limit. Simulated annealing is easily implemented, and in a short time, good solution can be attained. To compare quality of results, adaptive large neighborhood solutions is used to solve same problem. Examples of 20, 50, 75 and 100 node sizes are prepared and 8 scenarios are created using different parameters for each size. Different problem sizes and scenarios are solved, and for all of the samples, Simualted Annealing gives better results in a

Sigma J Eng Nat Sci, Vol. 44, No. 1, pp. 140−152, February, 2026

shorter time than adaptive large neighborhood solutions. It is seen that as the problem size increases, the gap values increase in the results obtained with the exact solution method. Time-dependent speed choices and durations can be incorporated into the model in the future. In addition, stochastic versions of this problem in which the durations or speeds are random due to unknown traffic conditions, can be analyzed. In recent years, algorithms using artificial intelligence have begun to be used to solve vehicle routing problems. Algorithms using artificial intelligence can also be used to solve this problem. The production and use of electric vehicles has increased in recent years. The energy consumption of these vehicles can be handled with the same objectives and constraints. Finally, several extensions of this vehicle routing problem such as using heterogeneous fleet of vehicles, multiple depots etc. can be analyzed in future studies.

Data Availability Statement

The authors confirm that the data that supports the findings of this study are available within the article. Raw data that support the finding of this study are available from the corresponding author, upon reasonable request.

Conflict Of Interest

The author declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Ethics

There are no ethical issues with the publication of this manuscript.

Statement On The Use Of Artificial Intelligence

Artificial intelligence was not used in the preparation of the article.

References

1. Goel A. Vehicle scheduling and routing with drivers’ State of the art and future directions. IEEE Access working hours. Transp Sci 2009;43:17–26. [CrossRef] 2022;10:8544–8569. [CrossRef]
2. Kok AL, Meyer CM, Kopfer H, Schutten JMJ. A dynamic programming heuristic for the vehi- local search multi-objective methodology for the cle routing problem with time windows and green vehicle routing problem considering workload European Community social legislation. Transp Sci equity with a private fleet and a common carrier. Int 2010;44:442–454. [CrossRef] J Ind Eng Comput 2021;12:115–130. [CrossRef] Sigma J Eng Nat Sci, Vol. 44, No. 1, pp. 140−152, February, 2026 151
3. Cheng C, Qi M, Wang X, Zhang Y. Multi-period inventory routing problem under carbon emission al. MIMOA: A membrane-inspired multi-objec- regulations. Int J Prod Econ 2016;182:263–275. tive algorithm for green vehicle routing problem [CrossRef] with stochastic demands. Swarm Evol Comput
4. Toro EM, Franco JF, Echeverri MG, Guimaraes FG. 2021;60:100767. [CrossRef] A multi-objective model for the green capacitated [34] Fan H, Zhang Y, Tian P, Lv Y, Fan H. Time-dependent location-routing problem considering environmen- multi-depot green vehicle routing problem with tal impact. Comput Ind Eng 2017;110:114–125. time windows considering temporal-spatial dis- [CrossRef] tance. Comput Oper Res 2021;129:105211. [CrossRef]
5. Xiao Y, Konak A. A genetic algorithm with exact dynamic programming for the green vehicle routing Multiobjective capacitated green vehicle routing problem & scheduling problem. J Clean Prod 2017;167:1450– with fuzzy time-distances and demands split into bags. Int 1463. [CrossRef] J Prod Res 2021. doi: 10.1080/00207543.2021.1888392.
6. Cai L, Lv W, Xiao L, Xu Z. Total carbon emissions [Epub ahead of print]. minimization in connected and automated vehicle [36] Wen M, Sun W, Yu Y, Tang J, Ikou K. An adaptive routing problem with speed variables. Expert Syst large neighborhood search for the larger-scale multi Appl 2021;165:113910. [CrossRef] depot green vehicle routing problem with time win-
7. Prakash R, Pushkar S. Green vehicle routing prob- dows. J Clean Prod 2022;374:133916. [CrossRef] lem: Metaheuristic solution with time window. [37] Wang S, Han C, Yu Y, Huang M, Sun W, Kaku I. Expert Syst 2022;39:e13007. [CrossRef] Reducing carbon emissions for the vehicle routing
8. Naderipour M, Alinaghian M. Measurement, evalu- problem by utilizing multiple depots. Sustainability ation and minimization of CO2, NOx and CO emis- 2022;14:1264. [CrossRef] sion in the open time dependent vehicle routing [38] Durmaz N, Budak A. An integrated bi-objec- tive green vehicle routing and partial disassembly problem. Measurement 2016;90:443–452. [CrossRef] line problem for electronic waste: An industrial
9. Koç Ç, Bektaş T, Jabali O, Laporte G. The fleet size case study. Int J Comput Integr Manuf 2024. doi: and mix pollution-routing problem. Transp Res Part
10. 1080/0951192X.2023.2285188. [Epub ahead of B Methodol 2014;70:239–254. [CrossRef] print].
11. Dutta J, Barma PS, Mukherjee A, Kar S, De T. A green vehicle routing problem with time window hybrid multi-objective evolutionary algorithm for and simultaneous pickup and delivery. J Fac Eng open vehicle routing problem through cluster pri- Archit Gazi Univ 2024;39:757–770. [CrossRef] mary-route secondary approach. Int J Manag Sci
12. Yang B, Hu ZH, Wei C, Li SQ, Zhao L, Jia S. Routing Eng Manag 2021;17:34-47. [CrossRef] with time-windows for multiple environmental [40] Wu D, Wu C. TDGVRPSTW of fresh agricultural prod- vehicle types. Comput Ind Eng 2015;89:150–161. ucts distribution: Considering both economic cost and [CrossRef] environmental cost. Appl Sci 2021;11:10579. [CrossRef]
13. Maden W, Eglese R, Black D. Vehicle routing and scheduling with time-varying data: A case study. J neighborhood search for the green mixed fleet Oper Res Soc 2010;61:515–522. [CrossRef] vehicle routing problem with realistic energy con-
14. Franceschetti A, Honhon D, Van Woensel T, Bektaş sumption and partial recharges. Appl Soft Comput T, Laporte G. The time dependent pollution-routing 2021;105:107251. [CrossRef] problem. Transp Res Part B Methodol 2013;56:265– [42] Demirbilek M. A metaheuristic solution approach
15. Niu Y, Yang Z, Chen P, Xiao J. Optimizing the green problem with simultaneous linehauls and backhauls. open vehicle routing problem with time windows Sigma J Eng Nat Sci 2021;39:226–236. [CrossRef] by minimizing comprehensive routing cost. J Clean [43] Yücenur GN, Çetin Demirel N. A hybrid algorithm Prod 2018;171:962–971. [CrossRef] with genetic algorithm and ant colony optimization
16. Suzuki Y. A new truck-routing approach for reducing for solving multi-depot vehicle routing problem. J fuel consumption and pollutants emission. Transp Eng Nat Sci Sigma 2011;29:340–350. Res Part D Transp Environ 2011;16:73–77. [CrossRef] [44] Anvari S, Turkay M. The facility location problem
17. Demir E, Bektaş T, Laporte G. An adaptive large from the perspective of triple bottom line account- neighborhood search heuristic for the pollu- ing of sustainability. Int J Prod Res 2017;55:6266– tion-routing problem. Eur J Oper Res 2012;223:346– 6287. [CrossRef]
18. Demir E, Bektaş T, Laporte G. The bi-objective pollu- effective rank based ant system algorithm for solving tion routing problem. Eur J Oper Res 2014;232:464– the balanced vehicle routing problem. Int J Ind Eng
19. [CrossRef] 2016;23. 152 Sigma J Eng Nat Sci, Vol. 44, No. 1, pp. 140−152, February, 2026
20. Koulaeian M, Seidgar H, Kiani M, Fazlollahtabar H. A multi depot simultaneous pickup and delivery with crossover operator for capacitated vehicle rout- problem with balanced allocation of routes to driv- ing problem. Swarm Evol Comput 2021;64:100991. ers. Int J Ind Eng 2015;22:223–242. [CrossRef]
21. Halvorsen-Weare EE, Savelsbergh MWP. The bi-ob- jective mixed capacitated general routing problem ing algorithm for multi depot two-echelon capaci- with different route balance criteria. Eur J Oper Res tated vehicle routing problem. Eur Transp 2020;78. 2016;251:451–465. [CrossRef] [CrossRef]
22. Huang SH, Huang YH, Lee HC, Tong YY. A new hybrid algorithm for solving the vehicle routing simulated annealing for solving the capacitated problem with route balancing. Int J Ind Eng Manag vehicle routing problem. J Exp Theor Artif Intell 2023;14:51–62. [CrossRef] 2021;33:179-197.
23. Yu VF, Redi AANP, Hidayat YA, Wibowo OJ. A Thibbotuwawa A. Optimizing fresh-cut flower dis- simulated annealing heuristic for the hybrid vehicle tribution using the vehicle routing problem for per- routing problem. Appl Soft Comput 2017;53:119– ishable goods. Sci J Logist 2024;20:23–37. [CrossRef]
24. Fan M, Wu Y, Cao Z, Song W, Sartoretti G, Liu H, 132. [CrossRef] et al. Conditional neural heuristic for multiobjective [62] Chiang W, Russell RA. Simulated annealing meta- vehicle routing problem. IEEE Trans Neural Netw heuristic for the vehicle routing problem with time Learn Syst 2024. doi: 10.1109/TNNLS.2023.3343467. windows. Ann Oper Res 1996;63:3–27. [CrossRef] [Epub ahead of print]. [63] Kesen SE, Alim M. Solution approaches for mixed
25. Yue B, Ma J, Shi J, Yang J. A deep reinforcement pallet collection problem: A case study in a logistics learning-based adaptive search for solving time-de- company. Sigma J Eng Nat Sci 2019;37:827–840. pendent green vehicle routing problem. IEEE Access [64] Alinaghian M, Shokouhi N. Multi-depot multi-com- 2024;12:2855–2867. [CrossRef] partment vehicle routing problem, solved by a
26. Goel A, Gruhn V. Drivers’ working hours in vehi- hybrid adaptive large neighborhood search. Omega cle routing and scheduling. In: Proceedings of the 2018;76:85–99. [CrossRef] 2006 IEEE Intelligent Transportation Systems [65] Azi N, Gendreau M, Potvin JY. An adaptive large Conference; 2006 Sep 17-20; Toronto, Canada. neighborhood search for a vehicle routing prob- IEEE; 2006. [CrossRef] lem with multiple routes. Comput Oper Res
27. Abdullahi H, Reyes-Rubiano L, Ouelhadj D, Faulin 2014;41:167–173. [CrossRef] J, Juan AA. Modelling and multi-criteria analysis of [66] Alinaghian M, Jamshidian M, Tirkolaee EB. The the sustainability dimensions for the green vehicle time dependent multi-depot fleet size and mix green routing problem. Eur J Oper Res 2021;292:143–154. vehicle routing problem: Improved adaptive large [CrossRef] neighborhood search. Optimization 2022;71:3165–
28. Kirkpatrick S, Gelatt CD, Vecchi MP. Optimization sumption model. Technical report. California by simulated annealing. Science 1983;220:671–680. Partners for Advanced Transit and Highways [CrossRef] (PATH); 2005. Available at: http://escholarship.org/ uc/item/67f0v3zf. Accessed on January 22, 2026. [68] Ropke S, Pisinger D. An adaptive large neighborhood
29. Turkensteen M. The accuracy of carbon emission search heuristic for the pickup and delivery problem and fuel consumption computations in green vehicle with time windows. Transp Sci 2006;40:455–472. routing. Eur J Oper Res 2017;262:647–659. [CrossRef] [CrossRef]
30. Bektaş T, Laporte G. The pollution-routing problem. Transp Res Part B Methodol 2011;45:1232–1250. ry-routing problem with transshipment. Comput [CrossRef] Oper Res 2012;39:2537–2548. [CrossRef]
31. Ferreira KM, Queiroz TA. A simulated annealing based heuristic for a location-routing problem with large neighborhood search algorithm for a selective two-dimensional loading constraints. Appl Soft and periodic inventory routing problem. Eur J Oper Comput 2022;118:108443. [CrossRef] Res 2014;239:413–426. [CrossRef]

Share and Cite