Schilde M, Doerner K F, Hartl R F
University of Vienna, Department of Business Administration, Bruenner Strasse 72, 1210 Vienna, Austria.
Comput Oper Res. 2011 Dec;38(12):1719-1730. doi: 10.1016/j.cor.2011.02.006.
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.
在文献中，运送患者或老年人的问题已得到广泛研究，通常将其建模为电话预约出行问题（DARP）。在本文中，我们分析了奥地利红十字会日常运营中出现的相应问题。这个非政府组织是奥地利最大的提供患者运输服务的组织。目标是使用固定的车辆车队设计车辆路线，以服务部分动态的运输请求。每个请求都需要将患者从其家中运送到医院（出站请求）或从医院送回家（进站请求）。其中一些请求是预先已知的。有些请求是动态的，即它们在当天出现且没有任何预先信息。最后，一些进站请求是随机的。更确切地说，每个出站请求有一定概率在同一天导致相应的进站请求。关于这些返程运输的一些随机信息可从历史数据中获得。本研究的目的是调查在设计路线时使用此信息是否对解决方案质量有显著的积极影响。该问题被建模为具有预期返程运输的动态随机电话预约出行问题。我们针对此问题提出了四种不同的元启发式解决方案方法的修改。详细地说，我们测试了可变邻域搜索（VNS）和随机VNS（S-VNS）的动态版本，以及多计划方法（MPA）和多场景方法（MSA）的修改版本。使用基于真实道路网络的12组测试实例进行测试。根据可用的真实数据生成各种需求场景。结果表明，使用返程运输的随机信息可使平均改进约15%。此外，对于某些测试实例，改进幅度可达41%。
