A genetic algorithm for solving the fixed-charge transportation model: Two-stage problem

Transportation of goods in a supply chain from plants to customers through distribution centers (DCs) is modeled as a two-stage distribution problem in the literature. In this paper we propose genetic algorithms to solve a two-stage transportation problem with two different scenarios. The first scenario considers the per-unit transportation cost and the fixed cost associated with a route, coupled with unlimited capacity at every DC. The second scenario considers the opening cost of a distribution center, per-unit transportation cost from a given plant to a given DC and the per-unit transportation cost from the DC to a customer. Subsequently, an attempt is made to represent the two-stage fixed-charge transportation problem (Scenario-1) as a single-stage fixed-charge transportation problem and solve the resulting problem using our genetic algorithm. Many benchmark problem instances are solved using the proposed genetic algorithms and performances of these algorithms are compared with the respective best existing algorithms for the two scenarios. The results from computational experiments show that the proposed algorithms yield better solutions than the respective best existing algorithms for the two scenarios under consideration.     

Addressing a nonlinear fixed-charge transportation problem using a spanning tree-based genetic algorithm

In this paper, we consider the fixed-charge transportation problem (FCTP) in which a fixed cost, sometimes called a setup cost, is incurred if another related variable assumes a nonzero value. To tackle such an NP-hard problem, there are several genetic algorithms based on spanning tree and Prüfer number representation. Contrary to the findings in previous works, considering the genetic algorithm (GA) based on spanning tree, we present a pioneer method to design a chromosome that does not need a repairing procedure for feasibility, i.e. all the produced chromosomes are feasible. Also, we correct the procedure provided in previous works, which designs transportation tree with feasible chromosomes. We show the previous procedure does not produce any transportation tree in some situations. Besides, some new crossover and mutation operators are developed and used in this work. Due to the significant role of crossover and mutation operators on the algorithm’s quality, the operators and parameters need to be accurately calibrated to ensure the best performance. For this purpose, various problem sizes are generated at random and then a robust calibration is applied to the parameters using the Taguchi method. In addition, two problems with different sizes are solved to evaluate the performance of the presented algorithm and to compare that performance with LINGO and also with the solution presented in previous work.     

Algorithms for the boundary selection problem

User-oriented clustering schemes enable the classification of documents based upon the user's perception of the similarity between documents, rather than on some similarity function presumed by the designer to represent the user's criteria. In an earlier paper it was shown that such a classification scheme can be developed in two stages. The first stage involves the accumulation of relevance judgements provided by users,vis-à-vis past query instances, into a suitable structure. The second stage consists of cluster identification. When the structure chosen, in the first stage, for the accumulation of corelevance characteristics of documents is a straight line, the second stage can be formulated as a function optimization problem termed the Boundary Selection Problem (BSP). A branch-and-bound algorithm with a good bounding function is developed for the BSP. Although significant pruning is achieved due to the bounding function, the complexity is still high for a problem of a large size. For such a problem a heuristic that divides it into a number of subproblems, each being solved by a branch-and-bound approach, is developed. Then the overall problem is mapped to an integer knapsack problem and solved by the use of dynamic programming. The tradeoff between accuracy and complexity can be controlled, giving the user a preference of one over the other. Assuming that the heuristic which divides the overall problem introduces no errors and is given sufficient time, the branch and bound with dynamic programming (BBDP) approach will converge to the optimal solution. Two other heuristic approaches, one with the application of a polynomial dynamic programming algorithm and the other which works in a greedy way, are also proposed for the BSP and an experimental comparison of all these approaches is provided. Experimental results indicate that all proposed algorithms show better performance compared with the existing algorithm.     

A genetic algorithm-based approach for solving the resource-sharing and scheduling problem

We introduce a heuristic that is based on a unique genetic algorithm (GA) to solve the resource-sharing and scheduling problem (RSSP). This problem was previously formulated as a continuous-time mixed integer linear programming model and was solved optimally using a branch-and-bound (B&B) algorithm. The RSSP considers the use of a set of resources for the production of several products. Producing each product requires a set of operations with precedence relationships among them. Each operation can be performed using alternative modes which define the subset of the resources needed, and an operation may share different resources simultaneously. The problem is to select a single mode for each operation and accordingly to schedule the resources, while minimizing the makespan time. The GA we propose is based on a new encoding schema that adopts the structure of a DNA in nature. In our experiments we compared the effectiveness and runtime of our GA versus a B&B algorithm and two truncated B&B algorithms that we developed on a set of 118 problem instances. The results demonstrate that the GA solved all the problems (10 runs each), and reaches optimality in 75% of the runs, had an average deviation of less than 1% from the optimal makespan, and a runtime that was much less sensitive to the size of the problem instance.     

Some consequences on the planar three-index transportation problem

In this study, some algebraic characterizations of the coefficient matrix A of the planar three-index transportation problem are derived and the equivalent formulation of this problem is obtained using the Kronecker product. It is shown that eigenvectors of the matrix G ⁺ G are characterized in terms of eigenvectors of the matrix A ⁺ A , where G ⁺ is the Moore–Penrose inverse of the coefficient matrix G of the equivalent problem.     

Cross-facility management of production and transportation planning problem

This paper studies an integrated production and transportation planning problem in a two-stage supply chain. This supply chain consists of a number of facilities, each capable of producing the final product, and a number of retailers. We assume that retailers’ demands are known deterministically and there are no production or transportation capacity constraints. We formulate the problem as a network flow problem with fixed charge costs. This is an NP  -hard problem. To solve the problem we propose a primal-dual based heuristic that generates upper and lower bounds and runs in O(FRT²)$O({\mathit{FRT}}^2)$. The quality of the upper and lower bounds is tested on a large set of randomly generated problems. The maximum error reported for these problems is 4.36% and the maximum running time is 7.65 cpu seconds.     

Improved genetic algorithm for solving multiobjective solid transportation problem with fuzzy numbers

In this paper, we present improved genetic algorithm for solving the fuzzy multiobjective solid transportation problem in which the coefficients of objective function are represented as fuzzy numbers. The ranking fuzzy numbers with integral value are used in the evaluation and selection. The proposed algorithm is incorporated with problem-specific knowledge and conductive to find out the set of nondominated points in the criteria space based on decision maker degree of optimism.     

A fuzzy bi-criteria transportation problem

In this paper, a fuzzy bi-criteria transportation problem is studied. Here, the model concentrates on two criteria: total delivery time and total profit of transportation. The delivery times on links are fuzzy intervals with increasing linear membership functions, whereas the total delivery time on the network is a fuzzy interval with a decreasing linear membership function. On the other hand, the transporting profits on links are fuzzy intervals with decreasing linear membership functions and the total profit of transportation is a fuzzy number with an increasing linear membership function. Supplies and demands are deterministic numbers. A nonlinear programming model considers the problem using the max–min criterion suggested by Bellman and Zadeh. We show that the problem can be simplified into two bi-level programming problems, which are solved very conveniently. A proposed efficient algorithm based on parametric linear programming solves the bi-level problems. To explain the algorithm two illustrative examples are provided, systematically.     

动态搜索算法求解时间依赖型旅行商问题研究

时间依赖型旅行商问题(TDTSP)是旅行商问题(TSP)的延伸.在该问题中,任意两节点间的旅行时间(成本)不仅取决于节点间的距离,还依赖于一天中具体时段或节点在哈密顿圈中所处的具体位置.对基于节点所处哈密顿圈中具体位置的TDTSP问题建立相应的数学模型,并提出求解该问题的动态搜索算法.通过实验仿真,验证了动态搜索算法优于目前在邻域搜索领域求解该问题最有效的动态规划启发式算法.     

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     

Branch-and-bound algorithm for a competitive facility location problem

We study a mathematical model generalizing the well-known facility location problem. In this model we consider two competing sides successively placing their facilities and aiming to “capture” consumers, in order to make maximal profit. We state the problem as a bilevel integer programming problem, regarding optimal noncooperative solutions as optimal solutions. We propose a branch-and-bound algorithm for finding the optimal noncooperative solution. While constructing the algorithm, we represent our problem as the problem of maximizing a pseudo-Boolean function. An important ingredient of the algorithm is a method for calculating an upper bound for the values of the pseudo-Boolean function on subsets of solutions. We present the results of a simulation demonstrating the computational capabilities of the proposed algorithm.     

Improved core problem based heuristics for the 0/1 multi-dimensional knapsack problem

We consider the 0/1 multi-dimensional knapsack problem and discuss the performances of a new heuristic procedure particularly suitable for a parallel computing environment embedding core problem approaches and a branching scheme based on reduced costs of the corresponding LP relaxation solution value. The proposed approach compared favorably to the recent state of the art procedures available in the literature on the well known OR-Library multi-dimensional knapsack problem benchmarks instances.     

A dynamic programming method with lists for the knapsack sharing problem

In this paper, we propose a method to solve exactly the knapsack sharing problem (KSP) by using dynamic programming. The original problem (KSP) is decomposed into a set of knapsack problems. Our method is tested on correlated and uncorrelated instances from the literature. Computational results show that our method is able to find an optimal solution of large instances within reasonable computing time and low memory occupancy.     

On single-walk parallelization of the job shop problem solving algorithms

New parallel objective function determination methods for the job shop scheduling problem are proposed in this paper, considering makespan and the sum of jobs execution times criteria, however, the methods proposed can be applied also to another popular objective functions such as jobs tardiness or flow time. Parallel Random Access Machine (PRAM) model is applied for the theoretical analysis of algorithm efficiency. The methods need a fine-grained parallelization, therefore the approach proposed is especially devoted to parallel computing systems with fast shared memory (e.g. GPGPU, General-Purpose computing on Graphics Processing Units).     

Exact solution of the robust knapsack problem

We consider an uncertain variant of the knapsack problem in which the weight of the items is not exactly known in advance, but belongs to a given interval, and an upper bound is imposed on the number of items whose weight differs from the expected one. For this problem, we provide a dynamic programming algorithm and present techniques aimed at reducing its space and time complexities. Finally, we computationally compare the performances of the proposed algorithm with those of different exact algorithms presented so far in the literature for robust optimization problems.     

A decomposition approach for the solution of the unit loading problem in hydroplants

This paper presents a decomposition approach for the solution of the dynamic programming formulation of the unit loading problem in hydroplant management. This decomposition approach allows the consideration of network and canal constraints without additional computational effort.     

An enumeration algorithm for solving the fleet management problem in underground mines

This paper presents an enumeration algorithm based on dynamic programming for optimally solving the fleet management problem in underground mines. This problem consists of routing and scheduling bidirectional vehicles on a haulage network composed of one-lane bidirectional road segments. The method takes into account the displacement modes of the vehicles, either forward or in reverse, and makes sure that these vehicles move forward when they arrive at their service point. The method has been developed for the underground mine context, but it can be extended to the industrial environment.     

Decremental state space relaxation strategies and initialization heuristics for solving the Orienteering Problem with Time Windows with dynamic programming

We present an exact optimization algorithm for the Orienteering Problem with Time Windows (OPTW). The algorithm is based on bi-directional and bounded dynamic programming with decremental state space relaxation. We compare different strategies proposed in the literature to guide decremental state space relaxation: our experiments on instances derived from the literature show that there is no dominance between these strategies. We also propose a new heuristic technique to initialize the critical vertex set and we provide experimental evidence of its effectiveness.     

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

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