AP10_1.vp 1 Allocation task The problem of allocation tasks lies in selecting an opti- mal number of logistics centers to be located subsequently on the basis of a multiple criteria evaluation. The difficulty of multiple criteria evaluation tasks results not only from the number of evaluation criteria, but also from how these criteria are expressed and from the degree which they are dependent on their nature in various units of measurement. It is not uncommon for there to be a mixed set of criteria, where some criteria are quantitative, i.e. expressed numeri- cally, and others are of a qualitative nature (expressed in a verbal description). Decision making a basic managerial actively, where a bad decision may be a key cause of a business failure. The impor- tance of decision making depends directly on the level of resources (primarily financial) that are closely connected with the decision making. The process of selecting feasible options from a set of pro- posed options forms a decision-making process and is a part of a broader decision-making task, namely selecting the best option. 1.1 Elements in the decision-making process The key elements in the decision-making process include: the decision-making objective, the subject and the object of the decision, evaluation criteria, decision-making options and their outcomes, and states of the world. 1.1.1 Decision-making objective(s) We understand the decision-making objective in solving a decision-making problem as a certain state that we wish to attain by means of a solution to the decision-making problem. In our case, the only objective is a decision on the optimal number of logistics centres. 1.1.2 Evaluation criteria Evaluation criteria are factors selected by the decision maker, serving for evaluating the advantageousness of indi- vidual decision-making options, from the viewpoint of meet- ing the objectives of the decision-making problem that is being solved. The evaluation criteria are usually derived from set objectives. Selected evaluation criteria for allocation tasks: � cost criterion 1. one-off acquisition costs for a new logistics centre – direct material (equipping the depot with vehicles by purchase or leasing, with furniture, computers, mobile telephones, a fixed telephone line and other office equipment) 2. monthly operating costs for a branch – direct wages, other direct costs, operating margin, administra- tion margin, etc. (basic wages, supplements and additional payments, bonuses and remunerations, operating expenses, depreciation charges, repair and maintenance fees, offsetting up a repair fund, transport and travel costs, contributions from wages, fuel costs, telephone charges, energy, insurance, fines, penalties, loan repayments, leasing) 3. costs for providing the branch with the required sup- ply of materials and spare parts – storage costs, funds tied up in stock 4. environmental costs. The one-off costs and the capital field up in supplies will grow along the curve with the growing number of depots; however, the operating costs will decrease as a result of smaller catchments areas. � response times (speed) – by setting up another depot, the response period will be reduced due to the reduced size of the catchment areas. This will be reflected in the reduced average number of kilometers driven and, consequently, in decreased fuel costs, � technology demands – equipping the depot with special vehicles, machinery and handling equipment, � customer convenience, � share of services in the public interest – fire-fighters, emer- gency services, � energy requirements, � geographical considerations, � economic importance, � social considerations – solution to unemployment, � importance of the hub as a transit hub, 30 © Czech Technical University Publishing House http://ctn.cvut.cz/ap/ Acta Polytechnica Vol. 50 No. 1/2010 Allocation and Location of Transport Logistics Centres D. Mocková The facility allocation problem sets out to determine the optimal number of facilities to be opened. Based on multiple criteria evaluation, the optimal location of the facilities is usually solved subsequently. Several considerations, e.g. technical parameters, costs and finance must be taken into account. Economic analysis is carried out on the basis of the specific instance of the problem. Let us assume that the number of potentially located facilities is known. Then the problem of the optimal location of a given number of facili- ties in a network is referred to as the facility location problem. The solution to the problem is a set of facilities optimally located in an area such that this area is fully covered by the required services that the facilities provide. An example of a real-life problem of this type is the location of logistics centers. Keywords: Allocation tasks, set of criteria, multiple criteria evaluation, location tasks, heuristic method, genetic algorithm, fitness function. � importance of the hub from the viewpoint of resources – raw materials, � importance of the hub from the viewpoint of customers. 1.1.3 Decision-making subject The decision-making subject (decision maker) is the per- son making the decision, i.e. the person selecting the option for implementation. The decision-making subject may be an individual or a group of people. 1.1.4 Decision-making object The decision-making object is, as a rule, understood as be- ing the field for which the problem has been formulated, for which the objective of the solution has been set, and which the decision making concerns (a decision-making object may, for example, be to determine the reserve stocks of logistics centre warehouses, the equipment of logistics centres, finan- cial provision for development, etc.). 1.1.5 Decision-making options and their outcomes The options for solving a problem represent for the de- cision maker possible courses of action that will lead to the solution of the problem, or, as relevant, to the fulfillment of the objectives that have been set. While many decision- -making problems have given or known alternative solutions, there are many cases (especially in the case of complex de- cision-making problems) where the creation of options is time-consuming and requires a creative approach for de- manding complex processing and searching for information. Decision-making options are closely linked with their out- comes, which we can understand as being the anticipated impacts and effects of the options. 1.1.6 States of the world States of the world (scenarios, risk situations) may be understood as future mutually exclusive situations that may occur following implementation of the option, and which influence the outcomes of the given option with regard to spe- cific evaluation criteria. 1.2 Solution methodology � Determining the decision-making object, subject and objective. � Determining the criteria for evaluating the options – informa- tion should be fully exploited in selecting the criteria. The primary consideration in setting the evaluation cri- teria is the objectives to be achieved by the solution to the decision-making problem. Besides the objectives for the problem being solved, the selection of the evalu- ation criteria may also be supported by identifying the subjects whose interests, objectives, or needs may be affected by solving the problem or by choosing one of the options. In addition, searching for and clarifying the potential adverse impacts and effects of the options is also important. Applying the above-mentioned criteria helps to eliminate at least some of the shortcomings that can arise in decision making. � Methods for setting criteria weightings – most methods for multiple criteria evaluation of options require first that weightings be set for the individual evaluation criteria that will express numerically the importance of these criteria. The greater the importance of the criterion, the higher its weighting. In order to achieve comparability between the weightings of a set of criteria determined by different methods, these weightings are as a rule stan- dardized so that the sum of the weightings is equal to one. � Generation of options – this is the most important stage in the decision-making problem, and the quality of the so- lution to of the whole decision-making problem de- pends on it. � Evaluation of options and selection of the option intended for implementation – the final objective is to determine an option of the decision-making problem solution that will best meet the solution objectives of the problem. The option intended for realization must be feasible. Therefore it is necessary to exclude from the set of eval- uated options those that are inadmissible. Inadmissible options are those that: 1. do not meet some of the objectives of the solution to the decision-making problem, 2. do not fullfil some of the limiting conditions. 1.3 Multiple criteria decision making Multiple criteria decision making involves modeling deci- sion-making situations containing a defined set of options and a set of criteria according to which the options will be evaluated. The outcome of the option evaluation process is that we can establish of the preferential arrangement of the options, i.e. we can rank their overall advantageousness. The first place is occupied by the most advantageous option, i.e. the optimal option. Determining the preferential ranking is in general a demanding process, the complexity of which grows with the increasing size of the set of options and with the increasing number of criteria. If a given criterion is of a quantitative nature, it is sufficient to rank the options by their descending or ascending values (where this concerns a cost or revenue type criterion). The complexity of multiple criteria evaluation of options is often dealt with by unjustified simplification of the task, where the number of evaluation criteria is reduced by neglect- ing less important criteria. A different, more acceptable approach to multiple criteria evaluation attempts to convert all the criteria into the same unit of measurement, which ensures that the individual crite- ria are enumerable, and thus that they can be converted to a single criterion. Determining the preferential ranking of options often de- pends on the importance attributed by the decision maker to the individual evaluation criteria, i.e., it depends on the value hierarchy of the decision maker and his subjective appraisal. Different decision makers may reach different preferential rankings of options. 2 Location tasks Common solution approaches are either exact methods or heuristics. The latter are preferred, and many approaches have been developed with the application of genetic algo- © Czech Technical University Publishing House http://ctn.cvut.cz/ap/ 31 Acta Polytechnica Vol. 50 No. 1/2010 rithms. The advantage of this heuristics is that the elementary steps of the algorithm do not depend on the criterion, i.e. the algorithm works even though the criterion has been changed. 2.1 Heuristics for locating of transport logistics centres 2.1.1 Methods for solving location tasks The problems dealt with here belong to the category of combinatory tasks of discrete optimization. We can use two different approaches. The first approach comprises exact methods based on examining all possible options, deter- mining the value of the criterion and selecting the optimal solution. This approach is time-consuming, and may be used for tasks that are not too extensive. However, such tasks are rare in practice. Let us take 1000 nodes as the possible location of logistics centres, and the total number of possible locations is given by the formula: 1000 1000 1000 1 1000 k k k k � � ���� � � ����� � � ! ( ) ! ! , (1) where k is the number of depots in the network. Another approach uses heuristic methods and proce- dures. The result is, as a rule, a suboptimal solution that may be significantly far from the optimal solution. There is, for example, a heuristic method that uses an iterative algorithm to determine the peak optimal location of k depots in the network. The model is simplified (deterministic) with a known number of operating requirements, the quality criterion being the minimization of transport work, or, as relevant, minimization of the time necessary for reaching each point in the network at which a logistics requirement may arise. 2.1.2 Solving location tasks by means of genetic algorithms A further heuristic method involves solving location tasks by means of genetic algorithms. The basic advantage of these algorithms is that they scan the area at several points at the same time, with concurrent information exchange between the scanned points. Another advantage is that they find better solutions without needing to know of the structure of the problem solved. The algorithm, in solving a problem, works only with a string of ones and zeros and with the quality of such strings. The quality is discovered by using a decoding function. This function is the only mediator between the problem and the algorithm. The purpose of the algorithm is thus to obtain the best strings possible. The whole algorithm is very simple. It is composed of only three operators – repro- duction, crossover, and mutation. Each of these operators uses random selection. The whole algorithm works in by creating a new genera- tion from an old generation. This means that after obtaining a new generation, via reproduction, crossover and mutation operations, it uses the same generation as the basis for the next generation, i.e. it begins to run the procedure again. Af- ter many repetitions to create an improved generation (e.g. one thousand repetitions), the algorithm finds the best string obtained in the last generation. This string is declared the best string found. Representation of an individual, genetics operators An individual in our task is a selected subset of logistics centres, or depots (parameter k), of the total number of n nodes. One of the possible representations of the individual that presents itself is the natural display of a subset of depots, i.e. a field of integral numbers containing k elements; the numbers in the field move in the range 1 n. Given the aspect of the nature of the task, the form of the mutation operator results quite clearly – one node in the subset of depots is randomly selected and replaced by a randomly se- lected node not present in the subset. From the viewpoint of implementing the mutation (as well as crossover) algorithm, it is more advantageous to select a representation that is commonly used for the implementation of the set in pro- gramming languages. This is the display of the characteristic function of the set. For the total number of n nodes, the indi- vidual is represented by a bit field containing n elements. If node i belongs to the selected subset of depots, the element (bit) in field i has the value 1, else 0. In the field, each indi- vidual will contain k ones. Fig. 1 gives an example. In total we 32 © Czech Technical University Publishing House http://ctn.cvut.cz/ap/ Acta Polytechnica Vol. 50 No. 1/2010 1 1 110 000 65432 71 8 representation of a subset of depots ( )v1, v4, v5, v8 Fig. 1: Representation of an individual 1 0 0 1 1 0 0 1 1 2 3 4 5 6 7 8 (v1,v4,v5,v8) i=3 j=8 1 0 1 1 1 0 0 0 1 2 3 4 5 6 7 8 (v1,v3,v4,v5) 1 0 0 1 1 0 0 1 1 2 3 4 5 6 7 8 (v1,v4,v5,v8) i=1 j=4 � j=6 0 0 0 1 1 1 0 1 1 2 3 4 5 6 7 8 (v4,v5,v6,v8) Fig. 2: Principle of the mutation operation have n 8 nodes, designated as v1 to v8. Let k 4. The sub- set of depots (v1, v4, v5, v8) will be represented as shown in Fig. 1. The mutation operation was described briefly in the previ- ous paragraph. From the subset, a node is selected randomly and is replaced by a node not present in the subset. The latter node is likewise selected on a random basis. In practice, mu- tation is realized in the following way (Fig. 2): index i is randomly generated (naturally with a uniform distribution) into a field. This determines the allele (the position of the gene) that is to be changed. If the i gene (bit) is true (the node is in a subset), it is zeroed (the node is taken out of the subset), and if the i gene (bit) is zero (the node is not in the subset), it will be set to true (the node is entered in the subset). The second index j is generated in a random manner, and the allele of the second gene is determined. If the j bit has a value opposite to that originally held by the i bit, it will be inverted. The exchange of the two nodes is thus complete (Fig. 2 – left). Where the j bit has a value equal to that held by the i bit, it searches linearly (cyclically) towards the higher indices for a bit having a value opposite to that held by the i bit, and then it is inverted (Fig. 2 – right). Since 1 k n, a bit of this quality is always found. The crossover operation is based on the general principle described above. Principle of the mutation operation it is applied without any alterations, it can produce invalid off- springs, since its result may be a bit vector representing a subset containing a number of elements other than k. The ad- justed form of the crossover is as follows. Again a crossover point is generated in a random manner. The creation of an offspring – a part of the first parent, is copied on the left of the crossover point into the offspring without change. It is then progressively supplemented from the right from the second parent by ones up to the total number of k ones, until the total number of ones corresponds to k, as shown in Fig. 3. Then the ones are supplemented, from the right, from the second par- ent’s to the left of the crossover point. The principle of the crossover operator is demonstrated in Fig. 3. Fitness The quality criterion is the transport work. In contrast to common practice, in calculating the fitness function the better individuals are given a lower score (in usual practice a higher quality individual receives a higher score). The selection algorithms then presume that the probability of the selection of the i individual into the next generation is proportional to its fitness value fi, e.g. p f f i i j j n � 1 . (2) In order to minimize transport work, the DP value was lin- early converted to the fitness value according to the following relation [1]: fitness s DP avg best avg � 1 1( )( ) , (3) where avg is the average value of transport work in a gene- ration and best is the best value of transport work in a genera- tion. The parameter s (usually in the scope of 1, 2-2) controls the selection pressure. In order that individuals having a transport work value below the average do not have a nega- tive fitness value, s is alternatively selected, as per [1]: s best avg best worst � 1 . (4) In this case the worst individuals have a zero fitness value for s. Above the fitness values the selection is arranged by the roulette wheel method. In fitness transformed in this manner, the worst individuals in no case progress into the next generation, which may sometimes be a disadvantage (a bad individual may become good by mutation). 3 Conclusion Allocation tasks need to be assessed and evaluated taking into account a considerable number of criteria, i.e. they are problems of a multiple criteria nature. In determining the optimal number of logistics centres it is necessary to take into account the required technical parameters of the centers, fi- nancial and cost considerations, etc. It is necessary to make an economic analysis based on the particular task assign- ment. Allocation tasks are, by their nature, highly individual. We have therefore merely outlined the theoretical side of using multiple criteria decision making and the solution methodology. Location tasks serve for distributing of logistics centers in networks. Tasks of this type belong to the group of discrete optimization tasks. They may be solved by means of exact or heuristic methods. Since these tasks offer an unmanage- able number of candidate solutions, calculation using exact methods is abandoned and preference is given to compiling suitable heuristic methods, such as the application of genetic algorithms. Such a heuristic has the huge advantage that the individual steps in the algorithm do not depend on a crite- rion, i.e. the algorithm still works in the event of a change to the criterion. In essence, the criterion of quality is the greatest, but not the sole problem in location tasks. This application was tested on a sample of approximately 2000 examples, the quality of the solution was assessed by comparing it with the results from an exact method, and the deviations of this heuristic are minimal, around 0.5 % of the total number of examples, whereby the deviation – the fitness function value – is always the second best solution from the optimum. © Czech Technical University Publishing House http://ctn.cvut.cz/ap/ 33 Acta Polytechnica Vol. 50 No. 1/2010 1 1 110 000 65432 71 8 1 1 110 000 65432 71 8 0 0 101 011 10 R1: R2: 1 0 100 011 10P: crossover point problematic gene (v1, v4, v5, v7) (v2, v3, v6, v8) (v1, v3, v6, v8) Fig. 3: Principle of the crossover operation (R1, R2 – Parent, P – Offspring) 4 References [1] Mařík, V., Štěpánková, O., et al.: Artificial Intelligence (3, 4), Prague: Academia, 2001, 2003. [2] Mocková, D.: Solution of Allocation-Location Tasks, thesis, Prague: CTU – Faculty of Transportation Science, 2005. [3] Volek, J.: Operational Research I. Pardubice, 2002. Ing. Denisa Mocková, Ph.D. phone: +420 224 359 160 fax: +420 224 919 017 e-mail: mockova@fd.cvut.cz Czech Technical University in Prague Faculty of Transportation Sciences Horská 3 128 03 Prague 2, Czech Republic 34 © Czech Technical University Publishing House http://ctn.cvut.cz/ap/ Acta Polytechnica Vol. 50 No. 1/2010