EconPapers    
Economics at your fingertips  
 

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

Zhixing Luo, Hu Qin and Andrew Lim

European Journal of Operational Research, 2014, vol. 234, issue 1, 49-60

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.

Keywords: Branch-and-price; Branch-and-price-and-cut; Traveling repairmen problem; Distance constraint (search for similar items in EconPapers)
Date: 2014
References: Add references at CitEc
Citations: View citations in EconPapers (20)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221713007698
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:234:y:2014:i:1:p:49-60

DOI: 10.1016/j.ejor.2013.09.014

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu (repec@elsevier.com).

 
Page updated 2024-12-28
Handle: RePEc:eee:ejores:v:234:y:2014:i:1:p:49-60