Cargando…
Metaheuristics for the dynamic stochastic dial-a-ride problem with expected return transports
The problem of transporting patients or elderly people has been widely studied in literature and is usually modeled as a dial-a-ride problem (DARP). In this paper we analyze the corresponding problem arising in the daily operation of the Austrian Red Cross. This nongovernmental organization is the l...
Autores principales: | , , |
---|---|
Formato: | Online Artículo Texto |
Lenguaje: | English |
Publicado: |
Pergamon Press
2011
|
Materias: | |
Acceso en línea: | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3611096/ https://www.ncbi.nlm.nih.gov/pubmed/23543641 http://dx.doi.org/10.1016/j.cor.2011.02.006 |
_version_ | 1782264541446406144 |
---|---|
author | Schilde, M. Doerner, K.F. Hartl, R.F. |
author_facet | Schilde, M. Doerner, K.F. Hartl, R.F. |
author_sort | Schilde, M. |
collection | PubMed |
description | The problem of transporting patients or elderly people has been widely studied in literature and is usually modeled as a dial-a-ride problem (DARP). In this paper we analyze the corresponding problem arising in the daily operation of the Austrian Red Cross. This nongovernmental organization is the largest organization performing patient transportation in Austria. The aim is to design vehicle routes to serve partially dynamic transportation requests using a fixed vehicle fleet. Each request requires transportation from a patient's home location to a hospital (outbound request) or back home from the hospital (inbound request). Some of these requests are known in advance. Some requests are dynamic in the sense that they appear during the day without any prior information. Finally, some inbound requests are stochastic. More precisely, with a certain probability each outbound request causes a corresponding inbound request on the same day. Some stochastic information about these return transports is available from historical data. The purpose of this study is to investigate, whether using this information in designing the routes has a significant positive effect on the solution quality. The problem is modeled as a dynamic stochastic dial-a-ride problem with expected return transports. We propose four different modifications of metaheuristic solution approaches for this problem. In detail, we test dynamic versions of variable neighborhood search (VNS) and stochastic VNS (S-VNS) as well as modified versions of the multiple plan approach (MPA) and the multiple scenario approach (MSA). Tests are performed using 12 sets of test instances based on a real road network. Various demand scenarios are generated based on the available real data. Results show that using the stochastic information on return transports leads to average improvements of around 15%. Moreover, improvements of up to 41% can be achieved for some test instances. |
format | Online Article Text |
id | pubmed-3611096 |
institution | National Center for Biotechnology Information |
language | English |
publishDate | 2011 |
publisher | Pergamon Press |
record_format | MEDLINE/PubMed |
spelling | pubmed-36110962013-03-29 Metaheuristics for the dynamic stochastic dial-a-ride problem with expected return transports Schilde, M. Doerner, K.F. Hartl, R.F. Comput Oper Res Article The problem of transporting patients or elderly people has been widely studied in literature and is usually modeled as a dial-a-ride problem (DARP). In this paper we analyze the corresponding problem arising in the daily operation of the Austrian Red Cross. This nongovernmental organization is the largest organization performing patient transportation in Austria. The aim is to design vehicle routes to serve partially dynamic transportation requests using a fixed vehicle fleet. Each request requires transportation from a patient's home location to a hospital (outbound request) or back home from the hospital (inbound request). Some of these requests are known in advance. Some requests are dynamic in the sense that they appear during the day without any prior information. Finally, some inbound requests are stochastic. More precisely, with a certain probability each outbound request causes a corresponding inbound request on the same day. Some stochastic information about these return transports is available from historical data. The purpose of this study is to investigate, whether using this information in designing the routes has a significant positive effect on the solution quality. The problem is modeled as a dynamic stochastic dial-a-ride problem with expected return transports. We propose four different modifications of metaheuristic solution approaches for this problem. In detail, we test dynamic versions of variable neighborhood search (VNS) and stochastic VNS (S-VNS) as well as modified versions of the multiple plan approach (MPA) and the multiple scenario approach (MSA). Tests are performed using 12 sets of test instances based on a real road network. Various demand scenarios are generated based on the available real data. Results show that using the stochastic information on return transports leads to average improvements of around 15%. Moreover, improvements of up to 41% can be achieved for some test instances. Pergamon Press 2011-12 /pmc/articles/PMC3611096/ /pubmed/23543641 http://dx.doi.org/10.1016/j.cor.2011.02.006 Text en © 2011 Elsevier Ltd. https://creativecommons.org/licenses/by-nc-nd/3.0/ Open Access under CC BY-NC-ND 3.0 (https://creativecommons.org/licenses/by-nc-nd/3.0/) license |
spellingShingle | Article Schilde, M. Doerner, K.F. Hartl, R.F. Metaheuristics for the dynamic stochastic dial-a-ride problem with expected return transports |
title | Metaheuristics for the dynamic stochastic dial-a-ride problem with expected return transports |
title_full | Metaheuristics for the dynamic stochastic dial-a-ride problem with expected return transports |
title_fullStr | Metaheuristics for the dynamic stochastic dial-a-ride problem with expected return transports |
title_full_unstemmed | Metaheuristics for the dynamic stochastic dial-a-ride problem with expected return transports |
title_short | Metaheuristics for the dynamic stochastic dial-a-ride problem with expected return transports |
title_sort | metaheuristics for the dynamic stochastic dial-a-ride problem with expected return transports |
topic | Article |
url | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3611096/ https://www.ncbi.nlm.nih.gov/pubmed/23543641 http://dx.doi.org/10.1016/j.cor.2011.02.006 |
work_keys_str_mv | AT schildem metaheuristicsforthedynamicstochasticdialarideproblemwithexpectedreturntransports AT doernerkf metaheuristicsforthedynamicstochasticdialarideproblemwithexpectedreturntransports AT hartlrf metaheuristicsforthedynamicstochasticdialarideproblemwithexpectedreturntransports |