Exact algorithms for the multiple depot vehicle scheduling problem with heterogeneous vehicles, split loads and toll-by-weight scheme

We study a general version of the multiple depot vehicle scheduling problem, which is motivated by the practice of line-haul transportation in Chinese express delivery firms. In this problem, there are a set of trips to be served by a fleet of vehicles. Each trip has a certain amount of packages to be transported from an origin to a destination. Each vehicle can serve a sequence of trips, but it has to depart from and return to its base depot. We aim at assigning trips to vehicles such that all trips are fully served and the total transportation cost is minimized. This problem is general because several practical features have been considered, including heterogeneous vehicles, service time windows, split loads, and the toll-by-weight scheme. These features greatly broaden the applicability of this problem, but at the price of complicating it. We first formulate this problem into a nonlinear route based model, and then equivalently transform it into a linear route-cover based model. To solve the model, we propose two exact algorithms, namely, a branch-and-price and a branch-and-benders decomposition. Both algorithms are built upon a branch-and-bound framework. Particularly, we design a column generation procedure equipped with an efficient label setting method to solve subproblems involved in the two algorithms. Computational experiments are conducted on a set of random instances, and the results have substantiated the effectiveness and efficiency of our model and algorithms.