1. Introduction

The Vehicle Routing Problem (VRP) is defined as the problem of establishing optimal delivery or collection routes from one or more depots to a number of geographically dispersed locations or clients while keeping certain limitations in mind. Belachgar and Kissani [1] described “Vehicle Routing Problem as a transportation related combinatorial optimization problem that seeks to generate an optimum tour for a set of cars in order to meet customer expectations while adhering to particular constraints”. According to Haimovich et al [2], the goal of VRP is to route the vehicles so that each customer is visited by exactly one vehicle and the overall distance travelled is kept to a minimum. According to Laporte [3], VRP is crucial in the disciplines of logistical and physical distribution. Collection of household waste, gasoline delivery, goods distribution, snow plowing, and mail delivery are the most available applications of the VRP. The vehicle routing problem helps to improve vehicle utilization, transports more goods in a go, saves lots of logistic costs, and also makes customers happier with services. The classical vehicle routing problem seeks to discover a set of routes with the lowest possible cost (shortest path, fewest cars, etc.) that begin and terminate at the depot and satisfy the known demand of all nodes”. Each node is only visited once by a single vehicle, and each vehicle has a restricted capacity. A common VRP is the challenge of determining the cheapest routes from one depot to a set of geographically dispersed locations (cities, warehouses, customers etc.).

Due to the increasing demand for drugs in Ghana, the pharmaceutical firm used for the study is faced with the problem of transporting drugs to its customers in other parts of the region. The firm uses two vehicles in its delivery process. The firm’s vehicles used in delivery cover more distance in the process hence affecting the firm’s returns.

The study therefore sought to use the concept of Vehicle Routing Problem to determine the optimal set of routes to be traversed by the pharmaceutical firm’s vehicles to serve its teeming customers with the aim of minimizing the distance covered by the vehicles. Specifically, the study sought to construct a distance matrix of the customer locations of the pharmaceutical firm. Also, it sought to determine some pre-optimality operating routes of the vehicles used by the pharmaceutical firm. Finally, the study sought to determine the optimal operating routes and total optimal distance that should be covered by the vehicles of the pharmaceutical firm.

2. Literature Review

The concept of vehicle routing problem was proposed by Dantzig and Ramser [4]. They demonstrated a practical application involving the distribution of fuel to petrol stations, as well as the first mathematical programming formulation and algorithmic technique. Clarke and Wright [5] developed a greedy heuristic that surpassed the Dantzig-Ramser method. Liebman and Marks [6] developed mathematical models for the waste collection routing problem. Marks and Stricker [7] suggested a model for routing public service vehicles whereas Wilson et al [8] proposed a telephone request for transportation assistance for people with impairments. Golden et al [9] were the first to use the term "vehicle routing" in their paper. Bodin [10] outlined the problem’s taxonomic structure without considering real demands. A taxonomy of routing and assignment difficulties was developed by Bodin and Golden [11]. Brown and Graves [12] were the first to release a research on personal deliveries (single-customer trips) and time windows, and Brown et al [13] developed a computerized assisted dispatch system for Mobile Oil Corporation in the United States. Laporte et al [14] proposed “the first cutting plane approach for a VRP based on the solution of linear relaxation of an integer model”. Solomon [15] proposed VRP with time windows (VRPTW). Specifically, he created and analysed methods for “Vehicle Routing and Scheduling Problems” taking into consideration Time Window limitations. His aim was to serve all customers in a defined time interval. Laporte [3] presented “a three-category characterization of exact approaches: direct tree search methods, dynamic, and Integer Linear Programming”. Li et al [16] investigated “Distance Constrained Vehicle Routing Problem (DVRP) in terms of total distance and number of cars”. They demonstrated that “the optimal solutions for both objectives are inextricably linked, and that any approximation guarantee for one objective implies a guarantee with an additional loss of factor 2 for the other”. Van der Bruggen et al [17] addressed “the single time variant of the problem as part of a bigger research aimed at maximizing a huge oil company's distribution network in the Netherlands”. They proposed some simple models for assigning customers to depots, determining fleet size and composition, and to reorganize the depot network. Avella et al [18] suggested “a heuristic and an accurate approach based on a route creation scheme and a branch-and-price algorithm to address a comparable problem”. They evaluated a fuel replenishment network with a single depot, a diversified tank truck fleet, and no time windows. Bazgan et al [19] investigated the distance constrained VRP and provided a constant-factor differential approximation algorithm. Olivera and Viera [20] solved a vehicle routing problem with multiple routes (VRPM) which had to do with identifying the routing of a fleet of cars where each car could conduct numerous routes at a specific time horizon using adaptive memory programming. Lai et al [21] proposed a mathematical model of the Vehicle Routing Problem with Simultaneous Pickups and Deliveries and Time Window limitations using Mixed Integer Programming (VRP-SPDTW). Their suggested concept aimed to reduce the number of vehicles on the road as well as the overall cost of travel. Lee et al [22] introduced a comprehensive optimization strategy in the VRP to minimize the overall distance traveled and the required number of vehicles in the Vehicle Routing Problem with Time Windows (VRPTW) by taking travel as well as demand as unexpected parameters and client deadlines into account. Zuzana et al [23] presented a heterogeneous fleet vehicle routing problem with the selection of inter-depots. The purpose of the proposed model was to plan shipments of commodities from a central depot to inter-depots and then to endpoint customers. Ghannadpour et al [24] proposed “a mathematical technique in vehicle routing problems with time windows (VRPTW) that takes unpredictability in client demands into account”. The main purpose of the described model was “to reduce the overall distance traveled and the necessary number of cars while concurrently maximizing customer satisfaction”. Cetin and Gencer [25] investigated a subset of the vehicle routing problem known as the Vehicle Routing Problem with Simultaneous Pick-up and Delivery with Hard Time Windows (VRPSPDHTW). Mohibul et al [26] addressed the Capacitated Vehicle Routing Problem. Actual information from a Coca-Cola Distribution Company in Bangladesh was obtained at multiple nodes, processed, and evaluated using numerous heuristic algorithms in their study. Katsuma and Yoshida [27] suggested a system for collecting actual road data through vehicle ad-hoc networks that recreates an emergency vehicle’s path on a regular basis. According to them, in order to get ambulances and fire engines to their destinations as rapidly as possible, real-time road conditions must be provided to these emergency vehicles via ad-hoc networks. Kayode et al [28] discussed a vehicle routing problem with multiple priorities. The concept was based on time and quantity. They again explained the interconnectivity between priorities based on time and quantity and formulated a dynamic that shows the combination of time and quantity into the vehicle routing problem.

From the reviewed literature and to the best of our knowledge, application of the concept of Vehicle Routing Problem in the manner presented in this paper appears non-existent. The study was therefore intended to fill that knowledge or research gap.

3. Materials and Methods

The underpinning concept of the study was Vehicle Routing Problem. The Vehicle Routing Problem is made up of four components. Without reducing the generality, the most common terminologies for these components are:

• A network which is typically represented by a graph;

• The sites to be visited (i.e. customers to serve, tasks to complete, etc.) are denoted as customers with a particular request, which is often referred to as a demand;

• The fleet of vehicles that represents the mobile performing the task;

• The depot, which is normally where the vehicles begin and end their journey. It is usually the vehicles’ starting and/or ending point. In some cases, we may need to have more than one depot.

Usually, there are also constraints or restrictions on the set of available solutions founded on the problem's special requirements. For example, if the company is unable to allocate packages weighing more than a certain amount to vehicles, this would impose a constraint on the solutions. The traditional goal of a Constrained Vehicle Routing Problem is to minimize the total cost, which is determined by the global travel distance or time, as well as the fixed expenditures associated with vehicle usage.

Figure 1 shows a typical example of a Vehicle Routing Problem consisting 6 cities and 2 vehicles. D is the depot and 1 to 6 are the cities.

Figure 1. Vehicle Routing Problem

The higher the number of cities, the more difficult the vehicle routing problem becomes. For instance, a problem with n cities which links with every pair of cities will have feasible destination routes to consider. The example above with 6 cities, will give us feasible destination routes.

The traditional VRP on which this study is based is formulated as follows:

(1)

Subject to:

(2)

(3)

(4)

(5)

(6)

The objective function (1) seeks to minimize the total distance travelled. The constraint (2) states that each customer can be visited directly from a starting depot or from any other customer and (3) means that, after a customer is visited from the depot, the vehicle can further visit another customer or back to the final depot. The next constraint (4) means that two arcs will take the value of one meaning from the depot N+1, the vehicle can visit any two customers. Constraint (5) on the other hand, means the vehicle can visit two customers and then back to the depot N+2. Lastly, (6) means that the vehicle moves from the depot N+1 through a set of nodes and then to the depot N+2.

The traditional Vehicle Routing Problem has been modified in a variety of ways by incorporating extra real-life components or features, resulting in a range of VRP variants. A fleet of vehicles based in a depot and with a limited capacity that must ensure tours between many customers (or cities) to satisfy their stipulated demand is the Capacitated Vehicle Routing Problem (CVRP). Every customer should be served at least once, and all tours should begin and end at the depot.

The goal or objective of the CVRP is to reduce the total cost while considering the vehicles’ capacities in every single tour.

Multi-Depot Vehicle Routing Problem (MDVRP) considers that the customers’ depots are geographically scattered according to Montoya-Torres et al [29]. A company may have multiple depots from which to serve its clients. The goal here is to serve all consumers while reducing the number of vehicles and travel distance. Vehicle Routing Problem with Time Windows (VRPTW) implies that deliveries to a single client must occur inside a specific time window that varies from customer to customer. Every customer or client has a time limit within which his/her demand must be met. The goal or objective is to limit the number of vehicles and total distance while adhering to the time constraint. Goods must be picked up from a specific place and delivered to a specific place in Vehicle Routing Problem with Pickup and Delivery. Since the same vehicle must pick up and drop off, the pick-up and drop-off locations must be in the same direction according to Tasan and Gen [30]. In Vehicle Routing Problem with backhauls (VRPB), a vehicle performs both deliveries and pick-ups in the same direction as stated by Pradenas et al [30]. In Distance Constrained Vehicle Routing Problem (DCVRP), the vehicles are constrained by their autonomy, which means that the total distance travelled should not exceed a predetermined distance, and that any conceivable sub tours formed in the solution should not exceed a predetermined distance. According to Campbell and Wilson [31], Periodic Vehicle Routing Problem (PVRP) is used when planning occurs over a specified period of time and deliveries to customers will take place on different days. Customers can be visited more than once under the PVRP.

The main approaches for solving VRPs are classified into Heuristics, Exact Algorithms and Meta-heuristics. The solution approaches or techniques for solving VRP of all variants are summarized in the Figure 2.

Figure 2. Solution Techniques for Vehicle Routing Problems

The study used both primary and secondary data. The primary data was obtained through an interview with the manager of the pharmaceutical firm. To be able to tell the distance between customer locations and the pharmaceutical firm, a secondary data was obtained using Bings Map Tool. VRP Spreadsheet Solver developed by Erdogan [32] which is based on the Clark and Wright saving algorithm was employed to find the optimal solution of the problem.

4. Results and Discussions

The manager of the pharmaceutical firm was interviewed to find out the usual routes taken by their two (2) vehicles to serve their scattered customers. Based on his responses, 20 customer locations were taken and the coordinates of their locations and the pharmaceutical firm (Depot) were obtained using the Bing map and are presented in Table 1.

For simplicity, numbers were then assigned to the twenty (20) customer locations of the pharmaceutical firm as given in Table 2.

Table 1. Coordinates of customer locations and the pharmaceutical firm

Table 2. Customer Locations of the Pharmaceutical firm and their assigned numbers

A distance matrix of the 20 customer locations and the pharmaceutical firm as given in Table 3 was constructed using Bing Maps driving distances in kilometers (km) worksheet in the VRP Spreadsheet Solver and it shows the various links connecting the pharmaceutical firm and all the twenty (20) customer locations. The cells indicated zero show that there is no distance.

PRE-OPTIMALITY ANALYSIS

The pharmaceutical firm’s vehicles do not have specific routes or no specific vehicle is assigned to a particular customer. Below are some routes and total distances usually covered by the vehicles of the pharmaceutical firm.

Route 1

Vehicle 1 starts from

Depot (0) Binduri (11) Belago (10) Nakpanduri (19) Nalerigu (6) Gushiegu (20) Yendi (17) Tamale (18) Savulugu (15) Bolga (13) Zebila (12) Depot (0)

Total distance covered: 18.04 + 12.11 + 39.84 + 25.83 + 73.76 + 131.84 + 5.86 + 24.45 + 138.86 + 45.98 + 34.62 = 551.19 km.

Vehicle 2 starts from

Depot Kugurago (16) Garu (3) Pariboko (9) Bugri Corner (18) Wariyanga (5) Dekulga (7) Biankori (14) Basyondi (4) Sugudi (2) Pusiga (1) Depot (0)

Total distance covered: 14.45 + 14.18 + 6.92 + 260.53 + 207.09 + 7.38 + 10.7 + 12.53 + 9.47 + 5.15 + 7.63 = 556.03 km.

The total distance covered by the two vehicles is (551.19 + 556.03) km = 1107.22 km.

Table 3. Distance matrix of customer locations of the pharmaceutical firm

Route 2

Vehicle 1 starts from

Depot (0) Pusiga (1) Sugudi (2) Basyondi (4) Biankori (14) Dekulga (7) Wariyanga (5) Bugri Corner (8) Parinboko (9) Nalerigu (6) Yendi (17) Tamale (18) Savulugu (15) Bolgatanga (13) Zebilla (12) Depot (0)

Total distance covered by Vehicle 1 is 7.63 + 5.15 + 9.47 + 12.53 + 10.70 + 7.38 + 9.60 + 7.88 + 55.90 + 161.98 +5.86 + 24.45 + 138.86 + 45.98 + 34.62 = 537.99 km.

Vehicle 2 starts from

Depot (0) Kugurago (16) Garu (3) Nakpanduri (19) Gushiegu (20) Belagu (10) Binduri (11) Depot (0)

Total distance covered by Vehicle 2 is 14.45+14.18+29.71+91.36+130.54+12.11+18.04 = 310.39 km.

The total distance covered by the two vehicles is (537.99 + 310.39) km = 848.38 km.

OPTIMALITY ANALYSIS

It should be recalled that a problem with n cities which links with every pair of cities will have feasible destination routes to consider. In the case of this work, the total number of feasible destination routes will be = 1216451004088320000. It was therefore practically impossible to determine all these numerous number of feasible destination routes and pick the optimal routes out of them.

The problem was therefore run using the VRP Spreadsheet Solver for the pharmaceutical firm’s 2 vehicles and 20 customers and optimal routes were generated for the 2 vehicles with their distances as follows:

Optimal tour for Vehicle 1 = 0 11 10 3 9 8 5 7 14 4 2 1 0

= d (0,11) + d (11,10) + d (10,3) + d (3,9) + d (9,8) + d (8,5) + d (5,7) + d (7,14) + d (14,4) + d (4,2) + d (2,1) + d (1,0)

= 18.04 + 12.11 + 10.18 + 6.92 + 7.88 + 9.60 + 7.38 + 10.70 + 12.53 + 9.47 + 5.15 + 7.63 = 117.59 km

This implies that the optimal movement of Vehicle 1 should be as follows:

Depot Binduri Belagu Garu Parinboko Bugri Corner Wariyanga Dekulga Biankori Basyondi Sugudi Pusiga Depot.

Figure 3 gives the optimal tour map for Vehicle 1.

Figure 3. Optimal Tour Map for Vehicle 1

Optimal tour for Vehicle 2 = 0 16 19 6 20 17 18 15 13 12 0

Thus, d (0,16) + d (16,19) + d (19,6) + d (6,20) + d (20,17) + d (17,18) + d (18,15) + d (15,13) + d (13,12) + d (12,0)

= 14.45 + 43.41 + 25.83 + 73.76 + 131.84 + 5.86 + 24.45 + 138.86 + 45.98 + 34.62

= 539.06 km

The optimal tour for Vehicle 2 is as follows: Depot Kugurago Nakpanduri Nalerigu Gushiegu Yendi Tamale Savulugu Bolgatanga Zebilla Depot

Figure 4 gives the optimal tour map for Vehicle 2.

Figure 4

The total optimal distance to be traveled by the two (2) vehicles of the pharmaceutical firm is (117.59 + 539.06) km = 656.65 km.

Figure 5 shows an optimal tour map of the two vehicles where V1(T1) and V2(T2) stand for Vehicle 1 (Tour 1) and Vehicle 2 (Tour 2) respectively.

Figure 5. Optimal Tour Map for the Two Vehicles of the Pharmaceutical firm

Discussion of Results

A distance matrix of the customer locations that has been constructed for the pharmaceutical firm will help the firm to know at a glance the various places toured by their two (2) vehicles and the distance between any pair of them. Also, the optimal operating routes that have been determined for the vehicles used by the pharmaceutical firm will go a long way to reduce the cost of transportation of the firm. Finally, the determined total optimal distance to be covered by the vehicles of the pharmaceutical firm will help the manager of the firm to monitor whether their vehicles are being used properly or not.

5. Conclusions

The concept of Vehicle Routing Problem has been successfully used to analyze the operations of a pharmaceutical firm in Upper East Region of Ghana. Specifically, a distance matrix of the customer locations has been constructed for the pharmaceutical firm. Also, optimal operating routes have been determined for the vehicles used by the pharmaceutical firm in order to reduce transportation cost. Moreover, the total optimal distance to be covered by the vehicles of the pharmaceutical firm has also been determined.

The study recommends that the pharmaceutical firm should always ensure that its vehicles traverse the determined optimal operating routes in order to minimize transportation cost. Also, other pharmaceutical firms or companies who do not know their optimal routes should make efforts to find out their optimal operating routes in order to minimize their cost of operation.