A scheme for determining vehicle routes based on Arc-based service network design
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, a...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Published: |
Taylor & Francis
2017
|
| Subjects: | |
| Online Access: | https://eprints.nottingham.ac.uk/37728/ |
| _version_ | 1848801177723994112 |
|---|---|
| author | Jiang, Xiaoping Bai, Ruibin Atkin, Jason Kendall, Graham |
| author_facet | Jiang, Xiaoping Bai, Ruibin Atkin, Jason Kendall, Graham |
| author_sort | Jiang, Xiaoping |
| building | Nottingham Research Data Repository |
| collection | Online Access |
| description | 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. |
| first_indexed | 2025-11-14T19:33:24Z |
| format | Article |
| id | nottingham-37728 |
| institution | University of Nottingham Malaysia Campus |
| institution_category | Local University |
| last_indexed | 2025-11-14T21:03:19Z |
| publishDate | 2017 |
| publisher | Taylor & Francis |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | nottingham-377282025-09-09T13:55:49Z https://eprints.nottingham.ac.uk/37728/ A scheme for determining vehicle routes based on Arc-based service network design Jiang, Xiaoping Bai, Ruibin Atkin, Jason Kendall, Graham 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. Taylor & Francis 2017-01-31 Article PeerReviewed Jiang, Xiaoping, Bai, Ruibin, Atkin, Jason and Kendall, Graham (2017) A scheme for determining vehicle routes based on Arc-based service network design. INFOR: Information Systems and Operational Research, 55 (1). pp. 16-37. ISSN 1916-0615 (In Press) Service network design depth first serach pruning set covering integer programming http://www.tandfonline.com/doi/abs/10.1080/03155986.2016.1262580 doi:10.1080/03155986.2016.1262580 doi:10.1080/03155986.2016.1262580 |
| spellingShingle | Service network design depth first serach pruning set covering integer programming Jiang, Xiaoping Bai, Ruibin Atkin, Jason Kendall, Graham A scheme for determining vehicle routes based on Arc-based service network design |
| title | A scheme for determining vehicle routes based on Arc-based service network design |
| title_full | A scheme for determining vehicle routes based on Arc-based service network design |
| title_fullStr | A scheme for determining vehicle routes based on Arc-based service network design |
| title_full_unstemmed | A scheme for determining vehicle routes based on Arc-based service network design |
| title_short | A scheme for determining vehicle routes based on Arc-based service network design |
| title_sort | scheme for determining vehicle routes based on arc-based service network design |
| topic | Service network design depth first serach pruning set covering integer programming |
| url | https://eprints.nottingham.ac.uk/37728/ https://eprints.nottingham.ac.uk/37728/ https://eprints.nottingham.ac.uk/37728/ |