Cargando…

School bus routing problem in the stochastic and time-dependent transportation network

Accidents, bad weathers, traffic congestions, etc. led to the uncertainties of travel times in real-life road networks, which greatly affected the quality of individual’s life and the reliability of transportation system. This paper addressed the school bus routing problem in such a stochastic and t...

Descripción completa

Detalles Bibliográficos
Autores principales: Sun, Shichao, Duan, Zhengyu, Xu, Qi
Formato: Online Artículo Texto
Lenguaje:English
Publicado: Public Library of Science 2018
Materias:
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC6107216/
https://www.ncbi.nlm.nih.gov/pubmed/30138472
http://dx.doi.org/10.1371/journal.pone.0202618
_version_ 1783349936701571072
author Sun, Shichao
Duan, Zhengyu
Xu, Qi
author_facet Sun, Shichao
Duan, Zhengyu
Xu, Qi
author_sort Sun, Shichao
collection PubMed
description Accidents, bad weathers, traffic congestions, etc. led to the uncertainties of travel times in real-life road networks, which greatly affected the quality of individual’s life and the reliability of transportation system. This paper addressed the school bus routing problem in such a stochastic and time-dependent road environment. Firstly, the problem was set based on a single-school configuration, and the students were picked up at their homes, which was in line with the current situation of school bus systems in China. Thus, it could be regarded as an independent problem of school bus route generation in random dynamic networks, which could be solved as a variant of extended Vehicle Routing Problem. However, due to the fluctuation and uncertainty of link travel times, the arrival time at each stop including the destination was varying. Therefore, the selection of optimal path connecting the current service node with the next one was treated as a sub-problem in this study, where the reliability of travel times in the stochastic and time-varying network was highly concerned by such time-rigid commuters. To this end, a Robust Optimal Schedule Times model with a hard time windows constraint was built to generate a most cost-reliable route for school buses. By the use of Robust Optimization method, it was intended to minimize the worst-case total cost which combined the cost of earlier schedule delays with the disutility of travel times. It was also proved that the proposed model could be converted into solving a conventional problem in deterministic dynamic networks for a reduction of computation complexity, which provided the potential of applying to the practical problems. Finally, the validity of the proposed model and its performance evaluation was analyzed through a small-scale computational instance, where all the link travel times in the simulated network were attributed to both time-varying and stochastic. Then, a mathematical programming solver was used to find the exact optimal solution. The results indicated that the model was valid, and the necessity of considering the stochastic and time-dependent nature of transportation networks was also confirmed in the case study.
format Online
Article
Text
id pubmed-6107216
institution National Center for Biotechnology Information
language English
publishDate 2018
publisher Public Library of Science
record_format MEDLINE/PubMed
spelling pubmed-61072162018-08-30 School bus routing problem in the stochastic and time-dependent transportation network Sun, Shichao Duan, Zhengyu Xu, Qi PLoS One Research Article Accidents, bad weathers, traffic congestions, etc. led to the uncertainties of travel times in real-life road networks, which greatly affected the quality of individual’s life and the reliability of transportation system. This paper addressed the school bus routing problem in such a stochastic and time-dependent road environment. Firstly, the problem was set based on a single-school configuration, and the students were picked up at their homes, which was in line with the current situation of school bus systems in China. Thus, it could be regarded as an independent problem of school bus route generation in random dynamic networks, which could be solved as a variant of extended Vehicle Routing Problem. However, due to the fluctuation and uncertainty of link travel times, the arrival time at each stop including the destination was varying. Therefore, the selection of optimal path connecting the current service node with the next one was treated as a sub-problem in this study, where the reliability of travel times in the stochastic and time-varying network was highly concerned by such time-rigid commuters. To this end, a Robust Optimal Schedule Times model with a hard time windows constraint was built to generate a most cost-reliable route for school buses. By the use of Robust Optimization method, it was intended to minimize the worst-case total cost which combined the cost of earlier schedule delays with the disutility of travel times. It was also proved that the proposed model could be converted into solving a conventional problem in deterministic dynamic networks for a reduction of computation complexity, which provided the potential of applying to the practical problems. Finally, the validity of the proposed model and its performance evaluation was analyzed through a small-scale computational instance, where all the link travel times in the simulated network were attributed to both time-varying and stochastic. Then, a mathematical programming solver was used to find the exact optimal solution. The results indicated that the model was valid, and the necessity of considering the stochastic and time-dependent nature of transportation networks was also confirmed in the case study. Public Library of Science 2018-08-23 /pmc/articles/PMC6107216/ /pubmed/30138472 http://dx.doi.org/10.1371/journal.pone.0202618 Text en © 2018 Sun et al http://creativecommons.org/licenses/by/4.0/ This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0/) , which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.
spellingShingle Research Article
Sun, Shichao
Duan, Zhengyu
Xu, Qi
School bus routing problem in the stochastic and time-dependent transportation network
title School bus routing problem in the stochastic and time-dependent transportation network
title_full School bus routing problem in the stochastic and time-dependent transportation network
title_fullStr School bus routing problem in the stochastic and time-dependent transportation network
title_full_unstemmed School bus routing problem in the stochastic and time-dependent transportation network
title_short School bus routing problem in the stochastic and time-dependent transportation network
title_sort school bus routing problem in the stochastic and time-dependent transportation network
topic Research Article
url https://www.ncbi.nlm.nih.gov/pmc/articles/PMC6107216/
https://www.ncbi.nlm.nih.gov/pubmed/30138472
http://dx.doi.org/10.1371/journal.pone.0202618
work_keys_str_mv AT sunshichao schoolbusroutingprobleminthestochasticandtimedependenttransportationnetwork
AT duanzhengyu schoolbusroutingprobleminthestochasticandtimedependenttransportationnetwork
AT xuqi schoolbusroutingprobleminthestochasticandtimedependenttransportationnetwork