An ILP-based local search procedure for the VRP with pickups and deliveries
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 capacitat...
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | JOUR |
| Materias: | |
| Acceso en línea: | http://hdl.handle.net/20.500.12110/paper_02545330_v259_n1-2_p327_Montero |
| Aporte de: |
| id |
todo:paper_02545330_v259_n1-2_p327_Montero |
|---|---|
| record_format |
dspace |
| spelling |
todo:paper_02545330_v259_n1-2_p327_Montero2023-10-03T15:11:35Z An ILP-based local search procedure for the VRP with pickups and deliveries Montero, A. José Miranda-Bront, J. Méndez-Díaz, I. Integer linear programming Matheuristic VRP with pickups and deliveries 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. Fil:Méndez-Díaz, I. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. JOUR info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar http://hdl.handle.net/20.500.12110/paper_02545330_v259_n1-2_p327_Montero |
| institution |
Universidad de Buenos Aires |
| institution_str |
I-28 |
| repository_str |
R-134 |
| collection |
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) |
| topic |
Integer linear programming Matheuristic VRP with pickups and deliveries |
| spellingShingle |
Integer linear programming Matheuristic VRP with pickups and deliveries Montero, A. José Miranda-Bront, J. Méndez-Díaz, I. An ILP-based local search procedure for the VRP with pickups and deliveries |
| topic_facet |
Integer linear programming Matheuristic VRP with pickups and deliveries |
| description |
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. |
| format |
JOUR |
| author |
Montero, A. José Miranda-Bront, J. Méndez-Díaz, I. |
| author_facet |
Montero, A. José Miranda-Bront, J. Méndez-Díaz, I. |
| author_sort |
Montero, A. |
| title |
An ILP-based local search procedure for the VRP with pickups and deliveries |
| title_short |
An ILP-based local search procedure for the VRP with pickups and deliveries |
| title_full |
An ILP-based local search procedure for the VRP with pickups and deliveries |
| title_fullStr |
An ILP-based local search procedure for the VRP with pickups and deliveries |
| title_full_unstemmed |
An ILP-based local search procedure for the VRP with pickups and deliveries |
| title_sort |
ilp-based local search procedure for the vrp with pickups and deliveries |
| url |
http://hdl.handle.net/20.500.12110/paper_02545330_v259_n1-2_p327_Montero |
| work_keys_str_mv |
AT monteroa anilpbasedlocalsearchprocedureforthevrpwithpickupsanddeliveries AT josemirandabrontj anilpbasedlocalsearchprocedureforthevrpwithpickupsanddeliveries AT mendezdiazi anilpbasedlocalsearchprocedureforthevrpwithpickupsanddeliveries AT monteroa ilpbasedlocalsearchprocedureforthevrpwithpickupsanddeliveries AT josemirandabrontj ilpbasedlocalsearchprocedureforthevrpwithpickupsanddeliveries AT mendezdiazi ilpbasedlocalsearchprocedureforthevrpwithpickupsanddeliveries |
| _version_ |
1807324298052894720 |