The logistic decision making in management accounting with genetic algoritms and fuzzy sets

Mathware & Soft Computing 7 (2000) 229-241 229 The Logistic Decision Making in Management Accounting with Genetic Algorithms and Fuzzy Sets E. López-González, M.A. Rodríguez-Fernández and C. Mendaña-Cuervo Dept. of Economy and Business Management, Univ. of León Campus de Vegazana, s/n. (24071) León, Spain dde{elg/mrf/cmc}@unileon.es Abstract The logistics problems in business environments deal with assignation from a number of sources to a number of destinations. Each source offers amounts of goods, while each destination demands quantities of these goods. The object is to find the cheapest transporting schedule that satisfies the demand without violating supply restraints. In this paper we propose to use Fuzzy Sets to represents the previsional information related to costs, demands and other variables. Moreover, we suggest including the problem of shortest route for the distribution vehicles. Finally, to solve this complex problem we propose to use a Genetic Algorithm with a Fuzzy Fitness Function. Keywords: transportation problem, shortest route problem, logistic, minimising costs, imprecise information, fuzzy sets and genetic algorithms. 1 Introduction Many different optimisation problems can be formulated on networks: For instance, we might be interested in finding the shortest path from one node to another, finding the cheapest way to connect all the nodes, or finding the best way to move objects through a network. Networks optimisation represents one of the most important areas of management science for several reasons [3] [5]. First, networks can be used to model many diverse applications such as transportation systems, communication systems, vehicle routing problems, production planning and cash flow analysis. Second, managers accept networks more readily because they provide a visual picture of the problem under study. Finally, networks have certain mathematical E. López-González, M A. Rodríguez-Fernández & C.Mendaña-Cuervo 2 3 0 properties that allow management scientists to develop special algorithms that are able to solve much larger problems than other optimisation methods. In this paper we pretend to show a new approach to a classical network optimisation problem: the transportation problem. Firstly, allowing the vehicles that can establish routes, and, also, permitting to manage with imprecise or vague information. We propose to use the Fuzzy Sets Theory [15] [8] [16], with the aim of being able to handle the uncertainty, which is a characteristic of decision-making processes in distribution problems. Moreover, to optimise the distribution network we suggest to use a Genetic Algorithm (GA) [4] [1] [10] [6]. The main reason for this is that the GAs are heuristic optimisation methods which don’t impose restrictions to the posing of the problem. In this study, the algorithm is characterised by its use of a Fuzzy Fitness Function that allows the evaluation of imprecise information. In the light of the above, the next section shows a description of the problem to be solved. Third section presents the fuzzy approach to this problem. In fourth section we introduces the genetic algorithm used to solve the aforementioned approach. Fifth section offers a practical example of the distribution problem and, finally, we include some concluding remarks. 2 The Logistic Business Problem We consider the problem of finding the least cost means of shipping supplies from several origins to several destinations. Origin points or sources can be factories, warehouses, or any other points from which goods are shipped. Destinations are any points that receive goods. To solve this problem we must find how many goods are supplied from each source to each destination and what is the route that the distribution vehicle must follow in order to minimize the total distribution costs. Traditionally this problem has been analysed in two different decisions. Firstly, obtaining the quantities to be shipped from each origin to each destination minimising the costs and satisfying the demand, or Transportation Problem (Figure 1). On the other hand, finding the shortest route that one vehicle must follow to reach all the destinations, or Shortest Route Problem, so known as Travelling Salesman Problem. In this paper we suggest to combine both problems in order to obtain an optimal solution that minimises the distribution costs of the quantities supplied and the routes followed. A logistic problem has a very large, sometimes infinite, number of feasible solutions. Traditionally, this problem has partially reduced not permitting shipments among destinations. This kind of problems can be solved with Linear Programming and other methods as Stepping Stone, MODI, Houthtaker Method or Hammer Balas Method. But the global approach, considering the vehicles distribution routes is poorly studied [13] [5]. The Logistic Decision Making in Management Accounting.... 2 3 1 Figure 1. Transportation Problem Moreover, some of the information considered is imprecise. Costs, supplies and demands may be not known in a crisp numerical way [2]. Therefore, in this paper we suggest to use Fuzzy Sets to represent their vague knowledge. 3 Fuzzy Logistic Model With this method the companies must know how many commodities supply from each origin to each destination when the information on held is not precise and a fuzzy representation in more accurate. As we show below, the information necessary is related to: • Destination or client demands. The company must satisfy the client demands. Sometimes this information is vague; therefore we consider a more realist representation using fuzzy sets. So, for n destinations we could have: { } n CCC C ~ , , ~ , ~ ~ 2 1  = • Sources number and its supply capacity. We suppose that each source has a supply capacity, normally known in a strict way. So for m sources we could have: { } m FFF F , , , 2 1  = • Vehicle Capacity. We consider that in each source the company has a vehicle used to distribute the commodities. Therefore, we must take into account the vehicle capacity, because the number of travels will depend of it. For the aforementioned m sources, the vehicle capacities could be: { } m VVVV , , , 2 1  = • Transporting costs of the empty vehicles. Sometimes, the vehicles must return to their respective sources due to that each one has distributed their capacities. Moreover, the last travel is made between the last client supplied and the source of the vehicle. Thus, we must take into account what is the shipping cost when E. López-González, M A. Rodríguez-Fernández & C.Mendaña-Cuervo 2 3 2 the vehicle is empty. This, normally depends of the distance (routed kilometres). So, for m sources, the transporting cost of empty vehicles could be: { } m cvcvcv c v , , , 2 1  = • Increasing cost for each unit of commodities shipped. When the vehicles distribute the commodities the transporting cost increase with each unit shipped. As well, this increasing cost depends of the distance travelled. Moreover, the knowledge of this cost could not be precise and then representing it using fuzzy sets could improve the results obtained. Thus, for m vehicles the increasing cost could be: { } m cvcvcvcv ∆∆∆=∆ ~ , , ~ , ~ ~ 2 1  • Distance among sources and destinations. The distribution is made from the sources to the destinations or clients. So, it is necessary to know the distance among them.               = mnmm n n DDD DDD DDD D , , , , , , , , , 2 1 2 22 21 1 12 11     • Distance among destinations. As we mentioned before, the vehicles can establish routes from the source to the several destinations that this source supplies. Thus, it is necessary to know the distances among the destinations               − − − = , , ' , ' ' , , , ' ' , , ' , ' 2 1 2 21 1 12     nn n n DD DD DD D According with this approach, we are trying to reach the real distribution problem. Thereafter, we need some tool capable to solve this complex problem or able to give a reasonable solution. In this paper we propose to use a Genetic Algorithm with a Fuzzy Fitness Function. Although we describe to use fuzzy sets, we suggest representing all the fuzzy information as Trapezoidal Fuzzy Numbers (TFN). 4 Genetic Algorithms and Fuzzy Logistic Problems Some authors have applied Genetic Algorithms to transportation problems [14] [12]. In many cases they solve the problem reducing their complexity or using precise knowledge for the variables. In our approach, we suggest a fuzzy representation (TFN) of the information on held and a less restrictive model. Due to this, the GA must determine the quantities supplied from each source to each destination and the routes travelled for the vehicles. For both objectives the criteria is the same: minimising the total distribution costs. The Logistic Decision Making in Management Accounting.... 2 3 3 4.1. Genetic Algorithms GAs are search algorithms which use principles inspired by natural genetics to evolve solutions to problems [7]. The basic idea is to maintain a population of chromosomes, which represents candidate solutions to the concrete problem being solved, which evolves over time through a process of competition and controlled variation. GAs have got a great measure of success in search and optimisation problems. A GA starts off with a population of randomly generated chromosomes (solutions), and advances toward better chromosomes by applying genetic operators modelled on the genetic processes occurring in nature. During successive iterations, called generations, chromosomes in the population are rated for their adaptation as solutions, and on the basis of these evaluations, a new population of chromosomes is formed using a selection mechanism and specific genetic operators such as crossover and mutation. An evaluation or fitness function must be devised for each problem to be solved. Given a particular chromosome, a possible solution, the fitness function returns a single numerical fitness, which is supposed to be proportional to the utility or adaptation of the solution represented by that chromosome. GAs may deal successfully with a wide range of problem areas, particularly in management applications. The main reasons for this success are: 1) GAs can solve hard problems quickly and reliably, 2) GAs are easy to interface to existing simulations and models, 3) GAs are extendible and 4) GAs are easy to hybridise. All these reasons may be summed up in only one: GAs are robust. GAs are powerful in difficult environments where the space is usually large, discontinuous, complex and poorly understood. They are not guaranteed to find the global optimum solution to a problem, but they are generally good at finding acceptably good solutions to problems quickly. These reasons have been behind the fact that, during the last few years, GAs applications have grown enormously in many fields. The basic principles of GAs were first laid down rigorously by Holland [7], and are well described in many books, such as [4] [11]. 4.2 A Genetic Algorithm for Fuzzy Logistic Problems To solve the fuzzy logistic problem we propose to use a GA with the following components: Genetic Representation The solutions to the problems are a set of distribution quantities to be shipped from each source to each destination and the routes followed by the vehicles of each source. To codify this solutions we propose to use two matrixes: one that contains the quantities distributed from each origin to each destination, and, other, that represents the path followed for the several vehicles. The codification of quantities matrix, for an example of five sources that must supply to four destinations could be: E. López-González, M A. Rodríguez-Fernández & C.Mendaña-Cuervo 2 3 4 1 1 SSource 1 Source 2 Source 3 Source 4 Source 5 Total Destination 1 15 0 0 70 0 85 Destination 2 0 40 0 0 0 40 Destination 3 25 10 40 0 50 125 Destination 4 0 0 60 0 5 65 Total 40 50 100 70 55 315 that indicates the quantities supplied from each source to each destination. On the other hand, the codification of vehicles routed could be: 2 1 SSource 1Source 2Source 3Source 4Source 5 Destination 1 1 2 1 4 3 Destination 2 4 3 2 3 2 Destination 3 2 1 3 2 1 Destination 4 3 4 4 1 4 that indicates the position of each destination in the vehicle routes. Moreover, in order to generate usefulness solutions, the company must decide the covering level of each client fuzzy demand. The TFN can be identified as possibility distributions. So, the company establish the risk of not cover demand of each client. According to this, the quantity matrix represents available solutions for the decision. Fuzzy Fitness Function The fitness function must assign more value to these solutions that are good solutions to the distribution problem. To this we propose to calculate the total distribution cost that the two matrixes suppose. The steps are as follows: At the beginning, each vehicle departs from its source full of commodities. The first destination, established by the routes matrix, determines the cost of this first travel. Once the first destination is satisfied (with one or more travels) the second destination is attempted. If the vehicle is empty during the route, it returns empty to the source to full its capacity. As well, when all the destinations are satisfied then the vehicle go back to its origin, completing the route. The sum of all these transporting costs (depart from origin full, attempt first destination, attempt second, go back to origin when empty, etc.) would be a part of the solution. To obtain the total cost we must add the cost of the other distribution routes contained in the matrixes and established for other vehicles. Due to the fact that some of the information can be represented by fuzzy sets, we suggest to use the operations designed for them [3]. Moreover, in the cases that the operations could not produce a TFN, we approximate the result as one of this [9], assuming a little error. To set up a hierarchy among the solutions, the proposal is to use the fuzzy distance [9], based on Hamming Distance. Doing it, we calculate the distance from the origin B ~ (singleton 0) to each solution fuzzy cost, which is defined as follows: α α αααα dBABABA d ) ( ) ~ , ~ ( 1 0 2 2 1 1 ∫−+−= = The Logistic Decision Making in Management Accounting.... 2 3 5 where [ ] 2 1 , αα AA is confidence interval of A ~ at the signification level α . The more accurate solutions will have a lower distance. Thus for obtaining the fitness value we propose to calculate the inverse of the distance of each solution. Selection process We propose to use Roulette Wheel Ranking [4] to select the individuals that will be the “parents” of the next generation. Crossover operator Traditional crossovers cannot be used, because the solutions are two matrixes that have to accomplish some constraints. Due to this we propose two different crossovers for each matrix, as follows: ♦ Distribution quantities matrixes. To combine the information of these matrixes obtained from two “parents” we have used the crossover proposed for Vignaux and Michalewicz to Transportation Problem [14]. ♦ Vehicle routes matrixes. As well, we must cross the route matrixes of both “parents”. To this, we select one source and interchange between the “parents” the routes that the vehicle of this origin must follow. If we have to cross the following route matrixes of the aforementioned problem, first we randomly select one source (source 2): 2 1 SSource 1 Source 2 Source 3Source 4Source 5 Destination 1 1 2 1 4 3 Destination 2 4 3 2 3 2 Destination 3 2 1 3 2 1 Destination 4 3 4 4 1 4 2 2 SSource 1 Source 2 Source 3Source 4Source 5 Destination 1 3 4 4 1 2 Destination 2 4 3 2 2 4 Destination 3 1 2 3 3 3 Destination 4 2 1 1 4 1 After that, we interchange the list of routes followed, being the matrixes resulting. '2 1 SSource 1Source 2Source 3Source 4Source 5 Destination 1 1 4 1 4 3 Destination 2 4 3 2 3 2 Destination 3 2 2 3 2 1 Destination 4 3 1 4 1 4 E. López-González, M A. Rodríguez-Fernández & C.Mendaña-Cuervo 2 3 6 '2 2 SSource 1Source 2Source 3Source 4Source 5 Destination 1 3 2 4 1 2 Destination 2 4 3 2 2 4 Destination 3 1 1 3 3 3 Destination 4 2 4 1 4 1 Mutation operator The intention of this operator is to introduce diversity into the solutions. Trying to this we must make differences among the two types of matrixes. • Distribution quantities mutation. We propose to use a special mutation method designed to keep the solutions resulting as feasible ones. The steps are as follow: • Step 1. We select one source (Source A) and one destination (Destination A) of the matrix. This destination must receive a non-zero quantity from the source selected. For the example, if we mutate the first matrix obtained after the crossing process, the source and destination could be: 1 1 SSource 1 Source 2 Source 3 Source 4 Source 5 Total Destination 1 8 0 25 35 17 85 Destination 2 0 40 0 0 0 40 Destination 3 15 5 45 35 25 125 Destination 4 17 5 30 0 13 65 Total 40 50 100 70 55 315 • Step 2. We generate a random number between 0 and the quantity assigned to this destination. For the example could be 20. • Step 3. We search in the remaining sources one quantity assigned to a different destination which amount is bigger than the random number generated before (Source B and Destination B). For the example could be: 1 1 SSource 1 Source 2 Source 3Source 4Source 5 Total Destination 1 8 0 25 35 17 85 Destination 2 0 40 0 0 0 40 Destination 3 15 5 45 35 25 125 Destination 4 17 5 30 0 13 65 Total 40 50 100 70 55 315 • Step 4. We discount the random number to the assigned amounts from the Source A to Destination A and from the Source B to Destination B. After that, we add the random number to the assigned amounts from Source A to Destination B and from Source B to Destination A. According to this, for the example, the mutated matrix could be: The Logistic Decision Making in Management Accounting.... 2 3 7 '1 1 SSource 1 Source 2 Source 3 Source 4 Source 5 Total Destination 1 8 0 25 35 17 85 Destination 2 0 20 20 0 0 40 Destination 3 15 25 25 35 25 125 Destination 4 17 5 30 0 13 65 Total 40 50 100 70 55 315 Finally, with the aforementioned process we can mutate the quantity matrixes maintaining them as feasible ones. • Vehicles routes mutation. On the other hand, for mutating the route matrix we propose and interchange method. First, we select randomly one source. After that, we select two destinations and interchange their position in the route followed for the source vehicle. Halt criteria for the best solution search The proposal is for the algorithm to go through a number of generations specified by the user until the best solution is found. Moreover, in order not to lose good solutions, the characteristic termed elitism [4] has been introduced. This procedure consists of keeping the best individual from a population in successive generations unless and until some other individual succeeds in doing better in respect of suitability. In this way, the best solution for a previous population is not lost until outclassed by a more suitable solution. As explained, application of the model proposed here allows solving the distribution problem under uncertain environmental conditions. 5 Experiment: an Example of Practical Application In this section we present an example that deals with the logistic problem for a production furniture company. To do that we divide this section in subsections: one with the posing of the problem and other with the solution using the GA proposed. 5.1 Introduction to the problem Let it be imagined that a furniture company supplies desks to several clients. To obtain the desks have four factories and each one with its own distribution vehicle. In Chart 1 we show the production capacity of each factory and the capacity, transporting cost empty and increase for transporting unit of their respective vehicles. Factor y Production capacity Vehicle capacity Transporting cost empty ($/Km.) Transporting cost Increasing for product unit ($/Km.) A2000 1000 60 (4; 8; 8; 10) B4000 1400 40 (8; 10; 10; 12) C6000 200 80 (2; 4; 4; 6) D2000 400 20 (6; 6; 6; 6) Chart 1