Journal of Applied Sciences

Year: 2014 | Volume: 14 | Issue: 17 | Page No.: 1909-1918
DOI: 10.3923/jas.2014.1909.1918

Tabu Search to Define Best Routes in Canvassing Distribution System: A Case Study

Henry Yuliando, Endy Suwondo, Adi Djoko Guritno and Arianti

Abstract: A process of distribution should be managed attentively in order to achieve a high growth and profitable output. It is necessary for the company to design a route arranging and scheduling to meet the company’s revenue target. The policy studied here in PT Andrawina Company, Yogyakarta, Indonesia, is canvassing strategy for determining best route in term of combining length of distance as well as revenue gains. This study presents the application of Tabu Search (TS) to define the best routes for the company. The method used here covered the features of initial solution by Greedy approach, nodes interchange as the selection of move, candidate lists strategy and aspiration criteria. According to the result of TS, the available routes could be modified into 5 daily and a buffer day for the after admission of the distribution. In addition, the best routes generated by TS did outweigh both over the nearest customers and potential customers (retailers).

Keywords: Canvassing distribution, capacitated vehicle routing problem, greedy approach and tabu search

INTRODUCTION

A distribution process has a great deal with many problems related to optimization which has been increasing surprisingly in diverse areas. However, the optimal distribution of the products is the main issue to any industry as well as to manufacturing company in the present age of competitive global economy. The most common issues of route determinations include optimizing travelled distance, travelling cost, travel time, a number of operated vehicles and other available resources.

As a distributor of Walls ice cream product of Unilever; PT Andrawina Company, Yogyakarta, Indonesia has a great deal with complex phenomena related to combinatorial and optimization problems. Some of the problems being faced are about route arranging and scheduling in respect of meeting the company’s fulfillment as revenue targets and ensuring the product placed in the right place at the right time. Accordingly, Sales Canvassing Strategy, one of distribution techniques, is used by the company in certain district routes. By applying canvassing method, the product spreading and the availability of product in the market can be distributed throughout the route territory and easily accessed by consumers (Asif, 2009). Apart from that, quick product replenishment from the warehouse to retail outlets with higher profitable margin is an important part of distribution system. Thus, the gap occurred by applying sales canvassing method and increasing the company’s profitable margin gained by potential customers can lead to a better routing and scheduling management in order to attain an optimal distribution.

Routing and scheduling management related to the problems of the company is generally referred as a Capacitated Vehicle Routing Problem (CVRP). According to Baldacci et al. (2004), CVRP can optimize a delivery schedule based on routes from one or more depots to several destinations. In the last decades, several meta-heuristic approaches have been put forward for the solution of the CVRP (Toth and Vigo, 2002; Brandao, 2006). Cordeau et al. (2002) identified six families of meta-heuristics for the CVRP i.e., simulated annealing, deterministic annealing, tabu search, genetic algorithms, ant systems and neural networks.

In this study, allied with the canvassing selling strategy, CVRP was employed to provide a delivery service to a set of customers from a depot. This study aims to determine the best solution by considering revenue of a canvassing distribution system allied with the CVRP. Consequently, a TS approach was found suitable to solve the problems in a sense of considering potential customers who give higher margin of profit as a decision parameter. TS approach has proven to be very effective for the VRP and its variants (Gendreau et al., 1994; Archetti et al., 2006; Brandao, 2006; El Fallahi et al., 2008).

In this study, an analysis was done in determining the optimal route for the assigned vehicles which deliver the product to district 11 route. The traffic lane passed by the canvasser was two ways so that the forward and reverse distances are indistinguishable (symmetric) and disregards the condition of travelled road. According to the canvassing distribution method, the salesman may do promotional selling activities. Thus, the quantity orders requested by retailers can easily be changeable. In order to ensure that the method used can be plausible to apply, the quantity order should have been ordered by the customers before the delivery time.

MATERIALS AND METHODS

Canvassing selling strategy: To increase the profitable margin, the company needs to increase the sales. To increase the sales, there has been widely marketing techniques in order to generate more leads and potential customers. Prospecting is one of tools of “seven steps of selling” where salespeople search for new customers and potential customers. One obvious reason for prospecting is to expand the customer base, which is necessary because most sales organizations lose customers every year. One of famous prospecting methods is canvassing selling (Moncrief and Marshall, 2005). Canvassing is a planned activity conducted by a person to offer, distribute, seeking sales for certain product and services, including to deliver and collect certain information from retailers and/or customers (Raynaldi and Hamsal, 2008).

During canvassing, there shall be three steps to carry on in order completing the sale successfully. The first step is called the contact, a good relationship building with customers. The contact should be firstly done to reach the impression of prospective customers. The second step is the presentation which takes no longer than one minute. This step may be called as one of the promotional activities as well. Unlike the contact in which the matters may not be merely talking about business, the presentation step should outline the features of products offered and the benefits given by the company to customers. The last step is the close, a magical moment when a salesman (canvasser) completes the sale. A canvasser shall be a good closer to make canvassing work at all. A good closer should be able to make such signs of prospective customers to say “Yes” or reach their wallet or merely nod affirmatively. If a salesman makes a good contact, a crisp presentation and an impressive close, as well as a good value of soliciting, canvassing may be the only marketing tool he or she ever need (Asif, 2009).

Vehicle Routing Problem (VRP) and Capacitated Routing Problem (CVRP): The Vehicle Routing Problem (VRP) is to find the optimal routes of delivery or collection from one or several depots to a number of cities or customers, while satisfying some constraints. Collection of household waste, gasoline delivery trucks, goods distribution and mail delivery are the most used applications of the VRP. The VRP plays a vital role in distribution and logistics. Huge research efforts have been devoted to study the VRP since 1959 when Dantzig and Ramser (1959) described the problem as a generalized problem of Travelling Salesman Problem (TSP). Thousands of papers have been written on several VRP variants such as Vehicle Routing Problem with Time Windows (VRPTW), Vehicle Routing Problem with Pick-Up and Delivery (VRPPD) and Capacitated Vehicle Routing Problem (CVRP).

Tabu Search is an extension of classical Local Search (LS) methods. In fact, TS can be seen as simply the combination of LS with short-term memories. It appears that the two first basic elements of any TS heuristic are the definition of its search space and its neighborhood structure. The search space of a LS or TS heuristic is simply the space of all possible solutions that can be considered (visited) during the search. For instance, in the CVRP case discussed in this study, the search space could simply be the set of feasible solutions to the problem, where each point in the search corresponds to a set of vehicles route satisfying all the specified constraints (Rochat and Taillard, 1995).

According to Toth and Vigo (2002) the most elementary version of the vehicle routing problem is the Capacitated Vehicle Routing Problem (CVRP). The Capacitated Vehicle Routing Problem (CVRP) is a generalization of VRP. CVRP is an issued problem in the fields of transportation, distribution and logistics which involves a set of routes that covers a set of customers. Till to date many models have been proposed where most of the proposed algorithms assume that the number of vehicles is unlimited and the objective is to obtain a solution that either minimizes the number of vehicles and the total travel cost. However, transport operators in the real world face resource constraints such as a fixed fleet. For example, if the given problem is over-constrained in the sense of insufficient vehicles, but optimal strategy is carried out so as to satisfy the demands of the clients within a time constraint.

The following is a model which vehicle is also limited due to the optimal resources management. In this case, customers’ demands must be satisfied by exactly one vehicle within one route while respecting the vehicle’s capacity.

The CVRP graphed at Fig. 1 Toth and Vigo (2002) can be referred as a graph G = (V, E) where V = {V₀, V₁, …,V_n} is a vertex set and E = {(vi,vj) : vi,vj∈V, i<j} is an edge set.

Vertex v₀ represents depots at which are based M identical vehicles of capacity Q, while the remaining vertices are cities or customers which are associated with a known demand.

Each customer v_i has a non-negative demand d_i to be delivered. A non-negative cost, distance or travel time matrix C = (cij) is defined on E. The VRP consists of determining a set of M vehicle routes of (1) Minimum total cost, (2) Starting and ending at the depot, (3) Each customer is visited exactly once by one vehicle, (4) The total demand of any route does not exceed Q, (5) The total duration of any route does not exceed a preset bound D. the number of vehicle is either an input value or a decision variable. In the latter case vehicle fixed cost are sometimes incorporated in the objective function. For the purpose to minimize the cost or travel route, the CVRP mathematically can be formulated as follow (Baldacci et al., 2004).

That objective function states that the costs should be minimized subject to the following constraints:

Tabu Search (TS) approach: Over the last two decades, more than hundred papers presenting application of TS, a heuristic method originally proposed by Glover in 1997 to various combinatorial problems in the operations research literature. In several cases, the methods provide solutions which are close to optimality and among the most effective. These successes have made TS extremely popular among those interested in finding good solutions to the large combinatorial problems encountered in may practical settings (Cordeau and Laporte, 2001).

The search space of a TS heuristic is simply the space of all possible solutions that can be considered (visited) during the search. For instance, in the CVRP case discussed in this study, the search space could simply be the set of feasible solutions to the problem, where each point in the search corresponds to a set of vehicles route satisfying all the specified constraints (Rochat and Taillard, 1995).

The core of TS is embodied in its short-term memory process which constitutes a form of aggressive exploration. The exploration seeks the best move possible, subject to satisfy certain constraints. These constraints, embodied in Tabu restriction, are intended to prevent a cycling behavior (revisiting some earlier solution) and take a best move away from a local optimum. To meet the best admissible move, a component of TS is designed in an algorithm.

Glover and Laguna (1997) stated in their book that TS is closely linked to the definition of the search space that explore the solution space beyond local optimality. Each iteration of TS, the local transformations that can be applied to the current solution, denoted as S, defines a set of neighboring solutions in the search space, denoted by N (X) (the neighborhood of X). Formally, N (X) is a subset of the search space defined by:

N(X) = {solutions obtained by applying a single local transformation to X}

In general, for any specific problem, there are many more possible neighborhood structures than search space definitions. This appears from the fact that there may be several plausible neighborhood structures for a given definition of the search space.

Simple neighborhood structures of the CVRP involve a move of a single customer from its current route at iteration; the selected customer is inserted in the same route or in another route with sufficient residual capacity. An important feature of these neighborhood structures is the way in which insertions are performed: one could use random insertion or insertion at the best position in the target route; alternately, one could use more complex insertion schemes that involve a partial re-optimization of the target route. Before going any further it is important to stress that these neighborhood structures involve moving a single customer, the neighborhoods they define contain all the feasible route configurations that can be obtained from the current solution by moving any customer and inserting it in the stated fashion. Examining the neighborhood can thus be fairly demanded (Cordeau and Gendreau, 2002).

Standard Tabu lists are usually implemented as circular lists of fixed length. It has been shown, however, that fixed-length Tabu cannot always prevent cycling and some authors have proposed varying the Tabu list length during the search (Taillard et al., 1996; Glover and Laguna, 1997). Another solution is to randomly generate the Tabu tenure of each move within some specified interval; using this approach requires a somewhat different scheme for recording Tabu that are then usually stored as tags in an array (the entries in this array will usually record the iteration number until which a move is Tabu) (Gendreau et al., 1994).

Data collection and algorithm: The study was conducted in the distribution process of PT Andrawina company allied with customers covered in district 11 route, Bantul. The focus is related to the optimal routes upon the depot and customers which entail initial route obtained by Greedy method and final route eventually obtained by TS. The materials requisite for the quantitative and qualitative data include the number of fleet used, length distance from depot to customers, inter-distances among the customers, demands of product Ice Cream Wall’s, product requirement system and delivery system. The tools used are Google Earth to define the distance route among the customers and the depot and Ms. excel was used to tabulate and compute manual iterations.

The operations involves of editing, clustering, tabulating, iterating and analyzing. The number of customers were geographically scattered in a large scale, clustered into nodes that represents as the vertex. This clustering is done in order of the revenue and the nearest distance. Besides, related the optimization problems this clustering in line with Traveling Salesman Problem (TSP) method. The tabulation referred in this study involves a process of summarizing raw data in compact form for further analysis. It is an orderly arrangement of data in columns and rows. The distance is set as a matrix based on the nodes that have been clustered. In line with TS use, the study covers the features of problem size, generation of initial solution by greedy method, nodes interchange as the selection of move, candidate lists strategy and the choice of short memory structure. Iteration and analysis are conducted to encounter the initial solution and the best solution which was successively done by using greedy and TS approachs. To make this approach working, it was undertaken by following steps:

RESULTS AND DISCUSSION

There are number of studies on scheduling and vehicle routing using Tabu Search as a heuristics approach to get the best solution space. Montane and Galvao (2006), employed a typical TS algorithm to solve the problem of vehicle routing concerning to the simultaneous pick-up and delivery. They used three type of movement for inter-route adjacent soultion with the relocation, interchange and crossover movements. Brandao (2006), used Tabu search to get a solution for vehicle with the problem of backhauls, where some customers (linehauls) receive a shipment from depot and others receive from other customers (backhauls). While in this study, allied to the canvassing selling strategy, the vehicle routing schedule is based on all possible order to get the highest revenue.

Customer clustering: In order to generate an initial route, the customer clustering was constituted by considering the nearest location among the customers called as nodes. Customer clustering is also proposed to easily determine the length of distance upon the scattered customers. The initial route to determine the best route is defined by using Greedy method. This clustering consists of 28 nodes which are constituted of 134 customers and includes the Depot (Dpt). Each node consists of one or several customers which have varying length distance upon each others and classified according to the nearest location. The Depot is denoted by Dpt while the other nodes are alphabetically symbolized as A to Z as well as A. The each correlative distance length of all nodes is determined using Google Earth software and adjusted into a symmetrical matrix shown in Appendix 1.

According to the case of CVRP derived into a TSP, the distance matrix generated is symmetric. This symmetrical matrix is formed based on the inter-distance among the nodes. The symmetrical (undirected) form of the TSP may be defined as finding a minimum length Hamiltonian tour on a graph G = (V, E) where V = {V₀, V₁, …, V_n} is a vertex set and E = {(vi,vj): vi,vj V, i<j}. In addition, c(i,j) denotes the length of path (i,j) in E. In the symmetrical form of the problem c (i,j) = c (j,i), elements of E is treated undirected, where the pair (i,j) is the same as the pair (j,i). Consequently, the forward and reverse expressions of nodes are indistinguishable.

Initial route proposed by Greedy method: Related to the case in finding the solution of CVRP, the tool used is by merging the route of CVRP into travelling salesman problem in which the Greedy method is assigned. The data required as inputs consists of the size (number) of the nodes (cities), the length of distance between the depot and nodes as well as the inter-distances of nodes and the capacity of fleet assigned. On the following computation of iteration, Vn shows a starting node where a salesman starts his travel from and Vc denotes the unvisited nodes which are going to be visited in related to find the current feasible solution as local optima.

Generally, the procedure of the Greedy method for solving the TSP is started from node Depot (Dpt) and then each time go to the nearest node not visited yet. The goal is to find a shortest route that visits each node exactly once and then returns to the starting city. The function of “f: Vn→Vc” shows the search function of finding the least length of paths started from starting city to the targeted cities. Once all nodes are visited, the fleet must return to the starting node Depot (Dpt). By referring the Symmetrical Distance Matrix, the computation of iterations is defined as follows:

The solution obtained by Greedy method is enacted as an initial solution in term of TS method. Eventually after the iteration 26, the initial solution obtained gives a route which starts from Depot to the K node to successively next vertexes (nodes) and stops at Depot again. The total length of distance generated of initial route is 149.5 km. The initial route allied with the company route and the best route obtained by TS as well as the daily revenue is depicted in Table 1.

Best routes obtained through ts approach: For further data processing upon the initial solution, the execution for the best is done by using TS. In sense of this TSP, the objective is to find the tour with better revenue and distance. The data inputs of the execution are constituted of the demand number of each node in every delivery stated in rupiah currency and distance matrix from the Depot to the nodes and the inter-distances of the nodes. The execution is done in a manual computation using Microsoft Office Excel 2007.

Based on the search of iterations, the TS approach yields an approximately best solution to find a route of the TSP and gives the better sequential revenue. The best route obtained is eventually reached at Search Iteration 10.

The route is now started from Depot to successively node D, O, Aa, H, L, T, J, G, X, N, R, B, K, M, A, P, Q, C, W, S, U, Z, V, I, F, Y, E and returned to Depot. The total length of this route is 81.6 km greater than the previous initial route obtained by Greedy method which is 149.5 km. On the other hand to enact the scheduling, the route must be broken down into daily schedules in order of fleet’s capacity and work time. The division into a daily schedule is described in appendix 1.

According to the graphs shown in appendix 2, the routes constitute three routes which include the company’s route being used. In case of CVRP, the route could easily be modified into five daily routes. The Fig. 2-7 above show that the whole company’s routes are mostly disordered. There have been many revisits to certain customers which certainly makes the travelling ineffective due to the further distances and potential customers that should have been prioritized to get more profitable margin.

Since, the best route has given the better sequential revenue.

The best route consists of 5 daily routes and differs from the existing (company’s routes) which consists of 6 daily routes (shown in appendix 3).

Aside, the other unscheduled day of the best routes could be allocated as a delivering buffer time for the next order. The routes which might be in an under target revenue by the time may increase the level of target revenue. It means that whenever there might be several retailers run out the ice cream which would order twice or more for the replenishment, accordingly the request could be arranged in the same week (time) of route. Thus, the best routes generated by TS give a better output that does not only strengthen upon the nearest customers but also on the profitable revenue and potential customers (retailers) consideration.

CONCLUSION

According to the use of Tabu search, as the case of PT Andrawina, the route could eventually be modified into shorter day schedules. Accordingly, this solution generates a buffering day for the after admission of the distribution. Besides, the best routes generated by Tabu search outweighed both over the nearest customers and the profitable revenue (potential customers).

REFERENCES