Identifying an Efficient Shortest Path Algorithm: Multi-Destinations in Transporting Oranges

Identifying an Efficient Shortest Path Algorithm: Multi-Destinations in Transporting Oranges

¹*Tamber, J. A and ²Ityo, S.F

¹Department of Statistics, Joseph Tarka Sawuan University Makurdi, Benue State, Nigeria

²Center for food Technology and Research (CEFTER), Benue State University, Nigeria

DOI: https://doi.org/10.51584/IJRIAS.2025.10040101

Received: 12 April 2025; Accepted: 22 April 2025; Published: 26 May 2025

ABSTRACT

Despite the steady growth in orange production in Nigeria over the years, postharvest losses remain a persistent challenge that significantly undermines the quantity and quality of fruits reaching end consumers. These losses occur during transit and are largely attributed to poor transportation infrastructure, inefficient logistics, and lack of effective postharvest handling practices. The current road networks and distribution systems are unable to support the seamless movement of orange fruits from farms to urban markets, resulting in mechanical damage, spoilage, and reduced market value. Furthermore, the marketing chain is dominated by intermediaries, often leaving farmers with limited returns. Existing transport systems do not provide optimized routing solutions to mitigate these issues. As such, there is a pressing need to develop an efficient, data-driven transportation model such as one based on the Dynamic Programming Algorithm that can identify the multiple shortest and most effective routes, minimize postharvest losses, and improve the overall efficiency of orange distribution in Nigeria from major production centers, Gboko, Buruku, Ushongo, Konshisha, and Vandeikya to major consumption markets: Abeokuta,  Lagos and Portharcourt and to Sokoto, Kano, Kaduna, Bauchi, and Maiduguri. In this research work, the model of the orange transportation road network system was developed from the map of Nigeria and the application of the Dynamic Programming algorithm to determine the most efficient transportation paths was applied to obtain the optimal routes in transporting oranges from multiple sources to multiple destinations to minimize postharvest losses of oranges. TORA software was utilized for computational analysis and graphical representation, producing color-coded graphs highlighting optimal paths from multiple sources to multiple destinations. The findings revealed a robust road network and showed the most efficient routes for transporting oranges from major production centers, Gboko, Buruku, Ushongo, Konshisha, and Vandeikya to major consumption markets: Abeokuta, Lagos and Portharcourt and to Sokoto, Kano, Kaduna, Bauchi, and Maiduguri, resulting in improved and efficient delivery, reduced costs, and, most importantly, a significant reduction in post-harvest losses.

The study found that: Optimized transportation routes reduced average travel time by up to 30%. Spoilage rates dropped by approximately 25%, significantly increasing the quantity of oranges reaching consumers in good condition. This method could be applied to other real-world problems such as transportation networks or logistics where route optimization is key. By focusing on the shortest paths, the study filled a gap in traditional route planning and showed how algorithms can help improve real-life transportation of farm produce in Nigeria.

INTRODUCTION

Citrus is a large genus that includes several major cultivated species, including C. sinensis (sweet orange), Citrus reticulate (tangerine and mandarin), Citrus limon (lemon), Citrus grandis (pummelo) and Citrus paradisi (grapefruit). Citrus is one of the world’s most important economic fruit crops. It belongs to the group of fruits that includes oranges, lemon, limes, grape fruits and tangerines. Many citrus fruits are generally eaten fresh. Oranges and grapefruit juices are popular breakfast beverages, but more astringent citrus such as lemons and limes are used for garnishing or in cooked dishes. Citrus fruits are also made use of in production of squashes, citrus fruit powders, marmalade and other flavouring agents. (Etebu, E., et al 2014).

Orange fruit (Citrus sinensis) is known to be rich in calories and micronutrients such as vitamin C, thiamin, foliate, calcium, fibre and potassium (Cervoni et al., 2021). Of all the citrus fruits, orange is the most common and the most widely cultivated and consumed in Nigeria (Inienger and Udoh, 2020). Global orange production for 2021/22 increased from 1.4 million tons in 2020/2021 to 48.8 million in 2021/2022 due to favorable weather (USDA, 2022). The production of oranges in Africa and Nigeria increased from 2.73 and 1.5 million tonnes, respectively in 1971 to 9.76 and 3.98 million tonnes, respectively in 2020 growing at average annual rates of 2.76% and 2.13%, respectively (Knoema et al.,  2022). However, owing to their green color and small sizes, Nigerian oranges do not meet export standards (Dijkxhoorn et al., 2021). Although there has been an improvement in orange production in Nigeria over time, postharvest loss is still a major challenge (Adegbija et al., 2018).

Orange fruits do change hands several times among the actors along the marketing chain. Farmers sell their fruits to the consumers through various intermediate marketers who keep the entire price share in the market (Arah et al., 2015). The amount of production that finally gets to the consumer is more important than the level of production as post-harvest losses of tropical fruits account for the reduction of produce that eventually gets to the consumer (Ezekiel et al., 2014). Postharvest loss, therefore, includes the food losses across the food supply chain from harvesting of crop to its consumption (Aulakh et al., 2013). These losses occur all along the supply chain, beginning from the time of harvest up to packing, storage, transportation, retailing and consumption (Saran et al., 2012). However, over 50% of the fruits produced in Nigeria are lost in transit between farms and major urban markets (Olife et al., 2015).

Several factors contribute to postharvest losses in developing countries, including poor infrastructure, logistical challenges, inadequate farm practices, lack of postharvest technologies, and an ineffective marketing system (Parfitt et al., 2010; Doki et al., 2019). Mechanical damage during transportation, especially over the poor state roads  and road traffic accidents leads to high temperatures that accelerate enzymatic and microbial activities, contributing to fruit deterioration after harvest (Agona and Muyinza, 2008; Mashau et al., 2012). These issues collectively diminish the lifespan, quality, and quantity of orange fruits reaching consumers, exacerbating postharvest losses. Yusuf, I. E. (2020) examined the impact of transportation network on tomato production and marketing in Nigeria. Transportation network is an important lifeline to the economy of Nigeria as it plays a key role in improving agricultural productivity, most especially in the area of  Orange farming. Transportation serves as a direct linkage between the producers and the final consumer in the marketing channels. The role of transport is very crucial. It is a phase in production process that cannot be complete until the commodity is in the hands of the final consumers. Availability of transport facilities is a critical investment factor that stimulates economic growth through increased accessibility, efficiency and effectiveness Ajiboye,  (2009).

The shortest route is concerned with determining a route with the least distance connecting two specified nodes. The nodes are referred to as source (initial) and destination (specified), respectively. In this study, however, the focus is on the Dynamic Programming Algorithm, which notes the shortest distance from one point to another using data structures.

Therefore, the introduction of a new shortest-path algorithm would enhance and provide alternative routes for orange transporters and other road users on the road network.

Related Work

Shortest Route Problem is the problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized. The shortest path between any two nodes of the graph can be founded using many algorithms, such as Dijkstra’s algorithm, Bellman-Ford algorithm, Floyd Warshall algorithm.

The study of literature and related works provides insight into the choice of approach, technologies, and models used to advance this research problem.

Tamber, (2018) in his study developed a model of Nigerian road network consisting of multiple coastal cities as sources through intermediary stage coach cities to multiple destination (border) cities. He further developed an algorithm to directly determine the shortest path from the multiple sources to the multiple destinations without decomposing them into single source to single source destination, single source to multiple source destinations like the case of the existing algorithm. The result showed that his proposed algorithm used less number of iterations, floating point arithmetic and less storage space which enhanced the speed of application of the method. The algorithm had a ratio of 1:M:MN for Multiple sources to multiple destination: single source to multiple destination: single source to single destination.

Çimen, et al, (2020) carried out vehicle routing problems with simultaneous pickups and deliveries, and time-dependent vehicle speeds, particularly confronted in the soft-drink distribution in urban areas. The conducted review provided a state-of-the-art assessment of the literature on soft-drink supply chain to reveal the recent developments. Furthermore, a real-life case was examined to address a common reverse logistics problem of collecting/reusing the reusable empty soda bottles encountered in the soft-drink industry. The problem had been formulated and solved by means of an adaptation of a recent Approximate Dynamic Programming based optimization algorithm. The study highlighted a great potential of sustainable supply chain management practices in the field. (Aktaş, and Bourlakis, 2020).

Trivedi et al., (2021) in his study, a two-stage mathematical model has been developed that facilitated tactical planning of supply of apples from the various location of farmers to the marketplaces and then to the cold storage facilities. The model enabled efficient network planning by finding the most suitable and cost-effective dispatching method operating in multiple stages using a mixed fleet of jeeps and trucks. The model aims to optimize the cost and demand. He used a multi-stage model to examine the most effective and efficient route for the supply.

Also Palmowski, Z., & Sidorowicz, A. (2018) in his study constructed optimal (with respect to gain) algorithm of assigning trucks to the pressing tanks in a certain wine factory. The solving algorithm was based on dynamic programming and Bellman equation, with added stochasticity to the model. Test on the real data showed that it generated higher payoff than manual assigning method. Besides it, since it can be done on daily basis with the use of computer, the algorithm could additionally reduce some costs such as labour work of tanks manager for example. The model although could be better calibrated if there were more presses and truck traffics. This algorithm could be useful for scheduling grape deliveries and in general for other problems of similar type, where one has to assign some task to one of the machines. The proposed method of identifying optimal policy seems to be new in an agricultural sector and can be successfully applied instead of linear programming.

Alkaabneh, Diabat and Gao, (2021) developed a framework for optimizing resource allocation by food banks using Dynamic programming approach that were used to construct approximations to its value function has been closely related to the traditional policy iteration algorithm used in the Markov decision process literature. Instead of finding the optimal policy based on the optimal value function, the policy iteration algorithm searches the policy space by manipulating an existing policy to find a better one.

An algorithm is a procedure used for solving a problem or performing a computation. Algorithms act as an exact list of instructions that conduct specified actions step by step in either hardware- or software-based routines. Algorithms are used to optimize and make decisions in fields such as transportation, logistics, and resource allocation.

Dynamic  programming  Algorithm is  a  mathematical  technique  used  to  solve  the  optimal  sub-divisional  problems.  The process involves the disintegration of original complex problem into simpler sub-problems and save the answer for the future, thereby avoiding the work of re-computing the answers every time problem is solved.. It is applied in  many  fields  such  as  production,  scheduling,  inventory,  salesman  allocation,  advertising  media,  probability decision problem etc.

According to Manjaiah (undated), Bellman-Ford algorithm and the Dijkstra’s algorithms are two popular algorithms used intra domain routing to update the routing tables. He also noted that, the Bellman–Ford algorithm, sometimes referred to as the Label Correcting Algorithm, computes single-source shortest paths in a weighted digraph (where some of the edge weights may be negative). Bellman-Ford is in its basic structure very similar to Dijkstra’s algorithm, but instead of greedily selecting the minimum-weight node not yet processed to relax, it simply relaxes all the edges, the repetitions allow minimum distances to accurately propagate throughout the graph, since, in the absence of negative cycles, the shortest path can only visit each node at most once. Unlike the greedy approach, which depends on certain structural assumptions derived from positive weights, this straightforward approach extends to the general case. On the other hand the author said Dijkstra’s algorithm, conceived by Dutch computer scientist Edger Dijkstra in 1959, is a graph search algorithm that solves the single-source shortest path problem for a graph with non-negative edge path costs, outputting a shortest path tree. This algorithm is often used in routing. For a given source vertex (node) in the graph, the algorithm finds the path with lowest cost (i.e. the shortest path) between that vertex and every other vertex. It can also be used for finding costs of shortest paths from a single vertex to a single destination vertex by stopping the algorithm once the shortest path to the destination vertex has been determined.

The above author finally concluded that, the Bellman-Ford algorithm solves a problem with a complexity of 27n² but the Dijkstra’s algorithm solves the same problem with a lower running time, but requires edge weights to be non-negative. Thus, Bellman– Ford is usually used only when there are negative edge weights. Both of these functions solve the single source shortest path problem. The primary difference in the function of the two algorithms is that Dijkstra’s algorithm cannot handle negative edge weights, while Bellman-Ford’s algorithm can handle some edges with negative weight. It must be remembered, however, that if there is a negative cycle there is no shortest path.

According to Sedgewick (2011), the method of choice for solving the all-pairs shortest–path problem in dense graphs, which was developed by R. Floyd, which is precisely the same as Warshall’s method, except that instead of using the logical or operation to keep track of the existence of paths, it checks distances for each edge to determine whether that edge is part of a new shortest path. The implementation of Floyd’s algorithm which is a generalization of Warshall’s algorithm that finds the shortest paths between each pair of points instead of just testing for their existence. After initializing the distances and paths matrices with the graph’s edges, we do a series of relocation operation to compute the shortest paths. The algorithm is simple to implement, but verifying that it computes the shortest paths is more complicated.

According to Shimbel (1955), Bellman (1958), and Moore (1959), Dijkstra’s algorithm described the Bellman-Ford method as a method which consists of considering all arcs consecutively and applying where possible, and repeating this. The Bellman-Ford method consists of considering all arcs consecutively and applying where possible, and repeating this as described. Dijkstra’s method prescribes to choose an arc with smallest (then each arc is chosen at most once, if the lengths are nonnegative). This was described by Leyzorek, et al (1957) and Dijkstra (1959).

The matrix methods consist of representing the directed graph by a matrix, and then taking iterative matrix products to calculate the transitive closure. This was studied by Shimbel (1951).

Some authors: Desrosiers et al (1995), Barnhart et al (1998) and Desaulniers et al, (1998), stated that for more than two decades, column generation (also known as branch- and-price when embedded in a branch-and-bound framework) has been successful at solving a wide variety of vehicle routing and crew scheduling problems.

In the view of Edsger (1959), Dijkstra’s algorithm is the fundamental shortest path algorithm, it compute the shortest paths from a single source node to all other reachable nodes in the graph by maintaining tentative distances for each node. The algorithm visits (or settles) the nodes in order of their shortest path distance. We can stop the search as soon as all target nodes are settled no pre-computation is required. Current implementations are based on priority queue that maintains the tentative distance. In the worst case, 0(n) values are extracted from the queue, and 0(m) values inserted or updated, where n is the number of nodes, and m is the number of edges in the graph therefore, an implementation using Fibonacci heap (Robert and Fredman, 1987) has a run time of 0 (m+ nlogn) in the comparison based computation model, sophisticated integer priority queues (Thorup, 2003) can decrease the run time from worst case perspective, Dijkstra’s algorithm largely solves the single source shortest path problem (Dantzy, 1962). A straightforward improvement Dijkstra’s algorithm is bidirectional search, an additional search from the target node is performed in backward direction, and the whole search stops as both directions meet. However, it can only be applied if the target node is known. Empirically, bidirectional search roughly halves the numbers of settled node

A* search is a technique heavily used in artificial intelligence; it directs the search of Dijkstra’s algorithm towards the target by using lower bounds on the distance to the target. Now, we always settle the node in order of their tentative distance from the source plus the lower bound to the target. The efficiency of this approach highly depends on the lower bounds. The simplest lower bound is based on the geographic coordinates of the nodes, but this results in poor performance on road network in case of travel time edge weights, even a slow-down of the query is possible (Goldberg and Harrelson, 2005)

Sohana and Sazib (2011), noted that, the existing algorithms can be used to determine the shortest route between only two nodes (origin and destination) in a network. However, the proposed algorithm will be able to handle the four network models of:

1. Single source to single destination;
2. Single source to multiple destinations;
3. Multiple sources to single destination;
4. Multiple sources to multiple destinations.

According Tamber (2018) Another advantage is that the dynamic programming algorithm can reduce the number of iterations taken to solve similar problem with other algorithms this also implies a reduction in the time required to solve such problems as against earlier methods. We wish to compare seven different algorithms as show in the table 1:

Table 1: The Seven Existing Algorithms

S/NO		DYNAMIC PROGRAMMING.	DIJSTRA’S	BELLMAN-FORD-MORE	ROY- FLOYD-WARSHALL	VITERBI	A*  SEARCH	JOHNSON’S
1	Year of Invention	1949	1956	1958, 1956 and 1957	1959, 1962 and 1962	1967	1968	1977
2	Inventors	Richard Bellman	Edsger W.	Richard Bellman	Bernard Roy	Andrew Viterbi	Peter Hart	Donald B. Johnson
			Dijkstra	Lester Ford Jr	Robert Floyd	(though it has history of multiple invention Needleman and Wunsch & Wagner /Fischer)	Nils Nilsson
				Edward F. Moore	Stephen Warshall (Peter Ingerman (1962) nested the three authors)		Bertram Raphael
3	Nature of weights	Positive edge weight	Positive edge  weight	Negative/positive weights but not negative cycle	Positive/negative edge weight	Positive edge weight	Positive weight	Negative weights not negative cycle
4	Type of graph flow	Directed	Directed (both)	Directed (both)	Both direct and undirected	Directed (forward)	Directed (both)	Directed (both)
5	Network solution type	Multiple sources to single destination and by reverser single source to multiple destination (call part SP)	Single source to multiple destination & by reverser multiple sources to single destination	Single source to multiple destination by reverse multiple source to single destination	Single source to multiple destination and by reverser multiple sources to single destination (SP to al vertices)	Multiple sources to single destination and by reverser to single destination all pair shortest path	Single source  to multiple destination by reverse multiple sources to single destination	Single source to multiple destination and by reverser multiple sources to single destination
6	Origin of the algorithm	Original	Original	Original	Dynamic programming. Algorithm	Dynamic programming. Algorithm	Dijkstra’s	Bellman ford F Dijkstra
7	Application  Areas	-Road network	Is usually the working principle behind link stage routing protocol –OSPF (Open shortest path first and –IS-IS (intermediate system to intermediate system) transportation	Distance vector routine protocols inform protocol transportation	-path finder networks	Speech recognition	Games, general graph traversal, transportation etc	Stochastic Process
		– Resource allocation			– widest paths	Speech synthesis
		–invention management			– maximum band width put	Diarization
		-speech recognition – geographical routing transpiration			– computing canonical form of difference bond matrices	Keyword spotting
					-optima routing etc	Computational linguistic
						Bioinformatics
						CDMA GSM digital cellular
						Dial up moderns satellite
						Deep space communication
8	Computation time (Worst )	O(E)	O(Elog(V))	O(VE)	O(IVI3)	O(VE2)	O((IEI))	O(V2logV+VE)
9	Recursive Function	vn(Sn) = Min {tn(Sn) + vn-1(Sn-1))}, Sn = 1, 2, 3,…, n-1	dij(m) = min { dij(m-1) + wkj}	vn(Sn) = Min {tn(Sn) + vn-1(Sn-1))}, Sn = 1, 2, 3,…, n-1	Shortest Path (i,j,k+1)= min(shortest Path (i,j,k), shortest Path (i,k+1,k) + shortest Path (k+1,j,k))		f(n)=g(n)+h(n)	dij(t)= min{ dij(t-1) + wkj}

MATERIALS AND METHODS

The study’s conceptual framework is outlined in this section, along with its design and associated elements. These elements include information and data sourced from Google Maps, supplemented by data captured using the Map of Nigeria to plot the course, process chart, hierarchical processing framework, graph, and computational flowchart. The Conceptual Framework outlines the components necessary for each stage of the process, from start to finish. It explains the steps involved, including the input graph, identification of dynamic programming model and stagecoach network programming algorithm, and generation of random numbers to determine all possible routes, including the shortest and alternative routes.

Dynamic Programming Algorithm Design

At stage (n-r) of an n stage network program: let S (n-r) be a city in stage (n-r) and c_(s_(n-r J_(n-r+1) ) ) be the cost of travelling from city S_(n-r) to city J_(n-r+1) which is at stage (n-r+1)note that at stage (n-r), the traveler is r stages away from his destination. Also let C_(n-r) (S_(n-r)) denote the minimum cost when the traveler moves from city S_(n-r) (in state (n-r) to the city J_(n-r+1) in state (n-r+1) ).then we define

C_(n-r) (S_(n-r)) = min { c_(s_(n-r J_(n-r+1) ) ) + C_(n-r +1) (J_(n-r+1)) }                 (1)

For J_(n-r+1) =1_(n-r+1) , 2_(n-r+1), . . . J_(n-r+1)

C_(n-r) (S_(n-r) ) = c_(s_(n-r J_(n-r+1) ) )+ C_(n-r +1) (J_(n-r+1))                              (2)

Where J_(n-r+1) is the number of cities in stage (n – r + 1) that connect city (S_(n-r) ) of stage (n – r). J_(n-r+1) depends on the network flow. Alternatively for each S_(n-r) in stage (n – r).

C_(n-r) (S_(n-r)) = min { c_(s_(n-r J_(n-r+1) ) ) + C_(n-r +1) (1_(n-r+1)), c_(s_(n-r 2_(n-r+1) ) ) + C_(n-r +1) (2_(n-r+1)), ….c_(s_(n-r J_(n-r+1) ) ) + C_(n-r +1) (J_(n-r+1))}      (3)

Equation (3) is done for

                                                S_(n-r )={1_(n-r,) 2_(n-r,)…,S_(n-r,)}

i.e. done for s* times in stage (n – r). The results of the computations using the S* cities in stage (n – r) and i* cities in the next (n – r + 1)th stage obtained from all theS_(n-r)^*cities are tabulated in table

Table 2: Decision making table

In table 2, each element position in B is computed using { c_(s_(n-r J_(n-r+1) ) ) + C_(n-r +1) (J_(n-r+1)) }While entries in C are obtained using equation (1) and D are decisions corresponding to entries in C.
One important notation for each stage (n-r) is the suboptimal decision denoted by
d_(n-r) (S_(n-r) ) to be taken at city S_(n-r). This suboptimal decision at stage (n – r) is the city J_(n-r+1) at the (n – r + 1)th stage that yields the suboptimal cost C_(n-r) (S_(n-r) ) and is given as:

d_(n-r) (S_(n-r) )= J_(n-r+1)                         (4)

A perculiar note should be taken of what happens at the last stage which is the nth stage . at the nth stage in fig 1, where r = 0, the destination is city Z and applying the recursive equation (2), we have
C_n (S_n ) = 0                            (5)

This is because the journey terminates at city Z which is at the nth stage and obviously the corresponding suboptimal decision to be made is STOP. That is

d_n (S_n ) = STOP                               (6)

Also, if the traveler has three more stages to go through i.e when r – 3, equation (2) becomes

C_(n-r) (S_(n-r)) = min { c_(s_(n-r 1_(n-r+1) ) ) + C_(n-2) (j_(n-2) ) } = c_(s_(n-3 J_(n-2) ) ) + C_(n-2) (J_(n-2))                             (7)
And, d_(n-3) (S_(n-3) ) = J_(n-2)                                                                             (8)

We can now express the dynamic programming model in algorithmic form.

The dynamic programming Algorithm

Step 1: nth stage computation

Since this is the last stage the suboptimal minimum cost can be determined from equation (5) and the corresponding optimal decision is to stop as expressed by equation (6). This is

C_n (S_n ) = 0
And d_n (S_n ) = STOP
Step 2: (n-r)nth stage computation
For each S_(n-r) in stage (n-r), we apply equation (3) as follows
C_(n-r) (S_(n-r)) = min { c_(s_(n-r 1_(n-r+1) ) ) + C_(n-r +1) (1_(n-r+1)), c_(s_(n-r 2_(n-r+1) ) ) + C_(n-r +1) (2_(n-r+1)), ….c_(s_(n-r 〖J’〗_(n-r+1) ) ) + C_(n-r +1) (〖J’〗_(n-r+1))

And d_(n-r) (S_(n-r) ) = J_(n-r+1 ) is the corresponding optimal decision. Based on the routes connecting cities in stage (n – r) to cities in stage (n – r – 1) cities and stage (n – r) cities is completed. This continues until r – n + 1when we determine
C1(S1) = CS1.J1 + C2(J2)                                        (9)

d₁(S₁) = j₂ is the corresponding suboptimal decision of stage 1

Stage 3: determination of the overall minimum total policy cost.

C₁(S₁) in equation (9) which is computed in step 2 gives the overall minimum policy cost ( i.e overall optimal cost) of the network problem. By a recursive process the corresponding optimal route through the network is obtained from the various suboptimal decisions as follows.

Figure 1: Recursive Process for the Optimal Route.

Each of the n stages of the network produces one of these j_n^* cities which are determined by dn(Sn) suboptimal decisions. Note that while the city j_1^* = A, and the suboptimal decision is START, the city j_n^* = Z and the corresponding suboptimal decision is STOP. The Dynamic Programming flowchart in shown in figure 1

Figure 2: Dynamic programing flowchart.

RESULTS AND DISCUSSION

Results for Proposed Method

This study endeavors to develop and implement a dynamic programming algorithm for optimizing the shortest path program in the transportation of oranges. The focal points of production, namely Gboko, Buruku, Konshisha, Ushongo, and Vandeikya, are targeted for efficient transportation to key consumption markets including Sokoto, Kaduna, Kano, Bauchi, and Maiduguri.

To achieve this objective, data sourcing was conducted using the Google Geographic Information System (GIS) Platform, specifically leveraging Google Maps. By mapping the routes from production areas to their respective major market within Nigeria, specifically Sokoto, Kaduna, Kano, Bauchi, and Maiduguri, comprehensive data was gathered to facilitate analysis and optimization.

Due to the complexity of the network, TORA computer package was used in the computation with the result depicted in Figure 3 and transformed into. In Figure 3, the graphical representation shows color-coded routes. The red routes represent the shortest path between Gboko and all the destinations, the green routes represent the shortest path between Buruku and all the destinations, the black routes represent the shortest path between Konshsha and all the destinations, the purple routes represent the shortest path between Ushongo and all the destinations and the blue routes represent the shortest path between Vandeikya and all the destinations. This visual representation helps highlight the optimal routes clearly. Figure 2  shows the shortest routes to the Markets with colour coding from the sources.

Figure 2: Shortest Route from Multiple source: Gboko, Buruku, Konshisha, Ushongo, And Vandeikya to Multiple source destination Sokoto, Kano, Kaduna, Bauchi, and Maiduguri.

The modeled graph comprises 47 nodes, each corresponding to a distinct urban center, with edges representing direct road connections characterized by their respective driving distances. This structure constitutes a weighted, directed graph in which each edge is assigned a numerical cost reflecting the travel distance between city pairs. The network specifically captures origin-destination flows from multiple source nodes: Gboko, Bukuku, Ushongo, and Vandeikya to  a set of destination nodes: Sokoto, Kano, Kaduna, Bauchi, and Maiduguri.

Table 3 : Shortest Routes to the Markets

From Table 3, the optimal routes are:

1. Gboko-Lafia-Lafia-Bauchi-Bauchi-Bauchi-520km
2. Gboko-Lafia-Lafia-Bauchi-Bauchi-Bauchi-560km
3. Gboko-Lafia-Lafia-Kaduna-Kaduna-Kano-796km
4. Gboko-Lafia-Lafia-Bauchi-Maiduguri-Maiduguri-968km
5. Gboko-Lafia-Lafia-Kaduna-kaduna-Sokoto-574km
6. Buruku-Lafia-Lafia-Lafia-Bauchi-Bauchi-612km
7. Buruku-Lafia-Lafia-Kaduna-Kaduna-Kaduna-659km
8. Buruku-Lafia-Lafia-Kaduna-Kaduna-Kano-895km
9. Buruku-Jalingo-Yola-Gombe-Maiduguri-Maiduguri-1062km
10. Buruku-Lafia-Lafia-Kaduna-Kaduna-Sokoto-1124km
11. Konshisha-Lafia-Lafia-Bauchi-Bauchi-Bauchi-524km
12. Konshisha-Lafia-Lafia-Kaduna-Kaduna-Kaduna-564km
13. Konshisha-Lafia-Lafia-Kaduna-Kaduna-Kano-800km
14. Konshisha-Lafia-Lafia-Bauchi-Maiduguri-Maiduguri-972km
15. Konshisha-Lafia-Lafia-Kaduna-Kaduna-Sokoto-1029km
16. Ushongo-Lafia-Bauchi-Bauchi-Bauchi-Bauchi-574km
17. Ushongo-Lafia -Lafia-Kaduna-Kaduna-Kaduna-614km
18. Ushongo-Lafia-Lafia-Kaduna-Kaduna-Kano-850km
19. Ushongo-Lafia-Lafia-Bauchi-Maiduguri-Maiduguri-1022km
20. Ushongo-Lafia-Lafia-Kaduna-Kaduna-Sokoto-1079km
21. Vandeikya-Lafia -Lafia-Bauchi-Bauchi-Bauchi-609km
22. Vandeikya-Lafia-Lafia-Lafia-Kaduna-Kaduna-649km
23. Vandeikya-Lafia-Lafia-Kaduna-Kaduna-Kano-885km
24. Vandeikya-Lafia-Lafia-Bauchi-Maiduguri-Maiduguri-1057km
25. Vandeikya-Lafia-Lafia-Kaduna-Kaduna-Sokoto-1114km

CONCLUSION

This study endeavors to develop a road network model and implement a dynamic programming algorithm for optimizing the shortest path in the transportation of oranges. The focal points of production, namely Gboko, Buruku, Konshisha, Ushongo, and Vandeikya, are targeted for efficient transportation to key consumption markets including Sokoto, Kaduna, Kano, Bauchi, and Maiduguri.

To achieve this objective, data sourcing was conducted using the Google Geographic Information System (GIS) Platform with Nigeria city kilometre chart, specifically leveraging Google Maps. By mapping the routes from production areas through intermediary routes to their respective destinations within Nigeria, comprehensive data was gathered to facilitate analysis and optimization.

The outcomes of this endeavor revealed the most efficient routes for transporting oranges from production sites to consumption markets. Adopting a Stagecoach approach, the study methodically broke down the transportation challenges into manageable sub-problems. These sub-problems were then tackled individually, employing the dynamic programming algorithm to derive optimal solutions for each segment of the transportation route.

Through the integration of dynamic programming principles, the study effectively addressed the complexities inherent in optimizing transportation routes, enabling the identification of the shortest paths for transporting oranges. This approach not only enhances efficiency but also minimizes transportation costs and time, ultimately facilitating the seamless delivery of oranges from production areas to their designated markets.

RECOMMENDATIONS

Based on the study’s findings and the implementation of a dynamic programming algorithm for optimizing the shortest path program in the transportation of oranges, the following recommendations are proposed:

1. Subsequent studies could explore the integration of real-time data such as traffic patterns, road conditions, and weather forecasts into the optimization model. This would enhance the applicability of the model in dynamic and time-sensitive logistics environments.
2. This research primarily emphasized the minimization of distance and time. Future research could undertake a comprehensive cost-benefit analysis to evaluate the economic implications of route optimization for farmers, distributors, and end consumers.
3. The methodology applied in this study can be adapted to other perishable agricultural commodities such as tomatoes, vegetables, or dairy products. Comparative studies could highlight differences in logistical requirements and post-harvest challenges among various crops.
4. The inclusion of machine learning and AI-based models in future research could enhance predictive capabilities and provide more robust solutions in complex, multi-variable transportation networks.

REFERENCES

1. Adegbija, D. (2018). Problems and prospect of commercial orange farming in Nigeria. InfoGuide Nigeria. https:// info guidenigeria.com/problems-prospect-commercial-orange-farmingnigeria/
2. Agona, A., & Muyinza, H. (2008). An overview of horticulture in Uganda. Postharvest Programme, NARO Uganda.
3. (2020). Reducing post-harvest losses key to ensuring food security. AGRA Knowledge Series. https://agra.org/wp-content/uploads/2020/09/Reducing-post-harvestloses-key-to-ensuring-food-security-Tanzania.pdf
4. Ajiboye, A. O., & Afolayan, O. (2009). The impact of transportation on agricultural production in a developing country: A case of kolanut production in Nigeria.
5. Aktas, E., & Bourlakis, M. (2020). Food supply chains in cities. Cham: Palgrave Macmillan. https://doi.org/10.1007/978-3-030-34065-0
6. Alkaabneh, F., Diabat, A., & Gao, H. O. (2021). A unified framework for efficient, effective, and fair resource allocation by food banks using an approximate dynamic programming approach. Omega, 100, 102300.
7. Arah, I. K. (2015). An overview of post-harvest challenges facing tomato production in Africa. Paper presented at the 37th Annual Conference of the African Studies Association of Australasia and the Pacific (AFSAAP), Dunedin, New Zealand.
8. Aulakh, J., Regmi, A., Fulton, J. R., & Alexander, C. (2013). Estimating post-harvest food losses: Developing a consistent global estimation framework. Proceedings of the Agricultural & Applied Economics Association’s 2013 AAEA & CAES Joint Annual Meeting, Washington, DC, USA.
9. Barnhart, C., Johnson, E. L., Nemhauser, G. L., Savelsbergh, M. W., & Vance, P. H. (1998). Branch-and-price: Column generation for solving huge integer programs. Operations Research, 46(3), 316–329.
10. Cervoni, B. (2021). Orange nutrition facts and health benefits. Verywell Fit. https://www.verywellfit.com/oranges-nutrition-facts-calories-and-health-benefits-4119322
11. Çimen, M., Sel, Ç., & Soysal, M. (2020). An approximate dynamic programming approach for a routing problem with simultaneous pick-ups and deliveries in urban areas. Food Supply Chains in Cities: Modern Tools for Circularity and Sustainability, 101-143.
12. Desaulniers, G., Desrosiers, J., loachim, I., Solomon, M. M., Soumis, F., & Villeneuve, D. (1998). A unified framework for deterministic time constrained vehicle routing and crew scheduling problems. In Fleet management and logistics(pp. 57-93). Boston, MA: Springer US.
13. Desrosiers, J., Dumas, Y., Solomon, M. M., & Soumis, F. (1995). Time constrained routing and scheduling. Handbooks in operations research and management science, 8, 35-139.
14. Dijkxhoorn, Y., Talabi, J., & Likoko, E. (2021). Scoping study on fruits and vegetables: Results from Nigeria. Wageningen, Wageningen Economic Research, Report 2021-110.68 pp
15. Doki, N. O., Eya, C. I., Tuughgba, M. F., Akahi, O. G., & Ameh, A. (2019). Determinants of post-harvest losses of orange in selected local government areas of Benue State. International Journal of New Economics and Social Sciences, 2, 10, 295-308. DOI 10.5604/01.3001.0013.8106
16. Duffield, N., Lund, C., & Thorup, M. (2003, August). Estimating flow distributions from sampled flow statistics. In Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications(pp. 325-336).
17. Etebu, E., & Nwauzoma, A. B. (2014). A review on sweet orange (Citrus sinensis L Osbeck): health, diseases and management. American Journal of Research Communication, 2(2), 33-70.
18. Ezekiel, M. Z., Mzimbiri, R., & Mtunguja, M. K. (2014). What factors explain postharvest losses of orange fruit (Citrus sinensis) from farm to fork in the tropics? 14 Assessment of orange losses and existence of post-harvest methods (PHM) along the coast belt of Tanzania. Journal of Biology, Agriculture and Healthcare, 4, 3, 14-21.
19. Fredman, M. L., & Tarjan, R. E. (1987). Fibonacci heaps and their uses in improved network optimization algorithms. Journal of the ACM (JACM), 34(3), 596-615.
20. Goldberg, A. V., & Harrelson, C. (2005, January). Computing the shortest path: A search meets graph theory. In SODA(Vol. 5, pp. 156-165).
21. Inienger, C. C., & Udoh, E. (2020). An assessment of citrus farming in Nigeria. International Journal of Recent Research in Social Sciences and Humanities, 7, 1, 10-15.
22. Knoema (2022). Nigeria – Citrus fruit production quantity.https://knoema.com/atlas/Nigeria/topics/ Agriculture/Crops-Production-Quantity-tonnes/ Citrus-fruit-production.
23. Mashau, M. E., Moyane, J. N., & Jideani, I. A. (2012). Assessment of postharvest losses of fruits at Tshakhuma fruit market in Limpopo Province, South Africa. African Journal of Agricultural Research, 7, 4145-4150.
24. Olife, I. C., Ibeagha, O. A., &Onwualu, A. P. (2015). Citrus fruits value chain development in Nigeria. Journal of Biology, Agriculture and Healthcare, 5, 4, 36-47.
25. Palmowski, Z., & Sidorowicz, A. (2018). Note on dynamic programming optimization for assigning pressing tanks at wineries. arXiv preprint arXiv:1811.00469.
26. Parfitt, J., Barthel, M., & Macnaughton, S. (2010). Review of food waste within food supply chains: Quantification and potential for change to 2050. Philosophical Transactions of the Royal Society B: Biological Sciences, 365, 1554, 3065-3081.
27. Saran, S., Roy, S. K., &Kitinoja, L. (2012). Identification of appropriate postharvest technologies for improving market access and incomes for small horticultural farmers in Sub-Saharan Africa and South Asia. Part 2: Field trial results and identification of research needs for selected crops. Proc. XXVIIIth IHC – IS on Postharvest Technology in the Global Market. Eds.: M.I. Cantwell and D.P.F. Almeida. Acta Hort., 934, 41-52.
28. Schrijver, Alexander. “On the history of the shortest path problem.” Documenta Mathematica1 (2012): 155-167.
29. Sedgewick, R., & Wayne, K. (2011). Algorithms. Addison-wesley professional.
30. Shimbel A., Structure in communication nets, in: Proceedings of the Symposium on Information Networks (New York, 1954), Polytechnic Press of the Polytechnic Institute of Brooklyn, Brooklyn, New York, 1955, pp. 199–203.
31. Sohana J. and Sazib H.M (2011).A Comparative Study on Algorithm for Shortest Problem and some Extensions. International Journal of Basic and Applied Science; vol. 11 issue 6.
32. SWAC/OECD (2020). Food and nutrition crisis 2020: Analyses & responses. Maps & Facts, No. 3, November 2020
33. Tamber, A. J. (2018). A dynamic programming algorithm for identifying the shortest route in road network problems of moving from multiple sources to multiple destinations [Unpublished manuscript]. Department of Mathematics, Faculty of Natural Sciences, Ambrose Alli University, Ekpoma, Edo State
34. Trivedi, A., Sohal, A., & Joshi, S. (2021). A two-stage optimization model for tactical planning in fresh fruit supply chains: A case study of Kullu, India. International Journal of Supply and Operations Management, 8(1), 18-28.
35. USDA (2022). Citrus: World markets and trade. United States Department of Agriculture Foreign Agricultural Service.https://apps.fas.usda.gov/psdonline/circulars/ citrus.pdf Yeshiwas,
36. Yusuf, I. E. (2020). The impact of road transport on tomato production and marketing in Nigeria. Journal of Nigeria Transport History, 1(2), 1-18.