Optimal Vehicle Routing in Consumer Goods Distribution: A GNU Linear Programming Kit-Based Analysis

In a 2020 report by the United States Environmental Protection Agency (EPA), it was highlighted that the transportation sector contributed to the largest proportion (27%) of greenhouse gas emissions (Figure 1) [1]. A staggering 90% of the fuel employed for transportation has been found to be petroleum-based, encompassing chiefly gasoline and diesel. Predominantly, these transportation-associated greenhouse gas emissions emanate from the combustion of petroleum-based products in internal combustion engines.

The VRP has been identified as having a pivotal role in minimizing distribution costs and underscoring the environmental repercussions stemming from excessive vehicle usage and fuel combustion [2]. The actual cost incurred by a vehicle transiting between two points has been determined to be contingent on various factors, including vehicle load, per-kilometer fuel consumption, fuel price, time expenditure, distance traversed, and depreciation.

Critical to distribution companies is the effective management of their vehicle fleets. It has been posited that resolving the "routing and scheduling problem" is essential to this end [2]. Decisions concerning the spatial configuration of vehicle routes within transportation networks often give rise to a myriad of challenges and stipulations that have been categorized under the umbrella term "routing problems".

The significance of the VRP is underscored by its prevalence in academic literature, with over 550,000 results retrieved on Google Scholar upon querying the term VRP [3]. Additionally, in recent years, more than 71,600 articles addressing the topic have been documented. It has been observed that with the evolution of corporate functions, increasing complexity of distributions, technological advancements, and the emergence of novel problem-solving tools, a variety of VRP modifications and optimizations have surfaced. Application areas for VRP have diversified, even spanning domains such as agriculture [4], [5].

Central to VRP is the delineation of the most efficient route conglomerate, all while adhering to operational constraints. Often, these constraints are informed by the nature of the freight, service quality benchmarks, and vehicular features [6]. Standard limitations encompass route duration, vehicular load constraints, specific customer requirements for goods delivery or pickup, and designated service timeframes.

Figure 2 shows the vehicle routing problem with one depot and a set of routes that include all customers. Each branch in the route has a weight coefficient associated with it.

In literature, the VRP has been characterized by certain authors [7] as the quest for route designs that minimize costs, with each route originating and culminating at a centralized depot, and a fleet tasked with goods delivery to geographically dispersed clientele. It has been emphasized that each client ought to be serviced once, and the cumulative delivery should not breach vehicle capacity constraints.

Recognized as a combinatorial optimization and integer programming challenge, VRP has been established as a tool for deducing the most propitious routes to facilitate goods and services delivery to a constrained client set [8]. Defined succinctly, VRP encompasses the route sets those vehicles, tasked with goods delivery, adopt to serve clients, with each client being serviced once and vehicles returning to their point of origin [9].

In recent decades, the adoption of optimization tools for the effective orchestration of goods procurement and delivery in distribution networks has witnessed an upswing. Concurrently, the environmental implications, particularly the deteriorative impact on the ecological milieu due to transportation vehicle activities, have garnered significant attention. Notwithstanding advancements in the integration of eco-friendly technologies aimed at curtailing greenhouse gas emissions, it has been observed that the quantum of pollutants, especially carbon dioxide equivalents CO₂, has escalated, thereby exacerbating public health concerns [10].

For the resolution of the routing conundrum, a collection of routes that aspires to minimize the total distance traversed is sought. Such a collection must adhere to the following criteria:

•All users or customers are encompassed within the formulated routes.

•Every user or customer is to be approached only once.

•Commencement and conclusion of each route occur at the depot.

Applications of the VRP have been observed across diverse industries, particularly those reliant on varied vehicle types to execute specific tasks. Given a complete graph $G=(N, E)$, where $N=\{0,1, \ldots, n\}$ and $E \subseteq\{(i, j) \mid i \in N, j \in N\}$, node 0 symbolizes the depot. C, which is depicted as $C \in N \backslash\{0\}$, denotes the cluster of users or customers, excluding the depot. To construct the mathematical model, a specific notation was introduced [11]:

$x_{i j}=\left\{\begin{array}{l}1, \text { arc }(i, j) \text { belongs to the route } \\ 0, \text { otherwise }\end{array}, i, j \in N\right.$,

$c_{i j} \text { - length of arc }(i, j) \in E, c_{i j}=c_{j i} \text {}$,

Subsequently, the mathematical formulation for the VRP, as proposed by Miller et al. [11], 1960, was adopted:

Subject to

The goal function, represented by Eq. (1), aims at minimizing the cumulative distance. Constraints depicted by (2) and (3) confirm that every customer gets a singular visit. Constraints labeled as (4) are purposed for sub contour elimination that lacks a depot. Here, auxiliary real variables, denoted as $u_i$, are designated for every node, sparing the depot. These variables epitomize the aggregate number of all users on the identical route to user $i$.

Within the Capacitated VRP (CVRP) domain, the introduction of vehicles bearing confined capacities is noteworthy. These vehicles are mandated to approach users at their specific locales, ensuring the service remains within the predefined capacity [6]. This framework seeks to unveil a collection of routes that strives to minimize the comprehensive distance traversed.

Given the extended variant of the foundational VRP model, the introduction of supplementary variables becomes imperative:

$q_i$ - demand of the $i$-th user, $i \in N \backslash\{0\}$,

$Q$ - denotes the vehicular capacity.

The mathematical formulation for the CVRP [6] is as follows:

Subject to

Constraints (7) and (8) ensure that every user is visited precisely once. Constraint (9) certifies that the maximum capacity isn't transgressed while simultaneously eliminating sub contours lacking a depot. Auxiliary variables are expressed as $u_i$ and are allocated to every node, barring the warehouse. These variables embody the cumulative count of all users following the same route to user $i$. In addition to these constraints, it becomes crucial to satisfy: $q_i \leq u_i \leq Q, i \in C$.

In the examined distribution process, upon making a purchase either in-store or online, the customer requests home delivery of the acquired goods. Subsequently, the enterprise initiates the delivery process. Based on the day's orders, a comprehensive document encompassing all pertinent product and customer details is generated. Excluding Sundays and Mondays, goods are dispatched daily.

At present, 14 distribution routes, primarily crafted based on the insights from the logistics and warehouse staff, are utilized without any optimization model's intervention. Every route emanates from the central warehouse, situated in Arandjelovac, Serbia. Figure 3 delineates the various cities encompassed within these distribution routes.

Distances to customers in the cities, as illustrated in Figure 3, were ascertained using data retrieved from Google Maps [12]. On the depicted Serbian geographic map (Figure 3), cities either with a populace exceeding 20,000 or those not in proximity to such populated cities are highlighted. For this study, cities were categorized in a specific manner: customers in smaller cities were allocated to adjacent larger cities (within a 20 km radius). Such an approach was adopted owing to the challenges associated with obtaining precise data concerning smaller cities and villages. In instances where a smaller locale did not lie near a major city, it was individually considered as a distinct user, exemplified by Svilajnac.

Outlined requirements for addressing the vehicle routing challenge include:

•Restricting routes where inter-city distances surpass 150 km due to unprofitability (e.g., arcs between Subotica and Niš would be non-existent). This stipulation serves to diminish the arc count.

•The emphasis on minimizing fuel expenditures serves as the predominant criterion. The fuel costs for each arc were determined for every vehicle type, using the fuel (diesel) pricing data dated 06.09.2022 (valued at 218 dinars per liter).

•The enterprise's fleet consists of diverse vehicle types: four smaller vans of 9.31$\mathrm{m}^3$ volume, five vans of 17$\mathrm{m}^3$, and a singular truck with a 50$\mathrm{m}^3$ volume.

•Stipulations dictate that vehicle occupancy must oscillate between 40% and 90%.

•The DIF parameter (Difference in Price) is monitored, referencing the profit margin from product sales. A vehicle will continue its distribution until the cumulative DIF for the loaded commodities surpasses a predetermined threshold, ensuring profitability.

Given the extensive product range, exceeding 60,000 distinct items, a holistic examination of each remains infeasible. As a solution, the study categorizes products into three volume-based groups (Table 1). Small products encompass items whose volume, inclusive of packaging, remains below 0.1$\mathrm{m}^3$. Medium products are characterized by volumes ranging between 0.1$\mathrm{m}^3$ and 0.23$\mathrm{m}^3$, whereas large products are those exceeding a volume of 0.23$\mathrm{m}^3$.

For the distribution problem of appliances and consumer goods, a mathematical model was established encompassing a set of constraints. The notations introduced are as follows:

•$N$ - Represents the set of nodes, inclusive of the depot.

•$S$ - Denotes the set of nodes, excluding the depot.

•0 - Designates the depot node.

•$V$ - Represents the set of vehicles.

•$Q_k$ - Denotes the capacity of the $k$-th vehicle.

•$g$ - Stands for the fuel price.

•$p_k$ - Refers to the fuel consumption of the $k$-th vehicle.

•$c_{i j k}$ - Represents the length of the arc, where $c_{i j k}=c_{j i k}$ for every $k \in V$.

•$q_i$ - Denotes the demand of the $i$-th customer, with $i \in N\{0\}$.

•$Q_{m i n_k}$ - Stands for the minimal capacity of the $k$-th vehicle (40%).

•$Q_{m a x_k}$ - Represents the maximal capacity of the $k$-th vehicle (90%).

•$m_i$ - Refers to the margin for the $i$-th user, where $i \in S$.

•$M_k$ - Indicates the minimal margin for every route with the $k$-th vehicle.

•$x_{i j k}$ - Designates a binary decision variable: 1 if arc $(i, j)$ is traversed by vehicle $k$, and 0 otherwise.

The mathematical model derived is given by:

Subject to

Objective function aims to minimize the overall distribution costs. Constraint (1) ensures that every customer is serviced once. Constraints (2) and (3) dictate the minimum and maximum vehicle occupancy limits. Constraint (4) caters to the company's need to achieve a minimum margin on each route. Constraints (5) and (7) specify that every route starts and concludes at the depot. Constraint (6) enforces a route's integrity by confirming entry and exit at each customer node. Finally, Constraint (8) eliminates sub-routes that bypass the depot.

Certain assumptions were made for the real-world problem evaluated:

•Each vehicle is limited to one route daily.

•The routing problem undergoes daily resolutions due to fluctuating customer locations.

•Vehicles should be loaded between 40-90% of their total capacity.

•Given the daily problem-solving frequency, fiscal costs (depreciation, salaries) are not integrated into the model.

•Deliveries that demand multiple vehicles for one customer, when orders surpass a single vehicle's capacity, remain unaddressed in this model.

For the proposed mathematical model, the GNU Linear Programming Kit (GLPK) package was employed [13]. This solver is designed for tackling problems associated with linear programming, mixed integer programming, and related challenges. The development environment utilized was GUSEK (GLPK Under Scite Extended Kit) [14], a freely accessible program that adheres to the stipulations of the GNU General Public License as published by the Free Software Foundation.

The mathematical model, elucidated in the preceding section, was examined under varied permutations of orders, customers, and vehicles. An exemplar solution, comprising 20 cities and 3 vehicles with a cumulative volume of 9.31$\mathrm{m}^3$, was illuminated, with the associated parameters delineated in Table 2.

Upon computation, three optimal routes were generated, utilizing three distinct vehicle categories. The initial route, depicted in blue in Figure 4, traversed the following cities: Aranđelovac - Knjaževac - Boljevac - Bor - Kladovo - Golubac - Aranđelovac. Subsequently, the second route, portrayed in green in Figure 4, comprised the cities: Aranđelovac - Inđija - Bačka Palanka - Apatin - Bečej - Kikinda - Belgrade - Aranđelovac. Lastly, the third route, illustrated in brown in Figure 4, included: Aranđelovac - Gornji Milanovac - Čačak - Bajina Bašta - Arilje - Ivanjica - Kraljevo - Kragujevac - Aranđelovac.

A distinction between the acquired optimal routes and the company’s pre-existing routes was observed. Apart from disparities in the city sequences, the optimal methodology necessitated the deployment of 3 vehicles, in contrast to the 5 employed in authentic scenarios. A reduction in vehicle utilization implies a diminution in total mileage, thereby inferring that the expenses deduced from the model are inferior to tangible expenditures.

Multiple experiments, with diverse instances, were conducted. The formulated mathematical model was tested for user groups of 4, 5, 10, 15, 20, and 25, with the intention of discerning alterations in total expenses, requisite routes, and vehicle commitments. Upon data incorporation, it was ascertained that a maximum of 3 vehicles were requisitioned for user sets of up to 20; the introduction of a fourth vehicle became pertinent when the user count exceeded this threshold.

A noticeable augmentation in computational time was discerned as the number of users and vehicles increased. For smaller models (encompassing up to 15 users), the duration to derive the optimal solution was approximately 5 minutes. Yet, for 20 users, this period extended to 18 minutes. Disturbingly, serving 25 users with 4 vehicles demanded in excess of an hour. Given these elongations, it was inferred that for extensive problems, encompassing a vast number of cities necessitating visits, exact methods may not yield the optimal solution within a feasible timeframe. Consequently, the recommendation leans towards formulating a specialized heuristic, capable of delivering a satisfactorily efficient solution in a diminished duration.

The challenge of vehicle routing within a distribution firm has been delineated and scrutinized. By leveraging specific data encompassing user or customer locations, varied vehicle types and dimensions, and the products ordered, a model was systematically formulated, and an optimal route configuration was subsequently derived. It was observed that the focal distribution firm, being of modest scale, has not previously employed any optimization models to address its distribution conundrums. Given the daily fluctuation in customer composition, the proffered model was discerned to not only provide a more efficient solution but also to be amenable to the company's operational nuances. Moreover, inter-city distances, integral for potential vehicular visits, were computed and archived in a format primed for future utilizations.

Authentic company data were harnessed to construct and decipher the presented model. Several avenues for prospective refinements and directional shifts have been identified:

•Should the need arise to incorporate multiple storage facilities or depots, the model stands ready for appropriate recalibration.

•In circumstances where specific customers mandate service within designated time brackets, provisions for time windows can be seamlessly integrated into the model.

It has been posited that this model is calibrated for diurnal applications, given the dynamic nature of deliveries and customer requisitions. Prior to each delivery cycle, critical input data - encompassing ordered product specifics (like computed product volume and price variations), vehicular availability metrics (enumeration and capacity), prevailing fuel price points, as well as the targeted margin for each route - would necessitate careful logging.

In future research endeavors, it might be prudent to probe the elasticity of this model when subjected to varied operational constraints, further enhancing its adaptability and efficiency in diverse logistical scenarios.