Capacitated Fixed Cost Facility Location Problem with Transportation Choices


Abstract

In this work a Supply Chain Design problem is addressed. The problem is based on a two-echelon distribution system for a single product. In the system, plants ship the product to distribution centers, and these dispatch the product to the customers. One of the decisions in the problem is to locate the distribution centers among a set of potential sites. There are optional arcs between each pair of facilities in each echelon that represent different transportation channels defined by cost and time parameters. These transportation channels can be seen as transportation modes (rail, truck, airplane, etc.), transportation services from the same company (regular, express, overnight, etc.) or services offered by different companies. At difference of similar models for the same type of problem the transportation channel selection introduces a tradeoff between cost and time. The cause of this tradeoff is that a faster delivery service is usually more expensive. The general problem named “Capacitated Fixed Cost Facility Location Problem with Transportation Choices” (CFCLP-TC) has two objectives: to minimize the cost and to minimize the transportation time from the plants to the customers. The cost criterion is an aggregated function of fixed and variable costs. The time function represents the maximum time that may take to transport the product along any path from the plants to the customers. The mathematical model decides distribution centers location, transportation channel selection, and transportation flows. The aim in the solution of the problem is to present the set of non-dominated alternatives to the decision maker. Therefore it is treated as a bi-objective mixed-integer program that minimizes the time and cost objectives simultaneously. To solve the CFCLP-TC several versions of one algorithm were developed to implement the ε-constraint method. These versions were compared among them and the best was selected to obtain true efficient sets and bound sets for the instances tested. A limit on the size of “solvable” instances was identified according to the available computational resources. This limit is on instance sizes with 255 binary variables and 940 constraints. Several instances of sizes below this limit were solved with the ε-constraint based algorithm and their true efficient sets were obtained. For instances of larger size a modification to the ε-constraint based algorithm was done to obtain their upper bound sets. Also four lower bounding schemes were studied. These were based on linear relaxations of the mixed-integer program. The relaxation of the set of variables corresponding to the distribution center location resulted in the best lower bound sets. Because of the computational complexity of the CFCLP-TC a metaheuristic algorithm was developed in an attempt to solve it. This algorithm uses some elements from state-of- the-art metaheuristics for single and multiobjective optimization. The parameters of the