Planning the Workday of Bus Drivers by a Graph List-Coloring Model

In this work, we address the problem of planning the workday of bus drivers in argentinian intercity bus transport companies. In particular, we focus on a company which needs to fulfill roughly 800 trips per day between 3 cities of the Province of Buenos Aires with a stuff of around 200 drivers and...

Descripción completa

Detalles Bibliográficos
Autores principales: Lucci, M., Nasini, G., Severín, D.
Formato: Articulo
Lenguaje:Español
Publicado: 2018
Materias:
Ciencias Informáticas
Integer programming model
Graph coloring
Heuristics
Planning workday of bus drivers
Acceso en línea:http://sedici.unlp.edu.ar/handle/10915/135196
https://publicaciones.sadio.org.ar/index.php/EJS/article/view/47
Aporte de:
SEDICI (UNLP) de Universidad Nacional de La Plata
id I19-R120-10915-135196
record_format dspace
institution Universidad Nacional de La Plata
institution_str I-19
repository_str R-120
collection SEDICI (UNLP)
language Español
topic Ciencias Informáticas
Integer programming model
Graph coloring
Heuristics
Planning workday of bus drivers
spellingShingle Ciencias Informáticas
Integer programming model
Graph coloring
Heuristics
Planning workday of bus drivers
Lucci, M.
Nasini, G.
Severín, D.
Planning the Workday of Bus Drivers by a Graph List-Coloring Model
topic_facet Ciencias Informáticas
Integer programming model
Graph coloring
Heuristics
Planning workday of bus drivers
description In this work, we address the problem of planning the workday of bus drivers in argentinian intercity bus transport companies. In particular, we focus on a company which needs to fulfill roughly 800 trips per day between 3 cities of the Province of Buenos Aires with a stuff of around 200 drivers and 100 buses. Planning consists of assigning one driver to each trip in a way the driver performs all the trips without scheduling conflicts and minimizing the overall amount of overtime among all bus drivers. We model the problem as a particular Graph Coloring Problem and we propose an Integer Linear Programming formulation. Computations experiments show that this formulation outperforms other ones given in the literature for the same problem. In order to address large instances as the one given by the company, we also propose a heuristic algorithm that delivers better solutions than the company actually uses in a reasonably amount of time. The heuristic has two phases where the first one constructs an initial solution and the second one improves the solution iteratively.
format Articulo
Articulo
author Lucci, M.
Nasini, G.
Severín, D.
author_facet Lucci, M.
Nasini, G.
Severín, D.
author_sort Lucci, M.
title Planning the Workday of Bus Drivers by a Graph List-Coloring Model
title_short Planning the Workday of Bus Drivers by a Graph List-Coloring Model
title_full Planning the Workday of Bus Drivers by a Graph List-Coloring Model
title_fullStr Planning the Workday of Bus Drivers by a Graph List-Coloring Model
title_full_unstemmed Planning the Workday of Bus Drivers by a Graph List-Coloring Model
title_sort planning the workday of bus drivers by a graph list-coloring model
publishDate 2018
url http://sedici.unlp.edu.ar/handle/10915/135196
https://publicaciones.sadio.org.ar/index.php/EJS/article/view/47
work_keys_str_mv AT luccim planningtheworkdayofbusdriversbyagraphlistcoloringmodel
AT nasinig planningtheworkdayofbusdriversbyagraphlistcoloringmodel
AT severind planningtheworkdayofbusdriversbyagraphlistcoloringmodel
bdutipo_str Repositorios
_version_ 1764820456474411008

Ejemplares similares