Minimum cost flow problem formulation for the static vehicle allocation problem with stochastic lane demand in truckload strategic planning

You are here: Homepage > Search

Minimum cost flow problem formulation for the static vehicle allocation problem with stochastic lane demand in truckload strategic planning

Mesa-Arango, Rodrigo / Ukkusuri, Satish V.

This paper studies the complex strategic planning problem faced by truckload (TL) companies related to finding the allocation of vehicles serving lanes with stochastic demand within their networks. Lanes are origin–destination pairs associated with volumes of TLs per unit of time that follow discrete probability distributions. Finding strategic vehicle allocations that anticipate demand variability is critical because unrealized demands increase repositioning costs and reduce perceived revenues. The allocation problem is formulated as a two-stage stochastic program. The paper proposes a novel procedure based on network transformations that formulate the complex stochastic problem as a minimum cost-flow problem (MCFP), which can be efficiently solved with classic MCFP algorithms. Numerical experiments demonstrate the computational efficiencies of the method (instances with 1404 nodes and 98,904 arcs solved in 20.74 seconds) and reinforce the necessity of incorporating stochastic effects to avoid overestimation from deterministic approaches.