A heuristic approach applied to the fleet sizing problem for military ground vehicles

Abstract

Purpose

This paper aims to propose two solution approaches to determine the number of ground transport vehicles that are required to ensure the on-time delivery of military equipment between origin and destination node pairs in some geographic region, which is an important logistics problem at the US Transportation Command.

Design/methodology/approach

The author uses a mathematical program and a traditional heuristic to provide optimal and near-optimal solutions, respectively. The author also compares the approaches for random, small-scale problems to assess the quality and computational efficiency of the heuristic solution, and also uses the heuristic to solve a notional, large-scale problem typical of real problems.

Findings

This work helps analysts identify how many ground transport vehicles are needed to meet cargo delivery requirements in any military theater of operation.

Research limitations/implications

This research assumes all problem data is deterministic, so it does not capture variations in requirements or transit times between nodes.

Practical implications

This work provides prescriptive details to military analysts and decision-makers in a timely manner. Prior to this work, insights for this type of problem were generated using time-consuming simulation taking about a week and often involving trial-and-error.

Originality/value

This research provides new methods to solve an important logistics problem. The heuristic presented in this paper was recently used to provide operational insights about ground vehicle requirements to support a geographic combatant command and to inform decisions for railcar recapitalization within the US Army.

Citation

Longhorn, D.C. and Stobbs, J.D. (2021), "A heuristic approach applied to the fleet sizing problem for military ground vehicles", Journal of Defense Analytics and Logistics, Vol. 5 No. 1, pp. 2-20. https://doi.org/10.1108/JDAL-03-2020-0005

Introduction

Military distribution within a geographic region involves the flow of equipment from origin to destination node pairs using ground transport vehicles, such as railcars and trucks. In the Continental USA, the origins are usually military installations and the destinations are usually seaports or airports. Outside the Continental USA, the distribution flow is reversed with ports as the origins and tactical assembly areas as the destinations. The most important consideration for military distribution is time definite, or on-time, delivery of material at a location specified by the military commander (U.S. Headquarters of the Army, 2014). Analysts at the US Transportation Command identify potential distribution constraints that would prevent the timely delivery of military equipment. The constraints are often either insufficient nodal capacity, which is represented as daily processing rates of trucks and railcars at each location, or too few transportation vehicles available to transport the equipment (U.S. Joint Chiefs of Staff, 2013b). Longhorn and Muckensturm (2019) addressed the question of required nodal capacities for military distribution problems, but the problem of determining the required vehicle fleet size had not been sufficiently solved at the US Transportation Command until this research.

Military logisticians attempt to optimize transport operations by efficiently employing available vehicles to meet stated requirements (U.S. Joint Chiefs of Staff, 2013b). Analysts at the US Transportation Command are often asked to determine the number of vehicles required to ensure the on-time delivery of military equipment between nodes in some geographic region. The answer depends on several factors, including the number and timing of movement requirements, the geography of the road and rail network and various operational factors such as vehicle availability, speed and daily operating hour restrictions. Analysts informally call this problem the Military Vehicle Fleet Sizing Problem (MVFSP), which is typically solved about every six months for up to three distinct, large-scale distribution scenarios. The problem is to determine the minimum fleet size of ground transport vehicles given the following considerations:

• the required flow of military equipment, i.e. the delivery requirements in terms of number of vehicle loads transported from origin to destination node pairs each day;

• the transit time in days between node pairs in the physical network given vehicle speed and daily operating hour limits; and

• information about each vehicle’s starting node and first day available.

Railcars and trucks generally constitute the military ground vehicle fleets; however, we focus exclusively on the railcar fleet. Transport trucks are generally abundant in number commercially (Smith, 2019) and thus can be contracted to be available as needed. Conversely, the types of railcars used to move military equipment are limited in quantity. This rail fleet consists of some military-owned railcars as well as railcars owned by commercial rail entities. The military-owned railcars are pre-positioned at installations and immediately available to execute missions, whereas commercial railcars become available over several weeks after being requested by the military.

Until our research, US Transportation Command analysts used simulation-based methods to estimate the required vehicle fleet size (Longhorn and Stobbs, 2019). Although analysts used this method with some success to address the MVFSP, the analysts had to iteratively run dozens of simulations using trial-and-error adjustments to the number of vehicles until delivery requirements were sufficiently met. Each simulation run could take up to six hours, so the entire iterative process was time-consuming at over a week or more and was prone to error due to the trial-and-error nature of vehicle additions or subtractions. As such, the MVFSP is a strong candidate for an application of more scientific solution methods.

The focus of this paper is introducing the MVFSP and then demonstrating that the quality, speed and interpretability of our new solution approach is better than the previous method. First, we review the available literature for similar problems and then propose two solution methods: a math programming approach using an integer program (IP) and a traditional, constructive heuristic. Next, we use our IP and heuristic to solve 40 randomly generated small-scale problems to assess the effectiveness and efficiency of the heuristic. In addition, we use the heuristic to solve a notional, large-scale problem indicative of the size and complexity of an operational MVFSP and interpret the results. Finally, we suggest future work on this military logistics problem.

Literature review

The MVFSP has characteristics of the vehicle routing problem (VRP), which academia and industry have studied extensively over the past 50 years, as noted by Eksioglu et al. (2009). Most traditional VRP research assumes a given fleet size. In fact, Montoya-Torres et al. (2015) note that only about 7% of VRP research papers consider fleet size as a decision; however, a rich line of research exists with the Fleet Size and Mix VRP (FSMVRP). This variant of the traditional VRP seeks to determine the fleet size and composition with the lowest fixed fleet acquisition cost and variable routing cost. Golden et al. (1984) gave the seminal work on the FSMVRP with various opportunity savings heuristics tested on 20 problem instances. Gheysens et al. (1984) provided assignment-based heuristics with a new lower bound procedure that performed favorably on Golden’s benchmark problems. Next, Desrochers and Verhoog (1991) developed a more complete savings heuristic based on a weighted matching problem to select from all feasible vehicle routes. Renaud and Boctor (2002) proposed a solution of the FSMVRP with the first sweep-based algorithm, which included five procedures to generate routes served by one or two vehicles before selecting the routes with the lowest cost via an optimal set-partitioning method. Several authors used meta-heuristics to solve the FSMVRP, including tabu search used by Brandão (2009), who achieved better results than previous researchers; and Liu and Lu (2013), who used a hybrid meta-heuristic with variable neighborhood search accounting for vehicle type information to yield favorable results. More recently, Pasha et al. (2016) allowed for multiple periods, each with possibly different customer demands, in their tabu search approach to the FSMVRP. Evolutionary algorithms were also applied to the FSMVRP, including a genetic algorithm with parents selected via tournaments by Liu et al. (2009). Finally, several authors incorporated the temporal aspect of VRPs by extending the FSMVRP to include delivery time windows. Notable FSMVRP research with time windows includes Liu and Shen (1999), who first proposed an insertion-based savings heuristic; Dullaert et al. (2002), who combined sequential insertion heuristics with Golden’s savings heuristics; and Belfiore and Fávero (2007), who applied scatter search as a novel instance of evolutionary methods to the problem.

Unfortunately, key differences exist between our MVFSP in this paper and most VRPs, including the FMSVRP. First, VRPs typically involve vehicles visiting multiple customers on a single trip, whereas vehicles in the MVFSP transport military equipment directly from an origin to a destination, i.e. direct shipping with no intermediate stops. Second, VRPs often focus on loaded vehicle trips, whereas the MVFSP considers both loaded trips and empty (i.e. deadhead) positioning trips. Similarly, VRPs involve a vehicle starting at a home depot and then returning after visiting customers, whereas vehicles in typical MVFSPs conduct multiple trips or cycles and move freely about the system with no home node during the distribution schedule. Thus, our problem does not directly reference most VRP or FSMVRP research. We direct the reader to several VRP survey papers (Bodin, 1990; Vidal et al., 2013; Montoya-Torres et al., 2015; Braekers et al., 2016; Matl et al., 2018).

Instead, our paper references fleet sizing research that excludes the typical VRP characteristics noted above. The attributes of such fleet sizing problems are numerous, but the most common research discriminators seem to be the use of homogeneous vs heterogeneous vehicle fleets, cyclic vs acyclic demands, known vs unknown demands, consideration of loaded vehicles vs loaded and empty vehicles and direct shipping vs multi-stop deliveries. The MVFSP presented in this paper assumes a homogeneous vehicle fleet, acyclic and known demands, consideration of both loaded and empty vehicles and direct shipping between origin and destination locations.

Other similarities exist between the MVSFP and fleet sizing problems. Fleet sizing is often considered a strategic decision (Dejax and Crainic, 1987; Sherali and Lunday, 2011; Żak et al., 2011; Allahviranloo and Chow, 2019) with the routing or scheduling of vehicles seen as a tactical (or operational) decision using the available fleet. Likewise, fleet sizing in the MVFSP is a strategic-level decision with military decision-makers ensuring enough railcars are available to meet numerous transportation scenarios during times of peace and war. Next, the notion of vehicle cycles, or multi-tours, is prevalent in the literature (Hurdle, 1973; Gaudioso and Paletta, 1992; Aghezzaf et al., 2006; Raa and Aghezzaf, 2008; Raa and Aghezzaf, 2009) and also in the MVFSP, where vehicles in the fleet should cycle throughout the duration of the distribution schedule. In addition, empty vehicle positioning to appropriate origin nodes is a key consideration for MVFSPs and also for other fleet sizing problems (Orlin, 1982; Dejax and Crainic, 1987; Egbelu, 1987; Beaujon and Turnquist, 1991; Du and Hall, 1997; Kochel, 1997; Kats and Levner, 1998; Soehodho and Yusuf, 2000). Furthermore, vehicles need not always be moving in the MVFSP; in fact, requirements change between high and low delivery activity periods with some vehicles idle during low delivery activity periods, as considered by Salzborn (1972) and Gaudioso and Paletta (1992). Finally, other operational factors for the MVFSP are similar to previous research, specifically direct shipping from origin to destination (Burns et al., 1985; Campbell and Hardin, 2005; Pascual et al., 2013; Coelho et al., 2014), using a vehicle load as the unit of measure for delivery requirements (Du and Hall, 1997), and vehicles assigned for whole day increments to execute missions (Campbell and Hardin, 2005), i.e. not allowing partial day assignments. We direct the reader to fleet sizing surveys by Dejax and Crainic (1987) and Campbell and Wilson (2014), as well as fleet sizing and composition problems reviewed by Baykasoğlu et al. (2019).

Additional literature and solution approaches applicable to fleet sizing problems exist in the field of graph coloring, namely, the k-coloring and chromatic number problems. Malaguti and Toth (2010) offer a survey of vertex coloring problems along with examples of its generalization to other computationally challenging problems, including problems involving logistics. As examples, Hertz et al. (2009) used graph coloring to assign cars from a rental fleet to meet customer requests with minimal cost; Urrutia and de Werra (2018) related the bounded chromatic number problem to general pick-up and delivery operations; Benkebir et al. (2019) used a graph coloring algorithm to minimize, via finding the chromatic number of the associated graph, the number of truck drivers for a multi-trip VRP while adhering to driving hour constraints; and Factorovich et al. (2020) related graph coloring problems to vehicle pick-up and delivery problems.

Methods

We introduce two solution approaches for the MVFSP in this section: an IP formulation and a heuristic algorithm. Campbell and Hardin (2005) showed strictly periodic fleet sizing problems to be NP-hard. The MVFSP is most similar to an aperiodic fleet sizing problem, which has yet to be demonstrated as NP-hard to the best of our knowledge. The focus in this paper is introducing the MVFSP and the solution approaches we employed to solve this logistics problem at the US Transportation Command. As such, we leave the formal analysis of the problem’s computational hardness to other researchers as future work. However, the relationship of the MVFSP to well-known NP-hard problems, such as the VRP and chromatic number problem, and the computational challenges demonstrated in this paper suggest the MVFSP may indeed be NP-hard.

Integer program

The following notation for the MVFSP represents problem attributes of time, nodes, requirements, vehicles and travel time. Let V represent the ordered set of days in the distribution schedule with v and w representing individual days. We assume the first day of the distribution schedule is always v = 1. Next, let I represent the set of nodes in the network with individual nodes given by i, j and k. Then, let A_i,j,v be a non-negative integer that represents the requirement in terms of number of loads to move from node i (i.e. the origin) to node j (i.e. the destination) departing the origin on day v. We assume the load requirements A_i,j,v are known with certainty. Next, let N be the set of homogeneous vehicles and let n represent an individual vehicle. We assume each vehicle has enough capacity to fulfill exactly one load requirement per trip. Then, let B_n ∈ I be the starting node of vehicle n and let C_n ∈ V be the first day vehicle n is available. Next, let D_i,j be the travel time from node i to node j as a positive integer number of days, such that D_i,j > 0. We assume the vehicle travel times are known with certainty. For the MVFSP, D_i,j should satisfy the triangle inequality (i.e. D_i,k + D_k,j ≥ D_i,j). However, D_i,j need not equal D_j,i because delays can differ based on the directional flow between any two nodes, e.g. more delays going from node i to node j than going from node j to node i. Finally, we assume D_i,i = 1 to simplify the IP, as we will demonstrate.

The IP has three groups of binary decision variables to represent the possible vehicle activities:

1. to identify whether a vehicle moves between nodes or remains idle at its current node;

2. to track vehicle locations by day; and

3. to identify whether a vehicle has been moved (i.e. is assigned to a loaded move) sometime during the distribution schedule.

First, let X_n,i,j,v = 1 if vehicle n is assigned to move from node i to node j departing on day v, and X_n,i,j,v = 0 otherwise. Note that X_n,i,i,v = 1 means that vehicle n remains idle at its current node i on day v. Our notation for the primary decision variable follows that of Beaujon and Turnquist (1991), who used X_ij(t) to represent loaded moves between nodes i and j in time period t. Second, let Y_n,i,v = 1 if vehicle n is located at node i at the start of day v, and Y_n,i,v = 0 otherwise. Third, let U_n = 1 if vehicle n is moved sometime during the distribution schedule, and U_n = 0 if vehicle n is idle throughout the distribution schedule.

The objective of the IP is to optimally assign vehicles to load requirements. Two initial fleet size cases are possible in the formulation. First, the analyst can initialize the IP with a sufficiently large fleet of vehicles available at the origin nodes on day 1 to meet expected requirements. In this case, the IP will meet all requirements with the minimum number of vehicles. Conversely, the analyst can initialize the IP with an existing vehicle fleet that is perhaps insufficient in number to meet all requirements, in which case the IP should best assign the existing fleet to meet as many requirements as possible, i.e. minimize shortfalls in meeting requirements. To accommodate this case, we introduce a non-negative integer variable S_i,j,v to represent the number of loads that cannot be met with the available vehicles, which is similar to the backordered variable U_ij(t) introduced by Beaujon and Turnquist (1991).

The IP formulation is provided in equations (13)–(13). The formulation is constructed to highlight specific operational aspects of our MVFSP application. Alternative formulations, such as the corresponding reduction to the chromatic number problem, may indeed be more concise:

(1) minimize ∑i∈I∑j∈I j≠i∑v∈Vα*Si,j,v+∑n∈Nβ*Un+∑n∈N∑i∈I∑j∈Ij≠i∑v∈VAi,j,v =0γ*Di,j*Xn,i,j,v 

Subject to:

(2) Yn,i,v=1  ∀n∈N ∀i∈I i=Bn ∀v∈V v=Cn 

(3) ∑i∈I∑v=1Cn-1Yn,i,v=0  ∀n∈N 

(4) ∑i∈I Yn,i,v≤1 ∀n∈N  ∀v∈V 

(5) ∑j∈I Xn,i,j,v≤Yn,i,v  ∀n∈N ∀i∈I ∀v∈V 

(6) ∑i∈IXn,i,j,v-Di,j≥Yn,j,v  ∀n∈N ∀j∈I ∀v∈V v>Cn 

(7) ∑n∈NXn,i,j,v=Ai,j,v-Si,j,v  ∀i∈I ∀j∈I ∀v∈V Ai,j,v>0 

(8) ∑k∈I ∑w=v+1v+Di,j-1Yn,k,w≤BigM*1-Xn,i,j,v  ∀n∈N ∀i∈I ∀j∈I ∀v∈V 

(9) ∑i∈I ∑j∈I j≠i∑v∈VXn,i,j,v≤BigM*Un  ∀n∈N 

(10) Xn,i,j,v∈{0, 1}  ∀n∈N ∀i∈I ∀j∈I ∀v∈V 

(11) Yn,i,v∈{0, 1}  ∀n∈N ∀i∈I ∀v∈V 

(12) Un∈{0, 1}  ∀n∈N 

(13) Si,j,v≥0 and integer  ∀i∈I ∀j∈I ∀v∈V 

Matl et al. (2018) suggest that real-world logistics is often multi-objective with competing priorities. Likewise, the MVFSP has three components with different priorities derived from the literature and operational realities. First, and most importantly, shortfalls in meeting delivery requirements should be avoided at all costs, as given in the first component of equation (1). US Joint Chiefs of Staff (2017) prioritizes time-definite delivery of military forces above all other considerations. Next, the minimum number of vehicles, as reflected in the second component of equation (1), should be prioritized before minimizing the positioning travel days of the vehicle fleet, as given in the final component of equation (1). Similarly, Yu et al. (2011) suggest that adding new vehicles to the fleet is significantly more costly than allowing the existing fleet to travel more miles, and Fleszar et al. (2009) likewise suggest minimizing fleet size before total distance traveled. Therefore, we assume positive, user-defined scalars α, β and γ are associated with the three components, respectively, with α ≫ β ≫ γ to enforce their relative importance. Analysts have flexibility to assign specific values to the scalars that best reflect the priorities of decisions makers.

Equation (2) initializes each vehicle’s starting node on its first day of availability, while equation (3) prevents each vehicle from being located at any node on any day prior to the vehicle’s first availability. Equation (4) permits each vehicle to be at no more than one node on any given day, and equation (5) allows each vehicle to be assigned an activity only if properly positioned at the origin node at the start of the depart day. Equation (6) allows each vehicle to either change locations based on a past assignment or to remain at its current location. To simplify the formulation, a vehicle that remains at a node on any day, i.e. is not assigned an activity (loaded or positioning move), will keep its current location but will be available for assignment the next day, because we assumed D_i,i = 1 by definition. Equation (7) ensures enough vehicles are assigned to meet all required loads between node pairs for each day, subject to any shortfalls. Equation (8) prevents vehicle assignments to other activities while in transit for a current activity and equation (9) ensures only vehicles assigned to some activity are counted as used. In equations (8) and (9), BigM is some large, positive value greater than the maximum number of vehicles possible. Finally, equations (10)–(12) ensure binary variables and equation (13) ensures non-negative integer variables.

Heuristic

The heuristic leverages the same notation as the IP. As with the IP, the algorithm can minimize the use of an existing fleet of vehicles, each with a specific starting location and availability day. Alternatively, the algorithm can be run with no initial vehicles in the fleet. In either case, the algorithm first uses the existing fleet of vehicles (if available) but will always generate enough vehicles to meet all requirements, i.e. there is no chance of a shortfall in meeting requirements with the heuristic. The algorithm iteratively considers each load requirement until all are assigned to some vehicle via one of three options. First, an untasked vehicle that is properly positioned at the requirement’s origin on the depart day is assigned to an unmet requirement (see algorithm lines 7–10). This is the preferred assignment option because it involves no extra positioning of a vehicle. Second, the algorithm could assign an untasked vehicle that has been positioned at some node other than the requirement’s origin, but only if it could have been dispatched (i.e. via a positioning move) to the correct origin in time to execute the requirement by the depart day (see algorithm lines 11–14). This assignment option is preferred to the final option, which is to create a new vehicle in the fleet and assign it to the requirement (see algorithm lines 19–23).

The following pseudocode outlines the MVFSP heuristic algorithm.

Algorithm Military Vehicle Fleet Sizing Problem

1: For each existing vehicle n

2: initialize starting location B_n and availability day C_n; assign Y_n,Bn,Cn = 1

3. End for

4: For each day v

5: While a requirement exists for some node pair (i,j) on this day v; while A_i,j,v > 0

6: For each vehicle n

7: If vehicle n is properly positioned at origin i on day v; if Y_n,i,v = 1

8: assign vehicle n to this requirement; assign X_n,i,j,v = 1

9: update vehicle n location after transit time D_i,j; assign Y_n,j,(v+Di,j) = 1

10: End if

11: Else if vehicle n has been positioned at some node k (not i) for each of the preceding days from today back to the transit time from k to i; if Y_n,k,w = 1 for some k ≠ i and for each day w = v, (v – 1), …, (v – D_k,i)

12: assign vehicle n to this requirement; assign X_n,i,j,v = 1

13: update vehicle n location after transit time D_i,j; assign Y_n,j,(v+Di,j) = 1

14: End if

15: Else

16: vehicle n remains idle at some node k (not i) on day v but is available for assignment the next day; assign Y_n,k,(v+1) = 1

17: End if

18: End for

19: If an existing vehicle could not be assigned to the current requirement

20: add another vehicle; assign n ← n + 1

21: assign new vehicle n to this requirement; assign X_n,i,j,v = 1

22: update new vehicle n location after transit time D_i,j; assign Y_n,j,(v+Di,j) = 1

23: End if

24: update remaining requirement; assign A_i,j,v ← A_i,j,v – 1

25: End while

26: End for

27: Output number of vehicles needed to meet all requirements

28: Output number of positioning days

29: Output computation time

Performance metrics

We introduce several outputs to assess the solution quality and speed of the heuristic compared to the IP. In all test problems in this paper, we assume the IP is initialized with enough vehicles to meet all requirements, so an assessment metric to quantify shortfalls (via S_i,j,v) is unnecessary. Thus, let Veh^o and Veh^h be the minimum fleet size in number of vehicles needed to meet all requirements from the optimal IP and heuristic, respectively. Then, let Time^o and Time^h be the computational time in seconds to determine the number of vehicles and confirm that all requirements are met from the IP and heuristic, respectively. Finally, let PosD^o and PosD^h be the number of positioning days for all vehicles used by the IP and heuristic, respectively. In our formulation, there is no distinction between executing the positioning earlier than required or arriving at the pickup location just in-time, although this could be an area of future work on this problem. The positioning days are computed using our earlier notation, as given in equation (14):

(14) ∑n∈N∑i∈I∑j∈Ij≠i∑v∈VAi,j,v =0Di,j*Xn,i,j,v 

Next, we construct three assessment measures using the outputs previously defined. First, let SolnErr be the relative percent error in number of vehicles used by the heuristic solution compared to the IP solution, as defined in equation (15). This metric relates to the second objective function component, i.e. minimizing the number of vehicles in the fleet:

(15) SolnErr=Vehh-VehoVeho *100 

Second, let PercTime be the percent of computation time used by the heuristic solution compared to the IP solution, as defined in equation (16):

(16) PercTime=TimehTimeo *100 

Finally, let PosErr be the relative percent error in positioning days used by the heuristic solution compared to the IP solution, as defined in equation (17). This metric relates to the third, and least important, objective function component, i.e. minimizing positioning miles:

(17) PosErr=PosDh-PosDoPosDo *100 

Results

In this section, we solve two types of problems. First, we randomly generate and solve small-scale problems using both the IP and heuristic to assess the accuracy and computational efficiency of the heuristic. Second, we use the heuristic to solve a notional, large-scale problem with the size and complexity of a realistic MVFSP at the US Transportation Command.

Software and hardware specifications

The IP was implemented in the General Algebraic Modeling System v24.3.3 software with a CPLEX solver. We set an optimality tolerance of 1% and a maximum time limit of 100,000 s for CPLEX to solve the IP. We implemented the heuristic algorithm in the RStudio v1.1.453 software (Team, 2017) using R v3.5.1. All solutions for the IP and heuristic problems studied were generated on a 64-bit Windows 7 computer with an Intel Xeon CPU at 3.33 GHz and 48 GB of RAM.

Random, small-scale problems

We arbitrarily selected five Army installations and five seaports in the USA to serve as our origin and destination nodes, respectively, for the small-scale problems. Table 1 gives the nodal information for the installation and port nodes. Table 2 gives the travel times in days between each node pair of the small-scale problems. We assumed symmetrical travel times between node pairs for our problem, but they need not be symmetrical for other problems.

Next, we randomly assigned values to key variables for the small-scale problems, as in Table 3. We generated three sets of random problems: sets A, B, and C with 10, 20 and 40 distinct A_i,j,v requirements for each problem instance, respectively. Note that each requirement is assigned from one to four loads, per the random attributes in Table 3, so the total number of loads are restricted to no more than 40, 80 and 160 for sets A, B and C, respectively. For set A, we assumed 20 vehicles were available to each problem instance, i.e. |N| = 20; for set B, we assumed 25 vehicles were available; and for set C, we assumed 50 vehicles were available. Finally, we assumed objective function scalars of α = 10⁶, β = 10⁴ and γ = 1 for the IP, which were derived by analysts balancing the competing objectives of, most importantly, meeting all requirements followed by minimizing fleet size and then, least importantly, reducing empty positioning miles.

For our empirical analysis, we generated 40 small-scale problem instances: 15 in set A, 15 in set B, and 10 in set C. For each set, we generated five base problem instances (A1, A2, …, A5; B1, B2, …, B5; C1, C2, …, C5) using the randomly assigned attributes from Table 3. Next, we generated additional, correlated problem instances with wider delivery windows by multiplying the depart day v of each requirement by two for sets A, B and C, and then by three for only sets A and B due to computational challenges solving the relatively larger problems in set C. The resultant wider delivery windows introduced a time spread (or scaling) of the requirements, which generated 25 new problems. Our rationale for this scaling was to control all random attributes except the timing of requirements, which should result in fewer vehicles needed due to more vehicle cycling given increased time between scaled requirements. Tables 4, 5 and 6 show the IP and heuristic solution results for the problem instances of sets A, B and C, respectively.

The assessment measures for all problem instances are shown in Table 7. The heuristic yielded SolnErr values of no more than about 8% of optimal and indeed matched the optimal in 36 of the 40 small-scale problems. The associated PercTime results were less than about 3.3% in the worst case and less than 0.3% in most cases. Finally, the positioning error, PosErr, is larger with an average of about 59% and a worst-case error of about 159%.

Figure 1 shows the daily activity of each vehicle in terms of loaded trips (black boxes), empty positioning trips (dark gray boxes) or idle time between trips (light gray boxes) for the optimal and heuristic solutions for problem B1 with depart day v multiplied by three. The optimal [Figure 1(a)] and heuristic [Figure 1(b)] solutions each required 11 vehicles, but the positioning days were 110 for the optimal and 137 for the heuristic.

Notional, large-scale problem

Our notional, large-scale MVFSP involves moving military equipment exclusively via rail in the USA from 126 origins to 24 ports. The problem calls for 21,164 distinct requirement loads occurring over 180 days in the distribution schedule, which is similar to real-world MVFSPs at the US Transportation Command. The maximum travel time is 10 days between any node pair.

We solved the large-scale problem with the heuristic in about 11 h. Figure 2 is a stacked bar chart that shows the total number of vehicles needed by day to meet requirements. As in Figure 1, the black bars represent vehicles executing a loaded movement, the dark gray bars represent vehicles executing a positioning movement, and the light gray bars represent idle vehicles on that day.

Discussion

Analysts at the US Transportation Command value three solution qualities: accuracy, speed and interpretability. First, we consider the accuracy of our solution approach. Several researchers from the literature compared the performance of heuristics against corresponding optimal solutions for various fleet sizing problem instances. Liu (2016) reported heuristic fleet size errors between 0 and 15% compared to the optimal for 50 small-scale problem instances. Raa (2015) reported average heuristic errors of about 0.5% for 80 problems with a small number of routes and average errors of about 0.4% for 80 problems with a large number of routes. Vidović et al. (2014) reported heuristic solutions within 4–7% of optimal for 100 small-scale problem instances. Similarly, Salhi et al. (2013) achieved heuristic results within about 5% of the optimal on average for 36 small-scale problem instances. Finally, the heuristic developed by Belfiore and Yoshizaki (2013) achieved an average error of 3.6% across 55 problem instances.

Our heuristic gives fleet size errors within about 0.7% on average, but no more than 8%, of optimal for the 40 small-scale problems tested. The heuristic yields positioning errors of about 59% on average, but as much as about 159%, of optimal for the problems tested. A possible reason for the relatively high positioning error of the heuristic stems from its decision logic that assesses only a vehicle’s ability to position to another location in time to meet a requirement and not necessarily selecting the closest vehicle that can be positioned. Adjusting the heuristic to consider minimum positioning days is a possible extension but would add computation time to the algorithm. Thus, analysts must weigh the benefits of improvements in a tertiary problem objective (positioning days) against the increased algorithm runtime.

In addition, the resultant vehicle fleet sizes generally decrease, as expected, when requirements are spread out by a factor of two or three from the base problem, as depicted in Tables 4, 5 and 6. This spreading of delivery requirements, while holding other random variates constant (i.e. from-to nodes, number of loads), seems to correctly mimic real-world cycling of an existing fleet, thereby reducing the required fleet size.

Next, we consider the relative speed of our heuristic. A runtime of about 11 h for a large-scale problem is a vast improvement to the week-long, iterative (and manual) process using the previous simulation-based method. In fact, the real time savings to the analyst are greater, because the analyst can setup the heuristic to run overnight during non-office hours.

Finally, we consider the interpretability of the solution output, as in Figure 2. The graphic suggests that the peak vehicle usage is on day 25 with 3,269 distinct vehicles in the fleet needed to satisfy all requirements. Furthermore, the “loaded” missions (at about 2,100) on the peak day do not account for all vehicle states, because some vehicles are either (1) involved in empty vehicle positioning on the peak day for loaded missions either before or after the peak day, or (2) idle on the peak day but required for a subsequent mission. Such interpretable visual insights are useful to analysts at the command, e.g. to better understand how vehicles requirements change over time.

Conclusions and future work

Our traditional heuristic gives near-optimal solutions to small-scale vehicle fleet sizing problems in just a few seconds and, more importantly, provides solutions to large-scale problems that are indicative of operational problems encountered at the US Transportation Command in about 11 h. The heuristic consistently provides solutions within about 1% of the optimal vehicle fleet size for small-scale test problems, which is the primary measure of solution quality. The greedy heuristic performs poorly on the less important measure of minimizing positioning days with errors of about 59% on average.

The fleet size solution quality, ease of use, interpretability and associated time savings of about a week from this new heuristic approach are useful to analysts at the US Transportation Command, who had previously used simulations in a trial-and-error, iterative manner to estimate military vehicle fleet sizes. As such, our heuristic fills an analytic gap at the US Transportation Command. The new heuristic has been used to estimate the fleet size for land movements supporting a Geographic Combatant Command and has been endorsed by US Transportation Command leaders as a better method to inform railcar recapitalization decisions for the US Army.

Future work on the MVFSP could include several key extensions and new solution approaches. As noted earlier, the formal computational complexity of the MVFSP should be analyzed, perhaps via a reduction to the chromatic number problem. Second, the timing of vehicle positioning could be incentivized to occur early to overcome possible transit delays or to arrive just in-time to reduce congestion at the pickup location. Third, the heuristic could be improved to select the closest vehicle to position to meet a requirement, which should reduce the error in positioning days but would increase algorithm runtimes. Fourth, most realistic military vehicle fleets have heterogeneous vehicles with different types preferred for hauling certain types of equipment, e.g. heavy and wide railcars to haul military tanks vs light and narrow railcars to haul smaller military trucks. As such, the heuristic could be extended to allow a heterogeneous fleet of military vehicles subject to various operational constraints, such as proposed by Abbass et al. (2006). Fifth, some aspects of real-world problems are inherently stochastic, such as the timing of demands and travel times between locations. Demands and travel time fluctuations are especially likely in a military environment given possible enemy disruptions to the network (U.S. Joint Chiefs of Staff, 2013a). The MVFSP heuristic could be modified to consider stochastic demands, similar to other researchers (Beaujon and Turnquist, 1991; Webb and Larson, 1995; Kochel, 1997; Diana et al., 2006; Stålhane et al., 2019), as well as stochastic travel times, similar to Diana et al. (2006) and Beaujon and Turnquist (1991). In this area, simulation-based methods may also be useful. As a final extension, the present heuristic makes no attempt to balance the workload of current vehicles in the fleet. Vehicle workload balancing was considered by Liu (2016) for the fleet sizing problem and by Matl et al. (2018) and Lee and Ueng (1999) for the VRP. A more balanced workload between existing vehicles would be more operationally realistic and could reduce mechanical breakdowns of overused vehicles.

Different solution approaches could also be applied to this operational problem. The present work solved the MVFSP with a constructive heuristic, which could settle at a local optimal with no mechanism to escape to the global optimal. Thus, other researchers might apply evolutionary or local search heuristics, perhaps in conjunction with graph coloring methods, to solve this transportation problem. The reader is directed to the review of local search heuristics for graph coloring problems by Galinier and Hertz (2006). Finally, future researchers might use alternative multi-objective solution techniques to improve the quality of MVFSP solutions.

Figures

Figure 1.

Optimal (a) and heuristic (b) solutions for problem B1 with depart day v scaled by 3; black box is a loaded move, dark gray box is a positioning move and light gray box is idle time

Figure 2.

Heuristic solution for large-scale problem; black bar is a loaded move, dark gray bar is a positioning move and light gray bar is idle time

Table 1.

Nodal information for random problems

Node ID	Node type	Name	State
1	Installation	Fort Carson	Colorado
2	Installation	Fort Drum	New York
3	Installation	Fort Hood	Texas
4	Installation	Fort McCoy	Wisconsin
5	Installation	Fort Riley	Kansas
6	Port	Oakland	California
7	Port	Philadelphia	Pennsylvania
8	Port	Tacoma	Washington
9	Port	Wilmington	North Carolina
10	Port	Beaumont	Texas

Table 2.

Node-to-node travel time matrix (in days)

Node ID	1	2	3	4	5	6	7	8	9	10
1		4	2	3	2	3	4	3	4	3
2	4		4	2	3	6	1	6	2	4
3	2	4		3	2	4	4	5	3	1
4	3	2	3		2	4	2	4	3	3
5	2	3	2	2		4	3	4	3	2
6	3	6	4	4	4		6	2	6	4
7	4	1	4	2	3	6		6	1	3
8	3	6	5	4	4	2	6		6	5
9	4	2	3	3	3	6	1	6		3
10	3	4	1	3	2	4	3	5	3

Note:

From nodes are shown on the vertical and To nodes are shown on the horizontal

Table 3.

Attributes assigned to key variables for random problem sets

Variable description	Variable	Assignment rule
Installation (origin)	i	Discrete uniform random number in [1, 5]
Port (destination)	j	Discrete uniform random number in [6, 10]
Depart day	v	Discrete uniform random number in [1, 18]
Number of loads	Ai,j,v	Discrete uniform random number in [1, 4]
Vehicle start location	Bn	Discrete uniform random number in [1, 5]
Vehicle start day	Cn	1

Table 4.

Results for random problem set A (10 requirements each problem instance)

Problem instance	Days scaled	Integer program			Heuristic
		Veho [LB]	Timeo (s)	PosDo	Vehh	Timeh (s)	PosDh
A1	1	14 [*]	60	31	15	2	48
A1	2	14 [11]	135	27	14	2	70
A1	3	12 [8]	5,656	32	12	3	77
A2	1	15 [10]	1,490	33	15	1	58
A2	2	11 [7]	17,372	46	11	2	70
A2	3	9 [6]	19,869	49	9	3	60
A3	1	15 [14]	338	49	15	2	67
A3	2	12 [9]	2,533	45	12	2	74
A3	3	11 [9]	10,683	47	11	3	74
A4	1	16 [15]	550	17	16	1	43
A4	2	11 [9]	41,283	36	11	3	57
A4	3	10 [5]	24,179	38	10	3	62
A5	1	13 [*]	383	39	13	3	66
A5	2	11 [7]	17,440	49	11	5	85
A5	3	11 [4]	13,533	54	11	5	88

Notes:

LB = lower bound as of 100,000 second CPLEX limit; *Proven optimal

Table 5.

Results for random problem set B (20 requirements each problem instance)

Problem instance	Days scaled	Integer program			Heuristic
		Veho [LB]	Timeo (s)	PosDo	Vehh	Timeh (s)	PosDh
B1	1	25 [*]	168	78	25	2	119
B1	2	16 [6]	10,290	105	16	2	134
B1	3	11 [6]	72,004	110	11	3	137
B2	1	24 [*]	94	62	24	1	93
B2	2	16 [9]	16,676	73	16	2	127
B2	3	15 [9]	31,741	76	15	3	130
B3	1	25 [*]	105	88	25	2	114
B3	2	19 [10]	1,051	86	19	3	137
B3	3	14 [7]	19,407	100	14	3	138
B4	1	21 [17]	1,428	72	22	1	123
B4	2	18 [10]	29,348	79	18	3	133
B4	3	15 [7]	5,134	88	16	4	140
B5	1	24 [19]	130	58	24	2	74
B5	2	17 [9]	1,946	68	17	2	109
B5	3	12 [5]	53,071	84	12	3	144

Notes:

LB = lower bound as of 100,000 second CPLEX limit; *Proven optimal

Table 6.

Results for random problem set C (40 requirements each problem instance)

Problem instance	Days scaled	Integer program			Heuristic
		Veho [LB]	Timeo (s)	PosDo	Vehh	Timeh (s)	PosDh
C1	1	46 [18]	5,659	100	46	3	171
C1	2	29 [8]	69,089	162	29	6	235
C2	1	45 [20]	51,548	133	45	3	204
C2	2	30 [9]	61,772	201	30	6	255
C3	1	42 [28]	32,736	127	42	4	200
C3	2	25 [16]	72,489	234	27	5	269
C4	1	48 [20]	26,823	108	48	4	187
C4	2	25 [7]	70,666	174	25	3	175
C5	1	48 [46]	3,114	126	48	4	203
C5	2	28 [9]	78,613	199	28	4	254

Notes:

LB = lower bound as of 100,000 second CPLEX limit; *Proven optimal

Table 7.

Assessment measures for random problems

Problem instance	Days scaled	Assessment measures
		SolnErr (%)	PercTime (%)	PosErr (%)
A1	1	7.1	3.3	54.8
A1	2	0.0	1.5	159.3
A1	3	0.0	0.1	140.6
A2	1	0.0	0.1	75.8
A2	2	0.0	<0.1	52.2
A2	3	0.0	<0.1	22.4
A3	1	0.0	0.6	36.7
A3	2	0.0	0.1	64.4
A3	3	0.0	<0.1	57.4
A4	1	0.0	0.2	152.9
A4	2	0.0	<0.1	58.3
A4	3	0.0	<0.1	63.2
A5	1	0.0	0.8	69.2
A5	2	0.0	<0.1	73.5
A5	3	0.0	<0.1	63.0
B1	1	0.0	1.2	52.6
B1	2	0.0	<0.1	27.6
B1	3	0.0	<0.1	24.5
B2	1	0.0	1.1	50.0
B2	2	0.0	<0.1	74.0
B2	3	0.0	<0.1	71.1
B3	1	0.0	1.9	29.5
B3	2	0.0	0.3	59.3
B3	3	0.0	<0.1	38.0
B4	1	4.8	<0.1	70.8
B4	2	0.0	<0.1	68.4
B4	3	6.7	<0.1	59.1
B5	1	0.0	1.5	27.6
B5	2	0.0	0.1	60.3
B5	3	0.0	<0.1	71.4
C1	1	0.0	0.1	71.0
C1	2	0.0	<0.1	45.1
C2	1	0.0	<0.1	53.4
C2	2	0.0	<0.1	26.9
C3	1	0.0	<0.1	57.5
C3	2	8.0	<0.1	15.0
C4	1	0.0	<0.1	71.6
C4	2	0.0	<0.1	0.6
C5	1	0.0	0.1	61.1
C5	2	0.0	<0.1	27.6
Average		0.7	0.3	58.9
Worst case		8.0	3.3	159.3