# Goal Programming for Supply Chain Optimization with Insufficient Capacity

Mohan Chiriki, Yooneun Lee, Vittaldas V. Prabhu

► To cite this version:

Mohan Chiriki, Yooneun Lee, Vittaldas V. Prabhu. Goal Programming for Supply Chain Optimization with Insufficient Capacity. IFIP International Conference on Advances in Production Management Systems (APMS), Sep 2017, Hamburg, Germany. pp.73-80, 10.1007/978-3-319-66926-7_9. hal-01707282

HAL Id: hal-01707282

https://inria.hal.science/hal-01707282v1

Submitted on 12 Feb 2018

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# Goal Programming for Supply Chain Optimization with Insufficient Capacity

Mohan Chiriki [0000-0001-9412-5135], Yooneun Lee [0000-0003-2515-6311] and Vittaldas V. Prabhu [0000-0002-8068-6318]

The Pennsylvania State University, University Park PA 16802, USA
mbc5423@psu.edu, yx15250@psu.edu, vxp7@engr.psu.edu

**Abstract.**

This article presents three different approaches to modeling and solving the classic transportation-location problem including the traditional cost-minimization mixed integer linear program. It is shown that modeling these problems as a profit maximization mixed integer program instead allows for the relaxation of a set of constraints. An alternative multi-objective optimization model using goal programming is also presented. A representative model of the fluid milk supply chain in the U.S. is developed to demonstrate the scenarios and solutions achieved by the three different models to conclude that the multi-objective model is a robust approach to solve these optimization problems even when there is only a single explicit objective.

**Keywords:** Goal programming, multi-criteria optimization, relaxed constraints.

## 1 Introduction

A standard transportation-location problem is defined as shipping goods from origins with fixed capacities to destinations with defined demand requirement. The objective is to select source nodes to open and distribute the goods to destinations subject to capacity and demand constraints minimizing the total cost [1]. Key assumptions are that there is only one kind of good being shipped from the origins to the destinations and that the unit transportation cost does not depend on the volume shipped.

These problems are traditionally modeled as an overall cost minimization mixed integer linear program. However, this approach fails to return a feasible solution when the assumption that “capacity equals or exceeds demand” is not met, which is a fairly common scenario in real life scenarios. One alternative approach is to model the problem as a maximize profit instead of minimize cost, thereby eliminating the necessity to define “capacity equals or exceeds demand” as a hard constraint. Although this mitigates the limitation of the cost minimization model, it does not provide the flexibility to the decision maker to define a minimum requirement at some or all of the demand points. This condition can be incorporated by defining a “*supply greater than or equal demand multiplied by fill rate*” constraint, where fill rate is specified by the decision
maker. The profit maximization model fails to return a feasible solution when there is not enough capacity in the system to fulfil this constraint across all the demand points.

We are interested in modeling this problem in such a way that a best possible solution is returned when there is not enough capacity to fulfil the demand, enabling decision makers to make the most of the situation. This way, they can schedule the shipments or inventory as optimized by the model and arrange for back ordering to fulfil the demand in the remaining nodes at a later point of time. To achieve this, the transportation-location problem can be modeled as a multi-objective optimization model with maximizing fill rate at the demand nodes and minimizing overall system cost.

The following sections present a review of the literature of interest and relevant to this work, the mathematical formulation of the different models described above and an illustrative case study of the fluid milk supply chain in U.S. demonstrating the performance of these models.

## 2 Literature Review

Perl and Daskin [2] define and solve a transportation problem simultaneous as a facility location and vehicle routing problem. A mixed-integer programming formulation was developed to minimize the system cost and also a heuristic was presented to solve this large and complex problem which decomposes the original program into three sub problems.

Hillier and Lieberman [3] present algorithms for linear programming with multiple objectives. Goal programming is defined as "an approach to establish a specific numeric goal for each of the objectives, formulate an objective function for each objective, and then seek a solution that minimizes the (weighted) sum of deviations of these objective functions from their respective goals". If the different objectives are of same importance, it is a non-preemptive goal program and if there is a priority order for the objectives, it is a preemptive goal program.

Maas et. al. [4] present a mixed-integer program that captures the operational options that facility managers have to meet demands in excess of capacity for short periods of time. This study empirically demonstrates the operational flexibility available with managers in reality which is not captured in the traditional facility location problems because of the use of hard capacity constraints.

Nicholson et. al [5] present an analysis of localization policies with the case of diary supply chain in the northeastern states of USA. A baseline scenario was defined with the objective is to minimize the cost of the entire system and two scenarios with additional constraints placed on shipments between sources and destinations and then eval-
uated on multiple criteria like food miles, supply chain costs, and greenhouse emissions. Milk demand is stated as being seasonal and two typical months of a year were considered– March (supply exceeds demand) and September (demand exceeds supply).

## 3 Formulation

In this section, we present the mathematical formulation of the three different models discussed. The followings are the model parameters.

* I – Set of source locations

* J – Set of destinations or demand points

* $f_i$ – fixed cost of locating a facility at candidate site $i \in I$

* $k_i$ – capacity of warehouse at site $i \in I$

* $c_{ij}$ – cost of shipping one unit from site $i$ to node $j \in J$

* $d_j$ – demand requirement at each destination $j \in J$

* $h_j$ – fill rate requires at each destination $j \in J$

* $p$ – unit selling price of product

The decision variables common to all three models are the following.

* $x_{ij}$ – volume shipped from warehouse (i) to destination (j)

$$B_i = \begin{cases} 1 & \text{if source location } i \text{ is chosen to open,} \\ 0 & \text{otherwise.} \end{cases}$$

The capacity constraint remains the same for all different models and is defined as

$$\sum_j x_{ij} \le k_i \times B_i, \forall i \in I \quad (1)$$

### 3.1 Cost Minimization Problem (CMP)

The CMP solves for the decision variables $x_{ij}$ and $B_i$ by minimizing the overall cost of the system, formulated in (2) subject to (1) and the demand constraint defined in (3).

$$\text{Min} \sum_i f_i B_i + \sum_i \sum_j x_{ij} c_{ij} \quad (2)$$

$$\sum_i x_{ij} = d_j, \forall j \in J \quad (3)$$

### 3.2 Profit Maximization Problem (PMP)

The PMP solves for the decision variables by maximizing the overall profit of the system, and the objective function is defined in (4).

$$\text{Max} - \sum_i f_i B_i + \sum_i \sum_j x_{ij} (p - c_{ij}) \quad (4)$$

The capacity constraint remains the same as in (1) but the demand constraint (2) is modified as in (5). An additional constraint (6) can be imposed if a minimum fill rate is required at each demand point.
$$ \sum_{i} x_{ij} \leq d_{j}, \forall j \in J, \qquad (5) $$

$$ \sum_{i} x_{ij} \geq h_{j} d_{j}, \forall j \in J \qquad (6) $$

### 3.3 Multi Criteria Problem (MCP)

A new set of decision variables is introduced in this model. Fill rate $h_j$ for each demand point j, defined as the fraction of demand to be supplied at each destination j such that

$$ 0 \leq h_j \leq 1, \forall j \in J \qquad (7) $$

The two objectives of this model are to maximize the fill rate across the system and to minimize the overall cost, which can be mathematically expressed as

$$ \text{Max} \sum_{j} h_{j}, \qquad (8) $$

$$ \text{Min} \sum_{i} f_{i} B_{i} + \sum_{i} \sum_{j} x_{ij} c_{ij} \qquad (9) $$

Subject to (1), (7) and a modified demand constraint defined in (10).

$$ \sum_{i} x_{ij} = h_{j} d_{j}, \forall j \in J \qquad (10) $$

This problem can be modelled to be solved as a linear program introducing auxiliary slack variables U, E and target values for the different objectives.

$$ h_j + U_j^1 - E_j^1 = T_j^1 \forall j \in J, \qquad (11) $$

$$ \sum_{i} f_{i} B_{i} + \sum_{i} \sum_{j} x_{ij} c_{ij} + U^{2} - E^{2} = T^{2}, \qquad (12) $$

$$ U_j^1, E_j^1, U^2, E^2, T_j^1, T^2 \geq 0 \qquad (13) $$

The final objective function for MCP is defined in (14), where M is an arbitrarily large number, and subject to constraints (1), (7), (10), (11), (12), and (13).

$$ \text{Min} M \sum_{j} U_{j} + E \qquad (14) $$

## 4 Illustration and Results

A mathematical model of the fluid milk supply network in the U.S. was developed with the geographic centers of each mainland state excluding Washington D.C. as the candidate locations for the sources. Three scenarios were developed, differing on the system capacity (SC) available to satisfy the overall demand (OD). These scenarios are differentiated by the ratio SC/OD and any minimum fill rate (FR) condition specified ($h_i$ in (6) and $T_j^{-1}$ in (11)) at each destination and are listed in Table 1.

<table><caption>Table 1. Definition of scenarios for benchmarking</caption><thead><tr><td>Scenario</td><td>SC/OD</td><td>FR</td></tr></thead></table>
<table><tr><td>Scenario 1</td><td>1.7</td><td>1</td></tr><tr><td>Scenario 2</td><td>0.75</td><td>1</td></tr><tr><td>Scenario 3</td><td>0.75</td><td>0.8</td></tr></table>

## 4.1 Demand and Supply Data

The warehouse capacities were sized proportionally to the fluid milk produced in that particular state as obtained from USDA [6-8]. The annual milk production data from USDA was scaled to the time horizon to obtain the supply capacity of each warehouse and fixed costs of opening such warehouses have been estimated proportionally.

We model the demand points as the U.S. Zip codes and use a dataset acquired from the marketing company, Nielsen, via the James M. Kilts Center for Marketing at the University of Chicago, Booth School of Business [9] to calibrate our demand. The Nielsen Homescan Consumer Panel dataset contains six years of longitudinal panel data of consumer products. The data files were consolidated and segregated so as to obtain parameters in accordance with the purpose of our analysis. This extracted data was combined with the population distribution in zip code tabulation areas from the U.S. Census Bureau [9] to calibrate the demand in two different time periods of the year, when demand exceeds supply and when there is sufficient capacity to meet demand.

Longitudinal and latitudinal parameters were attributed to the zip codes to compute the distance matrix for the network using the formula presented in (15), where lat1, lat2, lon1 and lon2 are the latitudes and longitudes of the two points respectively and R ~ 3,963 miles [11] is the equatorial radius of the Earth returning distance between two zip codes as flown by a crow in miles [12]. It is assumed that all shipments are done in regular sized, fully loaded refrigerated trucks for which an average rate/mile is computed, taking into account fuel charges and refrigeration costs. Using a conversion factor, the distance in miles and capacity of each truck, the shipping rate per each unit can be computed using simple arithmetic [13, 14].

$$ \cos^{-1}[\sin(lat1) \sin(lat2) + \cos(lat1) \cos(lat2) \cos(lon2 - lon1)] * R \quad (15) $$

## 4.2 Benchmarking Results

All three models of a simplified version of the problem were formulated and solved in two software packages – Lindo Systems’ LINGO [15] and IBM’s ILOG CPLEX [16] on a Windows 10 machine with Intel Core i7-2670QM CPU @ 2.20 GHz and 8 GB of memory. This version considers only the transportation part of the original problem with all the source locations open, thereby making it a pure linear program and reducing the solving times. Both the software packages returned identical solutions in all three scenarios as can be seen in Table 2 and their performance is benchmarked for solving time in Fig. 1. CPLEX, being considerably faster was chosen to solve the complete MILP under different scenarios.
<table><caption>**Table 2.** Results achieved by the three models under different scenarios</caption><thead><tr><th>Scenario</th><th>Model</th><th>Result</th></tr></thead><tbody><tr><td rowspan="3">Scenario 1</td><td>CMP</td><td>Global Optimal</td></tr><tr><td>PMP</td><td>Global Optimal</td></tr><tr><td>MCP</td><td>Global Optimal</td></tr><tr><td rowspan="3">Scenario 2</td><td>CMP</td><td>Infeasible</td></tr><tr><td>PMP</td><td>Best Feasible</td></tr><tr><td>MCP</td><td>Best Feasible</td></tr><tr><td rowspan="3">Scenario 3</td><td>CMP</td><td>Infeasible</td></tr><tr><td>PMP</td><td>Infeasible</td></tr><tr><td>MCP</td><td>Best Feasible</td></tr></tbody></table>

<figure><img src="image_2.png" /><figcaption>**Fig. 1.** Solving times in seconds for Lingo and CPLEX under different scenarios</figcaption></figure>

All three models return a global optimal solution in Scenario 1 as expected. The PMP yields the same solution as CMP even with (2) modified to (4) because each additional unit of demand supplied contributes to an increase in profits and hence, the model has an inherent incentive to satisfy as much of the demand as possible. This property enables the PMP to return a best feasible solution in Scenario 2 when the overall demand is greater than the system capacity while CMP reaches infeasibility. Best feasible can described as satisfying the most profitable portion of the demand, given the system capacity. As for the MCP, first the fill rates for the demand nodes are decided depending on the system capacity and then, the shipping schedules are optimized for minimal cost. In Scenario 1, all nodes are given a fill rate 1 and in Scenario 2, the nodes with least cost to fulfill demand were allotted a fill rate 1. This adds up to the least expensive demand to fulfill within the system capacity. The solutions returned by PMP and MCP
in Scenario 2 are identical and termed best feasible because all the constraints have not been satisfied completely, but have been satisfied to the best capabilities of the system.

In Scenario 3, we simulate a situation where the decision makers want to maintain a minimum fill rate $h_i$ at each of the demand nodes, which is done by introducing (6) with $h_i = 0.8$ into the PMP and changing the $T_j^1$ to 0.8 in the MCP. The PMP reaches infeasibility because constraint set (6) cannot be satisfied at all the nodes. The number of nodes supplied by the MCP is more in Scenario 3 than Scenario 2 as the overall capacity is the same but each node is now being filled up to 80% only.

Identical results were returned when the complete MILP problem was run on CPLEX, but with longer solving times than the pure LP problem. These times can be seen in Fig. 2 and there is an increase in solving times of CMP and PMP to MCP as expected, because of the introduction of a new set of decision variables.

<figure><img src="image_3.png" /><figcaption>Fig. 2. Solving times in seconds in CPLEX for complete MILP</figcaption></figure>

# 5 Conclusions

Modeling the classic transportation-facility problem as a multi-objective optimization problem with maximizing fill rate at demand points and minimizing overall system cost proved to be a versatile and flexible approach. The model achieved the objective of returning the best feasible solution to decision makers as can be seen in the results of the illustrative example. While the PMP performed better than the CMP in solving the MILP problem, it could not offer the level of constraint flexibility the MCP could.

The problem size in MCP is larger due to introduction of new variables - one heuristic could be to check for the system feasibility and then choose between the PMP or MCP models to find the shipping schedules. As the demand and transportation matrices are sparse matrices, with numerous 0 entries, the solving times can be reduced by using
heuristic algorithms to traverse through these matrices. Further studies could be con-
ducted on the effect of the target values defined in MCP on the solution quality, defining
the second objective in MCP as a profit maximization, and the solutions differ when
the priorities of the two objectives are switched.

References

1. Dantzig, George B. Linear Programming and Extensions. Princeton, New Jersey, Princeton University Press, 1991, www.jstor.org/stable/j.ctt1cx3tvg.

1. Perl and Daskin, "A Warehouse Location-Routing Problem", Transportation Research Vol 19B, 1985, 381-396

2. Hillier, Frederick S., and Gerald J. Lieberman. Introduction to Operations Research. San Francisco: Holden-Day, 1967.

3. Maas, Daskin and Shen, "Mitigating Hard Capacity Constraints with Inventory in Facility Location Modeling", IIE Transactions, 2015, DOI:10.1080/0740817X.2015.1078015

4. Nicholson, He, Gomez, Gao and Hill, "Environmental and Economic Impacts of Localizing Food Systems: The Case of Dairy Supply Chain in the Northeastern United States", Environmental Science and Technology, 12005-12014, (2015)

5. National Agricultural Statistics Service. Dairy Products 2015 Annual Summary, U.S. Department of Agriculture: Washington D.C, 2016

6. National Agricultural Statistics Service. "Milk Production", November 2015

7. National Agricultural Statistics Service, "Capacity of Refrigerated Warehouses 2015 Summary", January 2016

8. "Calculated (or Derived) based on data from The Nielsen Company (US), LLC and marketing databases provided by the Kilts Center for Marketing Data Center at The University of Chicago Booth School of Business."

9. U.S. Census Bureau; American Community Survey, 2010 Population by ZTCA; using American FactFinder.

10. National Aeronautics and Space Administration, Earth Fact Sheet, https://nssdc.gsfc.nasa.gov/planetary/factsheet/earthfact.html.

11. Weisstein, Eric W. "Great Circle." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/GreatCircle.html

12. Beilock and Shonkwiler, "Modeling Weekly Truck Rates for Perishables", Southern Journal of Agricultural Economics, 83-88, July 1983.

13. Agricultural Marketing Service, "Truck Rate Report", Volume XXXVIII – Number 32, August 2016.

14. "LINGO – The Modeling Language and Optimizer", Lindo Systems, acquired from http://www.lindo.com/downloads/PDF/LINGO.pdf

15. "CPLEX User's Manual", IBM ILOG CPLEX Optimization Studio, acquired from https://www.ibm.com/support/knowledge-center/SSSA5P_12.7.0/ilog.odms.studio.help/pdf/usrcplex.pdf