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

Jiang, Xiaoping; Bai, Ruibin; Atkin, Jason; Kendall, Graham

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.

Citation

Jiang, X., Bai, R., Atkin, J., & Kendall, G. (2017). A scheme for determining vehicle routes based on Arc-based service network design. Information Systems and Operational Research, 55(1), 16-37. https://doi.org/10.1080/03155986.2016.1262580

• Journal Article Type: Article
• Acceptance Date: Sep 1, 2016
• Online Publication Date: Dec 22, 2016
• Publication Date: Jan 31, 2017
• Deposit Date: Oct 19, 2016
• Publicly Available Date: Dec 23, 2017
• Journal: INFOR: Information Systems and Operational Research
• Print ISSN: 0315-5986
• Electronic ISSN: 1916-0615
• Publisher: University of Toronto Press
• Peer Reviewed: Peer Reviewed
• Volume: 55
• Issue: 1
• Pages: 16-37
• DOI: https://doi.org/10.1080/03155986.2016.1262580
• Keywords: Service network design, depth first serach, pruning, set covering, integer programming
• Public URL: https://nottingham-repository.worktribe.com/output/838344
• Publisher URL: http://www.tandfonline.com/doi/abs/10.1080/03155986.2016.1262580
• Contract Date: Oct 19, 2016