Navegar

Colección

Datos Estadísticas

Artículo

Estamos trabajando para incorporar este artículo al repositorio
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

Abstract:

In this paper we address the Vehicle Routing Problem with Pickups and Deliveries (VRPPD), an extension of the classical Vehicle Routing Problem (VRP) where we consider precedences among customers, and develop an Integer Linear Programming (ILP) based local search procedure. We consider the capacitated one-to-one variant, where a particular precedence must be satisfied between pairs of origin-destination customers. We extend the scheme proposed in De Franceschi et al. (Math Program 105(2–3):471–499, 2006) for the Distance-Constrained Capacitated VRP, which has been successfully applied to other variants of the VRP. Starting from an initial feasible solution, this scheme follows the destroy/repair paradigm where a set of vertices is removed from the routes and reinserted by solving heuristically an associated ILP formulation with an exponential number of variables, named Reallocation Model. In this research, we propose two formulations for the Reallocation Model when considering pickup and delivery constraints and compare their behavior within the framework in terms of the trade off between the quality of the solutions obtained and the computational effort required. Based on the computational experience, the proposed scheme shows good potential to be applied in practice to this kind of problems and is a good starting point to consider more complex versions of the VRPPD. © 2017, Springer Science+Business Media New York.

Registro:

Documento: Artículo
Título:An ILP-based local search procedure for the VRP with pickups and deliveries
Autor:Montero, A.; José Miranda-Bront, J.; Méndez-Díaz, I.
Filiación:Departamento de Computación, FCEyN, Universidad de Buenos Aires, Pabellón I, Ciudad Universitaria, Ciudad Autónoma de Buenos Aires, C1428EGA, Argentina
Consejo Nacional de Investigaciones Científicas y Técnicas (CONICET), Ciudad Autónoma de Buenos Aires, Argentina
Palabras clave:Integer linear programming; Matheuristic; VRP with pickups and deliveries
Año:2017
Volumen:259
Número:1-2
Página de inicio:327
Página de fin:350
DOI: http://dx.doi.org/10.1007/s10479-017-2520-5
Título revista:Annals of Operations Research
Título revista abreviado:Ann. Oper. Res.
ISSN:02545330
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_02545330_v259_n1-2_p327_Montero

Referencias:

  • Archetti, C., Speranza, M., A survey on matheuristics for routing problems (2014) EURO Journal on Computational Optimization, 2 (4), pp. 223-246
  • Ascheuer, N., Fischetti, M., Grötschel, M., A polyhedral study of the asymmetric traveling salesman problem with time windows (2000) Networks, 36 (2), pp. 69-79
  • Ball, M.O., Heuristics based on mathematical programming (2011) Surveys in Operations Research and Management Science, 16 (1), pp. 21-38
  • Berbeglia, G., Cordeau, J.-F., Gribkovskaia, I., Laporte, G., Static pickup and delivery problems: A classification scheme and survey (2007) Top, 15 (1), pp. 1-31
  • Cordeau, J.-F., Laporte, G., The dial-a-ride problem: Models and algorithms (2007) Annals of Operations Research, 153 (1), pp. 29-46
  • Danna, E., Rothberg, E., Pape, C.L., Exploring relaxation induced neighborhoods to improve mip solutions (2005) Mathematical Programming, 102 (1), pp. 71-90
  • De Franceschi, R., Fischetti, M., Toth, P., A new ILP-based refinement heuristic for vehicle routing problems (2006) Mathematical Programming, 105 (2-3), pp. 471-499
  • Dumitrescu, I., Ropke, S., Cordeau, J.-F., Laporte, G., The traveling salesman problem with pickup and delivery: Polyhedral results and a branch-and-cut algorithm (2008) Mathematical Programming, 121 (2), pp. 269-305
  • Fischetti, M., Lodi, A., Local branching (2003) Mathematical Programming, 98 (1-3), pp. 23-47
  • Golden, B., Raghavan, S., Wasil, E., (2008) The vehicle routing problem: Latest advances and new challenges (Vol. 43), , (eds), Operations research/computer science interfaces US, Springer, Boston
  • Hansen, P., Mladenovic, N., Urosevic, D., Variable neighborhood search and local branching (2006) Computers & Operations Research, 33 (10), pp. 3034-3045
  • Helsgaun, K., An effective implementation of the Lin-Kernighan traveling salesman heuristic (2000) European Journal of Operational Research, 126 (1), pp. 106-130
  • Hernández-Pérez, H., Salazar-González, J.-J., The multi-commodity one-to-one pickup-and-delivery traveling salesman problem (2009) European Journal of Operational Research, 196 (3), pp. 987-995
  • Li, H., Lim, A., A metaheuristic for the pickup and delivery problem with time windows (2003) International Journal on Artificial Intelligence Tools, 12 (2), pp. 173-186
  • Lin, S., Kernighan, B.W., An effective heuristic algorithm for the traveling-salesman problem (1973) Operations Research, 21 (2), pp. 498-516
  • Muter, I., Birbil, I., Bülbül, K., Simultaneous column-and-row generation for large-scale linear programs with column-dependent-rows (2012) Mathematical Programming, 142 (1), pp. 47-82
  • Muter, I., Birbil, I., Bülbül, K., Güvenç, A note on A LP-based heuristic for a time-constrained routing problem (2012) European Journal of Operational Research, 221 (2), pp. 306-307
  • Naji-Azimi, Z., Salari, M., Toth, P., An integer linear programming based heuristic for the capacitated m-Ring-Star problem (2012) European Journal of Operational Research, 217 (1), pp. 17-25
  • Nanry, W.P., Barnes, J.W., Solving the pickup and delivery problem with time windows using reactive tabu search (2000) Transportation Research Part B: Methodological, 34 (2), pp. 107-121
  • Rodríguez-Martín, I., Salazar-González, J.J., A hybrid heuristic approach for the multi-commodity one-to-one pickup-and-delivery traveling salesman problem (2012) Journal of Heuristics, 18 (6), pp. 849-867
  • Ropke, S., Pisinger, D., An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows (2006) Transportation Science, 40 (4), pp. 455-472
  • Salari, M., Toth, P., Tramontani, A., An ILP improvement procedure for the open vehicle routing problem (2010) Computers & Operations Research, 37 (12), pp. 2106-2120
  • Toth, P., Tramontani, A., An integer linear programming local search for capacitated vehicle routing problems (2008) The Vehicle Routing Problem: Latest Advances and New Challenges, 43, pp. 275-295
  • (2014) Vehicle routing: Problems, methods, and applications, , Toth, P. Vigo, D. eds. 2nd ed., MOS-SIAM Series on Optimization. Philadelphia, PA, USA

Citas:

---------- APA ----------
Montero, A., José Miranda-Bront, J. & Méndez-Díaz, I. (2017) . An ILP-based local search procedure for the VRP with pickups and deliveries. Annals of Operations Research, 259(1-2), 327-350.
http://dx.doi.org/10.1007/s10479-017-2520-5
---------- CHICAGO ----------
Montero, A., José Miranda-Bront, J., Méndez-Díaz, I. "An ILP-based local search procedure for the VRP with pickups and deliveries" . Annals of Operations Research 259, no. 1-2 (2017) : 327-350.
http://dx.doi.org/10.1007/s10479-017-2520-5
---------- MLA ----------
Montero, A., José Miranda-Bront, J., Méndez-Díaz, I. "An ILP-based local search procedure for the VRP with pickups and deliveries" . Annals of Operations Research, vol. 259, no. 1-2, 2017, pp. 327-350.
http://dx.doi.org/10.1007/s10479-017-2520-5
---------- VANCOUVER ----------
Montero, A., José Miranda-Bront, J., Méndez-Díaz, I. An ILP-based local search procedure for the VRP with pickups and deliveries. Ann. Oper. Res. 2017;259(1-2):327-350.
http://dx.doi.org/10.1007/s10479-017-2520-5