The dynamic fleet management problem with uncertain demand and customer chosen service level
Introduction
We consider the problem faced by a carrier who needs to manage a fleet of homogeneous vehicles over space and time to serve a number of transportation requests. Each transportation request is defined by an origin–destination pair. The service for the request must start at a specific instant in time or be lost. The carrier may provide customers a portfolio of service levels that vary in travel time (24 h, 48 h or 3 days). For example, when customers place orders from E-commercial companies (such as amazon.com, 360buy.com, Taobao.com), they can choose delivery service level ranged from 3 days, 2 days and 1 day with different rates. Carriers, given orders with various service level and demand, need to allocate their fleets to fulfill the tasks. If customer demands a service level with shorter travel time, the carrier may need to pay additional transportation cost and ask for a higher rate. Customers select one service level when they place the order. This problem belongs to a class of dynamic fleet management problems (DFMPs), which can be viewed as a type of spatial, dynamic inventory management problem with reusable vehicles. At any point in space and time, a vehicle may be assigned to satisfy a revenue generating activity. It may be repositioned empty to another point in space and time or held in inventory.
The DFMP has received a lot of attention from the research community. Comprehensive reviews can be found in Dejax and Crainic (1987), Crainic and Laporte (1998), Powell and Topaloglu (2005) and Flatberg et al. (2007). We focus on the most relevant literature. Early fleet management models are deterministic and appear as the first applications of linear programming and min-cost network flow algorithms (see Dantzig and Fulkerson, 1954, White, 1972). These models formulate the problem over a time-space network (also called a dynamic network, or a time-staged network). A number of authors have studied the problem of random demands. The first to explicitly incorporate uncertainty in demands is Jordan and Turnquist (1983) in the context of the allocation of rail freight cars. Powell (1986) formulates the problem with random demands as a dynamic network with random arc capacities. Powell (1988) provides an overview of alternative modeling and algorithmic strategies for the stochastic fleet management problem. This model has been applied to dynamic truck allocation (Powell, 1987, Powell et al., 1988), empty container repositioning (Crainic et al., 1993, Chu, 1995) and transportation planning (Barbarosoglu and Arda, 2004). Godfrey and Powell (2002) and Topaloglu and Powell (2006) introduce the idea of adaptively estimating piecewise-linear approximations of the value of vehicles in the future.
All of this literature assumes that the time for completing the transportation request is fixed. In our motivating application, the time is not fixed but determined by the service level chosen by the customer. Therefore, the service time for a particular demand can be regarded as a random variable, and it becomes known as soon as the demand is known. But for orders moving in the future, we do not yet know the customer's choice, and for this reason the travel time is stochastic. We note that this type of randomness in the time to complete a service contrasts with randomness resulting from delays due to weather, congestion and equipment failures. In these settings, the service completion time only becomes known after the demand has been served.
A few authors have considered the problem of random travel times. Cheung et al. (2005) proposes a labeling method to handle uncertain service times. This method is able to handle a number of operational constraints, but does not scale to larger problems. Glockner and Nemhauser (2000) use scenario trees in a stochastic programming model to handle uncertainty. Simao et al. (2009) use approximate dynamic programming to model truckload operations which includes random travel times which become known only after a trip is completed.
There is a separate literature that includes customer choice. For example, Zhang and Adelman (2009) incorporate customer choice in airline revenue management. However, customer choice has not been considered in the fleet management literature.
Our solution strategy extends a line of research in stochastic vehicle allocation using separable approximations. This problem class has been most widely studied using the framework of two-stage stochastic programs with network recourse (Wallace, 1986, Wallace, 1987, Birge and Wallace, 1988). Wallace (1986) introduces a piecewise linear upper bound for networks and provides a result that is generalized in Birge and Wallace (1988) for stochastic programs. Independently, separable, piecewise linear approximations have been proposed for discrete vehicle allocation problems that arise in the context of fleet management (Powell, 1986). Frantzeskakis and Powell (1990) presents a method called the Successive Linear Approximation Procedure (SLAP) for approximating the expected recourse function. It is generalized by the Successive Convex Approximation Method (SCAM) in Cheung and Powell (1996). Similar to SLAP, SCAM decomposes the network into a series of trees and expresses the expected recourse function in terms of trees in the network. Furthermore, SCAM generalizes SLAP by using convex, instead of linear, approximations of the expected recourse function. The advantage of the SCAM is that it works quite well even with problems with huge sample space of random outcomes. SCAM and SLAP both estimate piecewise linear functions in a preprocessor. Godfrey and Powell (2002) and Topaloglu and Powell (2006) propose adaptive approximation procedures to estimate piecewise linear, separable approximations.
In this paper, we show that the problem of managing a fleet of vehicles where customers can choose the service level for orders can be formulated as a multistage dynamic network model with partially dependent random variables by an arc transformation. The contributions of this paper are:
- 1.
We formulate for the first time the fleet management problem with customer-chosen service levels. We formulate it as a dynamic network model with partially dependent random arc capacities. As this model retains the network structure, it enables us to apply structural decomposition techniques. Unlike previous dynamic fleet management models where random variables are usually assumed independent, our model allow random variables representing the customer selection of service level be partially dependent. It enables us to consider customer behaviors, which usually introduce a dependency in random demands, in fleet management field.
- 2.
We show that with slight modifications, SCAM works for DFMP with customer chosen service levels. We present a new structural decomposition approach: the Successive REsource directive Decomposition Method (SREDM). This approach provides a search mechanism which takes the advantage of the efficiency of solving the sub-problems. Both decomposition methods explicitly take the advantage of the network structure.
- 3.
We evaluate the efficiency of the decomposition method numerically. The results demonstrate that our approach is superior to the modified SCAM, and the gaps between the results of our approach and the lower bound are very tight.
The rest of this paper is organized as follows. Section 2 introduces how to transform the problem to a dynamic network model with partially dependent random arc capacities. Then it provides a multistage stochastic programming formulation. Next, Section 3 presents the structural decomposition approach that formulates the problem as a Discrete Resource Allocation Model (DRAM) and decomposes the problem into a number of stochastic tree recourse problems. Section 4 compares this approach with the alternative methods on a set of test problems. The results in Section 4 show the superiority of the new method over the alternative methods. Finally, Section 5 gives some concluding remarks.
Section snippets
Problem formulation
In this section, we first introduce an arc transformation. By this transformation, any arc with a random travel time can be transformed into a set of arcs with deterministic travel times and dependent random arc capacities. Then, the problem is formulated as a dynamic network model with dependent arc capacities.
Successive resource-directive decomposition method
Recently, Shi et al. (2007) introduce a new specialized algorithm to solve the problem where the network has a directed tree structure with partially dependent arc capacities. Our ability to solve tree problems motivates us to solve problems with general network structure. In this section, we introduce a new decomposition approach: the Successive REsource-Directive Decomposition Method (SREDM). Similar to SCAM in Cheung and Powell (1996), SREDM also uses a backward recursion framework to
Numerical experiments
In this section, we evaluate the SREDM algorithm by comparing it with the alternative methods. We conduct two sets of experiments. In the first set, the demands are deterministic and we compare the SREDM algorithm with a labeling algorithm. In the second set, both demands and service levels are random variables, and we compare the SREDM algorithm with the modified SCAM algorithm. We first introduce the design of the experiment and then report the numerical results.
Conclusion
In this paper, we propose the first model and algorithm for the dynamic fleet management problem with uncertain demand and customer chosen service levels. Then, we develop the SREDM algorithm for the resulting stochastic networks, which structurally decomposes the network into trees, whose expected recourse functions are obtained by a pseudo-polynomial algorithm in Shi et al. (2007). Numerical experiments show that the use of the SREDM methodology is very encouraging. In future, it is
Acknowledgment
This research is supported by the Natural Science Foundation of China via funding nos. 71171204, 71171205, and the Fundamental Research Funds for the Central Universities via no. 1209073.
References (31)
- et al.
A labeling method for dynamic driver-task assignment with uncertain task durations
Operations Research Letters
(2005) An operational planning model for the dynamic vehicle allocation problem with uncertain demands
Transportation Research
(1987)- et al.
A two-stage stochastic programming framework for transportation planning in disaster response
Journal of the Operational Research Society
(2004) - et al.
Introduction to Stochastic Programming
(1997) - et al.
A separable piecewise linear upper bound for stochastic linear programms
SIAM Journal on Control and Optimization
(1988) - et al.
An algorithm for multistage dynamic networks, with random arc capacities, with an application to dynamic fleet management
Operations Research
(1996) - Chu, Q., 1995. Dynamic and Stochastic Models for Container Allocation (Ph.D. thesis), Massachusetts Institute of...
- et al.
Dynamic and stochastic models for the allocation of empty containers
Operations Research
(1993) - Crainic, T.G., Laporte, G., 1998. Fleet Management and Logistics (Center for Research on Transportation 25th...
- et al.
Minimizing the number of tankers to meet a fixed schedule
Naval Research Logistics Quarterly
(1954)
Survey paper—a review of empty flows and fleet management models in freight transportation
Transportation Science
The greedy procedure for resource allocation problemsnecessary and sufficient conditions for optimality
Operations Research
A successive linear approximation procedure for stochastic, dynamic vehicle allocation problems
Transportation Science
A dynamic network flow problem with uncertain arc capacitiesformulation and problem structure
Operations Research
Cited by (20)
Planning low carbon oriented retrofit of diesel-driven cranes to electric-driven cranes in container yards
2022, Computers and Industrial EngineeringCitation Excerpt :Stasko and Oliver Gao (2012) studied the purchase, resale, and retrofit of vehicles in the case of random vehicle failure. For more studies on fleet management, see Parthanadee et al. (2012), Shi et al. (2014), and Ansaripoor et al. (2016). However, few studies focus on the management of port equipment, especially the management of YCs.
Deployment and retrofit strategy for rubber-tyred gantry cranes considering carbon emissions
2021, Computers and Industrial EngineeringCitation Excerpt :On the other hand, green fleet management with different types of vehicles involved is referred as a supplementary source. The problem has been tackled using integer programming (Stasko & Gao, 2010; Parthanadee, Buddhakulsomsiri, & Charnsethikul, 2012), stochastic dynamic programming (SDP; Hsu, Li, Liu, & Chao, 2011; Kleindorfer, Neboian, Roset, & Spinler, 2012), approximate dynamic programming (ADP; Stasko & Gao, 2012), stochastic programming (SP; Ansaripoor, Oliveira, & Liret, 2014), and a multistage dynamic network (Shi, Song, & Powell, 2014). For instance, Stasko and Gao (2012) presented an approximate dynamic programming approach for making vehicle purchase, resale, and retrofit decisions in a fleet setting with stochastic vehicle breakdowns.
Decision support for fleet allocation and contract renegotiation in contracted open-pit mine blasting operations
2018, International Journal of Production EconomicsCitation Excerpt :The proposed truck re-allocation model is used as an input for this analysis. Another relevant OR topic is fleet management for guaranteeing desired service levels under demand uncertainty (Shi et al., 2014). In our study, the mine contractor has established contracts for supplying explosives to the mine owners, who define a minimum number of trucks to be assigned to each open-pit, and the service level required, is measured as the volume of product that can be potentially supplied by the trucks with respect to the estimated peak-load demand at each open-pit.
Minimum cost flow problem formulation for the static vehicle allocation problem with stochastic lane demand in truckload strategic planning
2017, Transportmetrica A: Transport ScienceDynamic passenger demand oriented metro train scheduling with energy-efficiency and waiting time minimization: Mixed-integer linear programming approaches
2017, Transportation Research Part B: MethodologicalCitation Excerpt :In what follows, we first introduce the space-time networks for representation of train scheduling problem, and then we develop two linear formulations for solving this problem with the consideration of both dynamic passenger demands and train energy consumption. Space-time networks, which aim to integrate physical transportation networks with vehicle time-dependent movements/trajectories, are effective representation methods for capturing and analyzing spatial and temporal characteristics of dynamic traffic systems (e.g., see Kennington and Nicholson, 2010; Li et al., 2015; Tong et al., 2015; Shi et al., 2014; Boland et al., 2015; Yang et al., 2014; Mahmoudi and Zhou, 2016; Liu and Zhou, 2016; Lu et al., 2016; Yang and Zhou, 2017). For instance, Yang and Zhou (2014) constructed a space-time network to capture spatial and temporal travel time correlations for finding a priori least expected time path in a time-dependent and stochastic network.
A review on sustainability, Industry 4.0 and collaboration implications in vehicle allocation operations
2023, International Journal of Logistics Management