Determining nodal capacities for military distribution problems

Abstract

Purpose

This paper aims to introduce a new mixed integer programming formulation and associated heuristic algorithm to solve the Military Nodal Capacity Problem, which is a type of supply chain network design problem that involves determining the amount of capacity expansion required at theater nodes to ensure the on-time delivery of military cargo.

Design/methodology/approach

Supply chain network design, mixed integer programs, heuristics and regression are used in this paper.

Findings

This work helps analysts at the United States Transportation Command identify what levels of throughput capacities, such as daily processing rates of trucks and railcars, are needed at theater distribution nodes to meet warfighter cargo delivery requirements.

Research limitations/implications

This research assumes all problem data are deterministic, and so it does not capture the variations in cargo requirements, transit times or asset payloads.

Practical implications

This work gives military analysts and decision makers prescriptive details about nodal capacities needed to meet demands. Prior to this work, insights for this type of problem were generated using multiple time-consuming simulations often involving trial-and-error to explore the trade space.

Originality/value

This work merges research of supply chain network design with military theater distribution problems to prescribe the optimal, or near-optimal, throughput capacities at theater nodes. The capacity levels must meet delivery requirements while adhering to constraints on the proportion of cargo transported by mode and the expected payloads for assets.

Citation

Longhorn, D.C. and Muckensturm, J.R. (2019), "Determining nodal capacities for military distribution problems", Journal of Defense Analytics and Logistics, Vol. 3 No. 2, pp. 110-130. https://doi.org/10.1108/JDAL-03-2019-0006

Introduction

Military theater distribution problems, or alternatively military deployment problems, are similar to supply chain network design (SCND) problems. Both problems involve the flow of commodities between facilities over supply routes. More importantly, both problems necessitate the timely delivery of these commodities to meet customer demands. The US Transportation Command (USTRANSCOM) is responsible for identifying potential distribution shortfalls, which may prevent the on-time delivery of military cargo between transportation nodes using available assets, such as trucks and railcars (US Joint Chiefs of Staff, 2017). A significant challenge for analysts at the USTRANSCOM is to identify the constraining factors during military theater distribution operations. Although the constraints may be insufficient types or quantities of transportation assets, the theater nodes consisting of debarkation ports and final destinations are often the constraint due to congestion and bottlenecks inherent when processing large amounts of military cargo in a short timeframe (US Joint Chiefs of Staff, 2013). As such, the remedy to ensuring on-time delivery is most often to identify the required throughput capacities at theater nodes. Informally, USTRANSCOM analysts have called this important transportation problem the military nodal capacity problem (MNCP), which is the focus of this paper.

The MNCP closely resembles a SCND problem involving capacity expansion, which has been studied extensively. The types of SCND problems most applicable to the MNCP have three characteristics:

1. treating capacity as a decision variable instead of a constraint;

2. fully meeting customer demands instead of partially meeting demands given cost tradeoffs; and

3. permitting capacity changes on a continuous scale instead of allowing only stepwise, or modular, changes.

Both deterministic and stochastic variants of these SCND problems exist in the literature; however, this paper focuses exclusively on the deterministic variant, i.e. the input data is assumed to be known with certainty. The reader is directed to the work of Govindan et al. (2017) for a recent survey on stochastic variants of the SCND problem.

The primary decisions of most SCND problems involve determining the location of supply facilities (usually warehouses or distribution centers) and deciding the optimal capacity levels needed to meet customer demands. The nodal locations are usually pre-determined in military theater distribution problems, so decisions about locations are not considered in the MNCP. Also, capacity levels in SCND problems usually involve storage or throughput at nodes, whereas capacity levels in the MNCP reflect daily throughput of cargo at theater nodes via various transportation assets (US Headquarters of the Army, 2014b). Theater logisticians need to understand current capacity levels at theater nodes, as well as any potential capacity constraints that may delay distribution operations. More importantly, the specific capacity levels that could overcome nodal capacity constraints would be critical information to decision-makers, who could add personnel or equipment to the inadequate nodes to improve the infrastructure and maximize throughputs (US Headquarters of the Army, 2014b). There have been too few applications of SCND by analysts at the USTRANSCOM to answer this important military logistics problem. Instead, analytic methods at the command have relied on time-consuming iterations of simulation tools to identify the required capacity levels of hundreds of nodes and for thousands of movement requirements.

The MNCP is to determine the minimum daily nodal capacities required in terms of trucks per day and railcars per day, via expansion above the current capacities, given the following considerations:

• required flow of military cargo, as prescribed by a time-phased force deployment and data (TPFDD), which provides detailed information on the amounts of cargo to transport from debarkation ports to final destinations for each day;

• transportation information, including transport asset payloads, transport times over the physical distribution network, and the proportion of cargo requirements to move via each transport mode; and

• nodal information, including the current daily nodal throughput capacities in terms of number of transportation assets, usually trucks per day and railcars per day.

The focus of this paper is to solve the MNCP by ensuring the on-time delivery of military cargo requirements, subject to transportation and nodal throughput information. The methods used include mathematical programming, specifically a mixed integer program (MIP) to optimize daily nodal capacities by mode to meet distribution requirements, as well as a heuristic algorithm to provide near-optimal solutions for large instances of the MNCP, which would be computationally inefficient to solve using the MIP. The results of the MIP and heuristic solutions are compared for a relatively large problem indicative of problems encountered by analysts at the USTRANSCOM. In addition, the MIP and heuristic solutions for 27 randomly generated problems are compared to assess the accuracy and suitability of the heuristic. Regression analysis is then used to identify significant predictors of capacity expansion errors observed in the heuristic solutions. Finally, suggestions for future work on the MNCP are provided for other researchers.

Literature review

Although the MNCP has not been directly addressed in the literature, capacity decisions with respect to supply chain nodes have been the focus of much research under the broader topic of SCND. The reader is directed to the works of Julka et al. (2007) and Cuda et al. (2015) for surveys of deterministic capacity decision problems; however, the papers that best align with the MNCP are described in this section. The most typical solution approaches in the literature were optimal mathematical programs for small problems and non-optimal heuristics to solve larger problems due to the computational challenges of exact solution methods.

There are three key distinctions between the applicable research of this problem:

• whether capacity changes are continuous or modular;

• whether customer demands are fully met; and

• the approaches used to solve the problems.

The most prevalent research seems to involve determining modular capacity levels to fully meet customer demands by applying both mathematical programs and heuristics (Shulman, 1991; Antunes and Peeters, 2001; Rajagopalan and Swaminathan, 2001; Amiri, 2006; Thanh et al., 2010; Javid and Azad, 2010; Sadjady and Davoudpour, 2012; Melo et al., 2012; Badri et al., 2013; and Jena et al., 2016). Other researchers have used only heuristics to make modular capacity decisions that fully meet customer demands, including Bean and Smith (1985), Syam (2000) and Dias et al. (2008). Still others have used only mathematical programs to determine optimal modular capacity levels that fully meet customer demands, including Lee and Luss (1987), Aghezzaf (2005), Thanh et al. (2008), Wilhelm et al. (2013), Delmelle et al. (2014), Cortinhal et al. (2015) and Castro et al. (2017). Finally, several authors have considered modular capacity decisions to partially meet customer demands with a focus on mathematical programs (Bashiri et al., 2012; Correia et al., 2013; and Correia and Melo, 2017), with the problems involving tradeoffs between fully meeting demands and reducing costs.

Most research has focused on modular capacity due to the discrete, step-wise changes in capacity by either installing (in the case of capacity expansion) or removing (in the case of capacity contraction) physical components of supply or warehouse facilities. As such, relatively few authors have allowed continuous changes to capacity levels to meet customer demands. Notably, Fong and Srinivasan (1981) and Fong and Srinivasan (1986) applied both mathematical programming and heuristics to the capacity expansion problem, while allowing continuous changes in capacity levels. Although continuous capacities may not be typical of SCND problems, they are applicable for the MNCP because nodal throughputs, in terms of transportation asset processing rates per day, are often represented by non-discrete capacity levels (US Headquarters of the Army, 2014b). As an example, the graph in Figure 1 shows the pairwise railcar and truck daily processing rates at 52 key US Army nodes, which represent non-modular capacity levels of a continuous nature.

Some research reviewed was not necessarily applicable to the MNCP because capacity was:

• treated as a constraint instead of a decision variable (Geoffrion and Graves, 1974; Ambrosino and Scutella, 2005; Eskigun et al., 2005; Belenguer et al., 2011; Boujelben et al., 2014; Boujelben et al., 2016; and Tavakkoli-Moghaddam and Raziei, 2016);

• had an associated lead time before capacity was allowed to expand (Gaimon and Burgess, 2003); or

• was allowed to expand only once during the associated timeline (Dangl, 1999).

In addition, the research by Hsu (2002) was not applicable due to unmet customer demands, which the author allowed via deferred capacity expansion until higher demands could justify expansion costs.

The research referenced in this paper was useful in developing the MIP and heuristic algorithm to solve the MNCP. Specifically, the MIP and heuristic of the MNCP adopt the common research theme that capacity expansion can be a decision variable to meet customer demands occurring over a delivery timeline. In addition, the present research supports the general consensus that a MIP can provide exact solutions for relatively small problems; however, the challenge is to develop a heuristic that provides near-optimal solutions to large problems in a timeframe that is acceptable to decision-makers. The methods and results presented next suggest the MIP and heuristic are useful to analysts at the USTRANSCOM to solve the MNCP.

Methods

Notation

The MNCP involves estimating required capacity levels at each theater node to meet cargo transport requirements on a prescribed timeline subject to various transportation constraints. The set of TPFDD requirements I is indexed by i. The amount of cargo associated with requirement i, measured in short tons, is represented as A_i. Next, there are exactly two nodes associated with each requirement. First, each requirement originates at a port node, which is either a seaport or an airport. Let P be the set of all ports and let P_i ∈ P be the port for requirement i. Second, each requirement is to be delivered to a destination node, so let D represent the set of destinations and let D_i ∈ D be the destination for requirement i. Likewise, there are two dates associated with each requirement i. First, each requirement can begin departing its port (P_i) on a known start day, which is represented by S_i. Second, each requirement must be delivered to its destination (D_i) by a known end day represented by E_i.

In addition, the MNCP considers various transportation-specific information, which can be influenced by the military commander in the theater. First, let M be the set of possible transport modes, with road and rail the most often used modes based on cargo type, size and weight (US Headquarters of the Army, 2014a). Then, let m represent a specific transport mode and let R_m be the expected constant payload, measured in short tons, for each asset of transport mode m. Similarly, let Q_m reflect the proportion of total cargo in the TPFDD to be transported by mode m. Next, let V be the set of operation days and let v be a specific day within the timeframe of the operation. Then, let L_i,m be the transport time, measured in number of days, for requirement i moving between the port (P_i) and destination (D_i) nodes via transport mode m. The transport time is a positive integer computed by dividing the associated route distance by the asset speed for each mode and then rounding to the next higher integer. Finally, let k be a generic theater location with k ∈ (P∪D) and also let C_k,m,v represent the current capacity at location k via mode m on day v.

Assumptions

The data associated with the MNCP are assumed to be known with certainty, including the requirements, transportation and nodal information. In addition, each requirement involves transporting cargo from a single port to a single destination via each transport mode m, although the transport time may differ for each mode m. The start day S_i must be strictly less than the end day E_i for each requirement i to allow sufficient travel time. Similarly, assets must have enough time to complete at least a single delivery from each port and destination pairing, i.e. L_i,m must be less than or equal to E_i minus S_i for each mode m. In addition, nodal capacity levels can be increased or decreased from one day to another, i.e. there are no lead times associated with changing capacity levels at nodes. Also, there are no restrictions on the amount of capacity that can be added at each node and there are no cargo storage limits at nodes. Finally, the MNCP assumes an unlimited, homogeneous fleet of transportation assets having payloads and speeds differentiated only by the transport mode m.

Mixed integer program formulation

The MIP formulation identifies the minimal amount of daily capacity expansion required at each theater node for each transport mode to meet TPFDD movement requirements. Additionally, the MIP minimizes the sum of peak capacities over all theater nodes, but not at the expense of delivering cargo late. The MIP requires additional notation, including w to represent a generic day with w ∈ V and j to represent a generic theater location with j ∈ (P ∪ D).

The MIP requires four decision variables:

• x_i,k,m,v – Number of loads for requirement i departing location k via mode m on day v;

• y_i,k,m,v – Number of loads for requirement i arriving to location k via mode m on day v;

• z_k,m,v – Required capacity expansion at location k via mode m on day v; and

• u_k,m – Peak capacity expansion used at location k via mode m during the operation.

The MIP formulation is given in equations (1) through (9):

(1) minimize ∑k∈P∪D∑m∈M∑v∈Vzk,m,v +∑k∈P∪D∑m∈Muk,m 

Subject to:

(2) ∑v=SiEi-Li,mxi,k,m,v*Rm≥Qm*Ai ∀i∈I ∀k|k=Pi ∀m∈M

xi,k,m,v-yi,j,m,w=0                                                ∀i∈I ∀kk=Pi ∀jj=Di ∀m∈M

∀vv≥Si and v≤Ei-Li,m

(3) ∀ww=v+Li,m

(4) zk,m,v≥∑i∈Ixi,k,m,v+yi,k,m,v-Ck,m,v      ∀k∈P∪D ∀m∈M ∀v∈V

(5) uk,m≥zk,m,v                                                                   ∀k∈P∪D ∀m∈M ∀v∈V

(6) uk,m≥0∀k∈P∪D ∀m∈M

(7) xi,k,m,v≥0 and integer                                           ∀i∈I ∀k∈P∪D ∀m∈M ∀v∈V

(8) yi,k,m,v≥0 and integer                                            ∀i∈I ∀k∈P∪D ∀m∈M ∀v∈V

(9) zk,m,v≥0 and integer                  ∀k∈P∪D ∀m∈M ∀v∈V

The first component of the objective function in equation (1) reflects the total nodal capacity expansion in the theater, the minimization of which is the primary goal of the MIP. The second component of the objective function in equation (1) minimizes the sum of peak nodal capacity expansions over the nodes during the operation, e.g. two consecutive days at capacity level 50 is preferred to a single day at capacity level 100 if both options will meet requirements. Equation (2) ensures enough departures from the port occur to meet movement requirements during the delivery window, subject to the proportion of cargo to be transported by each mode and the corresponding asset payload. Equation (3) is a flow conservation equation that links the departures each day of the delivery window from a specific port to the arrivals each day at the corresponding destination given the transport time by mode. Equation (4) permits capacity expansion above the current capacity level to meet the combined daily departures and arrivals at each node. Equation (5) determines the peak capacity expansion for each node and by each mode over the entire operation. Equation (6) ensures non-negative variables and equations (7) through (9) ensure non-negative integer variables.

Heuristic notation and pseudocode

The MNCP heuristic requires additional notation beyond that used for the associated MIP. First, let F_i,m represent the number of allowable delivery days for requirement i via transport mode m, as computed with equation (10), which is based on the start day, end day, and transport time:

(10) Fi,m=Ei-Si-Li,m+1

Second, let W_i,m represent the expected amount of daily cargo that should be transported for requirement i by mode m, as computed with equation (11), which is based on the amount of cargo, the modal proportion and the allowable delivery days:

(11) Wi,m=Ai * QmFi,m

Next, let H_v be the set of requirements with active movements during day v; thus, H_v⊆I for all v and set membership is defined according to the condition stated in equation (12):

(12) i∈Hv if Si≤v≤Si+Li,m-1 ∀i    ∀m

Finally, let G_k,m,v be a non-negative integer counting variable that represents the number of assets processed at location k of transport mode m on day v. The following pseudocode outlines the MNCP heuristic algorithm:

Algorithm Military Nodal Capacity Problem1: Calculate Fi,m and Wi,m2: Build set Hv3: Initialize Gk,m,v←04: Declare minday = min (Si)5: Declare maxday = max (Ei)6: for each v in (minday: maxday) do7:    for each i in Hv do8:       for each m ∈ M do9:           if v ≤ Si+Li,m−1 then10:            while Wi,m > 0 do11:                    Wi,m←Wi,m−Rm12:                    GPi,m,v←GPi,m,v+113:                    GDi,m,(v+Li,m)←GDi,m,(v+Li,m)+114:             end while15:           end if16:       end for17:     end for18: end for19: output expansion estimate zk,m,v=Gk,m,v-Ck,m,v if Gk,m,v>Ck,m,v 0  otherwise 

Measures

Decision makers are interested in two theater-wide metrics, which are generated for the MIP and heuristic. These metrics provide insights into the total capacity expansion required to ensure the on-time delivery of military cargo in the theater. First, let T_m be the total capacity expansion required over all nodes and all days by transport mode m, as defined in equation (13):

(13) Tm=∑k∈P∪D∑v∈Vzk,m,v

Second, let T be the total capacity expansion required over all nodes, all days, and all transport modes, as defined in equation (14):

(14) T=∑m∈MTm

Additionally, decision makers are interested in two nodal metrics, which are generated for the MIP and heuristic. These metrics provide insights into which nodes require capacity expansion as well as how much capacity expansion is needed. First, let N_k,m be the total capacity expansion required at node k over all days by transport mode m, as defined in equation (15):

(15) Nk,m=∑v∈Vzk,m,v

Second, let B_k,m be the peak capacity (i.e. current capacity plus expanded capacity) at node k by transport mode m over all days, as defined in equation (16):

(16) Bk,m=maxCk,m,v+zk,m,v: v∈V

Finally, each theater-wide and nodal metric is reported with superscripts, o for optimal and h for heuristic, to distinguish between the MIP and heuristic metrics, respectively.

Results

This section presents the results of two types of notional problems solved using both the MIP and heuristic algorithm. First, a large-scale problem indicative of a typical MNCP encountered at the USTRANSCOM is studied. Second, 27 randomly generated notional problems of various sizes and attributes are examined to further test the accuracy and suitability of the present heuristic. A typical MNCP is within an overseas country transporting cargo from debarkation ports to final destinations; however, to avoid security classification issues, the problems presented in this paper are entirely within the USA with cargo moving from ports to inland destinations.

Assessment measures

Equations (17) and (18) are used to assess the relative per cent error of the heuristic solution compared to the MIP solution with respect to the theater-wide capacity expansion metrics:

(17) Theater_Em=Tmh-TmoTmo * 100

(18) Theater_E=Th-ToTo * 100

Similarly, the equations (19) and (20) are used to assess the relative per cent error of the heuristic solution compared to the MIP solution with respect to the two nodal capacity expansion metrics. Equation (19) returns the median nodal error over all nodes for each transport mode. The median error is preferred over the mean error because real problems previously studied have shown a positive skew in the distribution of nodal errors. Likewise, equation (20) returns the median absolute error in nodal peaks over all nodes for each transport mode. As with equation (19), the median error is preferred to the mean error given the positive skew of the error distribution. In addition, the absolute error is required in equation (20) because the MIP is not guaranteed to produce a minimal peak at the individual node level, i.e. it is conceivable that the heuristic will yield a lower absolute peak capacity expansion at a node compared to the MIP. This phenomenon occurs because the secondary objective of the MIP is to minimize the sum of peak nodal capacities over all nodes; therefore, higher peaks at some nodes compared to the heuristic are possible although the sum of peaks over all nodes will always be lower compared to the heuristic:

(19) Node_Em=medianNk,mh-Nk,moNk,mo *100: k∈P∪D 

(20) Peak_Em=median|Bk,mh-Bk,mo|Bk,mo *100: k∈P∪D 

The final metric, as given in equation (21), is the per cent time difference of the heuristic solution compared to the MIP solution. Let CPU^h represent the heuristic solution time in seconds and let CPU^o represent the MIP solution time in seconds. Negative values of the metric therefore reflect computational savings of the heuristic compared to the MIP:

(21) Time_Delta=CPUh-CPUoCPUo * 100

Large-scale military nodal capacity problem description

This large-scale MNCP involves transporting military cargo from US ports to inland destinations using roads and railways. This problem has 1,719 separate requirements totaling about 1.2 M short tons of cargo, which must be transported via truck (Q_road = 0.3) and rail (Q_rail = 0.7) from 14 debarkation ports to 18 total destinations. Transportation asset payloads are assumed to be 13 short tons per truck (R_road = 13) and 33 short tons per railcar (R_rail = 33), which are based on historical average payloads of typical problems. Figure 2 shows the physical network of roads and railways connecting the 14 ports to the 18 destinations. The modal transport times for each requirement (L_i,m) between ports and destinations are determined from the associated distances and speeds of the transportation assets. Asset speeds are assumed to be 40 miles per hour for trucks and 22 miles per hour for railcars, which are based on average historical speeds accounting for typical operational delays.

The distribution of cargo requirements is represented by the histogram in Figure 3. The distribution has a range of about 6,500 short tons, which is typical of most transportation problems due to requirements reflecting a vast range of light relief supplies to heavy military equipment. However, most of the requirements are less than about 500 short tons.

Large-scale military nodal capacity problem results

The large-scale MNCP was solved with the MIP and with the heuristic. The MIP solution resulted in a total capacity expansion (T^o) of 110,618. The optimal total capacity expansions by transport mode were Troado=57,416 and  Trailo=53,202. Conversely, the heuristic solution resulted in a total capacity expansion (T^h) of 114,922 with Troadh=59,948 and  Trailh=54,974. The theater-wide metrics errors were thus Theater_E_road = 4.4 per cent, Theater_E_rail = 3.3 per cent, and Theater_E = 3.9 per cent. Figure 4 shows the cumulative theater-wide capacity expansion measures by day of the operation for the MIP and heuristic, as well as the associated breakdowns by road and rail. A cumulative capacity expansion visual is often preferred by analysts and decision-makers, because it lessens the complexity of daily capacity spikes and shows the incremental nature of capacity expansion over time. As expected, the required capacity expansion prescribed by the heuristic exceeds the optimal throughout the deployment. The graph also shows a nearly identical shape between the heuristic and MIP solutions with errors increasing slowly throughout the operation.

The total nodal capacity expansion metrics were also calculated for each of the 32 theater nodes. Figure 5 (for m = road) and Figure 6 (for m = rail) compare the MIP (solid line) and heuristic (dashed line) solutions with respect to the cumulative nodal capacity expansion (vertical axis) on each day (horizontal axis) for each node, with nodes presented in no particular order.

The distribution of nodal capacity errors for the large-scale MNCP is provided in Figure 7, with each histogram showing a positive skew. The non-normal distribution of errors is further support for using the median error instead of the mean error for this assessment measure. The median errors at the nodal level by transport mode were Node_E_road = 4.7 per cent [Figure 7(a)] and Node_E_rail = 2.7 per cent [Figure 7(b)], which were generally consistent with the theater-wide capacity expansion errors. Also, the median errors in peak nodal capacity expansion by transport mode were Peak_E_road = 23.6 per cent [Figure 7(c)] and Peak_E_rail = 25.0 per cent [Figure 7(d)]. An analysis of the possible causes of the relatively high peak capacity errors at the nodal level is provided in the Discussion section.

Finally, the solution time of the heuristic was substantially lower (56 seconds) compared to the MIP (123,961 s), which resulted in Time_Delta = −99.95 per cent. Prior to the present research into MNCPs, analysts at the USTRANSCOM would iteratively adjust simulation settings reflecting capacities at hundreds of theater nodes, run the mobility simulation program, assess whether the adjusted nodal capacities met delivery requirements, and if not, the process was repeated. This time-consuming process could take at least a week and would rarely yield near-optimal capacities. As such, the considerable time savings of the MNCP heuristic and the demonstrated near-optimal results allows analysts at the USTRANSCOM to dedicate more time to other aspects of the problem, such as identifying transport asset requirements or recommending alternative ports.

Randomly generated problems

The large-scale MNCP results showed the relative accuracy and computational efficiency of the heuristic in solving a typical, large-scale problem at the USTRANSCOM. To study the suitability of the heuristic across a range of increasingly demanding problems, twenty-seven randomly generated problems were solved using the MIP and heuristic. Each random MNCP instance is distinguishable by three modified variables: the number of requirements (reqts), the number of locations (locs), and the number of days (days). The corresponding sets of variable inputs tested were reqts = {100,300,500}, locs = {10,30,50}, and days = {50,100,200}.

For each random problem instance, the asset payloads and proportions were the same as in the large-scale scenario, i.e. Q_road = 0.3, R_road = 13, Q_rail = 0.7, and R_rail = 33. Also, the locations were randomly split into possible ports (30 per cent of the number of locations) and possible destinations (the remaining 70 per cent of the number of locations). Finally, the requirements were assigned various random attributes, as described in Table I.

The modified variable settings and associated assessment measures for the random MNCP instances are given in Table II. The reported errors of the assessment measures for total capacity by mode, total capacity, and nodal capacity by mode are relatively stable at about 2 per cent or less. Conversely, the errors of the assessment measure peak nodal capacity ranged from zero per cent to almost 100 per cent. As noted with the large-scale MNCP, further exploration of the relatively high errors in peak nodal capacity is provided in the Discussion section.

Software and hardware specifications

The MIP was implemented in the General Algebraic Modeling System v24.3.3 software. The relative and absolute optimality tolerances of the software’s CPLEX solver were set to 0.1 per cent of optimal to avoid unnecessarily long execution times. The heuristic algorithm was implemented in the RStudio v1.1.453 software (Team, 2017) using R v3.5.1 and the R package openxlsx (Walker and Braglia, 2018) for reading input data and outputting results. The solutions for both the MIP and heuristic were generated on a common computing environment, specifically a 64-bit Windows 7 computer with an Intel Xeon CPU at 3.33 GHz and 48 GB of RAM.

Discussion

The MNCP results compare favorably with the results of previous researchers, who developed various heuristics to determine optimal or near-optimal capacity expansion levels for SCND problems. Previous heuristics yielding results within about one per cent of the optimal solution include those by Fong and Srinivasan (1981), Javid and Azad (2010), Melo et al. (2012) and Jena et al. (2016). Sadjady and Davoudpour (2012) also achieved heuristic results within 1 per cent of the optimal solution, but only for small problem instances. Other researchers produced heuristics within about three per cent of the optimal solution, including Shulman (1991), Rajagopalan and Swaminathan (2001), Amiri (2006), Thanh et al. (2010) and Sadjady and Davoudpour (2012). Finally, the heuristic by Badri et al. (2013) produced results within about four per cent of the corresponding optimal solutions.

Error analysis

As shown in Table II, the MNCP heuristic consistently provides results within about two per cent of optimal results for the theater-wide and total nodal capacity metrics across most problems studied. However, peak nodal errors were less consistent with an observed range from zero per cent to about 100 per cent compared to optimal results. The rationale for the heuristic giving higher capacities, especially with respect to peak nodal capacities, stems from the greedy nature of the algorithm. First, the heuristic splits each cargo requirement into smaller requirements that are spread evenly during the allowable delivery days per equations (10) and (11). Thus, the MIP can meet small cargo requirements with a fully loaded asset on a single day of the allowable delivery window [Figure 8(a)], whereas the heuristic might require partially loaded assets on each day spread over the allowable delivery window [Figure 8(b)].

In addition, the MIP can shift cargo movements anywhere within the allowable delivery window [Figure 9(a)], whereas the heuristic must evenly spread cargo movements to each day of the allowable delivery window [Figure 9(b)].

Advantages of the heuristic

Although the MIP will outperform the heuristic in terms of minimizing capacity expansions, the heuristic still provides near-optimal capacity expansion estimates for three of the four key assessment measures and, more importantly, provides computational time savings of about 86 per cent on average for the random problems studied in this paper. Indeed, the highest computational savings occur with the larger problems studied, which are more typical of real problems studied at the USTRANSCOM. Thus, the MNCP heuristic provides stable, near-optimal capacity expansion solutions for several key assessment metrics and is computationally efficient.

Regression analysis of random problem instances

A regression analysis of the errors in Table II was conducted to identify any statistically significant factors in predicting the observed errors in assessment measures. The regressors were the three modified variables in each MNCP instance: reqts, locs, and days. The low variability of errors in total capacity expansion by mode (Theater_E_road, Theater_E_rail), total capacity expansion (Theater_E), and total nodal capacity expansion by mode (Node_E_road, Node_E_rail) resulted in no significant factors at the 0.05 alpha level. However, significant models were achieved for peak nodal rail capacity expansion (Peak_E_rail) errors (F-stat = 33.3, p < 0.001, Adjusted R² = 0.79) and for peak nodal road capacity expansion (Peak_E_road) errors (F-stat = 39.4, p < 0.001, Adjusted R² = 0.82). In each fitted model, the regressors (reqts, locs and days) were each significant at p < 0.001. No interaction effects were found.

Finally, a regression analysis of the time delta results identified a significant model (F-stat = 8.7, p < 0.001, Adjusted R²=0.47) with locs (p < 0.001) and days (p = 0.005) each significant. Also, the model with locs, days and the interaction locs*days was likewise significant (F-stat = 20.9, p < 0.001, Adjusted R² = 0.70) with both regressors and their interaction significant at p < 0.001.

Additional sensitivity analyses

The previous regression analyses identified several significant regressors with respect to peak errors; however, the seemingly low variability of errors for the remaining assessment measures warranted further exploration. As such, additional sensitivity analyses were conducted to better understand if the heuristic might yield larger errors due to changes in other key problem variables. Two such variables, specifically the cargo range and the span of the delivery window, were suspected of influencing capacity expansion errors based on the greedy nature of the MNCP heuristic, as presented in Figures 8 and 9.

The additional variables under study, henceforth termed cargo and window, were pairwise incrementally changed for a single random MNCP instance from Table II and solved by the MIP and heuristic. Random problem 1 was selected due to its relatively small size, with reqts = 100, locs = 10, and days = 50, which facilitated faster MIP solution times. Each sensitivity run involved incremental changes to the cargo and window problem variables. Twelve incremental ranges of cargo short tons {1-500,501-1000,…,5501-6000} were used for the cargo variable, with each requirement assigned a cargo value drawn from a uniform distribution between the cargo range. For each incremental range of the cargo variable, six incremental values reflecting additional delivery days from zero to five were assigned to the window variable. The corresponding number of additional delivery days was simply added to the associated end day (E_i) variable for each requirement. This pairwise sensitivity design resulted in 72 instances of a relatively small-scale MNCP that could be solved using the MIP and heuristic. The resultant errors in theater capacity expansion (Theater_E) are graphed on a response surface in Figure 10 to visualize the effects of pairwise changes to the cargo and window variables.

Figure 10 shows relatively stable errors of less than about 10 per cent for runs with cargo requirements above about 1,500 short tons, regardless of the size of the delivery window expansion. However, as the cargo distribution range is lowered and the delivery window is expanded, the associated errors can increase to over 60 per cent. A regression analysis of the theater capacity expansion errors presented here identified a significant model (F-stat = 26.9, p < 0.001, Adjusted R²=0.42) with cargo (p < 0.001) and window (p = 0.01) each significant. Another model with the interaction term cargo*window included was also significant (F-stat = 21.7, p < 0.001, Adjusted R² = 0.47), but the cargo term was then insignificant (p = 0.06), so this interaction model was abandoned in favor of the more parsimonious model with cargo and window as the only regressors.

Conclusion

The research presented in this paper introduces a new type of SCND problem called the MNCP, which is to identify the required capacity expansion levels at theater nodes to ensure on-time delivery of military cargo from ports to destinations. Although supply chain problems involving capacity decisions have been studied, the MNCP had not been examined until this present work. Solution approaches to typical SCND problems have included optimal mathematical programs and near-optimal heuristics, with large instances of the problems typically solved using heuristics. In this paper, an optimal MIP and a fast, near-optimal heuristic were developed to solve real-world and random instances of the MNCP.

The heuristic results presented for a notional, large-scale MNCP with characteristics of typical problems studied at the USTRANSCOM produced solutions within about 4 per cent of optimal for three of the four measures of interest to decision makers. More importantly, the heuristic vastly outperformed the MIP with a 99.95 per cent reduction in computation time. In addition, the heuristic results for 27 random problem instances suggest the MNCP heuristic performs well across a breadth of problem instances, with solutions consistently within about 2 per cent of optimal for three of the four key assessment metrics. Regression analysis showed that the number of requirements, locations, and days were significant predictors of peak nodal capacity expansion errors. Further analysis of the heuristic results suggests that high errors in total capacity expansion occurs when cargo movement requirements are relatively small and delivery windows are relatively wide, which was confirmed with regression analysis of the associated errors given changes to regressors for cargo size and delivery window expansion.

Prior to this research, analysts at the USTRANSCOM used deterministic simulation tools to estimate the nodal capacity expansion levels needed to meet theater transportation requirements. This method was inherently time-consuming because it required the analyst to conduct trial-and-error iterations with different nodal capacities until all transportation requirements were met. Analysts at the command are now using the MNCP heuristic described in this paper to provide near-optimal nodal capacity levels for diverse theater distribution problems.

Future work

Future work on the MNCP could incorporate stochastic aspects of the MNCP encountered in most real problems, such as uncertain cargo requirements, flexible start and end shipment dates, variations in transportation asset payloads and variations in transport times due to weather, congestion or enemy actions. In addition, future work could incorporate heterogeneous fleets of transportation assets with different payloads and speeds, restrict the capacity levels to some pre-determined limit based on resources or allow tradeoffs between late deliveries and increased infrastructure capacity costs.

Figures

Figure 1.

Railcar and truck daily processing rates at 52 key army nodes

Figure 2.

Physical network of roads and railways connecting ports and destinations for the large-scale MNCP

Figure 3.

Cargo distribution of large-scale MNCP

Figure 4.

Cumulative total capacity expansion for large-scale MNCP; optimal vs heuristic

Figure 5.

Cumulative total nodal capacity expansion (road) for large-scale MNCP; optimal vs heuristic

Figure 6.

Cumulative total nodal capacity expansion (rail) for large-scale MNCP; optimal vs heuristic

Figure 7.

Distribution of total nodal capacity errors and peak nodal capacity errors for large-scale MNCP

Figure 8.

Comparing MIP and heuristic approaches for meeting small cargo requirements

Figure 9.

Comparing MIP and heuristic approaches for distributing requirements within the delivery window

Figure 10.

Capacity expansion errors given cargo and window changes for random problem 1

Table I.

Random attributes assigned to requirements for each MNCP instance

Variable name	Variable	Assignment rule
Port	Pi	Random draw from possible ports (30% sample of locations)
Destination	Di	Random draw from possible destinations (remaining 70% sample of locations)
Cargo in short tons	Ai	Integer(Uniform(4000,5000))
Transport time (road) in days	Li,road	Random draw from integer set {1,2,…,6}
Transport time (rail) in days	Li,rail	Random draw from integer set {1,2,…,7}
Start day	Si	Random draw from integer set {1,2,…(number of days - Max(Li,road,Li,rail))}
End day	Ei	Min(number of days, Si + Max(Li,road,Li,rail) + Integer(Uniform(0,5))

Table II.

Variable settings and assessment measures for 27 random MNCP problems

	Variables			MIP	Heuristic
	reqts|I|	locs | P U D|	days |V|	Time (sec)	Time (sec)	Theater_Eroad (%)	Theater_Erail (%)	Theater_E (%)	Node_Eroad (%)	Node_Erail (%)	Peak_Eroad (%)	Peak_Erail (%)	Time delta (%)
1	100	10	50	23	18	1.9	1.8	1.8	2.0	1.8	56.4	45.5	−20.9
2	100	10	100	85	18	1.8	1.6	1.7	1.8	1.6	20.6	18.8	−78.8
3	100	10	200	321	18	1.8	1.6	1.7	1.9	1.6	14.2	23.9	−94.4
4	100	30	50	183	18	1.9	1.7	1.8	1.8	1.7	14.9	2.3	−89.9
5	100	30	100	721	19	1.5	2.2	1.9	1.5	2.1	0.0	0.0	−97.4
6	100	30	200	2837	20	1.9	1.5	1.7	1.9	1.6	0.0	0.0	−99.3
7	100	50	50	510	18	2.2	1.8	2.0	2.1	1.9	0.6	0.0	−96.4
8	100	50	100	1985	21	1.7	1.8	1.8	1.7	1.7	0.0	0.0	−99.0
9	100	50	200	7740	21	1.5	1.8	1.7	1.3	1.8	0.0	0.0	−99.7
10	300	10	50	68	50	1.9	1.8	1.8	1.9	1.8	77.4	68.4	−26.2
11	300	10	100	257	53	1.9	1.6	1.7	1.8	1.5	67.4	67.8	−79.3
12	300	10	200	982	52	1.6	1.6	1.6	1.6	1.6	37.7	37.2	−94.7
13	300	30	50	553	52	1.8	1.9	1.8	1.9	1.9	47.0	58.4	−90.6
14	300	30	100	2160	61	1.8	1.6	1.7	1.8	1.6	17.1	28.6	−97.2
15	300	30	200	8567	60	1.7	2.0	1.8	1.6	1.9	15.6	14.1	−99.3
16	300	50	50	1514	59	1.8	1.8	1.8	1.9	1.7	33.2	33.9	−96.1
17	300	50	100	5955	56	1.9	1.7	1.8	1.8	1.7	16.7	14.8	−99.1
18	300	50	200	23722	65	1.7	1.9	1.8	1.6	1.7	0.0	12.5	−99.7
19	500	10	50	113	99	1.8	1.9	1.8	1.9	1.8	69.9	64.1	−12.1
20	500	10	100	420	102	1.8	1.7	1.8	1.8	1.7	98.2	70.5	−75.7
21	500	10	200	1631	97	1.9	1.7	1.8	2.0	1.7	63.5	66.6	−94.1
22	500	30	50	904	90	1.8	1.7	1.7	1.7	1.7	64.0	60.1	−90.0
23	500	30	100	3588	98	1.9	1.7	1.8	2.0	1.7	39.8	49.3	−97.3
24	500	30	200	14277	102	1.7	1.8	1.7	1.7	1.8	24.9	17.2	−99.3
25	500	50	50	2502	103	1.7	1.7	1.7	1.7	1.6	54.3	49.7	−95.9
26	500	50	100	9857	103	1.7	1.7	1.7	1.7	1.7	27.0	24.8	−99.0
27	500	50	200	39310	108	1.7	1.9	1.8	1.7	2.0	11.1	13.9	−99.7