Home > Research > Publications & Outputs > An exact algorithm for a Vehicle-and-Driver Sch...


Text available via DOI:

View graph of relations

An exact algorithm for a Vehicle-and-Driver Scheduling Problem

Research output: Contribution to journalJournal article

<mark>Journal publication date</mark>05/2017
<mark>Journal</mark>Computers and Operations Research
Number of pages10
Pages (from-to)247-256
Publication statusPublished
Early online date28/12/16
Original languageEnglish


This article introduces a combinatorial optimization problem that consists of assigning tasks to machines and operators, and sequencing the tasks assigned to each one. Two configurations exist. Machines alternate configurations, while the operators must start and finish the process in the same configuration. Moreover, machines and operator have limited capacities, The sequencing of the tasks must guarantee that each one is performed by a machine and an operator at the same time, and it is determined in order to minimize an overall cost function. Two critical aspects of the problem are the need of synchronizing the machine and the operator performing each task, and the need of minimizing the changeovers, which are pairs of tasks done consecutively by the same machine but by different operators. The problem is modeled as a vehicle routing problem with two types of vehicles and with two depots. We propose a mixed integer programming formulation, and introduce valid inequalities to strengthen its linear programming relaxation. We describe separation routines for these inequalities and design a branch-and-cut algorithm for the problem. The algorithm is tested on a set of benchmark instances showing that it is able to solve to optimality instances with up to 50 customers. (C) 2016 Elsevier Ltd. All rights reserved.