TY - JOUR

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

AU - Dominguez-Martin, Bencomo

AU - Rodriguez-Martin, Inmaculada

AU - Jose Salazar-Gonzalez, Juan

PY - 2017/5

Y1 - 2017/5

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

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

KW - Task scheduling

KW - Branch-and-cut

KW - Multi-depot

KW - Vehicle routing

U2 - 10.1016/j.cor.2016.12.022

DO - 10.1016/j.cor.2016.12.022

M3 - Journal article

VL - 81

SP - 247

EP - 256

JO - Computers and Operations Research

JF - Computers and Operations Research

SN - 0305-0548

ER -