Research > Freight Transportation
By Ruibin Bai
19th March 2009
In recent years, logistics is becoming a major business worldwide due to economy globalization and the popularity of E-Business. There is a huge demand in shipping materials, parts, products, or even recycling goods to different places in a most economical, efficient way. In China, there are almost 5000 logistic companies of different sizes. Overall logistic business is growing at a rate of almost 30% each year. In 2008, e-business related logistic business increased by 100%.
There are many challenges ahead for Chinese logistic companies, however. For example, most companies are relatively small both in their transportation capabilities and in their service network. There are very limited uses of latest IT systems to automate and optimise allocation of critical logistic assets (vehicles, warehouses, etc.) in an efficient way. A recent survey by Georgia Institute of Technology showed that, when compared with leading international logistic companies, Chinese logistic companies provide similar quality services but with a managing cost 15% higher on average (Dai, Li et al. 2004). With the cost for labor, materials and transportation increasing rapidly in China, it is imperative that the Chinese logistic companies optimize utilization of their resources and reduce the cost in order to be continually competitive in the long term. For many freight transportation companies, one of most effective means to reduce the cost is to optimize their service network and detailed schedules, which are designed manually at moment in many Chinese logistic companies.
2. Freight transportation
Depending on freight transportation companies' sizes, freight transports can be loosely categorized into three types: full-truckload (FTL) transports, less-then-truckload (LTL) transports and express delivery. Our research will mainly concentrate on LTL transports and express delivery, for which consolidations are widely adopted in order to maximize the utilisation of the freight resources (truck, plane, train, ship - or a combination of them). A freight transportation company usually offers several types of services in an attempt to meet different types of demands. For example, express delivery companies may offer Next-Day Delivery, Second-Day Delivery and Deferred Delivery (Barnhart, Krishnan et al. 2002). The guaranteed delivery time ranges from 24 hours to 3-5 days.
2.1 Planning levels
Due to the huge transportation network and the interdependency of the decision variables, freight transportation planning is generally carried out in the following three levels. They are strategic level, tactical level and operational level. Strategic level planning usually involves the highest level of management and is mainly focusing on companies long-term decisions, including service types to be offered, locations of hubs and terminals, specifications of vehicles to be purchased, volume of personnel to be employed, the infrastructure, etc. In the tactical planning level, the aim is to design the service network in a way such that existing resources can efficiently be allocated in order to maximize customer service level and total profit (or minimize the cost). Operational planning is carried out in a dynamic environment where orders/demands are placed at very short notice and arrive dynamically. The planners have to adapt the schedule made during tactical level to the changes in customers' demands. Tactical planning and operational planning are the focus of many research papers in the literature and usually appeared with a rather “confusing” name: service network design problem (SNDP). Depending on different problem scenarios, aims to deal with some or all of the following issues:
· For any two nodes in the service network, what service types should be provided (Air, Road, Rail)? , at what frequencies (inc. timetables)?
· What types of transport vehicles (capacities, speed, etc.) are to be purchased or rented?
· Assignments of routes and schedules for vehicles and drivers in order to meet legal, social and technical requirements.
· Shipping flow paths for each of commodities from origin to destination, including consolidation and transfer plans.
· Repositioning idle transportation assets (vehicles, drivers, containers, etc.) among the network in order to get ready for next period services.
2.2 Service Network Design Problem (SNDP)
For most freight transportation companies, a service network consists of geographically distributed nodes of one or several hubs and a number of terminals. Hubs are strategic centres of the network. Terminals can be gateways or regional shipment centres. The network can be illustrated by a diagram in figure 1.
Freight transportation community often makes a distinction between two important terms:
· Route: A route defines a network nodes sequence which is feasible for a given vehicle to travel from the first node to the last.
· Path: A path describes a nodes’ sequence via which a shipment package flows from its origin to destination.
In figure 1, the service network consists of 1 hub, 4 gateways, and a number of shipment centres. For a delivery request from node 1 to 4, ignoring other constraints, there are 5 possible paths: P1=(1, 4), P2=(1,H,4), P3=(1,2,H,4), P4=(1,H,3,4), P4=(1,2,H,3,4). The packages can be delivered via one of these paths or a combination of them. For a given type of vehicle, the routes can be a mirroring one between two node R1=(1,H,1) or a cyclic one R2=(1,2,H,1).
Figure 1: An simple illustration of service network for LTL and express delivery.
Service network design problem is related to network flow problem (Ahuja, Magnanti et al. 1993) and network design problem (Magnanti and Wong 1984; Minoux 1989). In addition, it has added degree of complexity due to the requirement of balancing transportation assets at the end of each planning period.
Barnhart et al. (Barnhart, Krishnan et al. 2002) defines the service network design problem as two interrelated problems: design of service network and shipment movement scheduling. Service network determines the routes of transportation equipments (e.g. aircraft and ground vehicles). Shipment movement scheduling defines the movements of individual shipments from origins to destinations in the service network determined in the first problem. The proposed models, which will be introduced shortly, are suitable to solve the next-day delivery alone but not for delivery services lasting longer than one-day period. In these models, two types decision various are introduced in each model. They are network design variables (integer variables) and commodity flow variables (continuous variables).
2. Mathematical formulations for next-day express delivery
For next-day delivery, since the planning period is one day (24 hours) only, there is no need to introduce space-time network, which would be necessary for shipments which takes more than one day. For a given directed graph where N is the node set and A is the arc set. For a commodity k in the set , denote be the quantity of k and (respectively ) be its origin (respectively destination). Denote uf be the capacity of vehicle type where F is the set of all transport vehicle types.
2.1 Nde-Arc Formulation
where and are decision variables. Continuous variables stands for the commodity flow of k on arc . Design variable stands for the number of times (frequency) of vehicle type f used on arc . Therefore, are discrete variables. stands for the fixed cost for using vehicle type f on arc once， stands for the variable cost of shipping a unit of commodity k along arc . is defined as：
The objective function is to minimise the sum of fixed costs and variable costs in order to ship all commodities from origin to destination. Constraint (2) ensures that the total flow along each arc does not exceed its capacity. Constraint (3) is flow balance constraint, which makes sure that all the commodities are shipped entirely from their origins to corresponding destinations entirely. Constraint (4) is design balance constraint, which ensures all vehicles returning to their original nodes in order to get ready for next period service period. Constraints (5) and (6) make sure that non-negativity of the decision variables and integrity of design variables.
2.2. Path Formulation
Denote be the set of feasible routes for vehicle type f and be the set of feasible path for commodity k. Let stand for the fixed cost for using vehicle type f along route . Let be the variable cost of shipping unit commodity k along the path . Indicator variables means that the path p contains arc and otherwise. The variable cost for shipping a unit commodity along path p can be calculated: . The path formulation is as follows：
Where and are also indicator parameters. means that route r contains arc and otherwise. indicates whether node i is the start of the route r or the end or otherwise . The constraints are similar to the Node-Arc Formulation.
2.3 Tree Formulation
Another formulation was introduced in order to solvability of the problem (Kim 1997; Barnhart, Krishnan et al. 2002). The model is based on a concept “Super Commodity”. A super commodity is a collection of commodities that share the same origin. Denote be the origin of the commodity k , and denote be the super commodity at the node . Let S stands for the set of all super commodities. Each commodity requires one or many paths to be shipped and each super commodity can be delivered by a “path tree” set with node as the root. Denote be this path tree set. In each tree , there is only one path from to . Therefore, is the set of all path combinations of all commodity . For a super commodity with n commodities, suppose that each commodity k has m feasible paths, the cardinality of the tree set for this super commodity is , which will explode with the increase in either m or n. Kim (Kim 1997) reported successes in adopting this formulation in conjunction with the assumption that the variable cost for shipping a unit commodity along a path is independent on the type of commodity. The tree formulation appears in the following form：
where are binary indictors. if the tree q includes arc ， otherwise.
Armacost et al. (Armacost, Barnhart et al. 2002) also introduced another formulation based on the concept of “composite variable”. It can be seen as an extension of the tree formulation. A composite variable is a combination of variables for path and commodity flow. A composite variable contains a set of routes that has sufficient capacity to deliver a subset of predefined commodities. A important advantage of this formulation is that the corresponding LP gives a much tighter lower bound.
2.4 A Comparison of different formulations
Each of the formulations above has their merits and drawbacks. The section provides a quick comparison in the following aspects.
Table 1：A Comparison of three formulations
* stands for the number of super commodities.
1. The number variables. For Node-Arc formation, decision variables are , the total number of variables are where |A|,|K| and |F| are the cardinality of the sets A, K and F respectively. In path formulation, decision variables are, if denote be the union of all vehicles’ route sets and be the union of all commodities’ path sets, the total number of variables for path formulation is . Since the route set and the path set increases exponentially with increase in the network size , the path formulation has far more variables than the node-arc formulation. The number of variables in the tree formulation is . Since, it has the most variables among three formulations. Nevertheless, in many real world applications, some practical constraints (e.g. the length of the route/path, capacity limits) could reduce the number of decision variables in the path formulation and the tree formulation significantly.
2. Constraints. Kim (Kim 1997) analysed the flow balance constraints of the three models above (see table 1). It can be seen that both the path formulation and tree formulation have far less flow balance constraints than the arc-node formulation. Of course, the reduction in the number of constraints comes at a cost of exponential increase in the number of decision variables.
3. Scalability. Compared with the node-arc formulation, path formulation and tree formulation have better scalability in the following two aspects: a) both the path formulation and the tree formulation are able to handle non-linear cost functions without explicitly introducing a non-linear objective function; b) it is more flexible to augment the path formulation and the tree formulation by incorporating more constraints. The more constraints it includes the better. For example, some applications might want to limit the maximal length of the vehicle routes and/or the number of transfers/consolidations. Or one might also want to apply time windows to some priorities deliveries. These practical constraints could reduce the number of feasible routes and feasible paths significantly.
4. Solvability. All the models above are mixed integer programming problems (MIP). It is extremely difficult to solve medium or large scale problems. However, the tree formulation and the path formulation are more likely solved by column generation because both formulations have fewer constraints than the node-arc formulation. Nevertheless, none of them can be solved directly by using existing IP techniques. Various techniques have been investigated and proposed to solve the problem, including decomposition, column generation, heuristics and metaheuristics (Crainic, Frangioni et al. 2001; Armacost, Barnhart et al. 2002; Barnhart, Krishnan et al. 2002; Ghamlouche, Crainic et al. 2003; Ghamlouche, Crainic et al. 2004; Jansen, Swinkels et al. 2004; Crainic, Li et al. 2006).
3. SNDP for deferred deliveries
For freight transport services with more than one delivery day, “time-space” network is often introduced to address scheduling issues. In the time-space network, each node represents a node in physical network at a particular time point. Depending on the number of time points in the planning period, time-space network can be huge.
4. SNDP with Uncertainties
There are a few possible sources of uncertainties in SNDP.
· Demand uncertainties in volume, location, and time
· Travelling time (affects costs and service level due to delays)
· Package sorting/processing time
· Unpredictable vehicle breakdowns or others...
4.1 Demand uncertainties
4.1.1 Demand uncertainty in volume
This uncertainty affects the service network design for freight transportation companies in the following ways. Firstly, large fluctuation in demand volume affects the frequency of the serviced to be offered. When the demands are high, companies could either use transportation vehicles with larger capacities or increase the service frequency. When the demand is low, however, freight transportation companies have to reduce the frequency and/or use vehicles with smaller capacities in order to save unnecessary costs. For express delivery companies, uncertainties in demand can be partially dealt with by dynamically allocating appropriate vehicles just before the latest departure time so that the total quantity of all the outgoing commodities is known. However, there is still a problem. Since the uncertainties in demand may exist across the entire service network, the vehicle schedule cannot cope with uncertainties in incoming commodities when the previous outgoing vehicle will be used as the incoming vehicle. In most applications, transport vehicles (especially ground vehicles) between gateways and the hub are scheduled to return to their original gateways in the next day or next few days, carrying incoming packages. Therefore, assignment of vehicles should consider not only the volume of the outgoing commodities but also the incoming ones. These vehicles should have sufficient capacities for both the outgoing shipments (for which it is not a problem since the information is almost accurate) and the incoming shipments, for which only estimated information is available. Ideally, the scheduled vehicle capacity between gateways and the hub should be the maximum of the outgoing and incoming commodities. However, since the volume of the incoming commodities is not available when the vehicle has to be schedule, it has to be estimated when the outgoing vehicle is scheduled. The potential problems are as follows. If the vehicle capacity is only just enough for the outbound packages but smaller than the inbound package of the next day, one would have to use one or more extra vehicles. If the vehicle capacity is far too larger than both the outbound packages and inbound packages, transport resources are not used efficiently and the cost is high.
Another challenges caused by uncertain demand is at local shipment centres where one has to adapt their pickup schedules to the real demand from customers. This problem is either caused by the inaccurate information problem from customers or the unexpected practical loading constraints (for example, some packages cannot be topped by other heavy packages). This particular problem falls into a broader topic of stochastic vehicle routing problem (SVRP). There have numerous papers on the relevant topics in this area with several techniques being proposed (see (Bertsimas and Simchi-levi 1996) for a review of SVRP).
4.1.2 Demand uncertainties in time and location
Customers' demand is uncertain in time. Take the express delivery for an example, demands are fluctuating weekly and are usually high on Wednesday, Thursday and Friday but decreases on the other days of the week (Chen 2008). Even on a particular day, customer demands are often geographically dispersed and arrive randomly in time horizon. These uncertainties often lead to challenges for many shipment centres which also offer pickup services. The managers in the local shipment centres want to minimize the pickup cost and maximize the satisfaction of customers' requirements. This problem may be categorized as the vehicle routing problem with stochastic customers (VRPSC) (Sungur, Ordonez et al. 2008).
At a slightly higher level, these uncertainties also create issues for gateways and the Hub. The main issue is the potential geographical imbalance of customers' demands, which would lead to an imbalanced distribution of transport assets over the service network.
In addition, these uncertainties could also result in some overloaded shipment centres and gateways, which would have to process excess packages than their actual capabilities. In order to maintain the service level and adapt to these uncertainties, a logistic company has to either invest more resources at nodes of the current service network (e.g. hiring more staff, buying more vehicles), or redesign the current service network by routing some of the packages to some less busier service terminals (i.e. shipment centres or gateways).
4.2 Travel time uncertainties
Another major uncertainty in freight transportation services is the travel time. Uncertain travelling time affects not only the business running costs but more importantly the service level. From one hand, inaccurate estimation of travel time could lead to failure of meeting time windows associated with the pickup and/or delivery operations. On another hand, the delivery path for a package often consists of several arcs with each arc is covered by a particular type of transport vehicle (except some dedicated delivery services which have no intermediate stops). Therefore any of delays during early stages of the path will cause potential disruptions, which probably means that the package will miss the transfer time window of the next vehicle.
Figure 2: An exemplary schedule for a delivery request from gateway 2 to gateway 4
For example, in figure 1, suppose that there is a delivery demand from gateway 2 to gateway 4, and a delivery path of (2,H,3,4) is assigned in a solution. Figure 2 illustrates the corresponding schedule. It can be seen that the package arrives at the Hub at time t2 but only departs at time t3. A time slack of (t3-t2) is scheduled in order to allow sufficient time to: a) unload the package from vehicle 1, sort it, and then reload it in vehicle 2; b) accommodate possible delays that may occur before t2. If the time slack (t3-t2) is too small, the package could miss the departure time of vehicle 2 (t3) and all the subsequent schedules (vehicle 3 in this example). An initial observation is that delay disruptions at the beginning of the path have larger impact than the delays occurring at end of the path. The second observation is that delays involving the hub are difficult to recover. The exact characteristics of these different delays need to be looked at in a more scientific manner.
4.3 Other uncertainties
Other uncertain factors in the freight transportation may include uncertain package sorting time, package (un-)loading time, vehicle breakdowns, natural disasters (earthquakes, snow storms, landslides, etc.). Except the first source of uncertainty, the other uncertainties occur less frequently but have much large impact on the robustness of the logistics service network. One of the possible solutions is to have contingency plans such that the services are not disrupted or at least it can be (partially) recovered in a short time.
4.4 Vehicle Balancing Problem
The vehicle balancing constraint requires that all vehicles that depart from a node should return to their origins at the end of the scheduling period so that it gets ready for the next period, whilst maximizing the vehicle capacity utilization (i.e. reducing the vehicle capacity waste). However, due to the fact that commodity flow over the network is usually not balanced (at least in short term), it is challenging to maintain the vehicle balanced whilst maximizing vehicle capacity utilization.
In this research, we plan to investigate whether there are better vehicle assignment approaches. To make meaningful comparison, we compare against a benchmark approach which we described as follows.
Benchmark vehicle assignment approach
In this approach, each selected vehicle is assigned with a fixed delivery route from node i to j via a sequence of nodes S. After delivery, the vehicle then returns to its origin through the same route, carrying the commodities from node j to i via S’ where S’ is the inverse of the sequence S.
Ahuja, R. K., T. L. Magnanti, et al. (1993). Network Flows: Theory, Algorithms and Applications. NJ, Prentice Hall.
Armacost, A. P., C. Barnhart, et al. (2002). "Composite Variable Formulations for Express Shipment Service Network Design." Transportation Science 36(1): 1.
Barnhart, C., N. Krishnan, et al. (2002). "Network Design for Express Shipment Delivery." Computational Optimization and Applications 21: 239-262.
Bertsimas, D. J. and D. Simchi-levi (1996). "A New Generation of Vehicle Routing Research: Robust Algorithms, Addressing Uncertainty." Operations Research 44(2): 286-304.
Chen, J. (2008). Personal Correspondance. Ningbo, China, Shentong Express Ltd., China.
Crainic, T. G., A. Frangioni, et al. (2001). "Bundle-based relaxation methods for multicommodity capacitated network design." Discrete Applied Mathematics 112: 73-99.
Crainic, T. G., Y. Li, et al. (2006). "A first multilevel cooperative algorithm for capacitated multicommodity network design." Computers & Operations Research 33(9): 2602-2622.
Dai, J., Y. Li, et al. (2004). China Road Transportation Enterprise Survey Report., The Logistics Institute-Asia Pacific, Singapore (TLI-AP).
Ghamlouche, I., T. G. Crainic, et al. (2003). "Cycle-based neighbourhoods for fixed-charge capacitated multicommodity network design." Operations Research 51(4): 655-667.
Ghamlouche, I., T. G. Crainic, et al. (2004). "Path relinking, cycle-based neighbourhoods and capacitated multicommodity network design." Annals of Operations Research 131: 109-133.
Jansen, B., P. C. J. Swinkels, et al. (2004). "Operational planning of a large-scale multi-modal transportation system." European Journal of Operational Research 156: 41–53.
Kim, D. (1997). Large Scale Transportation Service Network Design: Models, Algorithms and Applications, Massachusetts Institute of Technology. PhD.
Magnanti, T. L. and R. T. Wong (1984). "Network design and transportation planning:models and algorithms." Transportation Science 18(1): 1-55.
Minoux, M. (1989). "Network synthesis and optimum network design problem:models,solution methods and applications." Networks 19(4): 313-360.
Sungur, I., F. Ordonez, et al. (2008). "A robust optimization approach for the capacitated vehicle routing problem with demand uncertainty." IIE Transactions 40: 509–523.