Determination of optimal depot location for a capacitated vehicle routing problem (CVRP) based on gross vehicle weight

Abstract

The fuel consumption of a vehicle depends on its gross weight, which varies as goods are successively unloaded at each wholesaler site or distribution centre within a transportation network. There exist multiple routes and many wholesalers with different demand quantities within the network. Again, transportation cost varies according to the route and the depot location (DL) from which the vehicle departs. Hence, this article aims to determine the optimal DL for Ly-Foods Ltd.'s transportation network, utilising a capacitated vehicle to fulfil wholesalers’ demands, based on gross vehicle weight (GVW). First, we develop some analytical and mathematical models (mixed-integer programming-MIP) to determine the minimum transportation cost for each location. Second, we verify our models for other instances and compare our results with some heuristic results. We find the optimal location for the depot for the transportation network of Ly-Foods, which saves a maximum of 10.43 litres of fuel in a trip. This research holds significance for the manufacturing or distribution companies aiming to set up depots within a new transportation network. Furthermore, our models are applicable to transportation networks featuring multiple routes and numerous wholesalers, where the management is planning to shift DL with the changes in wholesalers’ demands.

KEYWORDS:

• Depot location
• gross vehicle weight (GVW)
• capacitated vehicle routing problem (CVRP)
• transportation networks

1. Introduction

Nowadays, transportation performance has become one of the most important factors in ensuring optimal and efficient logistics performance (Frazelle, 2020; Tseng et al., 2005). But achieving better performance in transportation is sometimes difficult due to the complexity of selecting the best route and optimal DL for transportation. A company must ensure timely delivery of items to specified destinations with consideration of vehicle capacity, transport routes, time constraints, and cost. However, a capacitated vehicle/cargo is chosen based on the demand of the customers, where the vehicle can meet the demand of each customer (Juan et al., 2010; Singh et al., 2023). The objective of a CVRP is to meet customers’ demands and reduce travel distance. In Bangladesh, the number of manufacturing industries is growing, and its manufacturing capacity is also increasing, which results in increased routing competence (Rahman & Al Amin, 2016; Rahman & Rahman, 2019). Besides, the importance of transportation performance is increasing due to the expansion of industries and global marketing. Moreover, management in logistics helps in optimising routing problems and distribution networks along with enhancing enterprises’ efficiency and competitiveness (Tseng et al., 2005; Aloui et al., 2022; Li & Shi, 2023). Routing complexity, transportation costs, vehicle underutilisation, delayed delivery, etc. are the common routing problems in Bangladesh that affect transportation performance and increase cost. Suppliers look for ways to cut costs in logistics because transportation costs account for roughly one-third of total logistics costs (Tseng et al., 2005; Yan & Zhang, 2015; Rahman & Rahman, 2020). Since this cost depends on the logistics components, good coordination among them is essential in bringing benefits. Coordination in logistics components helps in enhancing transportation efficiency, reducing transportation costs, and increasing consumer benefits (Braekers et al., 2016; Iriani & Asmara, 2020; Xiao et al., 2012).

The transportation performance of a CVRP depends on a few factors, such as its gross weight and travel distance. These factors are directly linked to fuel consumption for a vehicle, and therefore those are considered performance determinants (Baldacci et al., 2004; Xiao et al., 2012; Rahman et al., 2022). This means that the greater the distance travelled, the greater the fuel consumption. In those cases, methods to solve routing problems play a vital role in minimising transportation costs. At present, fuel consumption has become a major concern for logistics companies because more consumption affects environmental sustainability. A transportation company in Shanghai, China, found fuel costs account for 67.14% of the total transportation cost of US$2,308,608.8 (Sahin et al., 2009; Xiao et al., 2012). They also found that if fuel costs can be reduced by 5%, China can save approximately US$75,500 per year, which is over 3% of total transportation costs. Therefore, suppliers are now focusing on the reduction of fuel consumption that can be achieved through the minimisation of travel distance (Rahman et al., 2022; Efthymiadis et al., 2023; Hashemi & Tari, 2018). Solutions addressing the CVRP aim to optimise real-world scenarios by achieving rapid delivery at minimal cost, fulfilling customer demands via the most efficient routes, and other similar achievements. These outcomes represent significant successes for suppliers.

In the case of CVRP, it is important to find out not only the optimal DL but also the optimal route to ensure transportation performance, where DL stands for starting point, from where the vehicle departs. In this study, we have described a full methodology to solve similar problems by considering the real-world CVRP of Ly-Foods Ltd. (a pseudonym), which is one of the largest food and beverage manufacturing companies in Bangladesh. In this problem, there exist multiple routes and eight depots within the transportation network of Figure 2, described in detail in Section 2.3. If the company, Ly-Foods Ltd., can select the optimal DL as well as the optimal route, they can save transportation cost and overcome delayed deliveries. To meet our research goal, we developed some mathematical and analytical models to determine the minimum cost for each depot. The mathematical models were of MIP, and the purpose of those models was to assign where the vehicle would travel or not. Using those models, we determined the total fuel consumption for each DL. Instead of a distance matrix, we utilised a fuel consumption matrix to find the optimal depot and the optimal route. The basis for selecting the fuel consumption matrix was the equation y = 9.1141-0.278x, which was developed in our previous article (Rahman et al., 2022). Consideration of fuel consumption matrix and the methodology to determine the optimal DL for a transportation network is the novel contribution of this article. Additionally, this study examines other instances to aid Ly-Foods in understanding how optimality shifts with variations in vehicle loads and travel distances. Finally, to validate the optimality of our models, we compare our results with those obtained from several heuristics, namely Nearest Neighbor Heuristic (NNH), Sweeping Heuristic (SH), and Clarke & Wright’s Heuristic (CWH). To achieve the goal of our study, we have established the following objectives:

• Development of analytical and mathematical models (MIP) to determine fuel consumption for each DL,

• Determination of the optimal DL and the optimal route for the transportation network of Ly-Foods Ltd., and

• Comparison and validation of our models with other instances and heuristic methods

The rest of the paper is organised as follows: Related works, motivation, and case description have been documented in Section 2; research methods have been illustrated in Section 3; results and outcomes are reported in Section 4 with necessary discussion and key findings; model verification under various scenarios has been described in Section 5; and finally, the paper concludes with future research scopes and practical implications in Section 6.

2. Related works, motivation, and case description

2.1. Related works

This section highlights previous research that deals with identifying (1) the factors that affect CVRP and DL selection problems, and (2) various methods/techniques as well as heuristics for solving DL-related problems for a capacitated vehicle.

The optimal DL selection in the context of the CVRP has been a subject of extensive investigation within the field of transportation and logistics (Mohamed et al., 2023; Abu-Monshar et al., 2022; Diana et al., 2017). The CVRP deals with a set of customer demands with a fleet of vehicles from a central node or depot, where each vehicle has the same capacity. This forms constraints with the parameters such as fuel consumption, travel distance, vehicle weight, etc. because CVRP sets its objective function to minimise its total cost (Cordeau et al., 2007; Juan et al., 2010; Nagy & Salhi, 2007; Delgado-Antequera et al., 2020). Capacitated vehicles meet each customer’s demand, which generates a cost-distance matrix due to travelling from one demand point to another. This matrix represents costs for a certain distance (Cordeau et al., 2007; Juan et al., 2010). In most cases, the transportation cost between each pair of locations is the same in both directions, resulting in a symmetric cost matrix; however, in certain cases, such as distribution in urban regions with one-way traffic, the cost matrix is asymmetric (Rahman & Rahman, 2020; Mühlbauer & Fontaine, 2021). In the past decades, several researchers considered different routing problems to solve cost-distance matrices to find the most cost-efficient route and used heuristics, metaheuristics, and hybrid methods. Besides, they showed the main characteristics of each CVRP and tried to find alternatives to each algorithm (Mazzeo & Loiseau, 2004; Abu-Monshar & Al-Bazi, 2022). Algorithms to solve CVRP are now changing due to some real-life complexities such as traffic congestion, pickup and delivery times, and road fees are changing dynamically over time (Braekers et al., 2016; Mańdziuk & Świechowski, 2017; Li & Chung, 2019). Furthermore, Konstantakopoulos et al. (2022) and Shbool et al. (2022) determined some factors, such as vehicle capacities, time windows, travel distances, and customer satisfaction, that influence routing problems and the selection of DL.

The purpose of CVRP solution methods is to optimise transportation costs and determine optimal DL. Those determine optimal routes for a set of vehicles to meet customer demands at the optimal cost. Researchers are adopting various methods to solve routing problems and find optimal depots. For example, Lin et al. (2009) adopted a simulated annealing hybrid algorithm and tabu search to fourteen classical instances and twenty large-scale benchmark instances to find the best classical instances. Abu-Monshar and Al-Bazi (2022), Ke and Feng (2013), and Jin et al. (2014) used meta-heuristics to solve CVRP. Besides, researchers are employing both insertion heuristics and exchange methods to explore the neighbourhood in simulated annealing (Lin et al., 2009; Zeng et al., 2005). Ho and Gendreau (2006) used tabu search and path relinking to solve CVRP on a large scale, reserving better paths and improving local worse paths. Chen and Shen (2015) determined optimal DL through particle swarm optimisation where they proposed novel encoding and routing balance insertion techniques. Fermin Cueto et al. (2021) solved multi-trip routing problems with time windows, fleet sizing, and DL. Altabeeb et al. (2021) proposed a cooperative hybrid firefly algorithm to solve CVRP that maintained population diversity and prevented their proposed algorithm from emerging into a local optimum. Kuo and Wang (2012) proposed a variable neighbourhood search for solving the multi-depot vehicle routing problem with loading cost. Sungur et al. (2008) introduced a robust optimisation approach to minimise transportation costs by solving problems in vehicle routing. This approach also protects unmet demand and saves additional costs incurred over the deterministic optimal routes. Zhu et al. (2020) optimised multi-depot loading-capable electric vehicle routing problems using a neighbourhood search algorithm and a space saving heuristic algorithm. Besides, Mahmud and Haque (2019) used a genetic algorithm; Narasimha et al. (2013) followed the ant colony optimisation technique; Dubey and Tanksale (2023) applied an elitist genetic algorithm; Wirawan and Suharjito (2023) and Zhen et al. (2020) formulated multi-objective mixed integer programming; and Zhang et al. (2020) proposed a novel logistics collaboration model to solve DL-related problems in vehicle routing.

This section finds that the factors influencing the solution of CVRP, and the selection of optimal DL encompass delivery time, fuel consumption, travel distance, traffic congestion, pickup and delivery times, road conditions, the number of vehicles, vehicles’ capacities, GVW, and the number of depots. Besides, this aggregates various solution methods for solving DL-related problems for a capacitated vehicle. However, despite this comprehensive review, no method has been found that specifically deals with identifying optimal DL based on GVW for a CVRP.

2.2. Motivation

From the equation y = 9.1141-0.278x, travel economy varies with the increase in the gross weight of a vehicle. In this equation, y denotes travel economy, and x denotes GVW. This relationship indicates that a lightly loaded vehicle can travel more distance compared to a heavily loaded vehicle while consuming 1 L of fuel, as depicted in Figure 1. This relationship has been proven in our previous article (Rahman et al., 2022), which elaborated on how the travel economy fluctuates with GVW.

Figure 1. Travel economy of a truck for its various gross weights.

Source: Reproduced (Rahman et al., 2022).

As there is an effect of the gross weight on the travel economy, we have been motivated to implement this relationship to solve a practical problem for a company named Ly-Foods Ltd., as described in Section 2.3. We were also motivated to determine the optimal route as well as the optimal DL for the transportation network in Figure 2. Since the network comprises eight wholesalers, each with different demand quantities (measured in tons), we aim to employ our equation within this network to minimise fuel consumption. Given that GVW and travel distance differ among wholesalers, different transportation routes will incur different fuel consumption levels. Hence, our motivations were associated with finding out the optimal route as well as its starting point for transportation using this equation, which will save transportation costs and travel time for Ly-Foods.

Figure 2. (a) The geographical locations of wholesalers (b) within the western region of Bangladesh.

2.3. Case description

Ly-Foods Ltd. is one of the largest food manufacturing industries in Bangladesh and produces various types of products such as biscuits and bakery items, beverages, confectionery, culinary, dairy, and some frozen items. With a well-established distribution network spanning numerous districts across the nation, Ly-Foods is now gearing up to penetrate the western zone of Bangladesh. This strategic move comes considering the discovery of eight potential wholesalers situated across Choua danga (CHO), Faridpur (FAR), Jessore (JES), Jhenaidah (JHE), Kustia (KUS), Magura (MAG), Narail (NAR), and Rajbari (RAJ) districts within this zone. To facilitate efficient distribution, the company intends to establish a depot in a district where transportation costs will be minimal. Tables 1 and 2 present the distance matrix among these districts and their corresponding weekly demands, respectively. With a cumulative demand of 10 tons, Ly-Food aims to utilise a 10-ton capacitated vehicle for the transportation of products to the wholesalers. Figure 2 provides a visual representation of the geographical locations of the wholesalers.

Table 1. Distance matrix.

	FAR	MAG	RAJ	KUS	CHO	JHE	JES	NAR
FAR	0	31	30	95	117	80	96	92
MAG	31	0	32	73	65	29	46	45
RAJ	30	32	0	65	120	83	100	118
KUS	95	73	65	0	50	46	93	117
CHO	117	65	120	50	0	36	75	108
JHE	80	29	83	46	36	0	45	79
JES	96	46	100	93	75	45	0	33
NAR	92	45	118	117	108	79	33	0

Table 2. Weekly demands of the wholesalers.

Wholesalers	FAR	MAG	RAJ	KUS	CHO	JHE	JES	NAR
Weekly demand (tons)	1.5	0.5	1.5	3.0	1.5	0.5	1.0	0.5

In this study, we designate the wholesalers as follows: 1-FAR, 2-MAG, 3-RAJ, 4-KUS, 5-CHO, 6-JHE, 7-JES, and 8-NAR.

3. Research methods

This study follows a systematic research approach shown in Figure 3, presenting a step-by-step overview of the entire working process.

Figure 3. The research framework.

3.1. Mathematical models formulation

We developed some mathematical models of MIP to determine the fuel consumption for each location. We considered each location as a depot and determined the depot had minimal fuel consumption. In formulating our models, we made two assumptions: (1) as Ly-Foods wants to set up the depot near the location of any wholesaler, the transportation cost for this wholesaler is negligible, and (2) we have considered a constant weekly demand of the wholesalers as shown in Table 2 instead of variations in demands. The parameters and decision variables utilised in formulating mathematical models are listed in Table 3. (1) $\begin{array}{rl}& \text{minimize}\sum _{\mathrm{iϵN}}\sum _{\mathrm{jϵN}}{F}_{\mathrm{ij}}{x}_{\mathrm{ij}}\end{array}$(1) (2) $\begin{array}{rl}& \text{Subject to}\\ & \sum _{j\in N}{x}_{\mathrm{ij}}=1\mathrm{\forall i}\in N\end{array}$(2) (3) $\begin{array}{rl}& \sum _{i\in N}{x}_{\mathrm{ij}}=1\mathrm{\forall j}\in N\end{array}$(3) (4) $\begin{array}{rl}& u\left[i\right]+N\ast x_{\mathrm{ij}}\le u\left[j\right]+\left(N-1\right)\mathrm{\forall i},j\in N:i\ne j,j\ne 1\end{array}$(4) (5) $\begin{array}{rl}& x_{\mathrm{ii}}=0\mathrm{\forall i}\in N\end{array}$(5)

Table 3. List of parameters and decision variables used in mathematical modelling.

Parameters
N	Set of wholesalers
$F_{\mathrm{ij}}$	Consumption of fuel from a wholesaler $\left(i\in N\right)$ to another $\left(j\in N\right)$
Decision variables
$x_{\mathrm{ij}}\in \left\{0,1\right\}$	If the vehicle travels from $i\in N$ to $j\in N$ then 1, otherwise 0
$u_i\in Z+$	A value that connects $x_{\mathrm{ij}}$ to the next node

Equation 1 minimises fuel consumption during a trip, Equation 2 indicates the vehicle must leave each wholesaler, Equation 3 ensures the vehicle reaches each customer, Equation 4 links variables $x_{\mathrm{ij}}$ and $u_i$ and eliminates subtours, and Equation 5 prevents loops.

3.2. Analytical models formulation

To compare our results, as found in Equation 1, with other heuristic methods or other instances, we formulated some analytical models, Equations 6–10. The variables used in developing these analytical models are listed in Table 4, along with their descriptions.

Table 4. Description of the variables. 

Variables	Description
	$\begin{array}{l}\text{Fuel consumption in delivery route}\\ \text{Fuel consumption in return route}\\ \text{Total fuel consumption}\end{array}\}L$
$f_{\mathrm{ld}}$
$f_{\mathrm{lr}}$
$C_{\mathrm{tf}}$
	$\begin{array}{l}\text{Travel distance}\\ \text{Return distance from last wholesaler to DL}\\ \text{Total travelling distance}\end{array}\}\mathrm{km}$
$d$
$R_d$
D
x	Gross weight of a vehicle, ton
$C_l$	Cost of fuel per litre, tk./L
$y$	Travel economy, km/L
	$\begin{array}{l}\text{Transportation costs in delivery route}\\ \text{Transportation costs in return route}\\ \text{Total transportation cost}\end{array}\}\mathrm{Tk}$
$T{C}_D$
$T{C}_R$
$\mathrm{TTC}$
$\mathrm{TT}{C}_m$	Minimum transportation cost
$\mathrm{TT}{C}_P$	$\text{Cost performance }\left(\text{\%}\right)$

3.2.1. Models for transportation costs

To determine fuel consumption and transportation costs in a heuristic, some analytical models of Equations 6–9 were developed, adopting the fuel consumption model (Equation 6(6) $\begin{array}{r}y=9.1141-0.278x\end{array}$(6) ) of Rahman et al. (2022). The cost is determined by the fuel consumed on both the delivery route and the return route. The costs of a delivery route and a return route can be determined by Equations 7 and 8, respectively. However, Equation 6 of the travel economy adopted from Rahman et al. (2022) was used to determine $f_{\mathrm{ld}}$ and $f_{\mathrm{lr}}$. The travel economy, y, is affected by a vehicle's gross weight, x, and decreases whenever GVW increases. That means the maximum travel economy (y) is for an empty cargo, and with the increase in vehicle weight, y decreases. For example, the travel economy of a loaded and unloaded vehicle is 2.44 and 5.22 km/L, respectively, where their gross vehicle weights are 24 and 14 tons, respectively. However, the travel economy for each route has been determined in Appendix Section A1. (6) $\begin{array}{r}y=9.1141-0.278x\end{array}$(6) $\mathrm{TTC}$ in Equation 6 determines the transportation costs of a heuristic. (7) $\begin{array}{r}T{C}_D=f_{\mathrm{ld}}\times C_l\end{array}$(7) where $f_{\mathrm{ld}}=\left\{\frac{d_1}{y_1}+\frac{d_2}{y_2}+\dots \dots +\frac{d_n}{y_n}\right\}$ (8) $\begin{array}{r}T{C}_R=f_{\mathrm{lr}}\times C_l\end{array}$(8) where $f_{\mathrm{lr}}=\frac{R_d}{y}$ Here, $d_1+d_2+\dots \dots +d_n+R_d=D$ (9) $\begin{array}{r}\mathrm{TTC}=T{C}_D+T{C}_R=\left(f_{\mathrm{ld}}+f_{\mathrm{lr}}\right)\times C_l=C_{\mathrm{tf}}\times C_l\end{array}$(9) where $C_{\mathrm{tf}}=\left(f_{\mathrm{ld}}+f_{\mathrm{lr}}\right)$.

Equation 9 determines TTC requires in a trip, where $C_{\mathrm{tf}}$ and $C_l$ indicate total fuel consumption and fuel cost per litre, respectively. In this research, we used diesel as fuel and used its market selling price (136 tk./L) to determine the TTC that is shown in Appendix Section A1.

3.2.2. Models for performance comparison

The overall performance of a heuristic can be determined by measuring its cost performance. The analytical model of Equation 10 determines the overall performance of an $i^{\mathrm{th}}$ heuristic. $\mathrm{TT}{C}_{P-i}$ determines the performance of a heuristic compared with the other heuristics. Besides, this compares our results with these heuristics. (10) $\begin{array}{r}\mathrm{TT}{C}_{P-i}=\frac{\mathrm{TT}{C}_m}{\mathrm{TT}{C}_i}\times 100\mathrm{\%}\end{array}$(10) where $\mathrm{TT}{C}_m=\text{minimum }\left\{\mathrm{TT}{C}_i\right\}$.

3.3. Fuel consumption calculation

This study focused on the minimisation of TTC and the determination of the optimal DL. The TTC depends on the amount of fuel consumed in transportation from one wholesale location to others. Utilising Equation 6, we have calculated fuel consumption for each distance that exists among the eight wholesalers. Table 5 is the fuel consumption matrix for the distance matrix of Table 1, where we have considered FAR as DL. Alterations in depot locations result in variations in distances and fuel consumption. In Appendix Section A2, we have included another set of matrices (Table A1 for distances and Table A2 for fuel consumption) with KUS as the DL. These tables demonstrate that changing the DL changes fuel consumption due to variations in travel distances and vehicles’ gross weights.

Table 5. Fuel consumption matrix for the DL at FAR.

	FAR	MAG	RAJ	KUS	CHO	JHE	JES	NAR
FAR	0	10.84	10.00	27.81	27.53	17.14	19.97	18.09
MAG	10.84	0	10.67	21.37	15.29	6.21	9.57	8.85
RAJ	10.00	10.67	0	19.03	28.24	17.78	20.81	23.21
KUS	27.81	21.37	19.03	0	11.76	9.85	19.35	23.01
CHO	27.53	15.29	28.24	11.76	0	7.71	15.60	21.24
JHE	17.14	6.21	17.78	9.85	7.71	0	9.36	15.54
JES	19.97	9.57	20.81	19.35	15.60	9.36	0	6.49
NAR	18.09	8.85	23.21	23.01	21.24	15.54	6.49	0

4. Results and discussion

4.1. Calculation of fuel consumption for each depot

We used OPL CPLEX 22.1.1 Optimisation Studio software to solve the Equations 1–5. Table 6 summarises fuel consumption, travel route, and path distance for each depot. The analysis shows that despite travelling the same 335 km path, each route exhibits varying fuel consumption due to differences in GVWs. For instance, in the case of NAR, the vehicle carries varying loads to each depot: 23.5 tons to JES, 22.5 to JHE, 22 to CHO, 20.5 to KUS, 17.5 to RAJ, 16 to MAG, and 15.5 to FAR. Finally, it gets empty in FAR and returns to NAR with a load of 14 tons. Interestingly, it unloads lesser weights, approximately 0.5–1.5 tons, at the first four wholesalers, resulting in heavier loads towards KUS, the fifth DL from its starting point. This substantial weight at KUS leads to the highest fuel consumption recorded at 91.782 L. On the other hand, in the case of KUS, the vehicle's load distribution is different, with 21 tons carried to RAJ, 19.5 to MAG, 19 to FAR, 17.5 to CHO, 16 to JHE, 15.5 to JES, and 14.5 to NAR. Here, heavier loads (1.5–3.0 tons) are unloaded at the initial two wholesalers, resulting in minimised fuel consumption, recorded at 72.558 L.

Table 6. Fuel consumption, travel route, and path distance for each depot.

DL	Travel route	Path distance (km)	Fuel consumption (L)
FAR	1-3-4-5-6-7-8-2-1	335	79.168
MAG	1-8-7-6-5-4-3-2-1	335	79.168
RAJ	1-4-5-6-7-8-2-3-1	335	79.310
KUS	1-5-6-7-8-3-4-2-1	335	72.558
CHO	1-7-8-4-5-3-2-6-1	335	79.662
JHE	1-2-3-4-6-5-8-7-1	335	85.450
JES	1-8-6-7-5-4-3-2-1	335	80.703
NAR	1-2-3-4-5-6-8-7-1	335	91.782

Considering these findings, it's evident that KUS emerges as the optimal DL due to its lower fuel consumption.

4.2. Calculation of fuel consumption for various heuristic methods

We applied some heuristic methods (NNH, SH, and CWH) to our transportation network, as shown in Figure 2, to compare our results, as we have found in Table 6. The transportation routes show that the vehicle can travel varied paths under each heuristic. The routes followed by these heuristics are shown in Figure 4, with their algorithms applied as detailed in Table 7.

Figure 4. Transportation routes in (a) nearest neighbour heuristic (b) sweeping heuristic and (c) Clarke & Wright's heuristic.

Table 7. Heuristics’ algorithms.

Nearest neighbour heuristic	Sweeping heuristic	Clarke & Wright’s heuristic
Input set of customers $S_i=\left\{1,2,\dots \dots \dots ,n\right\}$Output routes $i=\left\{1,2,\dots ,n\right\}$ for $S_1$ = 1, 2, … , n; and $d=0$ do $D_{\mathrm{dj}}=min\left\{D_{\mathrm{dj}}\right\}j\in S_1$ Now, $d=j$ and unload $q_j$ at location j $S_1=S_1-j$ and $Q=Q-q_j$  while $\left(Q\ne 0\right)$ do repeat 2   if $\left(Q=0\right)$ then  back to DL and get route $i=1$   end if  end while  while $\left(S_1\ne 0\right)$ do repeat 2–4, and get routes $i=2,\dots ,n$   if $\left(S_1=0\right)$ then back to DL    end if   end while  end for return $S_2,S_3,\dots \dots .,S_n$	Input set of customers $S_i=\left\{1,2,\dots \dots \dots ,n\right\}$ Output routes $i=\left\{1,2,\dots ,n\right\}$ for $S_1$ = 1, 2, … , n; and $d=0$ do Turns a ray counterclockwise from the DL. Connect d with j that is crossed by the ray,  $j\in S_1$ Now, $d=j$ and unload $q_j$ at location j $S_1=S_1-j$ and $Q=Q-q_j$  while $\left(Q\ne 0\right)$ do repeat 3   if $\left(Q=0\right)$ then back to DL and get route $i=1$   end if end while  while $\left(S_1\ne 0\right)$ do repeat 3–5, and get routes $i=2,\dots ,n$   if $\left(S_1=0\right)$ then back to DL   end if  end while end forreturn $S_2,S_3,\dots \dots .,S_n$	Input set of customers $S_i=\left\{1,2,\dots \dots \dots ,n\right\}$ Output routes $i=\left\{1,2,\dots ,n\right\}$ for $S_1$ = 1, 2, … , n; and $d=0$ do $C_{\mathrm{dj}}=min\left\{C_{\mathrm{dj}}\right\}j\in S_1$ Now, $d=j$ and unload $q_j$ at location j $S_1=S_1-j$ and $Q=Q-q_j$  while $\left(Q\ne 0\right)$ do  repeat 2   if $\left(Q=0\right)$ then   back to DL and get route $i=1$   end if  end while  while $\left(S_1\ne 0\right)$ do  repeat 2–4, and get routes  $i=2,\dots ,n$   if $\left(S_1=0\right)$ then   back to DL   end if  end while  end forreturn $S_2,S_3,\dots \dots .,S_n$
Where $D$ is distance, $C$ is cost, $d$ is DL location, $Q$ is vehicle capacity, $q_j$ is the demand of a customer

Figure 4 illustrates that the heuristic methods NNH, SH, and CWH follow different routes, as shown in Figure 4(a–c), respectively. On different routes, there are discrepancies in fuel consumption and path distances, as summarised in Table 8. The detailed calculations of fuel consumption for each heuristic are shown in Appendix Section A1. The NNH method follows the longest route of 384 km, while CWH travels the shortest route, spanning 335 km. Consequently, NNH consumes the maximum amount of fuel at 93.988 L, whereas CWH consumes the minimum amount, totalling 79.815 L. Furthermore, SH travels a distance of 381 km and consumes 88.427 L of fuel, which is nearly comparable to NNH. Analyzing the results of Table 8, it is evident that CWH is optimal as it saves 14.63% and 13.73% of travel distance compared to NNH and SH, respectively.

Table 8. Routes, path distances, and fuel consumptions for the heuristics.

Heuristics	Route	Path distance (km)	Fuel consumption (L)
NNH	1-2-3-4-5-6-7-8-1	384	93.988
SH	1-3-4-5-6-2-7-8-1	381	88.427
CWH	1-2-8-7-6-5-4-3-1	335	79.815

4.3. Performance determination and comparison

We consider a large-scale cargo weighing 14 tons (CLVEHICLES.COM, n.d.) in this research to deliver 10 tons of goods to eight wholesalers. This travels through the various routes, as shown in Figure 4. From the comparison matrix in Table 8, we find that CWH is superior, as it cuts off 14.65% and 9.74% more transportation costs than NNH and SH, respectively. The details of cost performance for each heuristic have been shown in Appendix Section A3.

The performance determination of these heuristics shows that NNH, SH, and CWH achieved percentages of 85.35%, 90.26%, and 100%, respectively.

The efficiency and economic conditions of a route are determined by the cost performance of a heuristic. This performance depends on fuel consumption. As the vehicle travels along different paths due to the changes in DL, varying amounts of fuel are consumed. In this section, we have explained why there are differences in fuel consumption and compared their respective fuel usage.

Table 6 summarises that although the path distance remains consistent at 335 km for all DLs, the quantity of products unloaded to each wholesaler is not consistent. Figure 5(a–g) compare the GVWs across various routes with the DL, KUS. In Figure 5(a), the comparison between the GVWs depicted by the blue and orange curves primarily focuses on DL. If FAR is selected as the depot, the vehicle attains GVWs represented by the orange curve. Conversely, GVWs for the KUS depot are illustrated by the blue curve. W and D in the X-axis indicate the wholesalers and the depot, respectively, and the numerical values in the Y-axis indicate GVW. These figures consistently demonstrate lower GVWs for KUS compared to other depots, indicating higher fuel savings with more significant differences between GVWs. Notably, Figure 5(e and g) exhibit the highest differences, resulting in maximum fuel savings of 12.892 L and 19.224 L, respectively. Conversely, Figure 5(a–f) show lower differences among GVWs, resulting in average fuel savings of 6.61 L, 6.61 L, 6.752 L, 7.104 L, and 8.145 L, respectively.

Figure 5. Comparison of GVWs between (a) KUS and FAR, (b) KUS and MAG, (c) KUS and RAJ, (d) KUS and CHO, (e) KUS and JHE, (f) KUS and JES, and (g) KUS and NAR

Figure 6 shows the comparison of fuel consumption for each DL and heuristic method, highlighting that the DL, KUS consistently utilise the least fuel. This proves that the route for the depot KUS is optimal. Furthermore, it suggests that the employed heuristics fall short in identifying the optimal transportation route. The dark red colour represents fuel consumption for various depots, and the purple colour represents the heuristics.

Figure 6. Fuel consumption comparison for each DL and heuristic method.

5. Model verification under various scenarios

To justify our results and verify our mathematical models, we examined eight instances with random load distributions among the wholesalers, detailed in Table 9. In Figure 6, KUS demonstrated the optimal outcome. Hence, we adjusted its load by increasing it to 4 tons and subsequently reducing it to 0.5 tons. Later, we evenly distributed loads among the wholesalers, ensuring minimal disparities among them.

Table 9. Various quantities of loads (tons) are to be delivered to the wholesalers for different instances.

Instances	KUS	RAJ	MAG	FAR	CHO	JHE	JES	NAR
1	0.5	1	1.5	1	2.5	1.5	1	1
2	1	1	1.5	1	2	1.5	1	1
3	1.5	1	1.5	1	1.5	1.5	1	1
4	2	1	1.5	1	1.5	1	1	1
5	2.5	1	1.5	1	1.5	1	1	0.5
6	3	1.5	0.5	1.5	1.5	0.5	1	0.5
7	3.5	1	0.5	1.5	1	1	1	0.5
8	4	1	0.5	1	1	1	1	0.5

Our models were used to run these instances, and those showed different results for each instance. For instances 1 and 2, the loads assigned to KUS were 0.5 and 1.0 tons, respectively, leading JHE and FAR to be optimal, respectively. Those minimised fuel consumption to 77.885 L and 81.966 L, saving a maximum of 10.54% and 5.56% fuel, respectively. However, across the remaining six instances, from 3 to 8, KUS consistently demonstrated optimal results, with loads ranging from 1.5 to 4.0 tons. The details of fuel consumption have been summarised in Table 10, where we have reported the consumption of fuel in the delivery route $\left(f_{\mathrm{ld}}\right)$, the return route $\left(f_{\mathrm{lr}}\right)$, and their summation $\left(C_{\mathrm{tf}}\right)$. This table illustrates that increased loads on KUS result in greater fuel savings. For instance, loads of 2.0, 2.5, 3.0, 3.5, and 4.0 tons in instances 4–8 corresponded to fuel consumptions of 75.185 L, 73.197 L, 72.558 L, 72.799 L, and 72.243 L, respectively, demonstrating a clear trend of decreased fuel consumption with higher loads in KUS. The optimal depots for each instance are summarised in Table 11.

Table 10. Fuel consumption for each depot in various instances.

Inst.	DL	$f_{\mathrm{ld}}$	$f_{\mathrm{lr}}$	$C_{\mathrm{tf}}$	Inst.	DL	$f_{\mathrm{ld}}$	$f_{\mathrm{lr}}$	$C_{\mathrm{tf}}$
1	KUS	66.586	12.452	79.039	2	KUS	75.651	9.578	85.229
	FAR	76.556	5.938	82.495		FAR	76.027	5.938	81.966
	MAG	76.557	5.938	82.496		MAG	76.557	5.938	82.496
	RAJ	67.405	12.452	79.857		RAJ	76.346	5.747	82.093
	CHO	76.557	6.896	83.454		CHO	77.297	6.896	84.194
	JHE	70.988	6.896	77.885		JHE	74.505	8.620	83.126
	JES	69.736	8.620	78.357		JES	80.105	6.321	86.427
	NAR	77.479	8.620	86.100		NAR	77.899	8.620	86.520
3	KUS	64.103	12.452	76.556	4	KUS	62.732	12.452	75.185
	FAR	75.536	5.938	81.475		FAR	74.811	5.938	80.750
	MAG	75.536	5.938	81.475		MAG	74.811	5.938	80.750
	RAJ	75.855	5.747	81.602		RAJ	75.130	5.747	80.877
	CHO	77.877	6.896	84.774		CHO	76.206	6.896	83.103
	JHE	75.130	8.620	83.751		JHE	76.450	8.620	85.071
	JES	80.630	6.321	86.952		JES	81.734	6.321	88.056
	NAR	78.365	8.620	86.986		NAR	79.303	8.620	87.924
5	KUS	60.745	12.452	73.197	6	KUS	60.111	12.447	72.558
	FAR	73.423	5.938	79.362		FAR	73.232	5.936	79.168
	MAG	73.423	5.938	79.362		MAG	73.232	5.936	79.168
	RAJ	73.742	5.747	79.489		RAJ	73.565	5.745	79.310
	CHO	73.758	6.896	80.655		CHO	72.768	6.894	79.662
	JHE	74.953	8.620	83.574		JHE	76.833	8.617	85.450
	JES	80.5539	6.321	86.875		JES	72.086	8.617	80.703
	NAR	78.858	6.321	85.180		NAR	83.165	8.617	91.782
7	KUS	60.346	12.452	72.799	8	KUS	59.791	12.452	72.243
	FAR	74.276	5.938	80.215		FAR	75.642	5.938	81.581
	MAG	74.276	5.938	80.215		MAG	75.641	5.938	81.580
	RAJ	75.112	5.747	80.859		RAJ	75.991	5.747	81.738
	CHO	73.555	6.896	80.452		CHO	72.431	6.896	79.328
	JHE	71.656	6.896	78.552		JHE	74.545	8.620	83.166
	JES	70.985	8.620	79.606		JES	70.122	8.620	78.743
	NAR	79.006	6.321	85.328		NAR	77.915	6.321	84.237

Table 11. Optimal DL for each instance.

Instances	1	2	3	4	5	6	7	8
Optimal DL	JHE	FAR	KUS	KUS	KUS	KUS	KUS	KUS

6. Conclusions, implications, and future research scopes

The selection of optimal DL for a CVRP is important in logistics because the selection of non-optimal DL requires more transportation costs and delivery time. The choice of heuristic method may not result in optimality; hence, our study aims to develop mathematical and analytical models to identify the most efficient route within a transportation network. Besides, this article deals with identifying the starting point for transportation. Since a transportation network is composed of multiple routes and a number of distribution centres or wholesalers (see Figure 2), a random choice of a route and its starting point may result in higher transportation costs and delivery times. Our models work perfectly for those who are planning to locate a depot within a transportation network. Since travel distances and loads to be delivered make it complex to find the optimal route, our study offers companies the advantage of selecting the optimal route, thus enhancing operational efficiency.

Our research involved the utilisation of three heuristics – NNH, SH, and CWH – to analyze our findings. Despite CWH covering the same distance of 335 km, it falls short of optimality as it requires 79.815 L of fuel, whereas our optimal outcome stands at 72.558 L. On the other hand, the remaining two heuristics, NNH and SH, cover greater distances and incur higher fuel consumption rates of 29.54% and 21.87%, respectively. These results indicate the inability of heuristics to ensure optimality; the selection of a specific heuristic can lead to increased fuel usage or transportation expenses. Additionally, determining the optimal DL using heuristic techniques presents a greater challenge.

Our research concludes that a company should follow our models to find the best depot. It is essential to calculate fuel consumption for each potential location considered as a DL. In this study, we evaluated each district as a DL and identified KUS as the most suitable depot for Ly-Foods’ transportation network. We found that if the company locates its depot in KUS, they can save a maximum of 10.43 L fuel, or 1418.48 tk., in a single trip. This result is valid for the eight wholesalers and their demands that we have considered in this research. In the case of any changes in wholesalers’ demands or locations, we need to go through these models again. Hence, we have considered eight instances to verify our findings where we uniformly adjusted the loads among the wholesalers. These instances showed that optimal DL varies with changes in loads. For example, in instances 1 and 2, JHE and FAR were identified as optimal depots, respectively (refer to Tables 10 and 11). Nonetheless, KUS emerged as the optimal depot in the remaining six instances. We noted that delivering a higher quantity of goods, ranging from 1.5 tons to 4.0 tons, to the initial wholesaler, KUS, resulted in reduced fuel consumption for subsequent deliveries, thus yielding cost savings. The optimal depot for Ly-Foods will be KUS if the company delivers products to its wholesalers as per the considerations made in this study. Depot KUS will save a maximum of 1418.48 tk. in a single trip. These findings benefit the management by reducing not only the transportation costs but also the delivery time. The other benefits that might come from our study are summarised below.

• Determines fuel consumption in each route,

• Finds the optimal route, and

• Reduces fuel consumption and transportation costs.

One important thing, the distance from the factory to the selected depot, has not been considered in this study. The distance from the factory to each wholesaler can be considered in the future study. It has an impact on optimality. For example, we found KUS to be the optimal depot, but it may be the longest distance from the factory, and it may require much more fuel to reach KUS. Besides, this study has not considered any time window restricted by any wholesaler. However, this research suggests some guidelines for practical implications.

Practical implications: There are many food and beverage industries in Bangladesh that supply products in different quantities throughout the country. Some of them are startup companies that have started within a limited area, and they have a plan to expand their distribution areas soon. These scenarios present ideal opportunities for the adoption of our models. Besides, there are many companies that follow their established routes, but transportation costs are high. They can adopt our models and determine the optimal route. Again, the companies following heuristic methods can verify their optimality with our models. Finally, our models serve to aid companies in various scenarios: (a) incorporating a new wholesaler or distribution centre into their network, (b) removing an existing wholesaler or distribution centre from their network, and (c) adjusting supply quantities as needed.

Acknowledgements

Open Access funding provided by the Qatar National Library.

Data availability

The authors confirm that most of the data is available within the article, and the remaining data used in the OPL CPLEX 22.1.1 will be available on request.

Disclosure statement

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

Additional information

Funding

The authors declare that no funds, grants, or other support were received for this research work.

Appendix

Section A1

Transportation costs in NNH

From Figure 4(a), the vehicle unloads 1.5 tons in FAR and travels to MAG. It covers a distance of 31 km to reach MAG with a GVW of 22.5 tons. Here, $d_1=31\mathrm{km};x=22.5\mathrm{tons}$ and $y_1=9.1141-0.278\times 22.5=2.86\frac{\mathrm{km}}{L}$. Subsequently, it unloads 0.5 tons in MAG, 1.5 tons in RAJ, 3.0 tons in KUS, 1.5 tons in CHO, 0.5 tons in JHE, 1.0 tons in JES, and 0.5 tons in NAR. However, the total fuel consumption is 93.513 L, with 75.888 L consumed on the delivery route ($f_{\mathrm{ld}}$) and 17.625 L consumed on the return route ($f_{\mathrm{lr}}$). Finally, the transportation cost is 12717.77 Tk because $C_l$ is $136\frac{\mathrm{tk}.}{L}$. $\begin{array}{rl}{f}_{\mathrm{ld}}& =\left\{\frac{d_1}{y_1}+\frac{d_2}{y_2}+\dots \dots +\frac{d_n}{y_n}\right\}\\ & =\left\{\frac{31}{2.86}+\frac{32}{2.99}+\dots \dots +\frac{33}{5.08}\right\}=75.888L\end{array}$ From Equation 7, $T{C}_D=f_{\mathrm{ld}}\times C_l=75.888\times 136=10320.77\mathrm{tk}.$ $\begin{array}{r}{f}_{\mathrm{lr}}=\frac{R_d}{y}=\frac{92}{5.22}=17.625L\end{array}$From Equation 8, $T{C}_R=f_{\mathrm{lr}}\times C_l=17.625\times 136=2397\mathrm{tk}.$

From Equation 9, $\mathrm{TT}{C}_{\mathrm{NNH}}=T{C}_D+T{C}_R=10320.77+2397=12717.77\mathrm{tk}.$

Transportation costs in SH

In Figure 4(b), the vehicle travels along another route where $f_{\mathrm{ld}}=70.802L$ and $f_{\mathrm{lr}}=17.625L$ and $\mathrm{TT}{C}_{\mathrm{SH}}=12026.07\mathrm{tk}$. $\begin{array}{r}T{C}_D=f_{\mathrm{ld}}\times C_l=70.802\times 136=9629.07\mathrm{tk}.\end{array}$ $\begin{array}{r}T{C}_R=f_{\mathrm{lr}}\times C_l=17.625\times 136=2397\mathrm{tk}.\end{array}$ $\begin{array}{r}\mathrm{TT}{C}_{\mathrm{SH}}=T{C}_D+T{C}_R=9629.07+2397=12026.07\mathrm{tk}.\end{array}$

Transportation costs in CWH

In Figure 4(c), the vehicle travels along another route where $f_{\mathrm{ld}}=74.068L$ and $f_{\mathrm{lr}}=5.747L$ and $\mathrm{TT}{C}_{\mathrm{CWH}}=10854.84\mathrm{tk}$. $\begin{array}{r}\mathrm{TT}{C}_{\mathrm{CWH}}=T{C}_D+T{C}_R=10073.25+781.59=10854.84\mathrm{tk}.\end{array}$

Section A2

We have computed distances and fuel consumption among the wholesalers, considering the DL in each district. But here we have shown the distance matrix and fuel consumption matrix for the DL at KUS; as an example, those are detailed in Tables A1 and A2, respectively.

Table A1. The distance matrix for the DL at KUS.

	KUS	RAJ	MAG	FAR	CHO	JHE	JES	NAR
KUS	0	50	120	65	117	36	75	108
RAJ	50	0	65	73	95	46	93	117
MAG	120	65	0	32	30	83	100	118
FAR	65	73	32	0	31	29	46	45
CHO	117	95	30	31	0	80	96	92
JHE	36	46	83	29	80	0	45	79
JES	75	93	100	46	96	45	0	33
NAR	108	117	118	45	92	79	33	0

Table A2. The fuel consumption matrix for the DL at KUS.

	KUS	RAJ	MAG	FAR	CHO	JHE	JES	NAR
KUS	0	19.84	19.76	24.79	11.76	9.85	19.35	23.01
RAJ	19.84	0	8.66	7.82	28.24	17.78	20.81	23.21
MAG	19.76	8.66	0	8.08	15.29	6.21	9.57	8.85
FAR	24.79	7.82	8.08	0	27.53	17.14	19.97	18.09
CHO	11.76	28.24	15.29	27.53	0	7.71	15.60	21.24
JHE	9.85	17.78	6.21	17.14	7.71	0	9.36	15.54
JES	19.35	20.81	9.57	19.97	15.60	9.36	0	6.49
NAR	23.01	23.21	8.85	18.09	21.24	15.54	6.49	0

Section A3

Cost performance

Cost performance $\left(\mathrm{TT}{C}_{P-i}\right)$ was determined using Equation 10. $\mathrm{TT}{C}_{P-i}$ is the ratio of $\mathrm{TT}{C}_m$ and $\mathrm{TT}{C}_i$ where $i=\mathit{NNH},\mathit{SH},\mathit{CWH}\mathit{etc}$. $\begin{array}{rl}\mathrm{TT}{C}_{P-\mathrm{NNH}}& =\left(\frac{\mathrm{TT}{C}_m}{\mathrm{TT}{C}_i}\right)\times 100\mathrm{\%}=\left(\frac{\mathrm{TT}{C}_{\mathrm{CWH}}}{\mathrm{TT}{C}_{\mathrm{NNH}}}\right)\times 100\mathrm{\%}\\ & =\left(\frac{10854.84}{12717.77}\right)\times 100\mathrm{\%}=85.35\mathrm{\%}.\end{array}$ $\begin{array}{r}\mathrm{TT}{C}_{P-\mathrm{SH}}=\left(\frac{10854.84}{12026.07}\right)\times 100\mathrm{\%}=90.26\mathrm{\%}\end{array}$ $\begin{array}{r}\mathrm{TT}{C}_{P-\mathrm{CWH}}=\left(\frac{10854.84}{10854.84}\right)\times 100\mathrm{\%}=100\mathrm{\%}\end{array}$