Improved genetic algorithm for generalized transportation problem

In this paper, we introduce the genetic algorithm approach to the generalized transportation problem (GTP) and GTP with a fixed charge (fc-GTP). We focus on the use of Prüfer number encoding based on a spanning tree, which is adopted because it is capable of equally and uniquely representing all possible trees. From this point, we also design the criteria by which chromosomes can always be converted to a GTP tree. The genetic crossover and mutation operators are designed to correspond to the genetic representations. With the spanning-tree-based genetic algorithm, less memory space will be used than in the matrix-based genetic algorithm for solving the problem; thereby computing time will also be saved. In order to improve the efficiency of the genetic algorithm, we use the reduced cost for the optimality of a solution and the genetic algorithm to avoid degeneration of the evolutionary process. A comparison of results of numerical experiments between the matrix-based genetic algorithm and the spanning-tree-based genetic algorithm for solving GTP and fc-GTP problems is given. This work was presented, in part, at the Fourth International Symposium on Artificial Life and Robotics, Oita, Japan, January 19–22, 1999     

Nonlinear fixed charge transportation problem by minimum cost flow-based genetic algorithm

Nonlinear Fixed Charge Transportation Problem (NFCTP) is a variant of fixed charge transportation problem, which is to ship available amounts of goods to satisfy the demands at minimal total cost, on condition that any route has a fixed cost irrelative to its shipping amount if it is used, and a variable cost directly proportional to the quadratic of its shipping amount as a nonlinear term. This paper aims at developing an efficient method to solve NFCTP. In this paper, NFCTP is formulated using a mixed integer programming model. Based on steady-state genetic algorithm as framework, and minimum cost flow algorithm as decoder, a hybrid genetic algorithm named NFCTP-HGA is proposed as a solution method of the model. Taking advantage of nonlinear structure and special network structure of NFCTP, the NFCTP-HGA algorithm has good performance in the sense of being implemented on computer, computational time, required memory for computation, and ability to search global optimum. The application of the NFCTP-HGA algorithm is illustrated with examples. Numerical experiments demonstrate that the NFCTP-HGA algorithm is an efficient and robust method to solve NFCTP, especially applicable to large scale problems.     

求解固定费用运输问题的遗传算法

为克服基于边集编码的遗传算法求解固定费用运输问题的不足,对采用先根遍历边构成有序边集编码的生成树,提出了森林补充式多点交叉操作的遗传算法.经证明,对于有m个源节点和n个目的节点的固定费用运输问题,该算法的空间复杂度为O((m n-1)2),时间复杂度为Oβ(m n-1)3),β为最大迭代次数.实验数据表明,随着问题规模和求解难度的增加,该算法与边集编码的遗传算法解的质量都呈下降趋势,但所得解的质量优于边集编码的遗传算法.     

A solid transportation problem for an item with fixed charge, vechicle cost and price discounted varying charge using genetic algorithm

In this paper, discount in transportation cost on the basis of transportated amount is extended to a solid transportation problem. In a transportation model, the available discount is normally offered on items/criteria, etc., in the form AUD (all unit discount) or IQD (incremental quantity discount) or combination of these two. Here transportation model is considered with fixed charges and vechicle costs where AUD, IQD or combination of AUD and IQD on the price depending upon the amount is offered and varies on the choice of origin, destination and conveyance. To solve the problem, genetic algorithm (GA) based on Roulette wheel selection, arithmetic crossover and uniform mutation has been suitably developed and applied. To illustrate the models, numerical examples have been presented. Here, different types of constraints are introduced and the corresponding results are obtained. To have better customer service, the entropy function is considered and it is displayed by a numerical example. To exhibit the efficiency of GA, another method—weighted average method for multi-objective is presented, executed on a multi-objective problem and the results of these two methods are compared.     

A genetic algorithm with the heuristic procedure to solve the multi-line layout problem

The paper presents a genetic algorithm-based meta-heuristic to solve the facility layout problem (FLP) in a manufacturing system, where the material flow pattern of the multi-line layout is considered with the multi-products. The matrix encoding technique has been used for the chromosomes under the objective of minimizing the total material handling cost. The proposed algorithm produces a table with the descending order of the data corresponding to the input values of the flow and cost data. The generated table is used to create a schematic representation of the facilities, which in turn is utilized to heuristically generate the initial population of the chromosomes and to handle the heuristic crossover and mutation operators. The efficiency of the proposed algorithm has been proved through solving the two examples with the total cost less than the other genetic algorithms, CRAFT algorithm, and entropy-based algorithm.     

Fully fuzzy fixed charge multi-item solid transportation problem

This paper presents fully fuzzy fixed charge multi-item solid transportation problems (FFFCMISTPs), in which direct costs, fixed charges, supplies, demands, conveyance capacities and transported quantities (decision variables) are fuzzy in nature. Objective is to minimize the total fuzzy cost under fuzzy decision variables. In this paper, some approaches are proposed to find the fully fuzzy transported amounts for a fuzzy solid transportation problem (FSTP). Proposed approaches are applicable for both balanced and unbalanced FFFCMISTPs. Another fuzzy fixed charge multi-item solid transportation problem (FFCMISTP) in which transported amounts (decision variables) are not fuzzy is also presented and solved by some other techniques. The models are illustrated with numerical examples and nature of the solutions is discussed.     

On solving a multiobjective fixed charge problem with imprecise fractional objectives

The fixed charge problem is a special type of nonlinear programming problem which forms the basis of many industry problems wherein a charge is associated with performing an activity. In real world situations, the information provided by the decision maker regarding the coefficients of the objective functions may not be of a precise nature. This paper aims to describe a solution algorithm for solving such a fixed charge problem having multiple fractional objective functions which are all of a fuzzy nature. The enumerative technique developed not only finds the set of efficient solutions but also a corresponding fuzzy solution, enabling the decision maker to operate in the range obtained. A real life numerical example in the context of the ship routing problem is presented to illustrate the proposed method.     

An improved genetic algorithm with conditional genetic operators and its application to set-covering problem

The genetic algorithm (GA) is a popular, biologically inspired optimization method. However, in the GA there is no rule of thumb to design the GA operators and select GA parameters. Instead, trial-and-error has to be applied. In this paper we present an improved genetic algorithm in which crossover and mutation are performed conditionally instead of probability. Because there are no crossover rate and mutation rate to be selected, the proposed improved GA can be more easily applied to a problem than the conventional genetic algorithms. The proposed improved genetic algorithm is applied to solve the set-covering problem. Experimental studies show that the improved GA produces better results over the conventional one and other methods.     

A branch-and-price approach for a multi-period vehicle routing problem

In this paper, we consider tactical planning for a class of multi-period vehicle routing problems (MPVRP). This problem involves optimizing daily product collections from several production locations over a given planning horizon. In this context, a single routing plan for the whole horizon must be prepared, and the seasonal variations in the producers’ supplies must be taken into account. Production variations over the horizon are approximated using a sequence of periods, each corresponding to a production season, while the intra-period variations are neglected. We propose a mathematical model that is based on the two-stage a priori optimization paradigm. The first stage corresponds to the design of a plan which, in the second stage, takes the different periods into account. The proposed set partitioning-based formulation is solved using a branch-and-price approach. The subproblem is a multi-period elementary shortest path problem with resource constraints (MPESPPRC), for which we propose an adaptation of the dynamic-programming-based label-correcting algorithm. Computational results show that this approach is able to solve instances with up to 60 producers and five periods.     

A hybrid genetic algorithm based heuristic for an integrated supply chain problem

Supply chain management is becoming an essential component of efficient decision-making for companies, as they are increasingly implementing optimization strategies in order to improve their business performance. In this paper we develop a capacitated multi-echelon joint location-inventory model, according to which a single product is distributed from a manufacturer to retailers through a set of warehouses, the locations of which are to be determined by the model. Each retailer is assigned exactly one warehouse, while each warehouse can serve multiple retailers. The model decides where to locate warehouses, assigns retailers to the warehouses and decides the times between orders at the warehouses and the retailers, so as to minimize the cost of operating the supply chain. Notably, the model considers capacity constraints for each warehouse, ensuring that the reorder quantity is below the capacity limit. We develop a genetic algorithm (GA) based heuristic to solve the problem and the GA is validated on small size problems by comparing its solution to the optimal solution obtained by the General Algebraic Modeling System (GAMS). We focus our attention on specifically customizing the GA and thus an experimental analysis is carried out to find the optimal parameter setting for the GA as well as to obtain insights on the effect of the various GA parameters. Finally, a sensitivity analysis is conducted to show the effect of the capacity constraints.     

An improved model for vehicle routing problem with time constraint based on genetic algorithm

A vehicle routing problem (VRP) with time constraint is one of the important problems in distribution and transportation. Thus the generic VRP and its practical extensions are discussed in great detail in the literatures. In the VRP, the service of a customer must start and finish within a given time interval. The objective of this problem is to minimize the cost of servicing the set of customers without being tardy or exceeding the capacity or travel time of the vehicles. In this research we concentrated on developing a GA–TSP model by improving the genetic algorithm (GA) operators and the initial population. For the computational purpose, we developed a GUI (graphic user interface)-type computer program according to the proposed method. The computational results show that the proposed method is very effective on a set of standard test problems and it can be potentially useful in solving the VRPs.     

A genetic algorithm for solving economic lot size scheduling problem

The purpose of this research is to determine an optimal batch size for a product and purchasing policy of associated raw materials. Like most other practical situation, this manufacturing firm has a limited storage space and transportation fleet of known capacity. The mathematical formulation of the problem indicates that the model is a constrained nonlinear integer program. Considering the complexity of solving such model, we investigate the use of genetic algorithms (GAs) for solving this model. We develop GA code with three different penalty functions usually used for constraint optimizations. The model is also solved using an existing commercial optimization package to compare the solution. The detailed computational results are presented.     

A heuristic block-loading algorithm based on multi-layer search for the container loading problem

This paper presents an efficient heuristic block-loading algorithm based on multi-layer search for the three-dimensional container loading problem. First, a basic heuristic block-loading algorithm is introduced. This algorithm loads one block, determined by a block selecting algorithm, in one packing phase, according to a fixed strategy, until no blocks are available. Second, the concept of composite block is introduced, the difference between traditional block and composite block being that composite block can contain multiple types of boxes in one block under some restrictions. Third, based on the depth-first search algorithm, a multi-layer search algorithm is developed for determining the selected block in each packing phase, and making this result closer to the optimal solution. Computational results on a classic data set show that the proposed algorithm outperforms the best known algorithm in almost all the test data.     

Commentary on “On solving a multiobjective fixed charge problem with imprecise fractional objectives”

Upmanyu and Saxena (Applied Soft Computing 40 (2016) 64–69) proposed a method for solving a multiobjective fixed charge problem having multiple fractional objective functions which are all of a fuzzy nature. The aim of this note is to aware the researchers that the method, proposed by Upmanyu and Saxena, is not valid and hence, to propose a method for solving this type of fixed charge problem is still an open challenging research problem.     

A genetic algorithm for a bi-objective capacitated arc routing problem

The capacitated arc routing problem (CARP) is a very hard vehicle routing problem for which the objective—in its classical form—is the minimization of the total cost of the routes. In addition, one can seek to minimize also the cost of the longest trip.In this paper, a multi-objective genetic algorithm is presented for this more realistic CARP. Inspired by the second version of the Non-dominated sorted genetic algorithm framework, the procedure is improved by using good constructive heuristics to seed the initial population and by including a local search procedure. The new framework and its different flavour is appraised on three sets of classical CARP instances comprising 81 files.Yet designed for a bi-objective problem, the best versions are competitive with state-of-the-art metaheuristics for the single objective CARP, both in terms of solution quality and computational efficiency: indeed, they retrieve a majority of proven optima and improve two best-known solutions.     

MOTGA: A multiobjective Tchebycheff based genetic algorithm for the multidimensional knapsack problem

This paper presents a new multiobjective genetic algorithm based on the Tchebycheff scalarizing function, which aims to generate a good approximation of the nondominated solution set of the multiobjective problem. The algorithm performs several stages, each one intended for searching potentially nondominated solutions in a different part of the Pareto front. Pre-defined weight vectors act as pivots to define the weighted-Tchebycheff scalarizing functions used in each stage. Therefore, each stage focuses the search on a specific region, leading to an iterative approximation of the entire nondominated set.     

A genetic algorithm approach to solving the anti-covering location problem

Abstract: In this paper we address the problem of locating a maximum weighted number of facilities such that no two are within a specified distance from each other. A natural process of evolution approach, more specifically a genetic algorithm, is proposed to solve this problem. It is shown that through the use of a commercially available spreadsheet-based genetic algorithm software package, the decision-maker with a fundamental knowledge of spreadsheets can easily set up and solve this optimization problem. Also, we report on our extensive computational experience using three different data sets.     

多约束选址—路径问题的改进混合遗传算法研究

选址—路径问题(LRP)同时解决设施选址和车辆路径问题,使物流系统总成本达到最小,在集成化物流配送网络规划中具有重要意义。针对带仓库容量约束和路径容量约束的选址—路径(CLRP)问题,提出了一种结合模拟退火算法的混合遗传算法进行整体求解。改进混合遗传算法分别对初始种群生成方式、遗传操作和重组策略进行改进,并实现了模拟退火的良好局部搜索能力与遗传算法的全局搜索能力的有效结合。运用一组Barreto Benchmark算例进行数值实验测试其性能,并将求解结果与国外文献中的启发式算法进行比较,验证了改进混合算法的有效性和可行性。     

A heuristic genetic algorithm for product portfolio planning

Product portfolio planning has been recognized as a critical decision facing all companies across industries. It aims at the selection of a near-optimal mix of products and attribute levels to offer in the target market. It constitutes a combinatorial optimization problem that is deemed to be NP-hard in nature. Conventional enumeration-based optimization techniques become inhibitive given that the number of possible combinations may be enormous. Genetic algorithms have been proven to excel in solving combinatorial optimization problems. This paper develops a heuristic genetic algorithm for solving the product portfolio planning problem more effectively. A generic encoding scheme is introduced to synchronize product portfolio generation and selection coherently. The fitness function is established based on a shared surplus measure leveraging both the customer and engineering concerns. An unbalanced index is proposed to model the elitism of product portfolio solutions.     

Floorplan design problem using improved genetic algorithm

Genetic algorithms (GA) are applicable to many kinds of difficult problems. When a population keeps enough diversity and similarity, GA can obtain good solutions quickly. However, because these often compete with each other, it is difficult to fulfill both of these conditions simultaneously. In this article, taking these into consideration, we propose a new GA for the floorplan design problem, and aimed at improving the efficiency of calculation, the maintenance of the solution’s population diversity, and reduction of the number of parameters. We applied it to two MCNC (originally established as the Microelectronics Center of North Carolina) benchmark problems. The experimental results showed that the proposed method performed better than the existing methods. This work was presented, in part, at the 8th International Symposium on Artificial Life and Robotics, Oita, Japan, January 24#x2013;26, 2003