Matheuristics and Column Generation for a Basic Technician Routing Problem
This paper considers a variant of the Vehicle Routing Problem with Time Windows, with site dependencies, multiple depots and outsourcing costs. This problem is the basis for many technician routing problems. Having both site-dependency and time window constraints lresults in difficulties in finding...
Guardado en:
Autores principales: | , , |
---|---|
Formato: | article |
Lenguaje: | EN |
Publicado: |
MDPI AG
2021
|
Materias: | |
Acceso en línea: | https://doaj.org/article/f7d96d1eb633482d9cab6ceef952a97b |
Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
id |
oai:doaj.org-article:f7d96d1eb633482d9cab6ceef952a97b |
---|---|
record_format |
dspace |
spelling |
oai:doaj.org-article:f7d96d1eb633482d9cab6ceef952a97b2021-11-25T16:13:05ZMatheuristics and Column Generation for a Basic Technician Routing Problem10.3390/a141103131999-4893https://doaj.org/article/f7d96d1eb633482d9cab6ceef952a97b2021-10-01T00:00:00Zhttps://www.mdpi.com/1999-4893/14/11/313https://doaj.org/toc/1999-4893This paper considers a variant of the Vehicle Routing Problem with Time Windows, with site dependencies, multiple depots and outsourcing costs. This problem is the basis for many technician routing problems. Having both site-dependency and time window constraints lresults in difficulties in finding feasible solutions and induces highly constrained instances. Matheuristics based on Mixed Integer Linear Programming compact formulations are firstly designed. Column Generation matheuristics are then described by using previous matheuristics and machine learning techniques to stabilize and speed up the convergence of the Column Generation algorithm. The computational experiments are analyzed on public instances with graduated difficulties in order to analyze the accuracy of algorithms for ensuring feasibility and the quality of solutions for weakly to highly constrained instances. The results emphasize the interest of the multiple types of hybridization between mathematical programming, machine learning and heuristics inside the Column Generation framework. This work offers perspectives for many extensions of technician routing problems.Nicolas DupinRémi ParizeEl-Ghazali TalbiMDPI AGarticleoptimizationoperations researchmathematical programmingmixed integer linear programmingDantzig–Wolfe decompositioncolumn generationIndustrial engineering. Management engineeringT55.4-60.8Electronic computers. Computer scienceQA75.5-76.95ENAlgorithms, Vol 14, Iss 313, p 313 (2021) |
institution |
DOAJ |
collection |
DOAJ |
language |
EN |
topic |
optimization operations research mathematical programming mixed integer linear programming Dantzig–Wolfe decomposition column generation Industrial engineering. Management engineering T55.4-60.8 Electronic computers. Computer science QA75.5-76.95 |
spellingShingle |
optimization operations research mathematical programming mixed integer linear programming Dantzig–Wolfe decomposition column generation Industrial engineering. Management engineering T55.4-60.8 Electronic computers. Computer science QA75.5-76.95 Nicolas Dupin Rémi Parize El-Ghazali Talbi Matheuristics and Column Generation for a Basic Technician Routing Problem |
description |
This paper considers a variant of the Vehicle Routing Problem with Time Windows, with site dependencies, multiple depots and outsourcing costs. This problem is the basis for many technician routing problems. Having both site-dependency and time window constraints lresults in difficulties in finding feasible solutions and induces highly constrained instances. Matheuristics based on Mixed Integer Linear Programming compact formulations are firstly designed. Column Generation matheuristics are then described by using previous matheuristics and machine learning techniques to stabilize and speed up the convergence of the Column Generation algorithm. The computational experiments are analyzed on public instances with graduated difficulties in order to analyze the accuracy of algorithms for ensuring feasibility and the quality of solutions for weakly to highly constrained instances. The results emphasize the interest of the multiple types of hybridization between mathematical programming, machine learning and heuristics inside the Column Generation framework. This work offers perspectives for many extensions of technician routing problems. |
format |
article |
author |
Nicolas Dupin Rémi Parize El-Ghazali Talbi |
author_facet |
Nicolas Dupin Rémi Parize El-Ghazali Talbi |
author_sort |
Nicolas Dupin |
title |
Matheuristics and Column Generation for a Basic Technician Routing Problem |
title_short |
Matheuristics and Column Generation for a Basic Technician Routing Problem |
title_full |
Matheuristics and Column Generation for a Basic Technician Routing Problem |
title_fullStr |
Matheuristics and Column Generation for a Basic Technician Routing Problem |
title_full_unstemmed |
Matheuristics and Column Generation for a Basic Technician Routing Problem |
title_sort |
matheuristics and column generation for a basic technician routing problem |
publisher |
MDPI AG |
publishDate |
2021 |
url |
https://doaj.org/article/f7d96d1eb633482d9cab6ceef952a97b |
work_keys_str_mv |
AT nicolasdupin matheuristicsandcolumngenerationforabasictechnicianroutingproblem AT remiparize matheuristicsandcolumngenerationforabasictechnicianroutingproblem AT elghazalitalbi matheuristicsandcolumngenerationforabasictechnicianroutingproblem |
_version_ |
1718413294877802496 |