A scheme for determining vehicle routes based on Arc-based service network design

ABSTRACT

In freight transportation, less-than-truckload carriers often need to assign each vehicle a cyclic route so that drivers can come back home after a certain period of time. However, the Node-Arc model for service network design addresses decisions on each arc and does not determine routes directly, although the vehicle balancing constraint ensures that the number of outgoing vehicles equals the number of incoming vehicles at each node. How to transform the optimized service network into a set of vehicle routes remains an important problem that has not yet been studied. In this paper, we propose a three-phase scheme to address this problem. In the first stage, we present an algorithm based on the depth-first search to find all of the different cyclic routes in a service network design solution. In the second stage, we propose to prune poor cyclic routes using real-life constraints so that a collection of acceptable vehicle routes can be obtained before route assignment. Some of the pruning can also be done in the first stage to speed up the proposed algorithm. In the third stage, we formulate the problem of selecting a set of cyclic routes to cover the entire network as a weighted set covering problem. The resulting model is formulated as an integer program and solved with IBM ILOG CPLEX solver. Experimental results on benchmark instances for service network design indicate the effectiveness of the proposed scheme which gives high-quality solutions in an efficient way.

KEYWORDS:

• Service network design
• depth-first search
• pruning
• set covering
• integer programming

Acknowledgments

This work was supported by the International Doctoral Innovation Centre (IDIC) scholarship scheme. We also greatly acknowledge the support from Ningbo Education Bureau, Ningbo Science and Technology Bureau, China's MOST and The University of Nottingham.

Disclosure statement

No potential conflict of interest was reported by the authors.

Additional information

Funding

This work is supported by the National Natural Science Foundation of China [grant number NSFC 71471092]; Zhejiang Natural Science Foundation [grant number LR17G010001]; Ningbo Science and Technology Bureau [grant number 2011B81006], [grant number 2014A35006].