1 Introduction

While globalization has made the distance among countries minute, their geographical locations are very apart thus causing higher freight damage in complex transport operations. To avoid damages or compromises throughout this process, the food, pharmaceutical, medical industries highly rely on cold chain [1]. Cold chain logistics is the management of goods moved from one point to the other in a controlled temperature without interrupting the refrigerated production, distribution, and storage activities [2].

Although the cold chain logistics industry is developing, third party logistics companies in Ghana still encounter challenges along the distribution chain. Distribution chain problem also called vehicle routing problem (VRP) is a challenge in logistics management. According to Joshi and Jadav [3] the greedy algorithm has several advantages over other algorithms, because it is simple and easy to code-up. It also has higher efficiency because it is easy to implement as compared to others. VRP is one of the variants of distribution network problems and therefore this study shows how greedy search method can be used to solve VRP. Categorically the problem deals with reaching the customers from the distribution centre (depot) and returning to the depot.

The paper is organised as follows; Sect. 2 examines related literature on the problem and the methods used by other authors to solve the VRP. Section 3 explains the method and model used to solve the VRP. Section 4 reports on the results which are the set of possible routes identified and optimal path. This is presented in a table form and the latter showed as nodes. Finally, the paper concludes that the optimal path identified will facilitate in the daily dispatching activities of the truck in the company thus reducing the cost.

2 Literature review

Cold-chain logistics is a system which preserves frozen and refrigerated items in an environment which has low temperature throughout production, storage, transportation, process and sale in order to guarantee the quality and performance of goods. In this supply chain system, cold-chain logistics products have features of freshness, perishability, timeliness, large costs, logistics performance etc. It is imperative for every distribution centre of cold-chain logistics to reduce processing time in order to lower the risk of food spoilage [4].

The VRP is a combinatorial optimization and integer programming problem which assigns a set of clients to vehicles by means of routes. A VRP can be considered as a m-TSP where a demand is associated with each city. In a VRP a number of vehicles are stationed at one or several depots and these vehicles need to visit a number of geographically dispersed clients. The VRP is defined more than 50 years ago according and is considered one of the most challenging combinatorial optimization tasks. This is because VRP’s belong to the category of NP-hard (non-deterministic polynomial-time hard) problems. This means that the computational effort required to solve this problem increases exponentially with the problem size. Consequently, these kinds of problems are often solved with approximate solutions. The goal of a VRP-algorithm is to minimize a given objective function, usually characterized by the total length of the routes. The length of a route can be measured in distance (e.g. miles) or in time (e.g. hours). Another objective could be to minimize the number of routes of the number of vehicles needed [5] (Fig. 1).

Fig. 1
figure 1

Source: Laporte [6]

Shows a set of routes designed in order to serve given clients.

Full size image

There are also a number of different constraints that can be applied to a VRP. The most basic constraint is the time constraint for the vehicles. This constraint means that each vehicle only has a limited amount of time T it can drive each day. The VRP has to meet this constraint when minimizing the objective function. There are a number of different variants on the VRP. Each of the specific variants of the VRP has some different constraints or characteristics that have to be taken into account.

2.1 Travel Salesman Problem

With the Travelling Salesman Problem (TSP), a salesman visits quite a number of cities and afterwards the salesman returns to the location where (s)he began. The idea is to find the shortest possible route that visits every city exactly once and returns back to the starting point. The aim of the TSP is to construct a route such that the distance travelled is minimized. TSP can be generalized to a x-TSP where x salesmen have to cover the given cities. Within this problem, each city is visited by exactly one salesman. Every salesman starts from a starting point (depot) and must also return to this depot at the end of his/her journey. The idea in an x-TSP is to minimize the total distances travelled by the salesmen [5].

It is admitted that the VRP is an NP-hard problem, therefore to resolve this problem in an efficient manner, many existing works have been studied in the past; summarized below in the table are related literatures on VRP.

Studies

Method

Results

Gap

Montané and Galvão [7]

Used a tour partitioning heuristic developed for the traveling salesman problem (TSP)

Heuristic procedures PCY3 and PFI3 produced better results than the other tour partitioning heuristics

Studied in particular the vehicle routing problem with simultaneous pickup and delivery service

Das and Borthakur [8]

Lexicographic search approach has been employed here to solve a general VRP problem

The proposed method can bring a quick convergence for the optimal solution

Vehicle routing problem which took into account the minimization of time with mixed constraints

Chen et al. [9]

Proposed a monarch butterfly optimization algorithm with greedy search strategy to solve DVRP

Results show that the proposed technique outperforms other existing approaches in the literature for average performance by at least 9.38%

Objective is to determine a set of routes that minimizes the total travel distance

Liu and Lee [10]

Used a dynamic particle swarm

Simulations results show that DPSO provides a competitive performance over other technique

Novel location inventory routing model to optimize costs in cold logistics

Zeng et al. [11]

Proposed a hybrid heuristic which is composed of a greedy randomized adaptive search procedure

Show that the algorithm is both effective and efficient and outperforms the best existing heuristics for the 2E-VRP

Solved a two-echelon vehicle routing problem arising in two-level transportation systems

Escobar Falcón et al. [12]

A hybrid algorithm was proposed

Results indicate that the proposed approach obtained good solutions

Solved a capacity vehicle routing problem with practical three-dimensional loading constraint

Euchi [13]

A hybrid genetic algorithm and scatter search is proposed to solve the problem

The obtained results indicate that the proposed method consistently minimizes the travelling cost of vehicles

A pickup and delivery transportation problem where one commodity is collected from many pickups locations to be delivered to many delivery locations within pre-specified time windows was considered

Chai [14]

Proposed a genetic algorithm and improved algorithm to solve VRP

The results showed that improved genetic algorithm is better than standard genetic algorithm in the calculation of speed and efficiency

Solved a VRP which considered the receiving points for fresh perishable goods, transports cost and energy cost

Hsu et al. [15]

A hybrid genetic algorithm

The results showed that inventory and energy costs could highly affect total delivery costs. The model produced quality results than the traditional vehicle routing problem with time windows

A stochastic vehicle routing problem with time windows

Lim and Xu [16]

An evolutionary algorithm was used

Results have shown how efficient and flexible the algorithm is by generating quality solution

Objective was to generate set of routes for a fleet of fuel trucks

Xiao Yin [17]

ACO-ant algorithm based on ant colony framework was proposed in the work

The results revealed that the routing method can provide a feasible transportation path with both less cost and less running time in comparison with existing work

Studied the problem of routing in cold chain distribution network with the goal of reducing the total cost

Govindan et al. [18]

Multi-objective hybrid approach was considered

Algorithms results show that the hybrid approach achieves better solutions as compared to other methods

A multi-objective optimization model which considers sustainability

Karaoglan et al. [19]

A branch-and-cut algorithm is considered

Result presented shows the method is feasible to solve small and medium size LRPSPD instances. It also helps find high quality solutions by reducing computational time and exploring fewer nodes of tree

Considers location–routing problem with simultaneous pickup and delivery

Stodola [20]

Proposed ant colony optimization and the best known solution

Results show that ACO algorithm is better than the BKS when recalculated to the modified criterion

Considers a modified multi-depot vehicle routing problem

Wang et al. [21]

A hybrid heuristic algorithm is developed to solve this problem

The computational result showed that, the algorithms had advantages for minimization of the cost of travel, number of vehicles, and loading rate

Studied the vehicle routing problem of simultaneous deliveries and pickups with split loads and time windows

Fuellerera et al. [22]

Ant colony optimization and heuristics are used to solve the problem

Results shows that the algorithm proposed outperforms previous heuristics while in small-size instances it reaches a high number of proven optimal solutions

A two-dimensional loading vehicle routing problem was considered

Yang and Xuan [23]

A taboo search was used

Simulated results indicated that optimal route in the distribution link can be obtained expeditiously when using the taboo search algorithm

They perform local search logistic optimization

Lucia and Roberto [24]

A saving algorithm heuristic method is used

Using a natural gas distribution network as a case study results showed how effective the approach was in tackling complex optimization task by providing highly pragmatic and realistic time-responsive solutions

Considered a capacitated vehicle routing problem which is applied to natural gas distribution networks

Ahmed et al. [25]

A lexicographic search approach is proposed

Computational details also reported showed that lexicographic search helps to obtain optimality, faster than branch and bound in many cases. It also specifies simpler rules for branching, bounding and termination

Aimed at obtaining an optimal route of a fleet of oil-delivery tankers from a source to a number of service stations and considers the minimization of the backload of tankers

Foysal Ahmed and Sun [26]

A bilayer local research-based particle swarm optimization

Results showed that the BLS-PSO performs better than other PSO-based methods

A novel decoding approach was developed to solve a CVRP

Shaw [27]

A new local search algorithm was proposed which is the greedy local search

The results showed that, the method helps better the best produced by competing techniques using minima-escaping methods

A vehicle routing problem which considers a large neighbourhood based upon rescheduling selected customer visit using constraints programming technique

In summary, to the best of our knowledge, little attention has been done to research on cold chain logistics that considers capacitated vehicle routing problem with traveling salesman and minimization of transport cost at the same time. Thus, compared to previous studies, this paper proposes a comprehensive CVRP which seeks to optimize distances routes and minimize cost. This model adopts a greedy search algorithm to determine routes and also an objective function is designed to help obtain the optimal cost. Finally, the validity and feasibility of the algorithm is verified by computational results and its benefits.

3 Research methodology

3.1 Conceptual framework

Vehicle routing problem has been one of the elementary problems in logistics ever since because of its wide use and high economic value. The research considers a depot having a fleet of vehicles with limited capacities and set of customers each with a certain demand for the merchandise or goods to be dispatched. This research shows the application of VRP in the distribution chain, specifically to identify possible routes and optimal path as well as reduce transport cost associated thus ensuring the completion of distribution services (Fig. 2).

Fig. 2
figure 2

Source: Osman [28]

Routing single depot with 3 vehicles and 9 customers

Full size image

The study seeks to solve the following questions:

  • RQ 1: What is the optimized total distance travelled by the vehicles?

  • RQ 2: What is the effect of optimized distance on administrative cost associated with transportation?

The objective of optimisation is to route all 3 vehicles such that all the 9 delivery points (customers) are visited by one of the vehicles. Routing of the 3 vehicles has been planned in a way to reduce total distance travelled by the vehicles. It gives an illustration of one possible plan of routing the three (3) vehicles starting and ending at the depot.

3.2 Model description/assumptions

The model considers the routing of a single depot with three (3) vehicles and nine (9) customers using the following procedure:

  1. (1)

    The model considers a single depot with three (3) vehicles with a loading capacity constraint and some customers to be served.

  2. (2)

    Customer demand which is a single product is known in advance, and the travel distance between customers and the depot is also known in advance.

  3. (3)

    The total demand of any vehicle route must not exceed the capacity of the vehicle.

  4. (4)

    The required goods by customers are served by one vehicle.

  5. (5)

    Three (3) vehicles and three (3) routes have been designated to reach the customers from the distribution centre. After servicing each customer within the cluster, the vehicles return to the distribution centre. Clustering of customers is done based on customer demand and nearest in route from the depot.

  6. (6)

    A threshold distance of 30 km is considered. All the customers are integrated like a travelling salesman problem node and an individual truck is assigned to reach all the nodes (i.e. customers) from the depot and returning to the depot covering all the chosen customers and completing it by means of single tour. In the distribution process $3/km is transportation cost in per unit mileage [29].

3.3 Establishing mathematical model

In this paper, this model takes transportation costs as objection function. This objective function ensures that the cost involved in transport is minimized.

Transportation cost may include fixed cost and variable cost such as fuel, maintenance and other factors. It is also having a proportional relation to the distance travelled by vehicles. Formula was modified from Alam [30] and it can be expressed as:

$$\mathop \sum \limits_{i = 1}^{L} Ci\left( { x\left( i \right) - \left( {n + 1} \right)} \right)^{2} , \quad N = 0,1,2,3$$
(1)

St.

$$\mathop \sum \limits_{i \in N} xi = 3 ,\quad {\text{where i}} \in {\text{N}}$$
(2)
$$\sum qix\left( i \right) \le Q_{k} , \quad i \in N$$
(3)
$$\sum qixi \le Q_{g} , \quad i \in N$$
(4)

The objective function as shown in Eq. (1) is to minimize cost.

Constraint (2) represents that 3 refrigerated vehicles will make delivery to each customer along their said routes. Constraints (3) says every customer demand assigned to a vehicle should not exceed the capacity of the vehicle. In constraints (4) the customers demand does not exceed the maximum storage capacity of the distribution centre g.

3.4 Methodology

The methodologies used to determine the best vehicle routing for truck dispatch system (TDS) are permutation enumerator and greedy search algorithm.

3.4.1 Permutation enumerator

Firstly, the distance of the stations and the vehicle capacity is known. Vehicles are designated to the cluster of customers upon their demand and the vehicle’s capacity. By the use of permutations and combinations sets of routes are formed based on vehicle; the method used is only suitable for identifying the total combination of route. However, the possible path of the vehicles is a limitation of this method, hence the greedy search method is adopted to single out the possible paths of the vehicles and the feasible route plan is obtained by initially identifying the total distance each truck uses to reach the customers using Matlab software (8.1 version).

3.4.2 Greedy search algorithm

The definition of greedy search algorithm differs slightly in literature, however, most define it as one that makes a sequence of choices. Each choice is some been in some way the best available at that time. One characteristic of the algorithm is that, it never goes back when decision is made earlier. They are less complex and are straight forward as well as efficient. They are also useful in many ways by solving problems in various combinatorics and beyond. They can be applied in many areas such as travelling salesman problem, Prim’s minimal sparring tree algorithm, Kruskal’s minimal sparring tree algorithm, Dijkstra’s minimal sparring tree algorithm, Knapsack problem etc. [31]. Greedy algorithms run faster than dynamic programming as they make the locally best choice at every step, where DP solution evaluates all possible choices at every step. Analysing the run time for greedy algorithms will generally be much easier than for other techniques. They are easier to implement and because of their simplicity, they are frequently straightforward and efficient. However, it can’t be applied to every problem because it turns out to be dynamic programming that is (when locally optimum doesn’t lead to global optimum [32].

Below is a mathematical notation: it depicts the nature of the greedy search. The nature of this method is to select the best local solution at its disposal. From the diagram below, if a travel salesman moving from node 7, the local best option to select from will be node 12. However, this would not always be the best since not all local best will lead to global best as seen from the diagram (when the customer moves from node 3 to node 99).

figure a

The possible route plan and the optimal path of the vehicles are identified using the greedy search method.

Steps

  1. a.

    In inception, a truck is assigned to serve based on the list of nodes available, customers are selected in sequential order starting from the nearest customers to the distribution centre.

  2. b.

    This series of action is repeated until all the customers (stations) have been exhausted to form the complete sequence starting and ending at the distribution centre as it is executed in phases.

  3. c.

    At each phase, the best outcome (individual optimal route; as shown in the results) is considered without regard for future consequences. It is observed that by choosing a local optimum route from each phase will help achieve the global optimum in the results.

3.5 A distance matrix and shortest route calculations for the stations

The distance between 9 customers are shown in 9 × 9 distance matrix table. Since a symmetric matrix is taken only one half is filled in Table 1. The distances between the stations are in kilometres (km) (Table 2).

Table 1 The meaning table of notations in the formula
Full size table
Table 2 Distance matrix (Data Source: Authors Own composition)
Full size table

  • 1—denotes the depot that is starting point of the vehicles. 2–9 denotes the cluster of customers to be visited by the vehicles.

Using permutation formula

$$nC_{r} = \frac{n!}{{r!\left( {n - r} \right)!}}$$

The number of all combinations of ‘n’ things, taken ‘r’ at a time.

By combination

The total no of customers = 9

No of vehicle = 3

$$\begin{aligned} 9C_{3} & = \frac{9!}{{3!\left( {9 - 3} \right)!}} \\ & = \, 84\;{\text{combinations}} \\ \end{aligned}$$

4 Results and discussion

Apply Matlab 8.1; compile the computer program which is suitable for the algorithm model, identify all set of possible combinations along the routes. In the distribution process, $3/km is the transportation cost in per unit mileage [29]. After computing for the three optimal distances, these distances are imputed into the optimal cost function. The results are shown in Table 3.

Table 3 Computational results for the routes and distance from depot to customers.
Full size table

From Table 3, the locally obtained optimum paths are presented below:

figure b

Therefore, the optimal paths are 1–7–8–9–1, 1–2–3–7–1 and 1–4–5–6–1 km respectively.

After computing for the three optimal distances to be optimal distance: 22.6, 10.25, 21.2 respectively, the researchers imputed these distances into the optimal cost function hence the result is \(2841.2175\).

5 Conclusion

VRP is a vital problem and a crucial link in reducing the transportation cost of distribution of cold chain logistics distribution. VRP and its variants have been studied and solved in many works.

However, few studies have considered the use of the greedy search method to solve capacitated vehicle routing problem with traveling salesman and thus minimize transport cost.

The present work proposed permutation enumerator to identify the set of routes. The limitation of this method necessitates the use of greedy search algorithm. The greedy search is used to solve the problem with an increasing number of customers. Finally, we presented computational results on eighty-four (84) set of routes out of which we identified the optimal routes to be 1–7–8–9–1, 1–2–3–7–1 and 1–4–5–6–1 at 22.6 km, 10.25 km, 21.2 km respectively. Furthermore, with regards to cost, the effect of an optimal distance on transport cost was analysed. We found out after imputing the optimal distance into the transportation cost function thus the optimal cost is $\(2841.2175\). Hence in the actual application, this model provides a theoretical basis in planning vehicle path for cold chain logistics and despatching activity for distribution centres and also to minimize cost.

For future research, time window for vehicle routing can be looked at to form routing considering loading and unloading time, real-time constraints and it can also take in account dynamic environments and stochastic demands. In addition to decreasing costs, diminishing the emission rates of CO2 may be considered.