An Exact Approach to the Multi-Compartment Vehicle Routing Problem: The Case of a Fuel Distribution Company

Abstract

Over the years, the vehicle routing problem has been studied by several authors, creating several extensions, such as the multi-compartment vehicle routing problem. Several studies in the literature have addressed this problem, but few have solved it through exact approaches owing to model convolution. In this way, a mathematical model is proposed for the multi-compartment vehicle routing problem with time windows, in which three types of fuel products are distributed to a set of customers using a limited homogeneous fleet. The model explicitly considers time windows, as well as regulatory rest times for the drivers and time limits for each trip and for working schedules, addressing a real company’s decision support requirements, which is scarce in the literature. The optimal solution determines, for each vehicle, the distribution route and time to carry out the deliveries with the corresponding loading of products to compartments, complemented by the calculation of carbon emissions. The main objective is to minimize the total distance traveled, which corresponds to the sum of the distances traveled by each one of the allocated vehicles. The results allow the assessment of the solution optimization applied to a set of instances for a Portuguese company to evaluate the performance and compare decision support improvements with current baseline company procedures.

1. Introduction

Over the years, organizations have increasingly recognized the value of effective supply chain management, which can significantly contribute to their competitive advantage. The efficiency of current global supply chains has been supported by advancements in information systems, logistics, operations management, and various other domains [1]. Nevertheless, achieving effective supply chain management is a complex task, considering the increasing product variability, short product life cycles, and globalization of business [2]. Lambert and Enz [3] noted that successful supply chain management requires the integration of diverse functions and entities, enabling optimal resource management decisions as companies operate within interconnected networks.

Within supply chains, the promotion of distribution systems that facilitate interconnectivity among entities is essential. These systems have assumed a crucial role because optimal operation and planning empower companies to reduce costs, regulate working hours, eliminate human errors, and allocate cost-effective transportation systems [4]. More specifically, route planning plays a key role in reducing the number of vehicles, optimizing goods’ transportation at lower costs, and fostering a heightened focus on sustainability toward the impact reduction of one of the major carbon-emitting industries [5].

Route optimization is paramount for enhancing operational efficiency, enabling the integration of model-based tools that extend decision support capabilities applied to real-sized problems and determine the optimal profitability. For this reason, the vehicle routing problem (VRP) has garnered substantial attention from researchers, with several studies exploring problem solving using diverse methodological approaches, encompassing both exact and heuristic models to build a set of routes that minimize transport costs while assigning a vehicle and a driver to each route, starting and ending at the same depot, so that all the customers’ demand is served [6,7,8,9].

This work presents a study to solve an applied problem of fuel distribution routes as a multi-compartment vehicle routing problem with time windows (MCVRPTW) by considering the requisites for the real case of a Portuguese distribution company. As noted by [10], many of these companies often do not have access to any model-based support tool and decide based on experience. The main objective is to develop a mathematical model that can perform efficient route planning in fuel distribution, assess the environmental impact caused by each vehicle, and increase the overall level of performance of the distribution process compared to the current baseline operation procedures. The optimal solution aims to minimize the distance traveled and extend the approach to consider related decision features suitable to the company’s requirements. The structure of the paper is as follows: in the next section, a brief background statement is provided for VRPs and, mainly, VRPs with fuel distribution. Section 2 presents the problem statement and the mathematical formulation. Section 3 discusses the computational experiments. Finally, Section 4 summarizes the main conclusions and final considerations.

Background

Distribution systems have become increasingly important in most diverse companies, where adequate analysis and effective planning are critical for reducing operating costs. The control of drivers’ working hours, elimination of certain human errors, and use of cost-effective transportation means are essential for effectively planning these systems [4].

The primary objective of VRPs, initially introduced by [11], is to formulate decisions toward the minimum total transportation cost. To achieve this objective, it is necessary to consider the geographical location of the company depots (or the departure points of its vehicles), the locations to be supplied, and the distances between the company and each station, as well as the distances between each station to be serviced [12]. This approach involves determining the vehicle routes, each starting and ending at the same location so that each location is visited only once, thereby minimizing costs. The number of routes can be defined as an input or a decision variable [13], considering that the demand on a route cannot exceed the vehicle’s total capacity or that the route’s duration cannot exceed the initially established time. Additional objectives can be to conduct traffic simulations to analyze various route possibilities, incorporating factors such as avoiding congestion. It is noteworthy that the importance of route planning is tied to optimizing the fleet of vehicles or route transportation costs and aligned to sustainability objectives, such as reducing greenhouse gas (GHG) emissions, pollution, and noise [5]. According to [14], the various environmental impacts caused by freight transportation are water acidification, toxic effects on ecosystems and humans, noise pollution, and the effects of GHGs. Furthermore, the authors found that GEE emissions from the transportation sector have increased and that the quantity of pollutants emitted by a vehicle depends on the cargo being transported and the speed of the vehicle. An extension of the VRP, called the pollution routing problem (PRP), aims to address the environmental impact of transportation by integrating pollution considerations into the route planning process. For instance, [12] extended the PRP by incorporating a heterogeneous fleet to minimize fleet and route costs, encompassing fuel costs, carbon emissions, and driver-related expenses.

Undoubtedly, VRP research has studied applications in logistics, engineering, applied mathematics, and computer science through the last decades. In a general formulation, routes are defined by arcs linking customers for each vehicle that must start and finish at its depot, and each arc has an associated cost, which is generally the arc’s length or travel time. From the origins of the traveling salesman problem (TSP), the VRP has been addressing several extensions, such as the capacitated vehicle routing problem (CVRP), vehicle routing problem with time windows (VRPTW), vehicle routing problem with pickup and delivery (VRPPD), and multi-compartment vehicle routing problem (MCVRP) [15]. The CVRP is a variant of the VRP that focuses on a homogeneous fleet of vehicles with a limited carrying capacity for goods and deterministic demands. The objective is to plan efficient routes for these vehicles to deliver the required goods to their destinations [16]. In the VRPTW, in addition to meeting vehicle capacities and minimizing costs, this problem imposes time windows during which customers must be served. The VRPPD involves planning routes for vehicles to collect goods from pickup locations and deliver them to specified destinations while adhering to vehicle overload capacity constraints. In contrast, the MCVRP involves vehicles with multiple compartments, each capable for carrying different types of goods or materials that are incompatible or for which their contact may be unstable or dangerous [17,18]. As noted by [19], the use of multi-compartment vehicles increases the actual logistics owing to the increasing mutually exclusive product variability, with the advantages of cost reduction and emission reduction compared with those of common single-compartment vehicles. The variants of the MCVRP are NP-hard problems [20], and the limitations of the exact approaches have been bridging the scope to heuristic/metaheuristic algorithms [21,22,23], demonstrating the model research and solution improvement to address the complexity of these decision problems, particularly in a real-world context.

In the case of fuel distribution companies, researchers have studied these systems by employing diverse approaches and planning techniques to explore different scenarios, primarily based on heuristic approaches owing to combinatorial hindrance. For instance, [24] studied an Italian road transport company for delivering fuel with vehicles of diverse capacities, focusing on developing a mathematical model to minimize the total distribution costs while satisfying customer requests. The results highlight a reduction from 5% to 25% in the total distribution costs and the high impact these savings had on the company’s total costs because the transport associated with distribution represented from about 10% to 25%. Cornillier et al. [25] addressed the same issue using an unlimited heterogeneous fleet of compartmentalized vehicles to deliver petroleum products to gas stations. In this way, it was intended to determine the amount of fuel needed to be transported in each vehicle to satisfy the demand of the station customers. In this case, the authors were limited to correspond one fuel product per compartment, and the compartment’s contents could not be divided between stations. Cornillier et al. [26] also addressed distribution systems, aiming to maximize profits by optimizing routes and minimizing distributor overtime costs, using a set of vehicles with a tractor and one or two trailers with four to six compartments that could transport between 6000 and 17,000 L. To embed stability when driving the vehicles, the authors defined that the front part of the trailers should be emptied at the end. Ng et al. [27] used a heterogeneous fleet of eight ships that could contain three fuel types, considering the replenishment of 48 stations with different capacities. Cornillier et al. [28] addressed the issue of distribution systems again, applying their study to a company based in Quebec, Canada, for which the delivery of petroleum products was carried out by a limited number of heterogeneous vehicles. For their study, they assumed that each vehicle could make several trips even though each station could only be refueled once. The main objective of their study was to maximize profit by removing the costs of routes and the distributor’s overtime from the sales revenue. More recently, [10] developed a heuristic-based approach for the MCVRPTW arising in a retail fuel distribution company to minimize the total distance traveled, achieving a distance-traveled reduction of 8%.

In conclusion, this study is motivated by the growing interest in the literature exploring exact approaches for the MCVRPTW. Given the challenges of a real distribution context, is it necessary to evaluate adequate model-based decision support approaches because the actual implementation is still limited [29]. Therefore, to evaluate and discuss the results of the proposed model, four indicators were analyzed: distance traveled, total distribution time, average vehicle capacity utilization rate, and model runtime. These indicators aim to compare the results obtained under the company’s current baseline procedures and discuss operational improvements.

2. Problem Statement and Mathematical Formulation

The problem addressed in this paper explores the real-world scenario of a fuel distribution company, as established by [10]. This company is located in the north of Portugal, as are the vast majority of its customers. The company faces added transportation challenges because there are stringent regulations for transporting hazardous materials [30]. It is assumed that customers can order three distinct types of products—agricultural diesel, road diesel, and heating oil—to be delivered exactly once. The company has a homogeneous fleet of four heavy-duty freight vehicles without a trailer, each with three compartments to accommodate the distinct types of fuel that cannot be commingled. Each compartment has a given capacity, and each fuel product type is allocated to one compartment. All the vehicles are diesel powered with an average fuel consumption rate, assuming all the vehicles travel at the same average speed. Each vehicle is driven by a worker, who is subject to a maximum number of driving hours and working hours in accordance with current legislation. In line with these regulations, the problem is extended to consider that each driver must take a rest stop on each journey. The fuel delivery demand is subject to the convenience of each customer, with each customer having their specific time window and service time, and is limited to the capacity of a vehicle’s compartment.

An extended mathematical formulation for the MCVRPTW in the fuel distribution is proposed by considering the specific issues of the applied problem for a real company. Compared with the approaches in the literature studies that were analyzed, the extended model approach addresses the company’s requirements by considering the ancillary assessment of carbon emissions, as well as the imposed rest times for drivers for regulatory purposes. The MCVRPTW concept and baseline formulation take the original models developed by [28,31] as a starting point. Let $G=\left(L, C\right)=\left(L^{\prime }\cup \left\{0\right\}, C\right)$ be a complete directed graph, where the set of locations to be visited ($N$ customer nodes) is given by $L^{\prime }=\{\mathrm{1,2},\dots ,N\},$ where 0 represents the depot, and the set of edges (arcs) is given by $C=\left\{\right(i,j):i,j\in L^{\prime },i\ne j\}.$ The cost of each arc, $\left(i,j\right)\in C$, corresponds to the distance traveled between the nodes, and it is represented by $d_{ij}.$ There is a set of different product types, $P=\left\{\mathrm{1,2},\dots ,Np\right\}$, and each customer, $i\in L^{\prime }$, demands a given quantity, $q_{jp}$, of a given product type, $p\in P$. The vehicle must serve each node, $i\in L$, within its time window, [α_i, β_i], and the service time at each customer, $i\in L^{\prime }$, is given by $s_i$. A homogeneous fleet of Nv multi-compartment vehicles is set by $V=\left\{1,\dots , Nv\right\}$ with a known capacity, Q_p, for each compartment,$p \in P$, where each compartment is associated with each product type and a corresponding loading environment. For generalization based on the considered regulations, each vehicle, $k$, travels at an average speed of $a_k$ kilometers per hour, where each corresponding driver can meet up to $h$ working hours and can drive at most t hours. Moreover, given the imposed company directives, a working rest stop is set at r hours for each trip. Finally, the FE parameter provides the carbon emission factor based on [32], where $m_k$ is the average fuel consumption per kilometer.

Decision Variables:

$w_{ik}$	Starting time at which node $i\in L$ is served by vehicle $k\in V$;
$x_{ijk}$	Equal to 1 if the arc, (i, j) $\in C$, is traveled by vehicle $\mathrm{k}\in \mathrm{V}$, 0 otherwise;
$y_{jkp}$	Equal to 1 if the product, $p\in P$, is delivered to customer $j\in L\prime$ using vehicle $k\in V,$ 0 otherwise;
$z_{jk}$	Equal to 1 if the vehicle, $k\in V$, visits node $j\in L$, 0 otherwise;
$o_k$	Auxiliary variable for calculating the average capacity utilization ratio of each vehicle, $k\in V$;
$e_k$	Auxiliary variable for calculating the carbon emissions of each vehicle, $k\in V$.

MIP Model:

$$\mathit{Minimize} {\sum }_{i,j \in L}{\sum }_{k \in V}{d}_{ij}{x}_{ijk}$$

(1)

$$\mathit{Subject}\mathit{to:} {\sum }_{i\in L}{x}_{ijk}\le 1 \forall j\in L^{\prime }, k\in V$$

(2)

$$\sum _{i\in L}{x}_{ijk}=\sum _{i^{\prime }\in L}{x}_{j{i}^{\prime }k} \forall j\in L^{\prime }, k\in V$$

(3)

$$y_{jkp}\le \sum _{i \in L}{x}_{ijk} \forall j\in L^{\prime }, k\in V, p\in P$$

(4)

$$\sum _{k\in V}{y}_{jkp}=1 \forall j\in L^{\prime }, p\in P$$

(5)

$$\sum _{j\in L^{\prime }}{y}_{jkp}{q}_{jp}\le Q_p \forall k\in V, p\in P$$

(6)

$$w_{ik}\ge \sum _{j\in L\prime }{\alpha }_i{x}_{ijk } \forall i\in L, k\in V$$

(7)

$$w_{ik} \le \sum _{j\in L^{\prime }}{\beta }_i{x}_{ijk}+h(1-\sum _{j\in L^{\prime }}{x}_{ijk}) \forall i\in L, k\in V$$

(8)

$$\frac{d_{ij}{x}_{ijk}}{a_k}\le t·z_{jk} \forall i,j\in L, j\ne i, k\in V$$

(9)

$$w_{ik}+s_i{x}_{ijk}+\frac{d_{ij}{x}_{ijk}}{a_k}+r·z_{jk}-w_{jk}\le h{(1-x}_{ijk}) \forall i\in L,j\in L^{\prime }, k\in V$$

(10)

$$\frac{\sum _{i,j\in L}{d}_{ij}{x}_{ijk} }{a_k}\le h \forall k\in V$$

(11)

$$o_k=\frac{{\sum }_{ j\in L^{\prime }, p\in P}{y}_{jkp}{q}_{jp}}{{\sum }_{ p\in P}{Q}_p} \forall k\in V$$

(12)

$$e_k=\sum _{i,j\in L}{d}_{ij}{x}_{ijk} ·m_k·FE \forall k\in V$$

(13)

$$x_{ijk}\in \left\{\mathrm{0,1}\right\} \forall i\in L, j\in L, i\ne j, k\in V$$

(14)

$$y_{jkp}\in \left\{\mathrm{0,1}\right\} \forall j\in L^{\prime }, k\in V, p\in P$$

(15)

$$z_{jk}\in \left\{\mathrm{0,1}\right\} \forall j\in L, k\in V$$

(16)

$$e_{k }\in {\mathbb{R}}^{+} \forall k\in V$$

(17)

$$w_{ik}\in {\mathbb{R}}^{+} \forall i\in L, k\in V$$

(18)

$$o_k\in {\mathbb{R}}^{+} \forall k\in V$$

(19)

In this mixed-integer programming (MIP) model, the objective function (1) seeks to minimize the distances traversed by the vehicles. Constraints (2) ensure that each customer may be visited at most once per route, and the corresponding flow conservation is addressed by constraints (3). Constraints (4) set decision variables at 0 for each product, $p\in P$, in cases where the customer, $j\in L^{\prime }$, is not visited by vehicle $k\in V$ and at 1 otherwise. Constraints (5) guarantee that each product a customer orders is transported by a single vehicle. Addressing both the compartment capacity and time window requirements, constraints (6)–(8) are applied to prevent exceeding compartment capacities and to ensure deliveries occur within the time windows defined by customers. Furthermore, constraints (9) ensure that the time taken by vehicle $k\in V$ to travel from node $i\in L$ to customer $j\in L^{\prime }$ does not exceed t hours. In this context, the binary variable, $z_{jk}$, takes the value 1 when a customer, $j\in L^{\prime }$, is visited by vehicle $k\in V$and 0 otherwise. Constraints (10) ensure the imposed company requirements, bearing that the start of the service at customer $j\in L^{\prime }$ occurs only after a rest stop, $r$, plus the completion of the service at customer $i\in L$ and the corresponding time taken on the arc, $(i,j) \in C$. Constraints (11) are imposed to enforce the working hour limit. Constraints (12) and (13) are applied to assess the average capacity utilization and resultant carbon emissions from the fuel consumption of each vehicle during deliveries$.$ Finally, the domain constraints for the decision variables are addressed in (14)–(19).

3. Numerical Experiments and Results

The developed model was implemented in IBM ILOG CPLEX Optimization Studio (version 12.10). The computational experiments were run on a PC Intel(R) CI(TM) i5-7200 U CPU @ 2.50 GHz (HP, Huston, TX, USA) and 2712 MHz, with 8 GB of RAM. All the instances are based on real data provided by the company, such as the distance matrixes in

Table A1. Distance matrixes for Cases I and II (based on [33]).

	0	1	2	3	4	5	6	7
0	-	17.57	6.12	4.69	8.30	8.75	19.95	26.92
1	17.46	-	23.19	19.97	17.81	24.61	35.28	19.25
2	6.10	23.28	-	7.48	10.62	4.37	15.04	32.09
3	4.78	20.20	7.33	-	13.09	5.86	16.86	31.71
4	8.31	17.91	10.40	13.00	-	14.11	23.21	21.99
5	8.84	24.65	4.41	5.91	14.10	-	11.78	35.58
6	20.08	35.86	14.98	17.22	23.21	12.24	-	44.10
7	27.01	19.04	31.81	31.70	21.82	35.51	43.98	-

in Appendix A, and the results are discussed based on the solution support improvement compared to the current baseline procedures. Given the considered parameters, $a_k$ is set at 55 km/hour for all the vehicles, $k\in V$; $r$ is set at 0.25 h; $t$ is set at 2 h; $h$ is set at 8 h; $m_k$ is set at 0.30 L per kilometer; Q_p is set at 5000 L; and $FE$ is set at 2.70 kgCO₂. Two initial cases for small-size instances are presented to highlight the model’s capabilities and then a computational study for several instances is discussed.

3.1. Case I

In

Table 1. Demand data for Case I.

Customer	Agricultural Diesel (L)	Road Diesel (L)	Heating Diesel (L)	Total (L)
1	500	–	–	500
2	–	5000	–	5000
3	–	1000	–	1000
4	–	–	800	800
5	500	–	–	500
6	800	–	–	800
7	–	–	800	800
Total (L)	1800	6000	1600	9400

, the set of demand orders for a given morning period is presented, in which the highest demand is set by Customers 2 and 3, who ordered road diesel. In the seven orders for a total of 9400 L, road diesel accounts for approximately 64%, agricultural diesel represents about 19%, and heating diesel represents approximately 17%. As mentioned, fuel delivery is conducted based on each customer’s available time window.

Table 2. Time window and service time data for Case I.

Customer	Time Window	Service Time (h)
1	[7 a.m., 11 a.m.]	0.25
2	[7 a.m., 11 a.m.]	0.33
3	[7 a.m., 11 a.m.]	0.33
4	[7 a.m., 12 p.m.]	0.25
5	[8 a.m., 11 a.m.]	0.25
6	[7 a.m., 12 p.m.]	0.25
7	[7 a.m., 11 a.m.]	0.25

provides the data overview of the time windows and service durations for the seven customers. It can be observed that most customers can receive orders starting from 7 a.m. until a maximum of 11 a.m. or 12 p.m., except for Customer 5, who can only accept deliveries starting from 8 a.m.

The solver achieves the optimal solution (gap 0) in approximately five seconds.

Table 3. Node schedule solution for Case I.

Node	Vehicle 1	Vehicle 2
0	07:15 a.m.	07:15 a.m.
1	11:24 a.m.	–
2	07:22 a.m.	–
3	–	07:20 a.m.
4	09:39 a.m.	–
5	08:01 a.m.	–
6	08:44 a.m.	–
7	10:33 a.m.	–
Average Capacity Utilization	56%	7%
Emissions (kgCO2)	84.2	7.7

presents the departure schedule from the initial depot and the time that each vehicle delivers to each customer, respecting the time windows. Given that the combined demand from Customers 2 and 3 exceeds the capacity of each compartment, the optimal solution involves using two vehicles for each of these customers. Therefore, Vehicle 1 delivers six orders, while Vehicle 2 only has one order, which will have a relevant impact on the capacity utilization of Vehicle 2. The total distance covered by the fleet was 113.4 km in approximately 4.25 h. The results also display the vehicle occupancy rates. In Vehicle 1, Compartment 1 has an occupancy rate of 36%, Compartment 2 is fully occupied at 100%, and Compartment 3 has an occupancy rate of 32%, resulting in an average occupancy rate of approximately 56%. Additionally, in Vehicle 2, only Compartment 2 is utilized at a rate of 20%, contributing to an average occupancy rate of around 7%. Thus, the overall average occupancy rate for both vehicles is 31.5%. Finally, by assessing the environmental impacts of the routes that were taken, it was determined that Vehicle 1 emitted most of the total carbon emissions (91.9 kgCO₂), as expected, owing to the distances covered by the vehicles.

3.2. Case II

In Case II, the number of orders is increased, as well as the ordered quantities for the same time period. The number of customers and their time windows and service times remain the same.

Table 4. Demand data for Case II.

Customer	Agricultural Diesel (L)	Road Diesel (L)	Heating Diesel (L)	Total (L)
1	5000	1500	–	6500
2	–	5000	4200	9200
3	–	1000	4200	5200
4	1850	–	800	2650
5	500	1250	–	1750
6	800	1250	–	2050
7	1850	–	800	2650
Total (L)	10,000	10,000	10,000	30,000

summarizes the customer demand. It is observed that Customer 2 has the highest order amount, totaling 9200 L, while Customer 5 has the smallest order, with only 1750 L, for a total of 30,000 L of fuel products.

The optimal solution is summarized in

Table 5. Node schedule solution for Case II.

Node	Vehicle 1	Vehicle 2	Vehicle 3	Vehicle 4
0	07:15 a.m.	07:15 a.m.	07:15 a.m.	07:15 a.m.
1	–	07:34 a.m.	–	–
2	–	–	07:22 a.m.	–
3	07:20 a.m.	–	–	–
4	–	–	–	08:38 a.m.
5	08:01 a.m.	–	–	–
6	08:44 a.m.	–	–	–
7	–	–	–	07:44 a.m.
Average Capacity Utilization	60%	43%	61%	35%
Emissions (kgCO2)	34.4	28.4	9.9	46.2

. It is observed that all four vehicles depart from the initial depot at 7:15 a.m. to avoid unnecessary waiting times, and the total distribution time is about 5 h. According to the results, the total average occupancy rate of the vehicles is approximately 50%, which is improved from Case I owing to the added orders. It is also verified that Vehicle 4 has the highest carbon emissions, given that Vehicle 4 covers a longer distance despite not performing the majority of the deliveries.

In summary, the optimal solution given for Case II, with more vehicles, generates a total distribution time decrease of 23.3% compared to Case I (Figure 1), despite covering more distance owing to the increased number of orders and the quantity demanded by each customer. This fact demonstrates the feasibility of the model to generate optimal solutions that minimize the route distance and compute additional performance indicators suitable for the decisionmaker.

3.3. Computational Experiments

These computational experiments aim to analyze the optimal solution and corresponding model runtime while varying parameters and instance sizes. The discussion of results deduces the expected computational hindrance of an exact approach to the given MCVRPTW feasibility. To achieve this, we generated 36 instances given the data presented in

Table A2. Distance matrixes for computational experiments (based on [33]).

	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
0	-	10.30	15.8	3.8	2.7	1.9	9	4.63	1	0.25	4.7	4.43	1.48	0.52	13.6	23	12.1	0.78	3.89	3.84	4.85
1	10.5	-	7.8	6.6	8.6	8.8	6.5	11.7	10.9	10.4	10.8	6.35	11.2	10.5	22.5	13	2.91	10.9	6.42	9.2	14.1
2	15.6	7.70	-	13.2	15.1	15	14.2	18.5	16.5	15.8	20.1	13	17	16.1	29.1	12.7	4.76	16.1	12.7	16.7	20.3
3	3.9	6.70	13.3	-	2	2.2	5.5	5.35	4.33	4.04	7.47	0.39	4.58	4.1	16.1	19.3	8.95	4.68	0.596	4.73	7.5
4	2.6	8.70	15.2	2.1	-	1	6.3	3.46	2.82	2.84	5.5	2.26	2.93	2.72	14.1	21.1	10.9	3.56	2.42	4.2	5.51
5	1.8	8.90	15.2	2.3	0.9	-	7.1	3.94	2.14	2.02	5.31	2.57	2.38	2	14.2	21.5	11	2.73	2.43	5.1	5.42
6	8.9	6.60	14.7	5.3	6.3	7.4	-	7.62	9.04	9.08	10.9	5.11	9.13	9	17.8	16.2	9.46	9.8	5.87	3.7	10.9
7	4.61	11.65	18.6	5.43	3.5	3.98	7.6	-	3.84	4.5	3.41	5.55	3.48	4.17	10.8	23.6	14.2	5	5.85	4.15	3.28
8	1.02	10.80	16.5	4.3	2.84	2.14	9.08	3.88	-	0.8	3.65	4.72	0.45	0.79	12.8	23.6	12.8	1.22	1.22	6.61	3.83
9	0.26	10.35	15.9	4	2.8	2.05	9	4.6	0.83	-	4.43	4.43	1.22	0.32	13.5	23.2	12.2	0.75	4.06	6.9	4.65
10	4.8	10.90	20	7.46	5.6	5.32	11	3.4	3.66	4.41	-	7.74	3.26	4.13	9.13	26.6	16.3	4.44	7.73	7.61	0.309
11	4.4	6.32	12.8	0.4	2.32	2.6	5.1	5.53	4.7	4.45	7.73	-	4.95	4.46	16.4	18.9	8.72	5.1	0.791	4.6	7.79
12	1.5	11.00	17.2	4.6	3	2.4	9.1	3.49	0.46	1.27	3.2	4.94	-	0.92	12.4	23.9	13.2	1.6	4.74	6.5	3.4
13	0.56	10.40	16	4.3	2.7	1.96	9.1	4.5	0.82	0.4	4.13	4.47	0.9	-	13.2	23.3	12.4	0.92	16.5	6.7	4.33
14	13.60	22.40	29	16.2	14	14.1	18	10.5	12.9	13.4	9.1	16.6	12.5	13.1	-	34	25	13.5	16.5	14.1	8.95
15	22.9	13.2	12.9	19.5	20	21	16.7	23.8	23	23.5	26.4	18.7	24	23.1	34.1	-	12.2	23.8	19.2	19.9	26.2
16	12	2.93	4.8	9	11	10.8	9.5	14.3	13	12	16.1	8.7	13.4	12.6	25.1	12.1	-	12.6	8.54	12	12
17	0.8	11	16	4.7	4.54	2.7	10	5.1	1.2	0.77	4.48	5	1.8	0.9	13.3	23.7	12.65	-	4.6	7.64	7.6
18	3.9	6.4	12.5	0.6	2.5	2.4	5.85	5.9	1.2	4	7.7	0.9	4.7	16.6	16.4	19.3	8.6	4.5	-	5.37	5.35
19	3.8	9.1	16.8	4.8	4.3	5	3.9	4.2	6.6	7	7.5	4.5	6.8	6.9	13.9	19.6	11.8	7.75	5.4	-	7.45
20	4.9	14	20.5	7.3	5.5	5.4	11	3.3	3.9	4.6	0.4	7.8	3.5	4.3	9	26.1	12.3	7.7	5.3	7.5	-

and

Table A3. Data table and results of the computational experiments (based on [33]).

Instance	Number of Customers	Number of Orders per Customer	Number of Vehicles	Number of Restrictions	Number of Variables	Number of Iterations	Traveled Distance (km)	Runtime (s)
1	5	1	1	112	63	35	34.9	4.30
2			2	209	126	835		4.49
3			3	306	189	510		4.79
4			4	403	252	966		4.93
5		2	1	112	63	35		4.61
6			2	209	126	835		4.88
7			3	306	189	510		5.20
8			4	403	252	966		5.09
9		3	1	112	63	35		4.32
10			2	209	126	835		4.39
11			3	306	189	510		4.43
12			4	403	252	966		5.13
13	10	1	1	317	173	99	48.13	4.95
14			2	604	346	25,273		5.91
15			3	891	519	12,487		6.44
16			4	1178	692	48,833		7.07
–		2	1	(a)	(a)	(a)	(a)	(a)
17			2	604	346	109,477	52.81	9.23
18			3	891	519	56,649		12.19
19			4	1178	692	74,646		10.90
–		3	1	(a)	(a)	(a)	(a)	(a)
20			2	604	346	52,178	53.53	7.55
21			3	891	519	53,051		9.97
22			4	1178	692	88,679		9.50
–	15	1	1	(a)	(a)	(a)	(a)	(a)
23			2	1199	666	249,698	83.16	18.91
24			3	1776	999	471,219		32.87
25			4	2353	1332	306,241		24.72
–		2	1	(a)	(a)	(a)	(a)	(a)
26			2	1199	666	48,927	87	96.79
27			3	1776	999	702,346		65.46
28			4	2353	1332	5,493,521		612.03
–		3	1	(a)	(a)	(a)	(a)	(a)
–			2	(a)	(a)	(a)	(a)	(a)
29			3	1776	999	27,174,164	94.59	1748.37
30			4	2353	1332	53,833,200		3438.25
–	20	1	1	(a)	(a)	(a)	(a)	(a)
31			2	1994	1086	481,747	85.87	47.67
32			3	2961	1629	1,155,072		102.65
33			4	3928	2172	1,641,255		170.10
–		2	1	(a)	(a)	(a)	(a)	(a)
–			2	(a)	(a)	(a)	(a)	(a)
34			3	2961	1629	19,773,423	91.51	908.14
35			4	3928	2172	72,681,394		8880.44
–		3	1	(a)	(a)	(a)	(a)	(a)
–			2	(a)	(a)	(a)	(a)	(a)
–			3	(a)	(a)	(a)	(a)	(a)
36			4	3928	2172	269,092,131	97.77	28,059.70

(a) Quantities exceed vehicle’s capacity.

in Appendix A based on real company data. The instances considered different combinations of the number of orders per customer and number of vehicles for 5, 10, 15, and 20 customers, while the ordered quantity was set at 1000 L for each product type. Considering the amount ordered and the fleet size, some combinations were disregarded as instances owing to capacity violations, as well as instances from 21 customers and 3 orders per customer onward to avoid exceeding the overloading boundaries. The time windows and service times for each customer are presented in

Table 6. Time window and service time data for the computational experiments.

Customer	Time Window	Service Time (h)
1	[7 a.m., 6 p.m.]	0.25
2	[7 a.m., 6 p.m.]	0.33
3	[7 a.m., 6 p.m.]	0.33
4	[7 a.m., 6 p.m.]	0.25
5	[8 a.m., 1 p.m.]	0.25
6	[7 a.m., 6 p.m.]	0.25
7	[7 a.m., 11 a.m.]	0.25
8	[7 a.m., 6 p.m.]	0.25
9	[7 a.m., 6 p.m.]	0.25
10	[7 a.m., 6 p.m.]	0.33
11	[7 a.m., 6 p.m.]	0.25
12	[8 a.m., 1 p.m.]	0.33
13	[7 a.m., 6 p.m.]	0.33
14	[7 a.m., 6 p.m.]	0.25
15	[8 a.m., 1 p.m.]	0.25
16	[7 a.m., 6 p.m.]	0.25
17	[7 a.m., 11 a.m.]	0.25
18	[7 a.m., 6 p.m.]	0.25
19	[7 a.m., 6 p.m.]	0.25
20	[7 a.m., 6 p.m.]	0.33

. It can be observed that most customers can receive orders starting from 7 a.m., except for customers 5, 12, and 15, who can only accept orders starting from 8 a.m. Furthermore, customers can receive orders until a maximum of 6 p.m., except for some customers who can only receive until 11 a.m. or 1 p.m.

Figure 2 shows the respective optimal solution objectives of the total distances traveled and the corresponding model runtimes of the 36 instances, which remain fairly negligible until Instance 27 and reach 30 min in Instance 28 (see detailed results in Table A3 in Appendix A). Beyond this point, there is an increase, reaching approximately 57 min in Instance 30. However, starting from Instance 34, the runtime rises exponentially, which can be explained by the combinatorial complexity of the number of customers associated with a different number of vehicles/orders per customer (e.g., Instance 36 considers 2172 variables and 3928 restrictions while performing over 2.7 × 10⁸ iterations). It should be noted that the company found this limitation suitable because current operational problems fall under these problem-size dimensions.

To highlight the advantages of the proposed optimization approach for the MCVRPTW, these results can be further analyzed and compared with current planning procedures implemented at the company. As expected, all the proposed solutions excelled, and, as an example, Figure 3 presents the compared values obtained for the distribution routes for Instance 30 and Instance 36. In Instance 30, a total distance of 94.59 km is traveled, while in Instance 36, the total distance traveled is 97.78 km, verifying reductions of 28.3% and 36.5%, respectively, which impact the overall reduction in carbon emissions.

Table 7. Comparison of results obtained for Instances 30 and 36.

		Instance 30	Instance 36
Proposed Approach	Emissions (kgCO2)	76.6	79.2
	Total Distribution Time (h)	11.7	8.9
	Total Average Capacity Utilization	60%	60%
Current Planning	Emissions (kgCO2)	106.9	124.7
	Total Distribution Time (h)	10.4	7.8

provides additional results comparing each solution concerning carbon emissions, total distribution times, and average vehicle capacity utilizations, whereas the company’s current procedure does not comply with the mandatory rest time of the drivers.

4. Conclusions

This paper explores the complexity of the MCVRPTW within the distribution sector, focusing on a fuel transportation company’s case. The developed mathematical formulation is proposed for route planning using multi-compartmental vehicles with time windows, aiming to minimize distances traveled and evaluate the solution distribution time, carbon emission impact of each vehicle, and average vehicle capacity utilization rate. Formulation constraints were extended to consider the maximum travel times, driver rest stop periods, and regular working hours to address regulations imposed on the company. The model was validated through real-world instances based on a Portuguese company. The results of computational experiments were discussed to explore the boundaries of the exact approach to implementation concerning the suitability of the model’s runtime, concluding that the model could be effectively applied to up to 20 customers, with three orders per customer and four vehicles, which is adequate for the company’s operational necessities. Furthermore, a comparative analysis with the company’s current planning procedures revealed that the proposed approach achieved route distance reductions of up to 36.5%. Additionally, model solutions with mandatory driver rest stop constraints were satisfied, enabling the generation of plans that closely align with real-world scenarios and regulatory conditions and can be easily adapted to transport other similar materials. As future work, it is intended to consider the sensitivity analysis of uncertainty parameters and introduce a heterogeneous fleet while incorporating the effects of carbon and other GHG emissions into the objective function. Likewise, owing to the verified limitations of an exact approach, non-exact approaches, such as metaheuristics, can also be explored to deal with increasing real-sized problems efficiently.