Skip to main content

Research Repository

See what's under the surface

Advanced Search

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

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

Authors

Xiaoping Jiang

Ruibin Bai

Jason Atkin

Graham Kendall



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.

Journal Article Type Article
Publication Date Jan 31, 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
APA6 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). doi:10.1080/03155986.2016.1262580. ISSN 0315-5986
DOI https://doi.org/10.1080/03155986.2016.1262580
Keywords Service network design, depth first serach, pruning, set covering, integer programming
Publisher URL http://www.tandfonline.com/doi/abs/10.1080/03155986.2016.1262580
Copyright Statement Copyright information regarding this work can be found at the following address: http://eprints.nottingh.../end_user_agreement.pdf

Files

revised manuscript.pdf (471 Kb)
PDF

Copyright Statement
Copyright information regarding this work can be found at the following address: http://eprints.nottingham.ac.uk/end_user_agreement.pdf





You might also like



Downloadable Citations

;