Branch-and-price-and-cut for the multiple traveling repairman problem with distance constraints

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journal

38 Scopus Citations
View graph of relations

Author(s)

  • Zhixing Luo
  • Hu Qin
  • Andrew Lim

Related Research Unit(s)

Detail(s)

Original languageEnglish
Pages (from-to)49-60
Journal / PublicationEuropean Journal of Operational Research
Volume234
Issue number1
Online published21 Sep 2013
Publication statusPublished - 1 Apr 2014

Abstract

In this paper, we extend the multiple traveling repairman problem by considering a limitation on the total distance that a vehicle can travel; the resulting problem is called the multiple traveling repairmen problem with distance constraints (MTRPD). In the MTRPD, a fleet of identical vehicles is dispatched to serve a set of customers. Each vehicle that starts from and ends at the depot is not allowed to travel a distance longer than a predetermined limit and each customer must be visited exactly once. The objective is to minimize the total waiting time of all customers after the vehicles leave the depot. To optimally solve the MTRPD, we propose a new exact branch-and-price- and-cut algorithm, where the column generation pricing subproblem is a resource-constrained elementary shortest-path problem with cumulative costs. An ad hoc label-setting algorithm armed with bidirectional search strategy is developed to solve the pricing subproblem. Computational results show the effectiveness of the proposed method. The optimal solutions to 179 out of 180 test instances are reported in this paper. Our computational results serve as benchmarks for future researchers on the problem. © 2013 Elsevier B.V. All rights reserved.

Research Area(s)

  • Branch-and-price, Branch-and-price-and-cut, Distance constraint, Traveling repairmen problem