1 Introduction

This project addresses the problem of Arkansas’s and other states’ underutilized waterway transportation networks. The underutilization of waterway transportation in the U. S. partially stems from a lack of understanding by shippers of the cost and time trade-offs associated with utilizing waterway transportation. There exists a need for easy to use and widely available models that can illustrate the advantages and disadvantages of barge transportation within the context of an intermodal transportation network. This project enhances prior MTBC research on intermodal transportation by enhancing intermodal shortest route models and demonstrating the models via a user-friendly, web-based application. An understanding of the intermodal decision process was developed through interaction with companies in and around the State of Arkansas.

· ShipCost calculations make assumptions concerning the final dray charges and transfer times that may underestimate the total transportation cost.

· ShipCost’s transfer time calculation assumes that all containers are moved simultaneously. A more realistic assessment should be made on a per-container basis. In addition, the software assumes that all containers are full. No less than container transport is allowed.

· The software does not correctly account for driver rest time if the travel time exceeds 10 hours.

· Due to its limitations on network size, the double sweep algorithm, developed by Shier and employed in ShipCost software, may not be feasible for the application to shipping scenarios of realistic size.

· Many of the costs assumed within the calculations are based on average (across network) costs and thus may not realistically capture the city and modal differences within the cost computations.

· ShipCost does not model the possibility of different freight rates bases on weight or volume to be shipped or allow for analysis of the impact of inventory fill-rates for the supplier.

The project report presents a literature review of ShipCost and other related background information and identifies the gaps related to the current project. This report further provides information on the design of the database and algorithm architecture that supports WebShipCost. The report also gives an overview of the implementation details and the algorithm processing details.

2 Background

This section presents an overview of prior modeling involving ShipCost and related intermodal literature. We also discuss the use of the waterways by Nucor Steel and some of their issues related to the intermodal choice decision.

2.1 ShipCost Overview

Prior MTBC research projects (MBTC FR 1036, MBTC FR 1079, MBTC FR 1100-1) contributed to the development of ShipCost, a PC/Windows implementation of cost models that describe the costs incurred by all activities (rail, truck, and barge) within an intermodal transportation network. ShipCost consists of a database, the double-sweep algorithm for solving the k-shortest paths model, and a user interface. The information below summarizes the cost elements and computations used in ShipCost. This analysis is based on data from research at University of Arkansas [1] and the ShipCost user’s manual [2]. The information is also derived from a detailed analysis performed for the Defense Logistics Agency [TLI-AR00-2].

ShipCost performs its analysis based on a formulation of the total transportation cost comprising of four elements: travel cost, transfer cost, drayage charges, and inventory carrying cost. Travel cost is the cost to transport goods by the selected travel mode. The transport cost rate within ShipCost is an average derived from several commercial and government sources. The distances between origin/destination pairs for each travel mode must be available to ShipCost. The distances currently within ShipCost were taken from various commercial and government publications and from mapping software programs. The cost of transferring goods from one mode of travel at the load/unload site to another travel mode is the transfer cost. Transfer cost includes the cost of labor and equipment at any intermediate points where there is a change in travel mode. Drayage charges are incurred for moving goods to/from a stationary site, such as a warehouse or factory, from/to the loading site for transport. The fourth element of transportation cost is the in-transit inventory carrying cost. Inventory carrying cost is a function of the number of individual units being shipped and of the total transit time of a shipment. Typical carrying costs include storage space, insurance, taxes, loss due to spoilage or obsolescence, opportunity cost, etc. The user inputs the inventory carrying rate as an annual percentage value, typically 10-15%. Unlike travel cost, drayage cost, and transfer cost, which are based on the number of containers in the shipment, inventory cost is based on the number of items shipped and their purchase price or production cost.

The user of ShipCost software must input the number of units being shipped and the number of units per container. The standard unit of shipment is via containers, which are defined as large boxes, approximately 8 feet high, 8 feet wide, and 20-55 feet long that can be transported by rail, truck, or water carrier. The capacity of a container is considered to be 15 tons. After user input of the origin, destination, shipment information, and objective (minimize total cost or total time of the shipment), the system displays the alternatives in order of increasing cost or time. The user can then compare the alternatives to the shipment’s requirements, such as service level or commodity type, and choose the best-suited alternative. The user can also define additional networks to be analyzed by ShipCost.

The original ShipCost study focused on the Mississippi River System, the Gulf Coast, and international shipments to Mexico [1]. It should be noted that the Mississippi River System encompasses the Arkansas River, the Alabama River, the Ohio River, the Illinois River, and the Missouri River. Table 1 identifies the cities, area of location, and the river on which the city is located [1].

Table 1 City Location and River

City Name	Location	River
Brownsville	Gulf Coast	Gulf Coast
Chicago	Midwest	Illinois
Cincinnati	Northeast	Ohio
Houston	Gulf Coast	Gulf Coast
Little Rock	South	Arkansas
Memphis	Midwest	Mississippi
Mobile	Southeast	Alabama
New Orleans	South	Mississippi
Omaha	Midwest	Missouri
Pittsburgh	Northeast	Ohio
St. Louis	Midwest	Mississippi
St. Paul	Midwest	Mississippi
Veracruz	Mexico/Central America	Ocean

The type of vessel used in this analysis is a standard river barge. The dimensions of a standard river barge are 195 X 35 X 9 X 12 (length, beam, draft, depth). Depending upon the tow size the amount of horsepower needed can range from 2,000 to 10,000. Due to the fact that most truck trailers are 48 or 53 feet long, the number of containers that a barge can carry is slightly less than 70. The commodities considered in the study are those that are non-time sensitive particularly of high volume and low value (For an extensive list of commodities being shipped in and out of each of the ports considered in the analysis consult p.76-86 of [1]). A few commodities cited that could possibly be transported via barge that currently aren’t being shipped by this mode of transportation are waste paper, old cardboard, mini steel beams, clay, cotton seed pellets, as well as various chemicals. The main concern is that the item is non-perishable. The container considered in the analysis is assumed to be a fifteen-ton container (detachable truck trailer).

2.2 ShipCost Cost and Time Data

In this section, we present an overview of the basic cost and time data assumptions that were used within the ShipCost application. The data involved in developing the ShipCost application include: distances, transportation rates, drayage costs, average speeds for the modes, transfer costs and times, and inventory holding costs. All ShipCost data assumptions are duplicated in the WebShipCost application.

2.2.1 Distances

When leaving a destination by barge, rail, or truck (highway) and entering a city/mode combination, distances are defined in barge (water), rail, or truck (highway) miles respectively. These distances are stored in the database as described in section 3.3 and are obtained from References [3,4,5].

2.2.2 Transportation Rates

The transportation rates by mode were obtained by averaging rate estimates obtained from multiple sources. All rate units are converted into dollars per container-mile. In order to perform necessary conversions, the following assumption is made:

· The standard container holds 15-tons [6].

Therefore, estimated rates in units of dollars per ton-mile were converted into dollars per container-mile by multiplying them by 15 tons per container.

2.2.2.1 Barge Transportation Rate

Table 2 contains the estimated and resulting average inland barge transportation rates.

Table 2 Inland Barge Transportation Rates

Source	Rate ($ per ton-mile)	Rate ($ per container-mile)
Pittsburgh Waterways Commission [7, 16]	$0.008	$0.12
Arkansas Waterways Commission [6]	$0.0097	$.1455
Haulk report [9]	$0.0073	$.1095
Chew report [10]	$0.0079	$0.1185
Average	$0.0083	$0.1234

As shown in Table 2, the inland barge transportation rate utilized in ShipCost is $0.1234. To convert the inland barge transportation rate into gulf coast and ocean going barge rates, the following assumptions are made:

· The rate for barges traveling along the gulf coast is assumed to be twice the inland barge transportation rate or $0.2468 [11].

· The rate for ocean going barges is assumed to be four times the inland barge transportation rate or $0.4935 [11].

2.2.2.2 Rail Transportation Rate

Table 3 contains the estimated and resulting average rail transportation rates.

Table 3 Rail Transportation Rates

Source	Rate ($ per ton-mile)	Rate ($ per container-mile)
Arkansas Waterways Commission [6]	$0.0253	$ 0.3795
Haulk report [9]	$0.0249	$0. 3735
Chew report [10]	$0.020	$0.30
Average	$0.0234	$0.3510

As shown in Table 3, the rail transportation rate utilized in ShipCost is $0.3510.

2.2.2.3 Truck Transportation Rate

Table 4 contains the estimated and resulting average truck transportation rates.

Table 4 Truck Transportation Rates

Source	Rate ($ per ton-mile)	Rate ($ per container-mile)
Howard [12]	$0.06	$ 0.90
Average	$0.06	$0.90

The following assumptions are made [12]:

· The truck transportation rate given in Table 4 applies to long hauls.

· The long haul rate is doubled for regional hauls to $1.80 per container-mile.

The rate for local hauls is assumed to be $3.00 per container-mile.

2.2.3 Drayage Costs and Lengths

Drayage costs/lengths include: (1) the cost/distance of transporting shipments from a shipper’s location (plant, warehouse, etc.) to the barge or rail terminal and (2) the cost/distance of transporting shipments from the barge or rail terminal destination to the final location (warehouse, store, etc.).

The following assumptions are made:

· Drayage cost/distance can be adequately represented as an average cost.

· Drayage cost/ distance is not incurred when transferring between modes or intermediate cities.

2.2.3.1 Truck-to-Barge Drayage Cost/Length

The average truck-to-barge drayage cost/distance per shipment was calculated using the following procedure:

1) Latitude and Longitude numbers for barge terminals at each city included in the study were obtained from the US Army Corps of Engineers [13]. This data is contained in Appendix F of Boardman’s report (1998). Approximately 25 terminals for each city were evaluated.

2) All zip codes for each city obtained from the United States Postal Service website [14].

3) Latitude and Longitude numbers for all zip codes in each of the cities were obtained from freight density records provided by J.B Hunt [15].

4) The Euclidean distance (D) in miles between each terminal and zip code for each city were calculated as follows:

5) The average truck-to-barge drayage length was calculated by computing the average length of all distances resulting from the previous Step 4.

6) Average truck-to-barge drayage cost per container was calculated by multiplying the average truck-to-barge drayage length by the $3.00 cost per local haul mile.

7) To compute the average truck-to-barge dray cost per shipment, the average truck-to-barge drayage cost per container is multiplied by 2 to account for both origin and destination drayage costs.

The summarized results of this analysis are found in Table 5. The full results are presented in Appendix F of Boardman’s report (1998).

Table 5Average Truck-to-Barge Drayage Cost Results

Length (miles)	Cost ($ at each end)	Cost ( per shipment)
14.67	$44.03	$ 88.06

2.2.3.2 Truck-to-Rail Drayage Cost

The average truck-to-rail dray cost was obtained from Howard [12] and is shown in Table 6.

Table 6 Average Truck-to-Rail Drayage Cost

Cost ($ at each end)	Cost ($ per shipment)
$50.00	$ 100.00

2.2.4 Average Mode Speeds

Throughput time (T_T) for each mode is calculated from the following equation:

Transfer time is accounted for in the average speed of each mode. The average speeds of each mode and the respective source of information are shown in Table 7.

Table 7 Average Mode Speed

Mode	Speed (miles per hour)	Source
Barge - Inland waterway	6	McCarville [7], Christy [8], COCITE Memphis Meeting participants [16].
Barge - Coastal waterway	4
Barge – Ocean going waterway	10
Rail	37	Howard [12]
Truck	42	Howard [12]

2.2.5 Transfer Costs and Time

2.2.5.1 Barge Transfer Cost and Time

The amount of time and associated cost of transferring containers from barge to another mode or from another mode to barge and the sources of this data are presented in Table 8. These values are not city specific and represent an average across all cities included in the network.

Table 8 Barge Transfer Cost and Time

Mode

Cost ($ per container)

Time (hours per container)

Source

Barge

$100

0.17

McCarville [7], Christy [8], Pittsburgh COCITE workshop [17]

2.2.5.2 Truck / Rail Transfer Cost and Time

The amount of time and associated cost of transferring containers from truck or rail to another mode or from another mode to truck or rail at each city in the network [12] are presented in Table 9.

Table 9 Truck / Rail Transfer Cost and Time

City	Cost ($ per container)	Time (hours per container)
Brownsville	$50	0.1
Chicago	$75	0.1
Cincinnati	$65	0.1
Houston	$75	0.1
Little Rock	$50	0.1
Memphis	$50	0.1
Mobile	$50	0.1
New Orleans	$60	0.1
Omaha	$50	0.1
Pittsburgh	$65	0.1
St. Louis	$65	0.1
St. Paul	$65	0.1
Veracruz	$35	0.1

2.2.6 Inventory Holding Costs

Inventory carrying cost is defined as the annual cost of carrying one unit of an item in inventory. Typical costs accounted for in the computation of inventory carrying cost are cost of capital invested, cost of deterioration, obsolescence, pilferage, insurance, taxes, and storage. The inventory carrying cost is computed from the following equation:

2.3 Relevant Literature

The literature contains limited articles focused on intermodal shortest path identification. Grasman and Karunakara [18] formulate a multimodal logistic system to minimize cost within service time requirements. Their cost model includes transport cost of road, rail, sea, and air and transfer costs of ports and rail freight terminals. The multimodal transportation network is a deterministic cyclic network with no negative cycles. Dijkstra’s algorithm [19] is used to determine the optimal multimodal transportation network. In their paper, they gave the mathematical formulation and illustrative examples without identifying a real world network. The Shortest Path problem lies in the core of many transportation and logistics problems. It has been extensively studied since the late fifties.

In deterministic cyclic network, Dijkstra’s algorithm [19] provides the basis for the most efficient algorithms known for solving this problem. It required for every arc in the network. Most computational improvements for solving shortest path problems have resulted from improving the data structures used to implement Dijkstra’s algorithm. This algorithm is a label-setting algorithm in that a label is made permanent at each iteration. Ford’s algorithm [20] is the first label-correcting algorithm for the shortest path problem. Label-correcting algorithms have the feature that no label is permanent until the algorithm terminates. A class of label-correcting algorithms called partitioning algorithms was proposed by Glover et al. (1985a). Another procedure was proposed by Yen [21]. These algorithms can detect negative cycles in the network to avoid unbounded solutions. Floyd [22] and Dantzig [23] show two algorithms which can find the shortest path between each pair of nodes. Tabourier [24] gave a modified Dantzig’s procedure which has considerably more efficient.

Instead of finding one optimal path, the k – shortest path problem is to list the k paths connecting a given source – destination pair in the network. Shier [25] talked about three methods for calculating the k shortest path from a given node to all other nodes of a network. Among these three methods, he showed that the Double Sweep method seems to dominate not only from a theoretical standpoint but also in terms of the computational standpoint. It offers a quite effect procedure for determining the k shortest path from a given node to all other nodes in a network. Two other methods named “the Jacobi method” and “the Gauss-Seidel method”. Eppstein [26] listed an overview of the k- shortest algorithms and showed an algorithm with superior computational complexity.

A variety of cost based transportation models have been proposed. Cunningham [27] and Mcginnis [28] reviewed the literature and gave a collection of general transportation models. Among them, four cost based models have been reported.

· Classical Economic Model, which is best described by the writings of Meyer et al. [29] and Friedlaender [30];

· Inventory-Theoretic Model, This approach sought to optimize modal choice by considering the “trade-off among freight rates, speed, dependability and enroute lossage”;

· Trade-Off Model, in this model, rational shipper’s choice between two model alternatives will minimize the sum of two cost categories, transportation costs and nontransportation costs;

· Constrained Optimization Model, McGinnis, Corsi and Roberts [31] concluded that the transportation choice process was a constrained optimization process with transportation costs and nontransportation costs such as product constraint, distribution pattern constraint and service need constraint.

Among them, the “Constrained Optimization Model” has been explained the findings of a wide range of transportation choice studies.

In the following section, we present a summary of how Nucor Steel Hickman utilizes intermodal transportation.

2.4 Summary of Nucor Report

In order to obtain insight into how major waterway users approach the intermodal choice decision, we formed a partnership with Nucor Steel Hickman. This partnership resulted in “Nucor Steel – Arkansas’s Coils And David J. Joseph Company’s Scrap Metal Shipping on the Waterways 2002.” This section summarizes the basic information found during the interaction with Nucor Steel. The full report is located in Section 6.8 of the Appendix. The project contact, Donna L. Jones Reams, has worked at Nucor Steel Hickman in Blytheville, Arkansas since 1991 and is presently a planner in the maintenance department.

Nucor and its affiliates are manufacturers of steel products, with operating facilities in ten states and have more than 8,000 employees. Products produced are: carbon and alloy steel -- in bars, beams, sheet, and plate; steel joists and joist girders; steel deck; cold finished steel; steel fasteners; metal building systems; and light gauge steel framing. Consolidated sales for Nucor Corporation in 2001 were $4,139,000,000 with consolidated earnings of $113,000,000.

Nucor Hickman can receive and ship products just in time with easy accessibility to three modes of transportation that includes the waterway, the railway and trucking. Customers have the opportunity to take advantage of any of the three modes of transportation when they purchase flat rolled sheet products, including free transportation. The Nucor Hickman mini mill began in 1992 producing 1.2 million tons annually. At that time 35% of the product was shipped by barge, 27% by rail and 10% by truck. 28% was shipped by the Nucor rail, to local customers that take advantage of the free shipping opportunities. Nucor Hickman shipped 2,023,070 tons in 2001 to 194 customers. Table 10 contains the amount of hot and cold mill product shipped by each mode of transportation in 2001.

Table 10 2001 Product Tons Shipped by Mode

Mode of Transportation	Hot Mill Tons Shipped	Cold Mill Tons Shipped
Barge	261,699.88	152,151.18
Rail	201,688.53	224,379.31
Truck	88,0561.14	235,049.52
Nucor Rail	67,541.13	0

Every year the Nucor Hickman Materials Manager re-negotiates and/or oversees the shipping freight cost from all the different vendors that provide a mode of transporting the product. The re-negotiation for the waterways is done annually. Rail systems negotiation takes place every quarter by the Material Handling Manager. The dispatcher or freight administrator, who is directed by the Material Handling Manager, negotiates trucking daily. Nucor Hickman’s goal is to get the best possible price for transporting the product to the customer and charge the customer that same negotiated price. Nucor Corporation is constantly searching for ways to meet the customer’s transportation needs and is certainly utilizing the waterway to receive material and products.

The report also contains information about the David J. Joseph Company (DJJ), which is the largest scrap broker in the United States. In the year 2001 the DJJ Company moved 43% of material by rail, 33% by barge, 20% by truck and 4% by vessel to its customers. The material that Nucor Hickman received in 2001 from the DJJ Company was shipped 85% by barge, 8% by truck, 7% by rail. The DJJ Company is constantly searching for ways to use the waterway as a primary mode of transportation for their customers.

Nucor Hickman and the David J. Joseph Company are utilizing the waterways. They are searching for the most economical mode of transportation to meet the customer’s needs. Their choice of waterway use depends heavily on three factors: economics of the transport, proximity to waterways, and type of cargo to be transported. Transporting by barge or vessel can be the most economical mode of transportation if there is proper planning and the waterway can be monitored closely.

3 WebShipCost Application

In this section, we discuss the results of the software analysis, design, and implementation phases of the project. The purpose of analysis is to fully understand the problem, application domain, and system requirements in order to yield a precise model of the real world situation. The purpose of design is to transform the analysis concepts into concrete software artifacts. Finally, the purpose of implementation is to translate the design artifacts into programming code. We first present a description of the use cases identified for the application, and then present the conceptual models that support the new functionality within WebShipCost. We then discuss the design of the underlying data model and algorithms involved in the intermodal shipment problem. Finally, we present an overview of the web application (architecture and user-interfaces) along with some testing results.

3.1 Use Case Models

A use case is a statement of high-level functional system requirements in narrative text. Use cases serve as the basis for the software requirements and for setting the stage for the early identification of objects within the system. In addition, use cases serve as a basis for system test development. Use cases should emphasize top-level functions and interfaces based on the viewpoint of an actor. An actor is a well-defined role for a user or group of users. Actors can be people or they may be other systems with which the system interacts. Use cases begin at a high level and can be refined by subsystem all the way down to the object level. A use case model is the statement of use, use case diagram, use case description, and actor description.

The following presents the major actors of the WebShipCost system.

Actors: (The main users of the WebShipCost system)

Actor Name: System User

Description: A system user uses the WebShipCost system to compute the shortest paths. The user can also make changes to the user-related data in the database.

Actor Name: Database Manager

Description: A human user who takes the data collected and places it into the database. The user must have knowledge of the validation process and the database. The user can make changes to all of the data in the database.

The following use case diagram identifies the “Calculate the Shortest Route” use case for the main needs described in the system concept section. A complete set of use cases and some important use case scenarios are listed in Appendix 6.1.

Table 11 Calculate the Shortest Route” Use Case Diagram


Use case:	Calculate the Shortest Route
Purpose:	To enter the information needed to calculate the shortest paths and get the computational results
Description:	System user enters transportation information into the program in order to get the shortest paths computed by the program
Actors:	System User

Table 12 “Input Transportation Information” Sub Use Case Diagram

Use case	Input Transportation Information
Purpose:	Input necessary transportation information into system in order to compute the shortest paths
Description:	Necessary information includes origin city, destination city, number of units, number of units per container, unit price, percentage of the unit cost to be used in the carrying cost, objective (such as time or cost) and the number of paths to be found

Table 13 “View the Calculation Results” Sub Use Case Diagram

Use case	View the Calculation Results
Purpose:	Show the computation results to the system user
Description:	User is provided with the computational results and analysis

3.2 Conceptual Model Diagrams

In this section, we present the system’s conceptual class diagrams that are necessary to support the functionality described in the use cases. The different classes describe the components that make up the WebShipCost application. Some of these classes have attributes and/or operations listed inside of the class box. Other attribute/operation information for the sake of brevity has been omitted from the diagram. Detailed information can be found in Appendix 6.2. Collectively, the diagrams document the complete conceptual model. To better understand and explain the conceptual model, it is easier to split up the complete model into manageable distinct packages: intermodal transshipment data model and web interaction model.

3.2.1 Intermodal Transshipment Data Model

In this section, we present the conceptual data model that supports the WebShipCost application. The two key design criteria for this model were to include flexibility for future extensions (sensitivity analysis, additional cost variation, etc) and to provide support for alternative algorithms.

In order to reach these two criteria, our model is a general object oriented transportation network model. The model includes general network elements such as Node and Arc. All costs occurred during the transportation were represented by classes or associations. The network does not depend on the specific algorithm to be used to compute the shortest paths. The cost information can be read in from a database and can thus be changed easily. Therefore, it is easy and convenient to perform sensitivity analysis and other parameter changes.

This intermodal transshipment model describes the relations among classes in the intermodal transportation network. The Network class involves three other classes: Node, Arc and Mode. A node is a conceptual location within the network and represents a potential point of origin for a shipment or a potential destination for a shipment. An arc represents a conceptual connection between nodes. A mode represents a method of traversal between nodes and along arcs within the network. Each network should include at least two nodes and one arc. The network may also contain one or more transportation modes. Each arc has two nodes: one for each end of the arc. Depending on the direction of traversal, the nodes can be conceptualized as the beginning or ending of the arc. An arc also has one or more transportation modes. The association ModeNetInfo denotes the average transport information about the mode, such as average speed and average cost rate, when this mode exists in the associated network. The association between Arc and Mode, ArcMode, denotes the transportation along one arc corresponding to a specific mode. When transferring between two modes, one might need information related to the transfer such as cost and time. When the information does not vary by node (location) then the cost rate and transfer time between modes can be considered as averages for the modes involved in the transfer. The reflexive relationship, TransferAvg, on Mode represents the average information for the transfer from one mode to another. TransferSpec denotes the transfer from one mode to another at a specific node. The association DrayCost denotes one mode’s dray cost at a specific node. In order to relate a conceptual node to the physical world each node can associate with one or more nearby cities and each city can have one or more nodes serving it. Appendix 6.2.1 presents the description of each class along with their attribute definitions and domains.

Figure 1 Intermodal Transshipment Class Diagram

We assume that the transfer cost should be node specific. So the transfer cost rate and transfer time are attributes of class TransferSpec. If specific by node (or city) data is not available, then we will use the average values that are attributes of class TransferAvg to provide values across nodes. Also, we assume that the transport speed and cost rate should be arc specific; they are attributes of class ArcMode. When such data is not available, then average values from ModeNetInfo will be used.

3.2.2 Web Interaction Model

In this section, we present the object model that supports the web user interaction with the WebShipCost application.

The web interaction model describes the relationship between the system user and the intermodal transshipment model. Figure 2 indicates that the class User holds the information about the user of the system. Each user may have some problems to be solved. A problem is a specific case by a user of the system. Each problem has a corresponding network and can contain many input scenarios. In each input scenario, two nodes were used to define the origin and the destination of the network for which the user wants to find the optimal solution path. Also, each input scenario will give a specific result; it describes the shortest path for which the user is interested. The description of each class along with their attribute definitions and domains are put into Appendix 6.2.2.

Figure 2 Web Interaction Class Diagram

The transshipment data model and the web interaction model both require persistent storage. In the following section, we discuss how each of these models is represented within a relational database framework.

3.3 Database Design

This section presents detailed documentation associated with the database design that supports the WebShipCost application. We present the specifics of implementing the database using the relational database paradigm. This includes the implementation of object identity, the implementation of data domains and constraints, and finally the mapping of the relevant class diagrams to relational tables.

In this application, we choose to use existence-based identity. We added an object identifier to each class and made it the primary key relying on internal support for identifiers from the relational database management system for implementation. Candidate keys were enforced via the use of unique indexes where appropriate. A domain refers to the set of possible values for an attribute. The specification of domains allows the values of an attribute to be represented by data types within the implementation language. The specification of domains is given in Appendix 6.3. For each attribute, the domain is then specified along with whether or not nulls are permitted for the attributes.

In the relational model, objects must be represented as tables (i.e. as rows and columns). The basic strategy is to begin by mapping each class to a separate table. In addition, additional attribute columns for existence-based identity, buried associations, and generalization discriminators are added as necessary to implement the relationships in the model. The full details are presented in Appendix 6.5. In the following, the underlined attribute indicates the primary key, italicized attributes indicate foreign keys, and candidate keys are noted by (CK).

3.4 Algorithm Processing

In this section, we present an overview of the algorithms and processing that supports the WebShipCost application. The algorithms of primary importance are the graph building processing and the K^th shortest path algorithm implementation.

3.4.1 Graph Building Processing

The purpose of the graph building processing is to extract the information that is stored in the database, for the transshipment model and the web interaction model, and build a proper intermodal graph representation. A graph is a set of vertices and arcs. Arcs are used to represent a linkage (either by cost or time) between two vertices.

We break each city into vertices as showing on the left side of Figure 3, where m denotes the number of transport modes in the network. In such a way, each city contains one start vertex, one end vertex, and 2m entry and exit vertices.

Figure 3 Network Representation

We define:

= the mode from the origin vertex to the entry vertex of city j

= the mode from the exit vertex to the destination vertex of city j

= the mode from the exit vertex of city j to entry vertex of city k

= the mode of the entry vertex of city j

= the mode of the exit vertex of city j

= dray cost at origin vertex of city j using mode

= inventory holding cost associated with drayage at origin vertex of city j using mode

= dray cost at destination vertex of city j using mode

= inventory holding cost associated with drayage at destination vertex of city j using mode

= travel cost from city j to city k using mode

= inventory holding cost associated with travel from city j to city k

= transfer cost from mode to mode at city j

= inventory cost associated with transfer from mode to mode at city j

= total cost from the origin city j to destination city k

Suppose the network contains n cities, m transportation modes, city 1 is the origin city and city n is the destination city, then the cost formulation from origin to destination can be formulated as:

In order to thoroughly explain the construction and makeup of the graph, we use an example network that contains three cities and three transportation modes to illustrate the method of mapping the conceptual intermodal model into the actual graph. The data used in this example are just illustrative.

In this example network, there are three cities named “Chicago”, “Cincinnati” and “Houston”. Three transportation modes “Barge”, “Rail” and “Truck” exist in the network.

So we could represent each node (in this example one city corresponds to one node) with vertices.

Goods are transported from the start vertex and will arrive at the end vertex. The other three pairs of vertices represent the entry into and exit out of each mode in this node (city). Drayage may occur when goods are shipped from the city’s start vertex to the city’s one specific mode entry vertex. In addition, drayage may occur when the goods arrive at the city’s end vertex. So we get 18 dray arcs for this particular example. We denoted them in Figure 4 using different line style.

Transfer cost occurs when the goods need to be shipped from one mode to another at a particular node, thus for this example at each node there are 6 transfer arcs. Notice that in order to construct the network we added zero transfer arcs between the entry vertex and the exit vertex that are of the same mode. That means when transfer doesn’t occur, the cost and time associated with it is zero. So totally there are 18 + 9 = 27 transfer arcs in the example network.

Goods are transported from one node’s exit vertex to another node’s entry vertex. So each arc between the out vertex of origin node and the entry vertex of the destination node is a transport arc. In our example network, we have 18 transport arcs.

All of the arcs and vertices are showed in the Figure 4:

Figure 4 Example Network Diagram

This graph was built using the data stored in the database. When we populate the vertices and arcs, we first construct each vertex in the graph. Then dray arcs, transfer arcs and transport arcs will be built from the database. We populate the cost and time information of the arcs at the same time in order to improve query efficiency. In the following section, we will show how the construction process was carried out. To further explore this procedure, we refer the interested reader to Appendix 6.7.

As previously stated, WebShipCost performs its analysis based on a formulation of the total transportation cost comprising of four elements: travel cost, transfer cost, dray cost, and inventory carrying cost. Inventory carrying cost is associated with the other three cost elements. Two formulas were used to compute the total transportation time and cost:

Total transportation time = total dray time

+ total transport time

+ total transfer time

Total transportation cost = total dray cost

+ total transport cost

+ total transfer cost

First of all, we extract the node information from the table DrayCost and Node, then break each node into vertices. In our example, each node has 8 corresponding vertices.

The transfer time associated with the dray process needs to be considered. It should be city specific and this information is in the table named TransferSpec; if the database doesn’t store the specific data, then the average transfer time will be used. Currently, we populate the specific value with the average value if city specific data is unavailable. Dray cost refers to the cost of transporting the shipment from the shipper’s location (warehouse, company, factory, etc.) to the barge or rail terminal. Dray cost also exists for transporting shipments from the barge or rail terminal destination to the final location (warehouse, company, factory, etc.). Dray cost can be expressed using the following formula:

Total dray cost = dray cost + associated transfer cost + associated inventory cost

Inventory cost is associated with other factors; we used the following formula to compute it:

where

I: inventory cost during time t

t: duration at holding inventory

u: unit cost of item to producer

c: carrying cost per unit ($/unit-year)

Q: number of units shipped

x: standard percentage used by a shipper

Transfer cost rate is city specific too. The formula is:

Total transfer cost = transfer cost + associated inventory cost

Average speed and distance between nodes are used to calculate transport times. When the mode is Truck, driver’s rest time needs to be considered, it can be calculated using the following formula:

R: rest time

T: total transport time (no rest)

D: distance between source and destination nodes

S: average speed

: floor operator, i.e. the greatest integer

Similarly, transport cost consists of transport cost and associated inventory cost:

Total transport cost = transport cost + associated inventory cost

We should note that in order to build a complete graph, transfer arcs without time and cost are necessary between each pair of entry and out vertices with the same mode of one node since there’s no transfer occurs in this case.

3.4.2 K^th Shortest Path Algorithm Implementation

The graph building process results in a validly constructed graph object that represents the problem that the user wants solved. The K^th Shortest Path Algorithm originally developed by Shier was implemented within an object-oriented framework using Java. The algorithm takes a graph object along with the origin and destination and computes the K shortest paths on the graph.

Two main classes are involved in the algorithm implementation. Class DoubleSweep inherits from the class IterativeProcess which is used to carry out the algorithm’s iterative process. Class DSWNode is an inner class of DoubleSweep, it provides a mapping of vertices to numbered nodes and provides data structures for each node for use during the algorithm’s iterative process.

Each DSWNode object keeps the information such as a set that contains the node’s lower incident edges, a set that contains the node’s upper incident edges, an ordered set of the current K shortest distances from original node to the node.

When the graph object is created by the Graph Factory object, it is passed to the DoubleSweep object. A DoubleSweep object uses the graph to initialize each node’s information. It divides all the incoming edges into two groups, edges which are incident to the bigger numbered vertices are stored into the array named myLowerIncidentEdges; edges which are incident to the smaller numbered vertices are stored into the array named myUpperIncidentEdges. Each node’s shortest path sets are initialized with infinity except for the first element of the set for the origin node. When we later do iterations, the values will be updated until the smallest values are found.

Then the DoubleSweep object iterates all the nodes from two different directions, backward iteration and forward iteration. During the backward iteration, a DoubleSweep object updates each node’s path set according to the path’s set of lower incident edges and the incident original node’s path set. The same thing happens during the forward iteration except for the difference that update is based on the upper incident edges. Here is an example to illustrate these procedures:

Figure 5 Before Backward and Forward Iteration

In this example, current node is node3, its K shortest paths is {6, 8, 12}; lower incident edges is {edge1, edge2}; upper incident edges is {edge3}.

We only consider the update of node3. After backward iteration, node3’s path set is updated because node5’s path 2 plus edge1’s length 3 is less than node3’s path 6. So we add value 2 + 3 = 5 into node3’s path set. Also we should add another value 2 + 2 = 4 into node3’s path set. Finally we get the result below:

Figure 6 After Backward Iteration, Before Forward Iteration

Then, the forward iteration will take place. The final result should be:

Figure 7 After Backward Iteration and Forward Iteration

If after one backward iteration and forward iteration, no path set was updated, we can say that the shortest paths were found. The algorithm only finds the shortest path distance from the origin vertex to all other vertices. From the shortest path distance the actual path must be derived. We also use an example to illustrate the procedure.

Figure 8 Example Graph

Suppose node3 is the destination node of the graph, and we found its three shortest paths which are {8, 10, 13}. Now we want to find the path of the third shortest path. The method is very simple. We subtract the path value, which is 13, from each incident edge’s length, and see if the result exists in the linked node by the edge. If the result is yes, then this edge is a part of the shortest path. We can find the complete path by proceeding backward from the destination in this manner.

In the following section, we will look at the architecture design and implementation of the application and how to achieve the goal of creating a maintainable and reusable web application.

3.5 Web Application Architecture and Implementation

We choose the standard MVC (Model – View – Controller) design pattern to implement our application. This architecture breaks the whole application into three parts. It provides a loose coupling between the parts and a clear application structure.

In the MVC design pattern, application flow is mediated by a central Controller. All the requests are sent to the Controller, and then they are delegated to the appropriate request handlers by the Controller. Each handler is tied to a Model. The Model encapsulates the application’s business logic. Control is usually returned through the Controller to the appropriate View. Finally the corresponding View is shown to the user.

In our application, Java Service Class, JSP and a Serlvet serve as Model, View and Controller respectively. All of the requests – in our application, they are HTTP requests – are forwarded to a Serlvet named WebController. The Controller then instantiates the appropriate Service Class to execute the service asked by the request. For instance, kth shortest path computation is encapsulated in the ComputeShortestPathService Class. The Service Class extracts/stores necessary data from/to the WebShipCost database. After that, the Controller decides the appropriate JSP as the result view for the user requests. Figure 9 illustrates the application architecture.

Figure 9 Application Architecture

3.6 Testing Results

In this section, we discuss the testing of the application on a small example scenario. We want to ship 10,000 items from Chicago to St. Paul. The value per item is 800 dollars. Each container holds 1,000 items. We assume the carrying holding cost is 5% of the total cost per unit per year. The scenario is presented in Table 14 Example Scenario below.

Table 14 Example Scenario

Origin City		Chicago
Destination City		St. Paul
The number of units to be shipped		10000
The number of units per container		1000
The cost of each unit to the producer		800
Carrying percentage		0.05
The objective		Minimize the cost
The number of path k		4

First of all, we fill in the query input form shown in Figure 10 below. The form is associated with the “Input Transportation Information” Sub Use Case.

Figure 10 Shortest Path Query Input Form

After the server finishes the computation, it will return the results of shortest paths. This form is associated with the “View the Calculation Results” Sub Use Case and shown in Figure 11.

Figure 11 Shortest Paths List

In this webpage, you can click the “Show Detail” button, and then the detailed path information will be presented as shown in Figure 12 Shortest Paths Details. Table 15 Shortest Path Test Results listed all the shortest paths detailed information in this scenario.

Figure 12 Shortest Paths Details

Table 15 Shortest Path Test Results

Path number	Cost (dollar)	Detail
1	5720	Start dray cost 0 dollar at city Chicago; Transport from city Chicago to city St. Paul using mode Truck with cost 5720 dollar; End dray cost 0 dollar at city St. Paul.
2	6082	Start dray cost 1295 dollar at city Chicago; Transport from city Chicago to city St. Paul using mode Rail with cost 3590 dollar; End dray cost 1195 dollar at city St. Paul.
3	10150	Start dray cost 1295 dollar at city Chicago; Transport from city Chicago to city Omaha using mode Rail with cost 4192 dollar; Transport from city Omaha to city St. Paul using mode Rail with cost 3466 dollar; End dray cost 1195 dollar at city St. Paul.
4	10575	Start dray cost 1295 dollar at city Chicago; Transport from city Chicago to city St. Louis using mode Rail with cost 2626 dollar; Transport from city St. Louis to city St. Paul using mode Rail with cost 5456 dollar; End dray cost 1195 dollar at city St. Paul.

4 Summary

Prior MBTC research on ShipCost has been enhanced and has resulted in the development of WebShipCost, a WWW-based implementation of cost models that describe the costs incurred by all activities (rail, truck, and barge) within an intermodal transportation network. WebShipCost allows online determination of the minimum path in terms of cost or time from an origin point to a destination point and enables shippers to understand the trade-offs associated with barge and container-on-barge transportation. In particular, the following results have been achieved:

1 A well specified object-model and database have been developed to support the inter-modal transshipment problem in a general and flexible manner. The object-model supports additional data requirements and allows for a separation between the network representation and the algorithmic solution process.

2 The appropriate costing formulas have been improved and properly implemented within the problem solving process.

3 A user interaction model has been developed and implemented using a flexible web services approach.

4 A review of the relevant literature in this area has been conducted.

Given the current architecture, WebShipCost is capable of solving the k-shortest path problem utilizing the data provided in the database. Future research should involve how to specify additional data and problem scenarios to the application.

In real world transportation decisions, input parameters such as shipping time may not be known or exact. Future work will explore the effect of uncertain input data on intermodal route determination and how to handle this uncertain data through simulation and sensitivity analysis. For example, WebShipCost assumes that the user is able to precisely estimate intermodal costs such as travel cost, transfer cost, dray charges, and inventory carrying cost, when in reality the true values of these future costs are uncertain. Exploring the effects of this uncertainty on the WebShipCost output is important. A thorough sensitivity analysis could determine how fluctuations in the input data affect selection of the optimal shipping routes. Often shippers choose shipping options based on the perceived reliability of the service. The enhancements to WebShipCost will allow for the incorporation of risks associated with intermodal transport. This enhanced risk and sensitivity analysis will help to better educate shippers in and around the State of Arkansas about the advantages of barge transportation and how these advantages might be put to use for their company. Future work will seek to:

§ Identify and model the key stochastic and risk-based performance metrics and their relative trade-offs.

§ Develop a multi-objective optimization approach that incorporates other constraints and objectives outside of the current single objective of either time or cost.

§ Perform a thorough sensitivity analysis.

§ Investigate methods of incorporating uncertainty into the decision making process and the transportation network.

Additional funding has been secured from the Mack Blackwell Transportation Center to complete the future work discussed in this section.

5 References

1. Trusty, Kristen and Eric M. Malstrom, A Feasibility Assessment of Truck-Barge Intermodal Freight Transportation, MBTC-FR-1079, University of Arkansas, 1998.

2. Boardman, Bonnie, and Eric M. Malstrom, Intermodal Cost Analysis Software User’s Manual, University of Arkansas Report, 1998.

3. Distances Between Ports, United States Government Printing Office, Washington, D.C., 1965.

4. Inland Waterways Mileage, Canal Barge Company, Inc., New Orleans, LA, 1987.

5. “Major North America Railroads”, Traffic Management, Vol. 33, July 1994.

6. Arkansas Waterways Commission published circular, 1997.

7. Personnel Communication with James McCarville, Executive Director, Port of Pittsburgh Commission, March 23, 1998.

8. Personnel Communication with Wayne Christy, Director of Marketing, Port of Pittsburgh Commission, March 1, 1998.

9. Haulk, C. J., Inland Waterways as Vital National Infrastructure: Refuting “Corporate Welfare” Attacks, Allegheny Institute for Public Policy, 1998.

10. Chew, Sze H., “A Methodology for Co mparative True Cost Assessment of Transportation Modes,” MSIE Thesis, University of Arkansas, May 1995.

11. National Ports and Waterways Institute, “ Maritime System of Americas: River/Ocean Operation,” Research Report MA-PORT-830-94001, U.S. Department of Maritime Administration, Louisiana State University, 1993.

12. Personnel Communication with Mike Howard, Director of Intermodal, J. B. Hunt Inc., March 27, 1998.

13. US Army Corp of Engineers, Navigation Data Center Publications and US Waterways Data CD-ROM, UA Army Corps of Engineers, 1997.

14. United States Postal Service, City/State/ZIP Code Associations, www.usps.com/ncsc/lookups/lookup_ctystzip.html.

15. Personnel Communication with Teresa Frazier, J. B. Hunt Inc., May 14, 1998.

16. Personnel Communication with various members of COCITE at the Pittsburgh 3^rd Annual Traffic Club Dinner, March 24-25, 1998.

17. Personnel Communication with various members of COCITE at the Memphis meeting, January 23, 1998.

18. Grasman, Scott E., and Ajith Kumar Karunakara, “Modern Multimodal Logistics,” Industrial Engineering Research Conference Proceedings, May 19-21, 2002.

19. Dijkstra, E. W., “A Note on Two Problems in Connexion with Graphs,” Numer. Math. 1, 1959, pp. 269-271.

20. Ford, L. R., Jr., “Network Flow Theory,” The Rand Corporation, P-293, 1956.

21. Yen, J. Y., “An Algorithm for Finding Shortest Routes from All Source Nodes to a Given destination in General Networks,” Quart. Appl Math. 27, 1970, pp. 526-530.

22. Floyd, R. W., “Algorithm 97, Shortest Path,” Comm, ACM 5, 1962, pp. 345.

23. Dantzig, G. B., “All Shortest Routes in a Graph,” Operations Research House, Stanford Univ. Tech. Rep. pp. 66-63, 1966.

24. Tabourier, Y., “All Shortest Distances in a Graph. An Improvement to Dantzig’s Inductive Algorithm,” Discrete Math. 4, 1973, pp. 83-87.

25. Shier, D. R., “Iterative Methods for Determining the k Shortest Paths In a Network”, Networks, 3, 1976, pp. 205-229.

26. Eppstein, David, “Finding the k Shortest Paths”, Society for Industrial and Applied Mathematics, 28, 1998, pp. 652-673.

27. Cunningham, Wayne H.J., “Freight Modal Choice and competition in Transportation: A Critique and Categorization of Analysis Techniques”, Transportation Journal, 1982, pp. 66-75

28. Mcginnis, Michael A., “A Comparative Evaluation of Freight Transportation Choice Models”, Transportation Journal, 1989, pp. 35-46

29. John R. Meyer, et al., “The Economics of Competition in the Transportation Industries”, Cambridge, Massachusetts: Harvard University Press, 1959

30. Ann Friedlaender, “The delimma of Freight Transport Regulation”, Washington, D.C., The Brookings Institution, 1969

31. Michael A. McGinnis, Thomas M. Corsi, and Merrill J. Roberts, “A Multiple Criteria Analysis of Modal Choice”, Journal of Business Logistics 2, No.2 1981, pp. 48-68

6 Appendices

6.1 Use Case

System Level:

“Calculate the Shortest Route” Use Case


Use case:	Calculate the Shortest Route
Section:	System level
Purpose:	To enter the information needed to calculate the shortest paths and get the computation results
Description:	System user enters transportation information into the program in order to get the shortest paths computed by the program
Actors:	System User

“Modify the Database Information” Use Case


Use case:	Modify the Database Information
Section:	System level
Purpose:	To change the data stored in database
Description:	System user and database manager can change the data stored in the database. These data must be created by database manager.
Actors:	System User, Database Manager

Subsystem level:

“Input Transportation Information” Sub Use Case

Use case	Input Transportation Information
Purpose:	Input necessary transportation information into system in order to compute the shortest paths
Description:	Necessary information includes origin city, destination city, number of units, number of units per container, unit price, percentage of the unit cost to be used in the carrying cost, objective(such as time or cost) and the number of path to be found

“View the Calculation Results” Sub Use Case

Use case	View the Calculation Results
Purpose:	Show the computation results to the system user
Description:	User is provided with the computation results and analysis with them

“Change the User Information” Sub Use Case

Use case	Change the User Information
Purpose:	To change information related to system user
Description:	User information includes user name, email address and user description

“Change the Problem Information” Sub Use Case

Use case	Change the Problem Information
Purpose:	To change information related to problem
Description:	Problem information includes title, create date and problem description

“Change the Input Scenario Information” Sub Use Case

Use case	Change the Input Scenario Information
Purpose:	To change information related to input scenario
Description:	Input scenario information includes title and description

“Change the Network Information” Sub Use Case

Use case	Change the Network Information
Purpose:	To change information related to network
Description:	Network information includes network name, currency units, distance units and time units

“Change the Node Information” Sub Use Case

Use case	Change the Node Information
Purpose:	To change information related to node
Description:	Node information includes node name

“Change the City Information” Sub Use Case

Use case	Change the City Information
Purpose:	To change information related to city
Description:	City information includes city name

“Change the Specific Transfer Information” Sub Use Case

Use case	Change the Specific Transfer Information
Purpose:	To change information related to specific transfer time and cost rate
Description:	Specific Transfer information includes transfer cost rate and transfer time

“Change the Mode Information” Sub Use Case

Use case	Change the Mode Information
Purpose:	To change information related to mode
Description:	Mode information includes mode name, mode average transportation speed, average cost rate, average dray cost rate and average carrying cost

“Change the Dray Cost Information” Sub Use Case

Use case	Change the Dray Cost Information
Purpose:	To change information related to dray cost information
Description:

City Name

Location

River

2.2.3 Drayage Costs and Lengths

2.2.5 Transfer Costs and Time

3.4.1 Graph Building Processing