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...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Nicolas Dupin, Rémi Parize, El-Ghazali Talbi
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