Multi-directional local search for a bi-objective dial-a-ride problem in patient transportation. (English) Zbl 1391.90078
Summary: This paper considers a generalization of a bi-objective dial-a-ride problem, incorporating real-life characteristics of patient transportation. It studies the impact of combination restrictions, preventing particular user combinations and limiting the set of drivers to which particular users can be assigned. The academic literature currently lacks insights into the effect of these restrictions on the cost structure of a service provider. A multi-directional local search algorithm is developed to solve this problem, taking into account the fundamental tradeoff between operational efficiency and service quality. Local search is integrated into a variable neighborhood descent framework that applies an intelligent candidate list principle to reduce computation time. Moreover, a new scheduling procedure is proposed, constructing time schedules that minimize total user ride time. It proves to be faster and more efficient than existing scheduling procedures. Overall, computational experiments on existing benchmark data extended with combination restrictions reveal a general pattern in the effect of the combination restrictions. Such insights are essential for service providers in order to support policy choices, e.g. related to service quality or medical education of drivers.
MSC:
| 90B06 | Transportation, logistics and supply chain management |
| 90C59 | Approximation methods and heuristics in mathematical programming |
| 90C29 | Multi-objective and goal programming |
| 90C57 | Polyhedral combinatorics, branch-and-bound, branch-and-cut |
| 90C10 | Integer programming |
Keywords:
dial-a-ride problem; patient transportation; combination restrictions; bi-objective optimization; multi-directional local search; scheduling procedureReferences:
| [1] | Anderson, D. R.; Sweeney, D. J.; Williams, T. A.; Freeman, J.; Shoesmith, E., Statistics for business and economics, 888, (2010), CENGAGE Learning Business Press Andover, Hampshire SP10 5BE, United Kingdom |
| [2] | Beaudry, A.; Laporte, G.; Melo, T.; Nickel, S., Dynamic transportation of patients in hospitals, OR Spectr, 32, 1, 77-107, (2010) · Zbl 1181.90173 |
| [3] | Braekers, K.; Caris, A.; Janssens, G. K., Exact and meta-heuristic approach for a general heterogeneous dial-a-ride problem with multiple depots, Transp Res Part B: Methodol, 67, 166-186, (2014) |
| [4] | Coppi A, Detti P, Raffaelli J. A planning and routing model for patient transportation in health care. In: Electronic notes in discrete mathematics, vol. 41; 2013. p. 125-32. |
| [5] | Cordeau, J.-F., A branch-and-cut algorithm for the dial-a-ride problem, Oper Res, 54, 3, 573-586, (2006) · Zbl 1167.90681 |
| [6] | Cordeau, J.-F.; Laporte, G., A tabu search heuristic for the static multi-vehicle dial-a-ride problem, Transp Res Part B: Methodol, 37, 6, 579-594, (2003) |
| [7] | Cordeau, J.-F.; Laporte, G., The dial-a-ride problemmodels and algorithms, Ann Oper Res, 153, 1, 29-46, (2007) · Zbl 1157.90353 |
| [8] | Diana, M.; Dessouky, M. M., A new regret insertion heuristic for solving large-scale dial-a-ride problems with time windows, Transp Res Part B: Methodol, 38, 6, 539-557, (2004) |
| [9] | Hansen, P.; Mladenović, N.; Moreno Perez, J. A., Variable neighbourhood searchmethods and applications, Ann Oper Res, 175, 367-407, (2010) · Zbl 1185.90211 |
| [10] | Ioachim, I.; Desrosiers, J.; Dumas, Y.; Solomon, M. M.; Villeneuve, D., A request clustering algorithm for door-to-door handicapped transportation, Transp Sci, 29, 1, 63-78, (1995) · Zbl 0826.90045 |
| [11] | Jaw, J.-J.; Odoni, A. R.; Psaraftis, H. N.; Wilson, N. H.M., A heuristic algorithm for the multi-vehicle advance-request dial-a-ride problem with time windows, Transp Res Part B: Methodol, 20, 243-257, (1986) |
| [12] | Lehuédé, F.; Masson, R.; Parragh, S. N.; Péton, O.; Tricoire, F., A multi-criteria large neighbourhood search for the transportation of disabled people, J Oper Res Soc, 65, 7, 983-1000, (2013) |
| [13] | Paquette, J.; Bellavance, F.; Cordeau, J.-F.; Laporte, G., Measuring quality of service in dial-a-ride operationsthe case of a Canadian city, Transportation, 39, 3, 539-564, (2012) |
| [14] | Paquette, J.; Cordeau, J.-F.; Laporte, G., Quality of service in dial-a-ride operations, Comput Ind Eng, 56, 4, 1721-1734, (2009) |
| [15] | Paquette, J.; Cordeau, J.-F.; Laporte, G.; Pascoal, M. M.B., Combining multicriteria analysis and tabu search for dial-a-ride problems, Transp Res Part B: Methodol, 52, 1-16, (2013) |
| [16] | Parragh, S. N., Introducing heterogeneous users and vehicles into models and algorithms for the dial-a-ride problem, Transp Res Part C: Emerg Technol, 19, 5, 912-930, (2011) |
| [17] | Parragh, S. N.; Doerner, K. F.; Hartl, R. F., A survey on pickup and delivery problemspart II: transportation between pickup and delivery locations, J Betriebswirtschaft, 58, 2, 81-117, (2008) |
| [18] | Parragh, S. N.; Doerner, K. F.; Hartl, R. F., Variable neighborhood search for the dial-a-ride problem, Comput Oper Res, 37, 6, 1129-1138, (2010) · Zbl 1178.90045 |
| [19] | Parragh, S. N.; Doerner, K. F.; Hartl, R. F.; Gandibleux, X., A heuristic two-phase solution approach for the multi-objective dial-a-ride problem, Networks, 54, 4, 227-242, (2009) · Zbl 1204.90096 |
| [20] | Parragh, S. N.; Schmid, V., Hybrid column generation and large neighborhood search for the dial-a-ride problem, Comput Oper Res, 40, 1, 490-497, (2013) · Zbl 1349.90119 |
| [21] | Qu, Y.; Bard, J. F., The heterogeneous pickup and delivery problem with configurable vehicle capacity, Transp Res Part C: Emerg Technol, 32, 1-20, (2013) |
| [22] | Røpke, S.; Cordeau, J.-F.; Laporte, G., Models and branch-and-cut algorithms for pickup and delivery problems with time windows, Networks, 49, 4, 258-272, (2007) · Zbl 1141.90340 |
| [23] | Røpke, S.; Pisinger, D., An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows, Transp Sci, 40, 4, 455-472, (2006) |
| [24] | Savelsbergh, M. W., The vehicle routing problem with time windowsminimizing route duration, ORSA J Comput, 4, 2, 146-154, (1992) · Zbl 0780.90105 |
| [25] | Schilde, M.; Doerner, K. F.; Hartl, R. F., Metaheuristics for the dynamic stochastic dial-a-ride problem with expected return transports, Comput Oper Res, 38, 12, 1719-1730, (2011) · Zbl 1215.90014 |
| [26] | Shaw, P. A new local search algorithm providing high quality solutions to vehicle routing problems. Glasgow, Scotland, UK: APES Group, Department of Computer Science, University of Strathclyde; 1997. |
| [27] | Tricoire, F., Multi-directional local search, Comput Oper Res, 39, 12, 3089-3101, (2012) · Zbl 1349.90751 |
| [28] | Xiang, Z.; Chu, C.; Chen, H., A fast heuristic for solving a large-scale static dial-a-ride problem under complex constraints, Eur J Oper Res, 174, 2, 1117-1139, (2006) · Zbl 1103.90022 |
| [29] | Zitzler, E.; Thiele, L., Multiobjective evolutionary algorithmsa comparative case study and the strength Pareto approach, IEEE Trans Evol Comput, 3, 4, 257-271, (1999) |
| [30] | Zitzler, E.; Thiele, L.; Laumanns, M.; Fonseca, C. M.; Grunert da Fonseca, V., Performance assessment of multiobjective optimizersan analysis and review, IEEE Trans Evol Comput, 7, 2, 117-132, (2003) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
