Dial-a-ride problem ; Vehicle routing ; Consistency ; Healthcare logistics ; Set partitioning ; Large neighborhood search
Résumé :
[en] In the context of door-to-door transportation of people with disabilities, service quality considerations such as maximum ride time and service time consistency are critical requirements. To identify a good trade-off between these considerations and economic objectives, we define a new variant of the multiperiod dial-a-ride problem called the time-consistent dial-a-ride problem. A transportation planning is supposed to be time consistent if for each passenger, the same service time is used all along the planning horizon. However, considering the numerous variations in transportation demands over a week, designing consistent plan for all passengers can be too expensive. It is therefore necessary to find a compromise solution between costs and time-consistency objectives. The time-consistent dial-a-ride problem is solved using an epsilon-constraint approach to illustrate the trade-off between these two objectives. It computes an approximation of the Pareto front, using a matheuristic framework that combines a large neighbourhood search with the solution of set partitioning problems. This approach is benchmarked on time-consistent vehicle routing problem literature instances. Experiments are also conducted in the context of door-to-door transportation for people with disabilities, using real data. These experiments support managerial insights regarding the inter-relatedness of costs and quality of service.
Disciplines :
Sciences informatiques
Auteur, co-auteur :
Tellez Sanchez, Oscar Augusto ; Université de Liège - ULiège > HEC Liège : UER > UER Opérations : Supply Chain Management
(2016) Améliorer la gestion des transports de personnes handicapées. Technical report, , France, Agence Nationale d'Appui à la Performance des établissements de santé et médico-sociaux
Braekers, K., Kovacs, A.A., A multi-period dial-a-ride problem with driver consistency (2016) Transp. Res. B Methodol., 94, pp. 355-377
Bunte, S., Kliewer, N., An overview on vehicle scheduling models (2009) Public Transp., 1 (4), pp. 299-317
Carosi, S., Frangioni, A., Galli, L., Girardi, L., Vallese, G., A matheuristic for integrated timetabling and vehicle scheduling (2019) Transp. Res. B Methodol., 127, pp. 99-124
Chankong, V., Haimes, Y.Y., (2008) Multiobjective decision making: Theory and methodology, , U.S.A., Courier Dover Publications
Doerner, K.F., Salazar-González, J.-J., Chapter 7: Pickup-and-delivery problems for people transportation (2014) Vehicle routing, pp. 193-212. , P. Toth, D. Vigo, Eds.,, Society for Industrial and Applied Mathematics, Philadelphia, PA
Drexl, M., Synchronization in vehicle routing-a survey of VRPs with multiple synchronization constraints (2012) Transp. Sci., 46 (3), pp. 297-316
Erera, A.L., Savelsbergh, M., Uyar, E., Fixed routes with backup vehicles for stochastic vehicle routing problems with time constraints (2009) Networks, 54 (4), pp. 270-283
Feillet, D., Garaix, T., Lehuédé, F., Péton, O., Quadri, D., A new consistent vehicle routing problem for the transportation of people with disabilities (2014) Networks, 63 (3), pp. 211-224
Grangier, P., Gendreau, M., Lehuédé, F., Rousseau, L.-M., Grangier Philippe, Gendreau Michel, Lehuédé Fabien, Rousseau Louis-Martin. A matheuristic based on large neighborhood search for the vehicle routing problem with cross-docking (2017) Comput. Oper. Res., 84, pp. 116-126. , http://dx.doi.org/10.1016/j.cor.2017.03.004
Groër, C., Golden, B., Wasil, E., The consistent vehicle routing problem (2009) Manuf. Serv. Oper. Manag., 11 (4), pp. 630-643
Haimes, Y., Lasdon, L., Wismer, D., On a bicriterion formulation of the problems of integrated system identification and system optimization (1971) IEEE Trans. Syst. Man Cybern., 1, pp. 296-297
Ho, S.C., Szeto, W., Kuo, Y.-H., Leung, J.M., Petering, M., Tou, T.W., A survey of dial-a-ride problems: Literature review and recent developments (2018) Transp. Res. B Methodol., 111, pp. 395-421
Kovacs, A.A., Golden, B.L., Hartl, R.F., Parragh, S.N., Vehicle routing problems in which consistency considerations are important: A survey (2014) Networks, 64 (3), pp. 192-213
Kovacs, A.A., Golden, B.L., Hartl, R.F., Parragh, S.N., The generalized consistent vehicle routing problem (2015) Transp. Sci., 49 (4), pp. 796-816
Kovacs, A.A., Parragh, S.N., Hartl, R.F., A template-based adaptive large neighborhood search for the consistent vehicle routing problem (2014) Networks, 63 (1), pp. 60-81
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 (2014) J. Oper. Res. Soc., 65 (7), pp. 983-1000
Lei, H., Laporte, G., Guo, B., Districting for routing with stochastic customers (2012) EURO J Transp Logist, 1 (1-2), pp. 67-85
Luo, Z., Qin, H., Che, C., Lim, A., On service consistency in multi-period vehicle routing (2015) Eur. J. Oper. Res., 243 (3), pp. 731-744
Luxen, D., Vetter, C., (2011), pp. 513-516. , Real-time routing with openstreetmap data, Proceedings of the 19th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, GIS'11, ACM, New York, NY
Michaelis, M., Schöbel, A., Integrating line planning, timetabling, and vehicle scheduling: A customer-oriented heuristic (2009) Public Transp., 1 (3), p. 211
Milburn, A.B., Spicer, J., Multi-objective home health nurse routing with remote monitoring devices (2013) Int. J. Plan. Scheduling, 1 (4), pp. 242-263
Molenbruch, Y., Braekers, K., Caris, A., Typology and literature review for dial-a-ride problems (2017) Ann. Oper. Res., 259 (1-2), pp. 295-325
Ogryczak, W., Luss, H., Pióro, M., Nace, D., Tomaszewski, A., Tomaszewski Artur. Fair Optimization and Networks: A Survey (2014) J. Appl. Math., 2014, pp. 1-25. , http://dx.doi.org/10.1155/2014/612018
Park, J., Kim, B.-I., The school bus routing problem: A review (2010) Eur. J. Oper. Res., 202 (2), pp. 311-319
Pisinger, D., Ropke, S., A general heuristic for vehicle routing problems (2007) Comput. Oper. Res., 34 (8), pp. 2403-2435
Ritzinger, U., Puchinger, J., Hartl, R.F., A survey on dynamic and stochastic vehicle routing problems (2016) Int. J. Prod. Res., 54 (1), pp. 215-231
Schmid, V., Ehmke, J.F., Integrated timetabling and vehicle scheduling with balanced departure times (2015) OR Spectr., 37 (4), pp. 903-928
Schneider, M., Stenger, A., Schwahn, F., Vigo, D., Territory-based vehicle routing in the presence of time-window constraints (2015) Transp. Sci., 49 (4), pp. 732-751
Smilowitz, K., Nowak, M., Jiang, T., Workforce management in periodic delivery operations (2013) Transp. Sci., 47 (2), pp. 214-230
Spliet, R., Desaulniers, G., The discrete time window assignment vehicle routing problem (2015) Eur. J. Oper. Res., 244 (2), pp. 379-391
Spliet, R., Gabor, A.F., The time window assignment vehicle routing problem (2015) Transp. Sci., 49 (4), pp. 721-731
Subramanyam, A., Gounaris, C.E., A branch-and-cut framework for the consistent traveling salesman problem (2016) Eur. J. Oper. Res., 248 (2), pp. 384-395
Sungur, I., Ren, Y., Ordóñez, F., Dessouky, M., Zhong, H., A model and algorithm for the courier delivery problem with uncertainty (2010) Transp. Sci., 44 (2), pp. 193-205
Tarantilis, C., Stavropoulou, F., Repoussis, P., A template-based tabu search algorithm for the consistent vehicle routing problem (2012) Expert Syst. Appl., 39 (4), pp. 4233-4239
Tellez, O., Vercraene, S., Lehuédé, F., Péton, O., Monteiro, T., The fleet size and mix dial-a-ride problem with reconfigurable vehicle capacity (2018) Transp. Res. C Emerg. Technol., 91, pp. 99-123. , http://dx.doi.org/10.1016/j.trc.2018.03.020
Téllez Sánchez, O.A., (2019), Optimisation du transport quotidien des personnes en situation de handicap, Ph. D. Thesis, INSA Lyon
Toth, P., Vigo, D., Algorithms for the Handicapped Persons Transportation Problem (1997) Transp. Sci., 31 (1), pp. 60-71. , http://dx.doi.org/10.1287/trsc.31.1.60
Xu, Z., Cai, Y., Variable neighborhood search for consistent vehicle routing problem (2018) Expert Syst. Appl., 113, pp. 66-76
Zhong, H., Hall, R.W., Dessouky, M., Territory planning and vehicle dispatching with driver learning (2007) Transp. Sci., 41 (1), pp. 74-89