Bus service for cargo

This paper studies the routing of multiple commodities (shipments) through a network with the aim to minimize the total cost. To transport these commodities from their origin to their destination hub, a combination of different services can be used, including scheduled trucks (following a dedicated trajectory, similar to bus routes) and express delivery. Each commodity starts its itinerary at its origin hub and needs to arrive at its destination hub before its deadline. The following cost factors are considered in the model: a fixed cost as well as a distance-based travel cost for the scheduled truck services, a cost for express delivery between each pair of hubs based on the size of the commodity, and the inventory holding cost at each hub. We first define the problem as a mixed-integer linear program (MILP). To solve this MILP, we apply a branch-and-price algorithm that relies on column generation. In a second phase, we extend our model formulation to also deal with demand uncertainty (i.e., the size of each shipment varies) and present a two-stage, scenario-based stochastic model which we also solve using the branch-and-price algorithm. To generate the scenarios for the stochastic model, we apply Sample Average Approximation (SAA). Extensive computational experiments, including a sensitivity analysis are presented.