[en] This paper introduces a fleet size and mix dial-a-ride problem with multiple passenger types and a heterogeneous fleet of reconfigurable vehicles.In this new variant of the dial-a-ride problem, en-route modifications of the vehicle’s inner configuration are allowed. The main consequence is that the vehicle capacity is defined by a set of configurations and the choice of vehicle configuration is associated with binary decision variables.The problem is modeled as a mixed-integer program derived from the model of the heterogeneous dial-a-ride problem. Vehicle reconfiguration is a lever to efficiently reduce transportation costs, but the number of passengers and vehicle fleet setting make this problem intractable for exact solution methods. A large neighborhood search metaheuristic combined with a set covering component with a reactive mechanism to automatically adjust its parameters is therefore proposed. The resulting framework is evaluated against benchmarks from the literature, used for similar routing problems. It is also applied to a real case, in the context of the transportation of disabled children from their home to medical centers in the city of Lyon, France.
Disciplines :
Quantitative methods in economics & management
Author, co-author :
Tellez Sanchez, Oscar Augusto ; Université de Liège - ULiège > HEC Liège : UER > UER Opérations : Supply Chain Management
Vercraene, Samuel
Lehuédé, Fabien
Péton, Olivier
Monteiro, Thibaud
Language :
English
Title :
The fleet size and mix dial-a-ride problem with reconfigurable vehicle capacity
Publication date :
2018
Journal title :
Transportation Research. Part C, Emerging Technologies
Archetti, C., Speranza, M.G., A survey on matheuristics for routing problems (2014) EURO J. Comput. Optim., 2 (4), pp. 223-246
Boland, N., Hewitt, M., Marshall, L., Savelsbergh, M., The continuous-time service network design problem (2017) Operat. Res., 65 (5), pp. 1303-1321
Braekers, K., Caris, A., Janssens, G.K., Exact and meta-heuristic approach for a general heterogeneous dial-a-ride problem with multiple depots (2014) Transport. Res. Part B: Methodol., 67, pp. 166-186
Chassaing, M., Duhamel, C., Lacomme, P., An ELS-based approach with dynamic probabilities management in local search for the Dial-A-Ride Problem (2016) Eng. Appl. Artif. Intell., 48, pp. 119-133
Christiaens, J., (2016), Vanden Berghe, G. A Fresh Ruin & Recreate Implementation For the Capacitated Vehicle Routing Problem, Technical report. Department of Computer Science, KU Leuven
Cordeau, J.-F., Laporte, G., A tabu search heuristic for the static multi-vehicle dial-a-ride problem (2003) Transport. Res. Part B: Methodol., 37 (6), pp. 579-594
Derigs, U., Gottlieb, J., Kalkoff, J., Piesche, M., Rothlauf, F., Vogel, U., Vehicle routing with compartments: applications, modelling and heuristics (2011) OR Spect., 33 (4), pp. 885-914
Doerner, K.F., Salazar-Gonzàlez, J.-J., Pickup-and-delivery problems for people transportation (2014) Vehicle Routing: Problems, Methods and Applications, 18, pp. 193-212. , D. Vigo P. Toth SIAM (ch. 7)
Dueck, G., New optimization heuristics (1993) J. Comput. Phys., 104 (1), pp. 86-92
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
Firat, M., Woeginger, G.J., Analysis of the dial-a-ride problem of Hunsaker and Savelsbergh (2011) Operat. Res. Lett., 39 (1), pp. 32-35
Foster, B.A., Ryan, D.M., An integer programming approach to the vehicle scheduling problem (1976) J. Operat. Res. Soc., 27 (2), pp. 367-384
Golden, B., Assad, A., Levy, L., Gheysens, F., The fleet size and mix vehicle routing problem (1984) Comp. Operat. Res., 11 (1), pp. 49-66
Grangier, P., Gendreau, M., Lehuédé, F., Rousseau, L.-M., A matheuristic based on large neighborhood search for the vehicle routing problem with cross-docking (2017) Comp. Operat. Res., 84, pp. 116-126
Gschwind, T., Drexl, M., (2016), Adaptive Large Neighborhood Search with a Constant-Time Feasibility Test for the Dial-a-Ride Problem. LM-2016-08, Gutenberg School of Management and Economics, Johannes Gutenberg University
(2015), Gschwind Timo. Route Feasibility Testing and Forward Time Slack for the Synchronized Pickup and Delivery Problem, Tech. Rep. 1503. Gutenberg School of Management and Economics, Johannes Gutenberg University
Henke, T., Speranza, M.G., Wäscher, G., The multi-compartment vehicle routing problem with flexible compartment sizes (2015) Euro. J. Operat. Res., 246 (3), pp. 730-743
Hunsaker, B., Savelsbergh, M., Efficient feasibility testing for dial-a-ride problems (2002) Operat. Res. Lett., 30 (3), pp. 169-173
Koç, C., Bektas, T., Jabali, O., Laporte, G., Thirty years of heterogeneous vehicle routing (2016) Euro. J. Operat. Res., 249 (1), pp. 1-21
Koch, H., Henke, T., Wäscher, G., (2016), A Genetic Algorithm for the Multi-Compartment Vehicle Routing Problem with Flexible Compartment Sizes, Tech. rep. Otto-von-Guericke-Universität Magdeburg, Faculty of Economics and Management
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
Luxen, D., Vetter, C., Real-time routing with openstreetmap data (2011) Proceedings of the 19th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, GIS’11, pp. 513-516. , ACM New York, NY, USA
Mahmoudi, M., Zhou, X., Finding optimal solutions for vehicle routing problem with pickup and delivery services with time windows: a dynamic programming approach based on state-space-time network representations (2016) Transport. Res. Part B: Methodol., 89 (July), pp. 19-42
Masson, R., Lehuédé, F., Péton, O., The dial-a-ride problem with transfers (2014) Comp. Operat. Res., 41, pp. 12-23
Parragh, S.N., Introducing heterogeneous users and vehicles into models and algorithms for the dial-a-ride problem (2011) Transport. Res. Part C: Emerg. Technol., 19 (5), pp. 912-930
Parragh, S.N., Doerner, K.F., Hartl, R.F., A survey on pickup and delivery problems (2008) Journal für Betriebswirtschaft, 58 (2), pp. 81-117
Parragh, S.N., Doerner, K.F., Hartl, R.F., Variable neighborhood search for the dial-a-ride problem (2010) Comp. Operat. Res., 37 (6), pp. 1129-1138
Parragh, S.N., Schmid, V., Hybrid column generation and large neighborhood search for the dial-a-ride problem (2013) Comp. Operat. Res., 40 (1), pp. 490-497
Pisinger, D., Ropke, S., A general heuristic for vehicle routing problems (2007) Comp. Operat. Res., 34 (8), pp. 2403-2435
Qu, Y., Bard, J.F., The heterogeneous pickup and delivery problem with configurable vehicle capacity (2013) Transport. Res. Part C: Emerg. Technol., 32, pp. 1-20
Qu, Y., Bard, J.F., A branch-and-price-and-cut algorithm for heterogeneous pickup and delivery problems with configurable vehicle capacity (2015) Transport. Sci., 49 (2), pp. 254-270
Rochat, Y., Taillard, É.D., Probabilistic diversification and intensification in local search for vehicle routing (1995) J. Heurist., 1 (1), pp. 147-167
Ropke, S., Cordeau, J.-F., Branch and cut and price for the pickup and delivery problem with time windows (2009) Transport. Sci., 43 (3), pp. 267-286
Ropke, S., Cordeau, J.-F., Laporte, G., Models and branch-and-cut algorithms for pickup and delivery problems with time windows (2007) Networks, 49 (4), pp. 258-272
Ropke, S., Pisinger, D., An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows (2006) Transport. Sci., 40 (4), pp. 455-472
Santini, A., Ropke, S., Hvattum, L.M., (2016), A Comparison of Acceptance Criteria for the Adaptive Large Neighbourhood Search Metaheuristic, Working Paper
Schrimpf, G., Schneider, J., Stamm-Wilbrandt, H., Dueck, G., Record breaking optimization results using the ruin and recreate principle (2000) J. Comput. Phys., 159 (2), pp. 139-171
Shaw, P., Using constraint programming and local search methods to solve vehicle routing problems (1998) International Conference on Principles and Practice of Constraint Programming, pp. 417-431. , Springer
Subramanian, A., Uchoa, E., Ochi, L.S., A hybrid algorithm for a class of vehicle routing problems (2013) Comp. Operat. Res., 40 (10), pp. 2519-2531
Taillard, E.D., A heuristic column generation method for the heterogeneous fleet VRP (1999) RAIRO-Operat. Res., 33 (1), pp. 1-14
Tang, J., Kong, Y., Lau, H., Ip, A.W.H., A note on efficient feasibility testing for dial-a-ride problems (2010) Operat. Res. Lett., 38 (5), pp. 405-407
Toth, P., Vigo, D., Heuristic algorithms for the handicapped persons transportation problem (1997) Transport. Sci., 31 (1), pp. 60-71
